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