expectation of random walk with barriers

Question

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.

Answer 1

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$.

Answer 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<k<n+m$, not visiting $0$ or $n+m$.

---

1) First, we notice that the probability of a path of length $\ell-1<t$ 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<t$ 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<k<n+m$, 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.

Answer 3

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$.