No. If that damn dungeon master hadn’t tossed that fair coin himself first, then it would be the best strategy to say “It’s my first time here”—and you are free.
But it may very well be, that he tossed heads up before and put you right back to sleep with amnesia induced. In that case, you are never out.
Let p_n be the probability that I say n. Then the probability I escape on exactly the nth round is at most p_n/2 since the coin has to come up on the correct side, and then I have to say n. In fact the probability is normally less than that since there is a possibility that I have already escaped. So the probability I escape is at most the sum over n of p_n/2. Since p_n is a probability distribution it sums to 1, so this if at most 1⁄2. I’ll escape with probability less than this is I have any two p_n nonzero. So the optimal strategies are precisely to always say the same number, and this can be any number.
I got the same answer, with essentially the same reasoning.
Assuming that each guess is a draw from the same probability distribution over positive integers, the expected number of correct guesses is 0.5 if I keep guessing forever (rather than leaving after 1 correct guess), regardless of what distribution I choose.
So the probability of getting at least one correct guess (which is the win condition) is capped at 0.5. And the only way to hit that maximum is by removing all the scenarios where I guess correctly more than once, so that all of the expected value comes from the scenarios where I guess correctly exactly once.
Define flip values as H=0 and T=1. You have to flip this fair coin twice. You increase x=x+value(1) and y=y+value(2) and z=z+1. If x>y you stop flipping and declare—It’s the z-th round of the game.
For example, after TH, x=1 and y=0 and z=1. You stop tossing and declare 1st round. If it is HH, you continue tossing it twice again.
No matter how late in the game you are, you have a nonzero probability to win. Chebyshev (and Chernoff) can help you improve the x>y condition a bit. I don’t know how much yet. Neither I have a proof that then the probability of exiting is > 1⁄2. But at least that much it is. Some Monte-Carloing seems to agree.
Would you mind showing your work on monte-carlo for this? If you’ve tried more than a few runs and they all actually terminated, you have a bug.
You’re describing a random-walk that moves left 25% of the time, right 25% and does not move 50% of the time, and counting steps until you get to 1. There is no possibility that this ends up better than 50% to exit after the same number of steps as 0.50^n.
I think you must just have an error in your code somewhere. Consider going round 3. Let the probability you say “3” be p_3. Then according to your numbers
164⁄512 = 15⁄64 + (1 − 15⁄64)*(1/2)*p_3
Since the probability of escaping by round 3 is the probability of escape by round 2, plus the probability you don’t escape by round 2, multiplied by the probability the coin lands tails, multiplied by the probability you say “3”.
But then p_3 = 11⁄49, and 49 is not a power of two!
There are two pretty strong sketches above here that this approaches 1⁄2 as you get closer to any static answer, but cannot beat 1⁄2.
The best answer is “ignore the coin, declare first”. There is no better chance of escape (though there are many ties at 1⁄2), and this minimizes your time in purgatory in the case that you do escape.
So, you say, the Sleeping Beauty is there forever with the probability of at least 1⁄2.
Then she has all the time in the world, to exercise this function which outputs z. Do you agree, that every natural number will be eventually reached by this algorithm, counting the double tossings, adding 0 or 1 to x and 0 or 1 to y and increasing z, until x>y?
She has all the time in the world, but only as much probability as she gave up by not saying “first”.
Every natural number is reachable by your algorithm, but the probability that it’s reached ON THE SAME ITERATION as the wake-up schedule converges to zero pretty quickly. Both iterations and her responses approach infinity, the product of the probabilities approach zero way faster than the probabilities themselves.
Really. Go to Wolfram and calculate “sum to infinity 0.5^n * 0.5^n”. The chance that the current wake-up is N is clearly 0.5^n − 50% chance of T, 25% of HT, 12.5 of HHT, etc. If your distribution is different, replace the second 0.5^n with any formula such that “sum to infinity YOUR_FORMULA” is 1. It’s 0.3333 that she’ll EVER escape if she randomizes across infinite possibilities with the same distribution, and gets closer to (but doesn’t reach) 50% if she front-weights the distribution.
Your basic idea is right here. But … this product isn’t that straightforward.
Say it’s the 100th session. It is a lot of ways, that x becomes greater than y exactly this time. Especially if the formula is x>y+sqr(y) or something alike from the Chebyshev’s arsenal.
If the session is then 101st, this new small probability isn’t much smaller than it was in the 100th session.
Still, you may be right that the product (1-p_n)*(1-p_n+1) … converges to 1⁄2 at the most.
Don’t doubt it, do the math (and http://www.wolframalpha.com/ helps a LOT with this. Provide any formula for probability of guessing “Nth wakeup” such that it sums to 1 (or less) from 1 to infinity. Calculate the sum from 1 to infinity of the product of this and the 0.5^n chance that you’re currently on the Nth wakeup.
You will never find one that sums to better than 0.5.
Your weirdness using X and Y is not helping—any algorithm you can state eventually comes out to “some probability for each N of guessing N”. And when you view it that way, you’ll see that the sum has to be less than 50%.
Simplest is always “this is wakening #1”. 50% chance of escape, and soonest possible if it happens. Has the psychological disadvantage that if the first coin is tails, you’re stuck forever with no future chance of escape. You have no memory of any of them, so that is irrelevant—all that matters is the probability of escape—but it feels bad to us as outside observers.
You can stretch it out by randomizing your answer with a declining chance of higher numbers. Say, flip YOUR coin until you get tails, then guess the number of flips you’ve made. HHHT you guess 4, for example. This gives you 25% to be released on day 1 (50% DM’s coin is tails X 50% your first flip is.). And 6.5% to be released the second day (25% of HT on his coin and yours). Unfortunately, sum (i: 1->infinity) 0.25^i = 0.33333, so your overall chance of escaping is reduced. But you do always have some (very small) hope, unlike the simple answer.
Randomization with weighting toward earlier numbers improves your early chance, but reduces your later chances, and it seems (from sampling and thinking, not proven) that it can approach 0.5 but not exceed it.
I think the best you can do is 50% unless you have some information when you wake up about how long this has been going on.
No. You will always say the same number each time, since you are identical each time.
As long as it isn’t that number, you are going another round. Eventually it gets to that number, whereupon you go free if you get the luck of the coin, or go back under if you miss it.
Coin doesn’t help. Say I decide to pick 2 if it is heads, 1 if it is tails.
I’ve lowered my odds of escaping on try 1 to 1⁄4, which initially looks good, but the overall chance stays the same, since I get another 1⁄4 on the second round. If I do 2 flips, and use the 4 spread there to get 1, 2, 3, or 4, then I have an eight of a chance on each of rounds 1-4.
Similarly, if I raise the number of outcomes that point to one number, that round’s chance goes up , but the others decline, so my overall chance stays pegged to 1⁄2. (ie, if HH, HT, TH all make me say 1, then I have a 3⁄8 chance that round, but only a 1⁄8 of being awake on round 2 and getting TT).
There is a problem …
The best strategy is to always say “it’s the first time”. (Or, equivalently, always say “it’s the second time”, etc.)
No. If that damn dungeon master hadn’t tossed that fair coin himself first, then it would be the best strategy to say “It’s my first time here”—and you are free.
But it may very well be, that he tossed heads up before and put you right back to sleep with amnesia induced. In that case, you are never out.
My strategy gives probability 1⁄2 of escaping. Can you show some strategy that gives higher probability? Doesn’t have to be the best.
If you always say “It’s my first time” you will be freed with the probability 1⁄2, yes.
I’ll give the best strategy I know before the end of this week. Now, it would be a spoiler.
Let p_n be the probability that I say n. Then the probability I escape on exactly the nth round is at most p_n/2 since the coin has to come up on the correct side, and then I have to say n. In fact the probability is normally less than that since there is a possibility that I have already escaped. So the probability I escape is at most the sum over n of p_n/2. Since p_n is a probability distribution it sums to 1, so this if at most 1⁄2. I’ll escape with probability less than this is I have any two p_n nonzero. So the optimal strategies are precisely to always say the same number, and this can be any number.
I got the same answer, with essentially the same reasoning.
Assuming that each guess is a draw from the same probability distribution over positive integers, the expected number of correct guesses is 0.5 if I keep guessing forever (rather than leaving after 1 correct guess), regardless of what distribution I choose.
So the probability of getting at least one correct guess (which is the win condition) is capped at 0.5. And the only way to hit that maximum is by removing all the scenarios where I guess correctly more than once, so that all of the expected value comes from the scenarios where I guess correctly exactly once.
Define flip values as H=0 and T=1. You have to flip this fair coin twice. You increase x=x+value(1) and y=y+value(2) and z=z+1. If x>y you stop flipping and declare—It’s the z-th round of the game.
For example, after TH, x=1 and y=0 and z=1. You stop tossing and declare 1st round. If it is HH, you continue tossing it twice again.
No matter how late in the game you are, you have a nonzero probability to win. Chebyshev (and Chernoff) can help you improve the x>y condition a bit. I don’t know how much yet. Neither I have a proof that then the probability of exiting is > 1⁄2. But at least that much it is. Some Monte-Carloing seems to agree.
Would you mind showing your work on monte-carlo for this? If you’ve tried more than a few runs and they all actually terminated, you have a bug.
You’re describing a random-walk that moves left 25% of the time, right 25% and does not move 50% of the time, and counting steps until you get to 1. There is no possibility that this ends up better than 50% to exit after the same number of steps as 0.50^n.
1._round_________________1____________________8______0.125
2._round________________15___________________64______0.234
3._round_______________164__________________512______0.32
4._round_____________1,585________________4,096______0.387
5._round____________14,392_______________32,768______0.439
6._round___________126,070______________262,144______0.481
7._round_________1,079,808____________2,097,152______0.515
8._round_________9,111,813___________16,777,216______0.543
9._round________76,095,176__________134,217,728______0.567
I think you must just have an error in your code somewhere. Consider going round 3. Let the probability you say “3” be p_3. Then according to your numbers
Since the probability of escaping by round 3 is the probability of escape by round 2, plus the probability you don’t escape by round 2, multiplied by the probability the coin lands tails, multiplied by the probability you say “3”.
But then p_3 = 11⁄49, and 49 is not a power of two!
Say, that SB has only 10 tries to escape.
The DM (Dungeon Master) tosses his 10 coins and SB tosses her 20 coins, even before the game begins.
There are 2^30, which is about a billion possible outputs. More than half of them grants her freedom.
We compute her exit by—At the earliest x>y condition in each output bit string, the DM has also the freeing coin toss.
Based on some heuristic calculations I did, it seems that the probability of escape with this plan is exactly 4⁄10.
Interesting. Do you agree that every number is reached by the z function defined above, infinite number of times?
And yet, every single time z != sleeping_round? In the 60 percent of this Sleeping Beauty imprisonments?
Even if the condition x>y is replaced by something like x>y+sqrt(y) or whatever formula, you can’t go above 50%?
Extraordinary. Might be possible, though.
You clearly have a function N->N where eventually every natural number is a value of this function f, but f(n)!=n for all n.
That would be easier if it would be f(n)>>n almost always. But sometimes is bigger, sometimes is smaller.
Yes, definitely.
Yes. I proved it.
Well, on average we have f(n)=n for one n, but there’s a 50% chance the guy won’t ask us on that round.
There are two pretty strong sketches above here that this approaches 1⁄2 as you get closer to any static answer, but cannot beat 1⁄2.
The best answer is “ignore the coin, declare first”. There is no better chance of escape (though there are many ties at 1⁄2), and this minimizes your time in purgatory in the case that you do escape.
So, you say, the Sleeping Beauty is there forever with the probability of at least 1⁄2.
Then she has all the time in the world, to exercise this function which outputs z. Do you agree, that every natural number will be eventually reached by this algorithm, counting the double tossings, adding 0 or 1 to x and 0 or 1 to y and increasing z, until x>y?
Agree?
She has all the time in the world, but only as much probability as she gave up by not saying “first”.
Every natural number is reachable by your algorithm, but the probability that it’s reached ON THE SAME ITERATION as the wake-up schedule converges to zero pretty quickly. Both iterations and her responses approach infinity, the product of the probabilities approach zero way faster than the probabilities themselves.
Really. Go to Wolfram and calculate “sum to infinity 0.5^n * 0.5^n”. The chance that the current wake-up is N is clearly 0.5^n − 50% chance of T, 25% of HT, 12.5 of HHT, etc. If your distribution is different, replace the second 0.5^n with any formula such that “sum to infinity YOUR_FORMULA” is 1. It’s 0.3333 that she’ll EVER escape if she randomizes across infinite possibilities with the same distribution, and gets closer to (but doesn’t reach) 50% if she front-weights the distribution.
Your basic idea is right here. But … this product isn’t that straightforward.
Say it’s the 100th session. It is a lot of ways, that x becomes greater than y exactly this time. Especially if the formula is x>y+sqr(y) or something alike from the Chebyshev’s arsenal.
If the session is then 101st, this new small probability isn’t much smaller than it was in the 100th session.
Still, you may be right that the product (1-p_n)*(1-p_n+1) … converges to 1⁄2 at the most.
Well, I doubt it.
Don’t doubt it, do the math (and http://www.wolframalpha.com/ helps a LOT with this. Provide any formula for probability of guessing “Nth wakeup” such that it sums to 1 (or less) from 1 to infinity. Calculate the sum from 1 to infinity of the product of this and the 0.5^n chance that you’re currently on the Nth wakeup.
You will never find one that sums to better than 0.5.
Your weirdness using X and Y is not helping—any algorithm you can state eventually comes out to “some probability for each N of guessing N”. And when you view it that way, you’ll see that the sum has to be less than 50%.
Simplest is always “this is wakening #1”. 50% chance of escape, and soonest possible if it happens. Has the psychological disadvantage that if the first coin is tails, you’re stuck forever with no future chance of escape. You have no memory of any of them, so that is irrelevant—all that matters is the probability of escape—but it feels bad to us as outside observers.
You can stretch it out by randomizing your answer with a declining chance of higher numbers. Say, flip YOUR coin until you get tails, then guess the number of flips you’ve made. HHHT you guess 4, for example. This gives you 25% to be released on day 1 (50% DM’s coin is tails X 50% your first flip is.). And 6.5% to be released the second day (25% of HT on his coin and yours). Unfortunately, sum (i: 1->infinity) 0.25^i = 0.33333, so your overall chance of escaping is reduced. But you do always have some (very small) hope, unlike the simple answer.
Randomization with weighting toward earlier numbers improves your early chance, but reduces your later chances, and it seems (from sampling and thinking, not proven) that it can approach 0.5 but not exceed it.
I think the best you can do is 50% unless you have some information when you wake up about how long this has been going on.
Is it possible to pass information between awakenings? Use coin to scratch floor or something?
No, that is not possible.
So you only get one choice, since you will make the same one every time. I guess for simplicity choose ‘first’, but any number has same chance.
Can you do worse than that?
Sure, you can guess zero or negative numbers or whatever.
Say, you must always give a positive number. Can you do worse than 1⁄2 then?
No. You will always say the same number each time, since you are identical each time.
As long as it isn’t that number, you are going another round. Eventually it gets to that number, whereupon you go free if you get the luck of the coin, or go back under if you miss it.
That’s why you get a fair coin. Like a program, which gets seed for its random number generator from the clock.
Coin doesn’t help. Say I decide to pick 2 if it is heads, 1 if it is tails.
I’ve lowered my odds of escaping on try 1 to 1⁄4, which initially looks good, but the overall chance stays the same, since I get another 1⁄4 on the second round. If I do 2 flips, and use the 4 spread there to get 1, 2, 3, or 4, then I have an eight of a chance on each of rounds 1-4.
Similarly, if I raise the number of outcomes that point to one number, that round’s chance goes up , but the others decline, so my overall chance stays pegged to 1⁄2. (ie, if HH, HT, TH all make me say 1, then I have a 3⁄8 chance that round, but only a 1⁄8 of being awake on round 2 and getting TT).
The coin can at least lower your chances. Say, that you will say 3 if it is head and 4 if it is the tail.
You can win at round 3 with the probability 1⁄4 and you can win at round 4 with the probability 1⁄4.
Is that right?
Oh, yeah, I see what you are saying. Having 2 1⁄4 chances is, what, 7⁄16 of escape, so the coin does make it worse.
Sure. But not only to 7⁄16 but to the infinite number of other values, too. You just have to play with it longer.
The question now is, can the coin make it better, too? If not, why it can only make it worse?
If you say two numbers with nonzero probability, you can improve your chances by shifting all the probability mass to one of them.
If you say either 1 or 2 with probability 1⁄2 each, the probability of escaping is 7⁄16.
True. You can do it worse than 1⁄2. Just toss a coin and if it lands head up choose 1, otherwise choose 2.
You can link more numbers this way and it can be even worse.