# Expected Hitting Time of Countably Infinite Birth-Death Markov Chain

I thought this would be an easy question to answer, but I've been stumped for two days despite copious textbook reading and algebra, so I thought I would reach out to the StackExchange community.

I'm trying to model a simple game of chance in which a player starts with some amount of money, and each round bets $1$ unit of money, and if the player ever runs out of all of their money then the game is over. The result of a given round can be a win (in which case the player earns $1$ unit of money), a loss (in which case the player loses $1$ unit of money), or a draw (in which case the player's amount of money remains unchanged). The probabilities of these three outcomes are denoted by $w$, $l$, and $d$ respectively, where $l>w$ and $w+l+d=1$.

This game can be modeled as a birth-death chain on the nonnegative integers, with the following (countably infinite) transition matrix:

$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \cdots \\ l & d & w & 0 & 0 & \cdots \\ 0 & l & d & w & 0 & \cdots \\ 0 & 0 & l & d & w & \cdots \\ 0 & 0 & 0 & l & d & \cdots \\ 0 & 0 & 0 & 0 & l & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix}$

I am particularly interested in knowing how long it will take for the player to run out of money, assuming they started with a money pool of size $n$. That is, I am trying to find a formula for $\mathbf{\operatorname{E}_n[T_0]}$, i.e. the expected time until the state $\mathbf{0}$ is reached given that the chain was started from $\mathbf{X_0=n}$

This is almost identical to the classic Gambler's Ruin problem, except that here there does not exist any upper limit to the amount of money which the gambler can make before stopping, resulting in an infinite state space. This is the root cause of my problem, as the normal method for computing the expected hitting time of some state requires inverting the transient portion of the transition matrix, or equivalently solving a certain system of linear equations, neither of which I've been able to figure out how to do in this infinite-state case. (For details about the matrix inversion/linear equation system approach see page 49 of "Essentials of Stochastic Processes" by Rick Durrett.)

I've spent quite a bit of time trying to row-reduce the matrix to a point where a pattern emerges, but thus far have not been successful, so any help would be greatly appreciated.

• One thought I have is to write a recurrence relation and solve it -- not sure how this will play out. Let $E_n$ be the expected time til failure starting at $n$ dollars. Then $E_n = 1 + wE_{n+1} + dE_n + \ell E_{n-1}$ for $n > 0$ and $E_0 = 0$. – user217285 Dec 29 '16 at 7:07
• Yes, just write a linear recurrence relation. [Edit: Yes, the one you give will work] – Michael Dec 29 '16 at 7:10
• On second thought, I think I've seen this problem before: ocw.mit.edu/courses/electrical-engineering-and-computer-science/… – user217285 Dec 29 '16 at 7:14
• To hit $0$ starting from $n$ one must first hit $n-1$ then $n-2$, and so on, hence $E_n=nE_1$ for every $n$. Furthermore, conditioning by the first step made starting from $1$, one gets $E_1=1+dE_1+wE_2$. Thus, $E_n=(1-d-2w)^{-1}n=(l-w)^{-1}n$ for every $n$, provided $l>w$. Bonus question: Why does the formula only make sense when $l>w$? – Did Dec 29 '16 at 8:44
• This might also be a good read for an example of the approach of writing down a recurrence relation to solve these sorts of problems. – Theoretical Economist Dec 29 '16 at 8:45

The solution wound up being $E_n = \frac{n}{l-w}$ as suggested by Did's comment. This can also be seen by noting that the expected payoff from each round is $(-1)\cdot l + 0\cdot d + 1\cdot w = w-l$, and therefore the expected number of rounds $r$ before the player loses all of their money is:

$n+r\cdot (w-l)=0 \ \longrightarrow \ r = \frac{n}{l-w}$

However it's still not clear to me how one might go about arriving at this answer purely by solving the recurrence relation provided by Nitin. The general solution to the recurrence is:

$E_n = k_1(\frac{l}{w})^n+k_2+\frac{n}{l−w}$

which after applying the boundary condition of $E_0 = 0$ becomes:

$E_n = k_1(\frac{l}{w})^n-k_1+\frac{n}{l−w}$

Setting $k_1 = 0$ then yields the result described above. However it is unclear what additional constraint can be applied to justify this. See Did's comment above for details

• "it is unclear what additional constraint can be applied to justify this" See comment on main. – Did Dec 30 '16 at 8:42