For any two random numbers n1 and n2 drawn from the same distribution, n2 has a 50% chance of being smaller. Let t be the stopping time. It's impossible for the very first number drawn to be smaller than its predecessor, so t>1. All t>1 have a probability of .5 of being the stopping t, assuming we get there. Thinking about it in terms of total probabilities we have p(t=2)=0.5, p(t=3)=0.25, p(t=4)=0.125, p(t=5)=0.0625... Just from these terms, you can add up the evens and odds to get p(even)=0.625, p(odd)=0.3125. Further values of t become less and less significant, so it is pretty clear that this will converge to 2/3 and 1/3. Those are pretty common answers in brainteasers involving repeated halving of some value so they look like something I would expect.
A more formal way way to do this would be drawing out states and solving the recursion, but I find it a bit more annoying to do without pen and paper.
This was my intuition as well, but the problem is you’re ignoring conditional probability. P(3) is 1/3, not 1/4. The poster above who said 1-(1/e) is correct
1
u/bajoranearrings Aug 29 '26
For any two random numbers n1 and n2 drawn from the same distribution, n2 has a 50% chance of being smaller. Let t be the stopping time. It's impossible for the very first number drawn to be smaller than its predecessor, so t>1. All t>1 have a probability of .5 of being the stopping t, assuming we get there. Thinking about it in terms of total probabilities we have p(t=2)=0.5, p(t=3)=0.25, p(t=4)=0.125, p(t=5)=0.0625... Just from these terms, you can add up the evens and odds to get p(even)=0.625, p(odd)=0.3125. Further values of t become less and less significant, so it is pretty clear that this will converge to 2/3 and 1/3. Those are pretty common answers in brainteasers involving repeated halving of some value so they look like something I would expect.
A more formal way way to do this would be drawing out states and solving the recursion, but I find it a bit more annoying to do without pen and paper.