a probability puzzle
No paradox and nothing profound here, just a little puzzle to pass the time until Monday.
I have two reasons for posting it: i) It is similar to some problems I have to deal with at work (*) and ii) it gives me an opportunity to link to the blog where I got it from (after the solution is revealed).
So Alice and Bob like to play a certain (card) game (if they are not busy with encryption problems and black hole entanglement). Everybody knows that Alice is slightly more skilled at this game and wins with probability 55%; However, she really likes to win and so Alice and Bob always play as many games as it takes for Alice to be ahead in winnings (x). So sometimes they play just one game (if Alice wins immediately) and sometimes many, but what is the expected number N of games the two will play (after a fresh start)?
(*) A similar problem I would be dealing with could be e.g. of the form "if I have an order sitting at the bid, how long will it take on average to get filled".
(x) Added later, just to clarify: Alice and Bob play N games until Alice wins one game more than Bob. E.g. Alice wins the 1st game; Or Bob wins the 1st and Alice wins the next 2 games; Or ...
------------------
This puzzle is equivalent to a biased random walk of the difference D in winnings between Bob and Alice. It begins at D=0 and if D>0 it means that Bob is ahead; The random walk ends at D=-1 i.e. when Alice is ahead by one. So what is the expectation value E = E[N] of the length N of this random walk?
There are two ways to solve it. One can (try to) sum up all terms in the series of all possible events as described here. I assume this is how John von Neumann would have solved this puzzle.
Fortunately, there is a much easier solution for the rest of us and you can find it in the comments.
It gives us E = 1/(2p - 1) and with p=0.55 for Alice to win a single game we get E=10.
Notice that E diverges for p=1/2 and I find this somewhat counterintuitive, knowing that an unbiased random walk will visit every point D with probability 1.
Subscribe to:
Post Comments (Atom)
6 comments:
So I'm probably missing something here, but wouldn't the expectation value just be 1/p or in this case 100/55 or 1.8182 games.
No, now that I think about it this isn't like rolling a die, so my above answer is wrong.
you are missing something 8-)
Let's see at the first game Alice has a chance of 55% percent to win - in this case N=1
Assume she did not win (prob = 45%): Now she has to win two games in a row (but Bob could win as well)
and so on and so forth.
I don't see how this would get you to 1/p
On 2nd thought, I think I know where the misunderstanding was: They do not play until Alice wins once - they play until Alice is "ahead in winnings" i.e. until she wins (one game) more than Bob.
Yeah, I just totally misunderstood the first time I read it and I thought this is easy. Then, I felt pretty foolish after I re-read it and understood the problem. Anyway, as soon as my wife will let me have some time, it will keep me entertained for a while. Thanks for the problem.
======= SPOILER ALERT ======
We want to know the expectation value E = E[N] and for the 1st game we have:
E = p*1 + (1-p)*( 1 + E' )
where p is the probability that Alice wins and E' is the expectation value E'[N] if Alice is one game *behind*.
The trick is to realize that E' = 2*E, because Alice needs twice as long to be ahead if she is one game behind, than if they start even.
Therefore we have an equation for E with
E = p + (1-p)*(1 + 2*E )
which is easy to solve.
Post a Comment