How to find the expectation when a finite-time random walk is not absorbed

Question

There is a gambler who gambles $t$ rounds every day. In each round, there is a half probability of winning \$1 and a half probability of losing \$1.

Leave the game when the total profit is $+1$ or when the maximum number of rounds is reached.

Ask for his daily income expectation.

---

My idea is to consider a random walk process, there is an absorbing wall at $n = 1$, and then I calculate the cumulative probability of hitting the absorbing wall in $t$ rounds, multiplying it by $+1$ is the expectation of winning money.

But I'm having trouble calculating the expectation of the situation where he lose money.

I calculated that the game is over and the probability of losing $k$ without hitting the absorbing wall is

$$2^{-t-1} \left((-1)^{k+t}+1\right) \binom{t}{\frac{k+t}{2}}$$

But I don't know how to calculates this summation.

$$\sum _{k=0}^t k\times 2^{-t-1} \left((-1)^{k+t}+1\right) \binom{t}{\frac{k+t}{2}}$$

Does this summation have a closed-form solution? Or how to estimate it asymptotically?

Answer 1

Here we show the following is valid \begin{align*} \color{blue}{\sum_{k=0}^t\frac{k}{2^{t+1}}\left((-1)^{k+t}+1\right)\binom{t}{\frac{k+t}{2}} =\begin{cases} \frac{t}{2^{t+1}}\binom{t}{\frac{t}{2}}\qquad\quad t\ \mathrm{even}\\ \frac{t+1}{2^{t+1}}\binom{t}{\frac{t+1}{2}}\qquad\ \ t\ \mathrm{odd}\\ \end{cases}}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^t}&\color{blue}{\frac{k}{2^{t+1}}\left((-1)^{k+t}+1\right)\binom{t}{\frac{k+t}{2}}}\\ &=\frac{1}{2^{t+1}}\sum_{k=0}^t(t-k)\left((-1)^k+1\right)\binom{t}{t-\frac{k}{2}}\tag{2}\\ &=\frac{1}{2^t}\sum_{k=0}^{\left\lfloor t/2\right\rfloor}(t-2k)\binom{t}{k}\tag{3}\\ &=\frac{t}{2^t}\sum_{k=0}^{\left\lfloor t/2\right\rfloor}\binom{t}{k}-\frac{1}{2^{t-1}}\sum_{k=1}^{\left\lfloor t/2\right\rfloor}k\binom{t}{k}\tag{4}\\ &=\frac{t}{2^t}\sum_{k=0}^{\left\lfloor t/2\right\rfloor}\binom{t}{k}-\frac{t}{2^{t-1}}\sum_{k=1}^{\left\lfloor t/2\right\rfloor}\binom{t-1}{k-1}\tag{5}\\ &\,\,\color{blue}{=\frac{t}{2^t}\sum_{k=0}^{\left\lfloor t/2\right\rfloor}\binom{t}{k}-\frac{t}{2^{t-1}}\sum_{k=0}^{\left\lfloor t/2\right\rfloor-1}\binom{t-1}{k}}\tag{6}\\ \end{align*}

Comment:

• In (2) we change the order of summation $k\to t-k$.

• in (3) we consider even $k$ only since terms with odd $k$ are zero.

• In (4) we split the sum.

• in (5) we use the binomial identity $\binom{p}{q}=\frac{p}{q}\,\binom{p-1}{q-1}$.

• In (6) we shift the index of the right-hand sum by one to start with $k=0$.

In order to simplify (6) we consider even and odd cases for $t$ separately.

Case $t=2q$ even:

We set $t=2q$ and obtain from (6) \begin{align*} \color{blue}{\frac{2q}{2^{2q}}}&\color{blue}{\sum_{k=0}^q\binom{2q}{k}-\frac{2q}{2^{2q-1}}\sum_{k=0}^{q-1}\binom{2q-1}{k}}\\ &=\frac{2q}{2^{2q}}\left(2^{2q-1}+\frac{1}{2}\binom{2q}{q}\right)-\frac{2q}{2^{2q-1}}2^{2q-2}\\ &=\frac{q}{2^{2q}}\binom{2q}{q}\\ &\,\,\color{blue}{=\frac{t}{2^{t+1}}\binom{t}{\frac{t}{2}}} \end{align*} and the claim (1) for even $t$ follows.

Case $t=2q+1$ odd:

We set $t=2q+1$ and obtain from (6) \begin{align*} \color{blue}{\frac{2q+1}{2^{2q+1}}}&\color{blue}{\sum_{k=0}^q\binom{2q+1}{k}-\frac{2q+1}{2^{2q}}\sum_{k=0}^{q-1}\binom{2q}{k}}\\ &=\frac{2q+1}{2^{2q+1}}2^{2q}-\frac{2q+1}{2^{2q}}\left(2^{2q-1}-\frac{1}{2}\binom{2q}{q}\right)\\ &=\frac{2q+1}{2^{2q+1}}\binom{2q}{q}\\ &=\frac{t}{2^t}\binom{t-1}{\frac{t-1}{2}}\\ &\,\,\color{blue}{=\frac{t+1}{2^{t+1}}\binom{t}{\frac{t+1}{2}}} \end{align*} and the claim (1) for odd $t$ follows.