# expectation of random walk with barriers

Suppose we are flipping a coin with probability $$p$$ of coming up heads and $$q$$ of coming up tails. We start with $$n$$ dollars, and the game is over when we either lose all our money or win $$m$$ dollars. Each toss wins (if heads) or loses (if tails) $$\1.$$ We play the game for $$t$$ turns (or until we hit one of the barriers). Question: what is our expected capital at the end of the game? Obviously, if $$p>q,$$ and $$t\gg 1,$$ we asymptote to $$m+n,$$ and if $$t < \min(m, n),$$ the expectation is simply $$n+t(p-q).$$ But in between it seems a bit less obvious.

• This seems to be equivalent to finding the probability distribution of the first hitting time of $\{0,n+m\}$ (together with the hitting distribution). I do not think there is a closed-form expression for this. – Mateusz Kwaśnicki Nov 30 at 8:10
• @MaxAlekseyev of course, yes. – Igor Rivin Nov 30 at 18:53

Let $$k:=m+n+1$$, and consider $$k\times k$$ transfer matrix: $$M := \begin{bmatrix} 1 & q & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & q & 0 & \dots & 0 & 0 & 0\\ 0 & p & 0 & q & \dots & 0 & 0 & 0\\ 0 & 0 & p & 0 & \ddots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ddots & 0 & q & 0\\ 0 & 0 & 0 & 0 & \dots & p & 0 & 0\\ 0 & 0 & 0 & 0 & \dots & 0 & p & 1 \end{bmatrix}$$ Then the expected capital at the game end is $$[0,1,\dots,m+n]\cdot M^t\cdot e_{n+1},$$ where the $$e_{n+1}$$ is the unit column vector with the $$(n+1)$$-st component equal 1.

Matrix $$M$$ is tridiagonal and almost Toeplitz, and so it should be possible to get an explicit formula. For example, its characteristic polynomial can be expressed in terms of Lucas sequences as $$(1-\lambda)^2 U_{k-1}(-\lambda,pq)$$. Its eigenvalues are $$1, 1$$, and $$2\sqrt{pq}\cos\frac{j\pi}{k-1}$$ for $$j=1,2,\dots,k-2$$.

UPD. Formulae corrected.

Second approach, which follows the ideas from this answer to other question.

Consider the game as a random walk on the real line, starting at vertex $$n$$ and making steps +1 with probability $$p$$ and $$-1$$ with probability $$q=1-p$$. To answer the question, we need to find the probabilities of the following outcomes:

1) Path of length $$\ell\leq t$$ from $$n$$ to $$n+m$$, not visiting $$0$$ and not visiting $$n+m$$ except at the end.

2) Path of length $$\ell\leq t$$ from $$n$$ to $$0$$, not visiting $$n+m$$ and not visiting $$0$$ except at the end.

3) Path of length $$t$$ from $$n$$ to $$k$$, where $$0, not visiting $$0$$ or $$n+m$$.

1) First, we notice that the probability of a path of length $$\ell-1 from $$n$$ to $$n+m-1$$, not visiting $$0$$, equals

$$[x^{n+m-1}]\ x^n (px + qx^{-1})^{\ell-1} - [x^{-(n+m-1)}]\, x^n (px + qx^{-1})^{\ell-1}$$ $$=[x^0]\ (x^{-(m-1)}-x^{2n+m-1})(px + qx^{-1})^{\ell-1}$$

Second, the probability of a path of length $$\ell-1 from $$n$$ to $$n+m-1$$, not visiting $$0$$ and $$n+m$$, equals $$[x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})(px + qx^{-1})^{\ell-1}$$

Finally, the probability of a path of length $$\ell\leq t$$ from $$n$$ to $$n+m$$, not visiting $$0$$ and not visiting $$n+m$$ except at the end, equals $$p\cdot [x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})(px + qx^{-1})^{\ell-1}$$

For all these paths the capital at the end is $$n+m$$ and their contribution to the expectation is given by the sum over $$\ell=1,\dots,t$$, i.e., $$(n+m)p\ [x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})\frac{1-(px + qx^{-1})^t}{1-(px + qx^{-1})}$$

2) The probability of such paths can be computed similarly, but their contribution to the capital expectation is zero.

3) Similarly, the probability of a path of length $$t$$ from $$n$$ to $$k$$, where $$0, not visiting $$0$$ or $$n+m$$, equals $$[x^0]\ (x^{n-k}-x^{n+k}-x^{n+k-2m}+x^{n+2m-k})(px + qx^{-1})^t.$$

Their contribution is given by $$\begin{split} [x^0]\ &\sum_{k=1}^{n+m-1} k(x^{n-k}-x^{n+k}-x^{n+k-2m}+x^{n+2m-k})(px + qx^{-1})^t \\ =[x^0]\ &\big(\frac{x^{n+1+2m}-x^{n+1-2m}-(x^{1+m}+x^{1-m})+(x^{1+2n+m}+x^{1+2n-m})}{(1-x)^2} \\ +& (n+m)\frac{x^{1+m}+x^{1-m}+x^{2n+m}+x^{2n-m}}{1-x}\big)(px + qx^{-1})^t. \end{split}$$

The expectation can now be computed routinely.

Call $$X_k$$ the amount of money at time $$k$$, $$T_0:=\inf\{k,X_k=0\}$$, $$T_{n+m}:=\inf\{k,X_k=m+n\}$$ and $$T=T_{0}\wedge T_{n+m}$$

First we have that $$M_k:=X_k-(p-q)k$$ is a martingale then (as already mentioned by Matheus) we have $$n =\mathbb{E}(M_0)= \mathbb{E}(M_{k\wedge T})=\mathbb{E}(X_{k\wedge T})+(p-q)\mathbb{E}(k\wedge T).$$

Second we have that $$N_k = \big(\frac{p}{q}\big)^{-X_k}$$ is a martingale, then $$\mathbb{P}(T_0<\infty)\leq \lim_{k\rightarrow \infty} \mathbb{E}(N_{k\wedge T_0}) = \mathbb{E}(N_{0})=\big(\frac{p}{q}\big)^{-n}$$ that decay exponentially with $$n$$. Therefore if $$(p-q)\gg\frac{1}{n}$$, I guess we can just forget about the $$0$$ boundary, and then $$T=T_{n+m}$$.

Third, for all $$i\geq k$$, $$Y_i :=(T_{i+1}-T_i)$$ are iid random variable with mean $$\mathbb{E}(Y)=\frac{1}{p-q}$$. And then by CLT $$\frac{T_{m+n}-m(p-q)^{-1}}{\sqrt{m}}=\frac{\sum_{i=n}^{n+m-1}(Y_i-(p-q)^{-1})}{\sqrt{m}}\rightarrow \mathcal{N}(0,\sigma^2)$$ as $$m\rightarrow \infty$$ with $$\sigma^2$$ the variance of $$Y$$.