0
$\begingroup$

I was considering an open problem recently: Start a simple random walk on the integers at 0. At any time, stop, and your payout is the ratio of positive-moves to overall moves.

It is easy to show that whenever you're at a negative integer, it's positive expectancy to flip exactly one more time. And whenever you're at a positive integer, it's negative expectancy to flip exactly one more time. However, it can be shown that if you if your path starts like: -1, 0, 1, it is actually optimal to not stop. So it is positive expectancy to continue but negative expectancy to continue just one step.

I guess I'm just seeking some sort of satisfying reason why there is no inconsistency here, whether it's intuitive or rigorous (even though this example itself proves it). Maybe I should just accept that this can be true and move on? By the way, more on this problem here.

$\endgroup$
1
  • $\begingroup$ In human terms, imagine betting against the housing market before the crash. In the short term, your bet has negative payoff (while the bubble is still inflating). But in the long term, your bet pays off. $\endgroup$
    – A.S.
    Commented Mar 4, 2016 at 21:19

1 Answer 1

0
$\begingroup$

While apparently a lot of computation was required to establish this result, it's not too difficult to see that it could be true.

If you flip exactly one more time, you end up with either $\frac34$ or $\frac12$. But you can always do better than $\frac12$ because the simple random walk is almost sure to return to a state with more heads than tails. So if you get $\frac34$, you can stop, whereas if you get $\frac12$, you can keep going until eventually you get more than $\frac12$. So you're certain to get more than you'd get from flipping exactly one more time. If you can show that in the $\frac12$ case your expected return is at least $2\cdot\frac23-\frac34=\frac7{12}$, then you're better off continuing to flip. As they calculated that continuing yields $\gt0.6693$, we can infer that the expected return in the $\frac12$ case is $\gt2\cdot0.6693-\frac34=0.5886$ (assuming that you should indeed stop in the $\frac34$ case, which seems reasonable).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .