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%.
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%.