DRMacIver's Notebook
Expected Time To Hit A Score Difference
Expected Time To Hit A Score Difference
For reasons I’ve recently found myself interested in the following problem: Suppose you have a series of bernoulli random variables \(X_1, \ldots, X_n, \ldots\) independently distributed with identical parameter \(p > \frac{1}{2}\). What is the expected time until you have at least \(k\) more successes than failures?
I spent an annoyingly long time with it before realising in the shower this morning that it’s actually very easy. The key to solving this is to realise the critical role that the \(k = 1\) version plays.
Let \(a_k\) be the expected time to get \(k\) more successes than failures. Then \(a_0 = 0\) clearly. The key observation is that for \(n \geq 1\) we have \(a_n = 1 + (1 - p)(a_1 + a_n) + p a_{n - 1}\).
Why does this hold?
Think of it as an infinite state markov chain. When you are at state \(n\), you can either drop down to state \(n - 1\) with probability \(p\), or go up to state \(n + 1\) with probability \(1 - p\). If we go up a state, in order to return to the current state subsequent draws need to have exactly one more success than failure. By definition, this takes an expected time of \(a_1\).
We can now plug in \(a_1\) to this and do some simple algebra to get that \(a_1 = (2 p - 1)^{-1}\).
For \(n > 1\) we again do some algebra and get \(a_n = p^{-1}(1 + (1 - p)a_1) + a_{n - 1}\), or \(a_n = (2p - 1)^{-1} + a_{n - 1}\). Putting these all together we get that \(a_n = n (2p - 1)^{-1}\)
Which all told is a much nicer result than I was expecting.