2. Main result

In this section we state and prove our main result.

To prove the theorem we need some lemmas. Let $T_0(p)$ denote the first time (after time 0) when the walk revisits the state 0, and let

\begin{equation*}A_p=\big\{T_0(p)<T(p)\big\}\end{equation*}

be the event that the walk revisits 0, having started at 0, before the game ends. We can write

\begin{equation*}T(p)=Z(p)+\sum_{i=1}^{N(p)-1} Y_i(p),\end{equation*}

where

\begin{equation*}Z(p)\sim \Big(T(p)|A^c_p\Big),\qquad Y_i(p)\sim \big(T_0(p)|A_p\big),\qquad N(p)\sim \mbox{Geometric} \Big( P\Big(A^c_p\Big)\Big)\end{equation*}

are all independent variables. We will prove the following lemma, from which Theorem 1 follows immediately.

To prove this lemma, let $u_i(p)$ be the chance that the walk goes up next when it is at level i given that it returns to 0 before the game ends, and let $v_i(p)$ be the chance that the walk goes up next when it is at level i given that the game ends before the walk returns to zero.

Proof of Lemma 2. Letting

\begin{equation*}P_i(p) = \left\{\begin{array}{l@{\quad}l}\frac{1-\left(\frac{1-p}{p}\right)^i}{1-\left(\frac{1-p}{p}\right)^k}, & p\neq \frac{1}{2}, \\[15pt]i/k, & p=\frac{1}{2},\end{array}\right.\end{equation*}

from [Reference Ross9, Equation (4.14), p. 235] be the chance that a gambler reaches k before 0 starting with i, we have

\begin{equation*}u_i(p)=\frac{p\big(1-P_{i+1}(p)\big)}{1-P_i(p)}.\end{equation*}

Making the substitution $n=k-i$ , we have

\begin{equation*}u_i(1/2)=\frac{n-1}{2n}.\end{equation*}

For $p\neq 1/2$ , when we make the substitution $x=(1-p)/p$ , we have

\begin{equation*}1-P_i(p)=1-\frac{1-x^{i}}{1-x^k}= \frac{x^{i}-x^k}{1-x^k}\end{equation*}

and $p=1/(1+x)$ , and we get

\begin{equation*}u_i(p) = \frac{1}{1+x}\frac{x^{i+1}-x^k}{x^i-x^k}=\frac{x^n-x}{(1+x)(x^n-1)}.\end{equation*}

We will thus have $u_i(p)\leq u_i(1/2)$ whenever

(1) \begin{equation}f(x)\equiv x^n-x-\frac{n-1}{2n}(x+1)\big(x^n-1\big)\left\{\begin{array}{l@{\quad}l}\leq 0 & \mbox{ if } x>1, \\[4pt]\geq 0 & \mbox{ if } x<1.\end{array}\right.\end{equation}

Since

\begin{equation*}f^{\prime}(x)=-\frac{(n+1)\big(x-x^{n+1}+n(x-1)x^n\big)}{2nx}\end{equation*}

implies $f^{\prime}(1)=0$ and

\begin{equation*}f^{\prime\prime}(x)=\frac{1}{2} (n-1)(n+1)(1-x)x^{n-2}\left\{\begin{array}{l@{\quad}l}< 0 & \mbox{ if } x>1, \\[4pt]> 0 & \mbox{ if } x<1,\end{array}\right.\end{equation*}

this means f(x) is monotone decreasing with $f(1)=0$ , and therefore (1) holds, implying $u_i(p)\leq u_i(1/2)$ .

Next, looking at the walk reflected across the origin gives $v_i(p)=1-u_{k-i}(1-p)$ , and thus, by the reasoning above, $v_i(p)\geq v_i(1/2).$

Finally, we have

\begin{equation*}P\big(A^c_p\big) =pP_1(p)+(1-p)P_1(1-p)\end{equation*}

and thus

\begin{equation*}P\Big(A^c_{1/2}\Big)=1/k,\end{equation*}

and for $p\neq 1/2$ , making the substitution $x=(1-p)/p$ gives

\begin{equation*}P\big(A^c_{p}\big) = \frac{1}{1+x}\frac{1-x}{1-x^k}+\frac{x}{1+x}\frac{1-x^{-1}}{1-x^{-k}} = \frac{(x-1)\big(x^k+1\big)}{(x+1)\big(x^k-1\big)}.\end{equation*}

So we will have $P\big(A^c_p\big)\geq 1/k$ whenever

(2) \begin{equation}f(x)\equiv k(x-1)\big(x^k+1\big)-(x+1)\big(x^k-1\big) \left\{\begin{array}{l@{\quad}l}\geq 0 & \mbox{ if } x>1, \\[5pt]\leq 0 & \mbox{ if } x<1.\end{array}\right.\end{equation}

Since

\begin{equation*}f^{\prime}(x)=-\frac{(k + 1) \Big((k (x - 1) - x) x^k + x\Big)}{x}\end{equation*}

implies $f^{\prime}(1)=0$ and

\begin{equation*}f^{\prime\prime}(x)=k(k-1)(k+1)(x-1)x^{k-2}\left\{\begin{array}{l@{\quad}l}> 0 & \mbox{ if } x>1, \\[4pt]< 0 & \mbox{ if } x<1,\end{array}\right.\end{equation*}

this means f(x) is monotone increasing with $f(1)=0$ and therefore (2) holds, implying $P\big(A^c_p\big)\geq P\big(A^c_{1/2}\big)$ .

Proof of Lemma 1. We first construct two coupled random walks, both conditional on a revisit to the origin before the game ends, but where the first walk uses any $0<p<1$ and the second uses $p=1/2$ . We will let Y(p) and $Y(1/2)$ respectively denote the first time the origin is revisited for each of the two conditioned walks. We let the first walk take the first step, and since the second walk is symmetric and has the same length distribution regardless of its first step, we let its first step be the same as that of the first walk. Suppose both the walks first step above the origin. Whenever the walks are at different levels, we let them step independently. When the walks are at the same level, by Lemma 2 the chance of a step away from the origin is at least as large for the second walk as it is for the first walk, so we can couple the steps so that the second walk always ends up no closer to the origin than the first walk. This means that in this case we will have $Y(p)\leq Y(1/2)$ almost surely. In the event that the walks first step below the origin, the same reasoning applies, because the distance to the origin for the first walk is the same as if the step had been above the origin, but with $1-p$ substituted for p. This shows that $Y(p)\leq_{st} Y(1/2).$

A similar construction using Lemma 2 gives $Z(p)\leq_{st} Z(1/2),$ and $N(p)\leq_{st} N(1/2)$ follows from Lemma 2 since $P\big(A^c_p\big)\geq P\big(A^c_{1/2}\big).$

Proof of Theorem 1. By Lemma 2, we can couple $T(1/2)$ together with T(p) on the same probability space so that $T(1/2)\geq T(p)$ almost surely, and the theorem follows.