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