### 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:
Posts (Atom)