tag:blogger.com,1999:blog-3722233.post8892467103290123546..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: Would you take this bet (Part 1) ?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-21357332850321715612021-07-12T01:16:20.043-05:002021-07-12T01:16:20.043-05:00But no, of course I wouldn't play this game, a...But no, of course I wouldn't play this game, at least not as a one-off stand-alone game. It's a game where you expect to lose money (since most paths lead to you losing money), even if there is an expected positive return. There's not really much motivation for me to do that in my current circumstances.Joehttps://www.blogger.com/profile/11034966968414912132noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72313549078509238172021-07-12T00:50:57.383-05:002021-07-12T00:50:57.383-05:00I'm not saying that this is the deciding facto...I'm not saying that this is the deciding factor, I'm just pointing out that for any sort of financial calculation you need to discount future gains based on when they will be realised.Joehttps://www.blogger.com/profile/11034966968414912132noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87068486146642782872021-07-10T04:38:38.176-05:002021-07-10T04:38:38.176-05:00This should not only depend on your scarcity of mo...This should not only depend on your scarcity of money, but also on how useful large sums are for you. Suppose, I don't care whether I have 1 billion dollars or more, so my utility function is capped at 2^30, and further suppose that up to that point it grows at most linearly. Then my expected gain from a game is at most 30/2=15.<br /><br />ps. What a nice timing to post this question before this year's IMO!domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45819073386036636762021-07-09T09:35:24.338-05:002021-07-09T09:35:24.338-05:00No, I would not pay $1000 to play the game (I just...No, I would not pay $1000 to play the game (I just tried it once with a real coin and lost $998) ... but I'm waiting for more insights ...Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86499944957041627592021-07-08T13:05:53.502-05:002021-07-08T13:05:53.502-05:00Suppose we can flip the coin once a minute and kee...Suppose we can flip the coin once a minute and keep it up for a year. Would you take the bet?David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76095889674255016632021-07-08T12:59:44.776-05:002021-07-08T12:59:44.776-05:00What does ten heads in a row have to do with it? T...What does ten heads in a row have to do with it? The game ends on the first head.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48970077349573690692021-07-08T12:58:18.100-05:002021-07-08T12:58:18.100-05:00Number the rounds starting with 1. The probability...Number the rounds starting with 1. The probability of winning on round n is the probability of getting n - 1 tails followed by one head, i.e., 1 / 2^n. If you win on round n, you win 2^(n-1) dollars. 2^(n-1) * (1 / 2^n) = 1/2. Your expected value is the sum of the expected values on each round, i.e., 1/2 + 1/2 + ...David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84064290585486412462021-07-08T10:26:08.305-05:002021-07-08T10:26:08.305-05:00Readers who are familiar with the doubling cube in...Readers who are familiar with the doubling cube in backgammon may find it interesting that a similar paradox can arise if there is no limit on how high the cube can go. See my website for more discussion. http://alum.mit.edu/www/tchow/cg/undefined.htmlTimothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-201433942227919072021-07-07T22:25:44.189-05:002021-07-07T22:25:44.189-05:00Nonsense. The expected value computation is wrong....Nonsense. The expected value computation is wrong. Each term in the sum of .5s must be weighted by the probability that the game did not stop at earlier steps. To steal a term from physics, this is so bad it is not even wrong!Chmossshttps://www.blogger.com/profile/11446150859905158904noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81047047674205180582021-07-07T16:11:59.721-05:002021-07-07T16:11:59.721-05:00Here is some code that (if correct) simulates repe...Here is some code that (if correct) simulates repeated runs of the game. In particular, I simulated starting with $100,000,000 and repeatedly taking the bet until I had no money or at least $100,000,001. Out of 500 trials, I made at least $1 only twice. <br /><br />It's fun to run the code. (Unfortunately, it lost the indents, but those are easy to put back in.)<br /><br />import numpy as np<br /><br />def run_one():<br /> if not np.random.randint(2):<br /> return 0<br /> counter = 1<br /> while np.random.randint(2):<br /> counter *=2<br /> return counter<br /><br />def run_many(money, target):<br /> while money < target:<br /> money += run_one() -1000<br /> if money <= 0:<br /> return 0<br /> return 1<br /><br />def run_experiment(start, target, trials):<br /> y = np.zeros(trials)<br /> for i in range(trials):<br /> y[i] = run_many(start,target)<br /> if i < 10 or i % 10 == 0:<br /> print("i equals ", i, " and fraction is ", np.average(y[:i+1]))<br /> return(np.average(y))<br /><br />start = 100000000<br />target = 100000001<br />trials = 500<br />print(run_experiment(start, target, trials))Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54428521851665953492021-07-07T05:19:42.407-05:002021-07-07T05:19:42.407-05:00No. Try to compute how often you would have to rep...No. Try to compute how often you would have to repeat this game such that the probability that you won money is bigger than the probability that you lost money. And now compute how much money you need before starting the game, such that you would be able to repeat the game sufficiently often.Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53535408627950960122021-07-07T05:04:23.977-05:002021-07-07T05:04:23.977-05:00Aside from the low probability of winning, the exp...Aside from the low probability of winning, the expected value calculation is incorrect. Summing up all of the payouts weighted by their probability only gives you the expected return, but not when that return will be realised. But money invested now in another way would likely grow over time, so you need to discount the payout by an amount that depends on how much time has passed before you receive the payout in order to compare it the the $1000 you have at the start of the bet. This means that the expected payout should be sum_{n=1}^infinity exp(-r*n)*(1/2). Where r is some small non-zero constant depending on interest rate and the time it takes to flip a coin. This sum converges to a finite value: (1/2)/(e^r -1). So if they flip a coin too slowly, then you definitely shouldn't take the bet.Joehttps://www.blogger.com/profile/11034966968414912132noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88299956559309876522021-07-07T04:14:28.074-05:002021-07-07T04:14:28.074-05:00The paper Evaluating gambles using dynamics by Ole...The paper <a href="https://scirate.com/arxiv/1405.0585" rel="nofollow">Evaluating gambles using dynamics</a> by Ole Peters and Murray Gell-Mann contains the following paragraph: "Gambles are often treated in economics as so-called one-shot games, ... The one-shot setup seems ill-conceived to us, and the methods we propose produce little insight into the situations it may represent. It is ill-conceived because any gamble affects what we may be able to do after the gamble. If we lose our house, we cannot bet the house again. ... One situation that may be represented by a one-shot game is a bet on a coin toss after which the player (who does not believe in an afterlife) will drop dead. Our methods are not developed for such a-typical cases."<br /><br />The methods proposed in that paper give a resolution of the paradox that does not need to invoke "my highly non linear reward function". It is enough to work out the actual consequences of "my scarcity of money" (hinted at by Unknown's comment above) to see why you should not take this bet.<br /><br />Murray Gell-Mann was a famous physicist, and some people wondered why he agreed to appear as coauthor of the above paper. That paragraph ridiculing one-shot games had a strong impact on me, allowing me to <a href="https://www.physicsforums.com/threads/infinities-in-qft-and-physics-in-general.1002079/post-6482089" rel="nofollow">better understand the following paradox</a>: "But what I had in mind was more related to a paradox in interpretation of probability than to an attack on using real numbers to describe reality. The paradox is how mathematics forces us to give precise values for probabilities, even for events which cannot be repeated arbitrarily often (not even in principle)."<br /><br />My <a href="https://stats.stackexchange.com/questions/286853/is-everyday-probability-just-a-way-of-dealing-with-the-unknown-not-talking-quan/287055#287055" rel="nofollow">impression is that Pascal's Wager can be misused</a> as a one-shot game to nicely illustrate the paradox: "Even if not meant that way, Pascal's Wager presents a similar type of paradox. It describes an experiment which can not be repeated, and then assumes that one could assign a probability like 0.000001 or 1e-3000 to a certain outcome, without questioning whether such an accurate probability even makes sense in this context."Jakitohttps://www.blogger.com/profile/08235089048981338795noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22940287958438522292021-07-07T01:58:42.785-05:002021-07-07T01:58:42.785-05:00The expected value is only so high because of extr...The expected value is only so high because of extremely unlikely outcomes with extremely high payouts. But nobody in the world can actually pay me 2^100 dollars (or whatever) so those extremely high payouts are in some sense not "real."<br /><br />Here's an example. Suppose I play against Jeff Bezos. He can afford to pay me up to about 2^38 dollars, but no more than that. So my reward is really capped at 2^38, no matter how many tails I get in a row. And if I calculate the expected value of the game with the reward capped by 2^38 then the expected value is less than $40. So it's definitely not worth paying $1000 to play the game.Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57900930095087491222021-07-06T22:10:50.137-05:002021-07-06T22:10:50.137-05:00Given my highly non linear reward function and sca...Given my highly non linear reward function and scarcity of money, no. Now if I had enough money? Yes. How much would I need? Probably about 100k, ball park. But I would need to more closely model my reward function first.Anonymoushttps://www.blogger.com/profile/13145307157323355035noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33208531835150583042021-07-06T20:22:22.883-05:002021-07-06T20:22:22.883-05:00No, I would not take this bet. $1,000 is over 2^9...No, I would not take this bet. $1,000 is over 2^9, and flipping ten heads in a row is 1/2^10, so this is a losing proposition.Lew Proudfoothttps://www.blogger.com/profile/15678999432006342923noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17490063700254494732021-07-06T20:15:51.321-05:002021-07-06T20:15:51.321-05:00No. The probability of regaining my $1000 is abou...No. The probability of regaining my $1000 is about 1/2^10, which is too low for the risk-averse gambler. I have a high probability (~1) of losing money and a very low probability (<1/2^10) of winning money (albeit a potentially large amount of money).Rodneyhttps://www.blogger.com/profile/01768193870857453631noreply@blogger.com