How much should you be willing to pay to play this game if you only care about the expected value of your payoff, i.e. if you have linear utility?
It’s a random walk in 1D. It will hit any finite integer value “eventually” with probability one.
(Of course, this assumes that you have an arbitrarily long amount of time available.)
Once you have this insight the rest of the behavior becomes clear.
A 1D random walk attains a maximum (or minimum) value of O(sqrt(steps)) O(sqrt(steps log log steps)). So if you can play for N steps at max, you should be willing to pay O(sqrt(N)) O(sqrt(N log log N))[1]. This is obviously unbounded in the limit n→∞.
In other words, playing this game is worth nothing in the case both our bankrolls are finite.
Another way to look at this: the probability of a random walk starting at zero hitting b before −a is aa+b. So your expected payoff is baa+b+−a(1−aa+b)=aba+b−a((a+b)−aa+b)=aba+b−aba+b=0
EDIT: thanks to Ege Erdil for the correction. The expected final value is O(sqrt(N)); the expected maximum value is O(sqrt(N log log N)). An interesting distinction I was previously unaware of.
This is all true, but these are all points I make in the post already.
Edit: I couldn’t point this out earlier because I was on my phone, but the maximum attained by a random walk is not actually O(√N), it’s O(√NloglogN). It really doesn’t affect your argument, but strictly speaking the claim is otherwise not true.
Edit: I couldn’t point this out earlier because I was on my phone, but the maximum attained by a random walk is not actually O(√N), it’s O(√NloglogN). It really doesn’t affect your argument, but strictly speaking the claim is otherwise not true.
Interesting. You were correct and I was wrong here. I was unaware that the expected maximum was enough larger than the expected final value that it ended up asymptotically different.
It’s a random walk in 1D. It will hit any finite integer value “eventually” with probability one.
(Of course, this assumes that you have an arbitrarily long amount of time available.)
Once you have this insight the rest of the behavior becomes clear.
A 1D random walk attains a maximum (or minimum) value of
O(sqrt(steps))O(sqrt(steps log log steps)). So if you can play for N steps at max, you should be willing to payO(sqrt(N))O(sqrt(N log log N))[1]. This is obviously unbounded in the limit n→∞.Another way to look at this: the probability of a random walk starting at zero hitting b before −a is aa+b. So your expected payoff is baa+b+−a(1−aa+b)=aba+b−a((a+b)−aa+b)=aba+b−aba+b=0
EDIT: thanks to Ege Erdil for the correction. The expected final value is O(sqrt(N)); the expected maximum value is O(sqrt(N log log N)). An interesting distinction I was previously unaware of.
...glossing over the question as to if you actually know when you reach said max if you should stop.
This is all true, but these are all points I make in the post already.
Edit: I couldn’t point this out earlier because I was on my phone, but the maximum attained by a random walk is not actually O(√N), it’s O(√NloglogN). It really doesn’t affect your argument, but strictly speaking the claim is otherwise not true.
Interesting. You were correct and I was wrong here. I was unaware that the expected maximum was enough larger than the expected final value that it ended up asymptotically different.
Is it?
Ctrl-F “random walk” in the post shows no hits (aside from this comment.)
I don’t use the same vocabulary but your profit from the game is obviously a random walk.
It is obvious in hindsight; many things that are obvious in hindsight aren’t necessarily obvious until pointed out.
I thought it good to explicitly point out the connection in case someone didn’t see it.