Consider the simple symmetric random walk , where each step increment satisfies . The initial position is . Let . Prove that for .

Probability Theory Solution – Problem 43: Prove that for

Question

Consider the simple symmetric random walk $\{S_{n},n\geqslant0\}$ , where each step increment $\xi_{n}=S_{n}-S_{n-1}$ satisfies $P\left(\xi_{n}=1\right)=P\left(\xi_{n}=-1\right)=\frac{1}{2}$ . The initial position is $S_{0}=0$ . Let $T_{1}=\operatorname*{min}\left\{n\geqslant0:\,S_{n}=1\right\}$ . Prove that $E\left[s^{T_{1}}\right]=\frac{1-\sqrt{1-s^{2}}}{s}$ for $0\leqslant s\leqslant1$ .

Step-by-step solution

Step 1. Let $\phi(s) = E[s^{T_1}]$ be the probability generating function of the first hitting time $T_1$ . The random walk starts at $S_0=0$ . The first step $S_1$ has two possibilities: 1. $S_1 = 1$ , occurring with probability $\frac{1}{2}$ . If the first step reaches 1, then by definition, $T_1=1$ . 2. $S_1 = -1$ , also occurring with probability $\frac{1}{2}$ . If the first step reaches $-1$ , then the walk must travel from $-1$ to $1$ . By the law of total expectation: $\phi(s) = E[s^{T_1}] = E[E[s^{T_1} | S_1]]$ $= P(S_1=1) E[s^{T_1} | S_1=1] + P(S_1=-1) E[s^{T_1} | S_1=-1]$ $= \frac{1}{2} E[s^{T_1} | S_1=1] + \frac{1}{2} E[s^{T_1} | S_1=-1]$ Given $S_1=1$ , we have $T_1=1$ , so $E[s^{T_1} | S_1=1] = s^1 = s$ . Given $S_1=-1$ , the walk is at $-1$ . To reach $1$ , it must first return from $-1$ to $0$ , and then travel from $0$ to $1$ .

Step 2. Let $T_{i,j}$ denote the first passage time from position $i$ to position $j$ . After $S_1=-1$ , the total first hitting time is $T_1 = 1 + T_{-1,1}$ . By the spatial homogeneity of the random walk, the time from $-1$ to $0$ has the same distribution as the time from $0$ to $1$ . That is, $T_{-1,0}$ has the same distribution as $T_{0,1} = T_1$ . Similarly, the time from $0$ to $1$ also has the same distribution as the time from $-1$ to $0$ . Therefore, the process of traveling from $-1$ to $1$ can be decomposed into two steps: The first step is from $-1$ to $0$ , requiring time $T_{-1,0}$ . The second step is from $0$ to $1$ , requiring time $T_{0,1}$ . Since each step is independent, the times of these two processes are also independent. So $T_{-1,1} = T_{-1,0} + T_{0,1}$ . Given $S_1=-1$ , we have $T_1 = 1 + T_{-1,0} + T_{0,1}$ .

Step 3. Since $T_{-1,0}$ and $T_{0,1}$ both have the same distribution as $T_1$ , and they are independent: $E[s^{T_1} | S_1=-1] = E[s^{1 + T_{-1,0} + T_{0,1}}] = s \cdot E[s^{T_{-1,0}}] \cdot E[s^{T_{0,1}}] = s \cdot \phi(s) \cdot \phi(s) = s\phi(s)^2$ . Substituting both conditional expectations into the original equation: $\phi(s) = \frac{1}{2}s + \frac{1}{2}s\phi(s)^2$ Rearranging into a standard quadratic equation in $\phi(s)$ : $s\phi(s)^2 - 2\phi(s) + s = 0$ This is of the form $Ax^2+Bx+C=0$ with $x=\phi(s)$ , $A=s$ , $B=-2$ , $C=s$ . Using the quadratic formula: $\phi(s) = \frac{-(-2) \pm \sqrt{(-2)^2 - 4(s)(s)}}{2s} = \frac{2 \pm \sqrt{4 - 4s^2}}{2s} = \frac{2 \pm 2\sqrt{1 - s^2}}{2s} = \frac{1 \pm \sqrt{1 - s^2}}{s}$

Step 4. The probability generating function $\phi(s) = \sum_{k=1}^{\infty} P(T_1=k)s^k$ is a power series near $s=0$ . As $s \to 0^+$ , $\phi(s) \to 0$ since $T_1 \ge 1$ . Checking the behavior of the two candidate solutions as $s \to 0^+$ : 1. For $\phi_+(s) = \frac{1 + \sqrt{1 - s^2}}{s}$ : $\lim_{s \to 0^+} \frac{1 + \sqrt{1 - s^2}}{s} = \frac{1+1}{0^+} = +\infty$ . This solution does not satisfy $\phi(0)=0$ . 2. For $\phi_-(s) = \frac{1 - \sqrt{1 - s^2}}{s}$ : $\lim_{s \to 0^+} \frac{1 - \sqrt{1 - s^2}}{s}$ is a $\frac{0}{0}$ indeterminate form. Multiplying by the conjugate: $\lim_{s \to 0^+} \frac{1 - \sqrt{1 - s^2}}{s} \cdot \frac{1 + \sqrt{1 - s^2}}{1 + \sqrt{1 - s^2}} = \lim_{s \to 0^+} \frac{1 - (1 - s^2)}{s(1 + \sqrt{1 - s^2})} = \lim_{s \to 0^+} \frac{s^2}{s(1 + \sqrt{1 - s^2})} = \lim_{s \to 0^+} \frac{s}{1 + \sqrt{1 - s^2}} = \frac{0}{1+1} = 0$ . This solution satisfies $\phi(0)=0$ .

Step 5. Therefore, the unique valid solution is $\phi_-(s)$ . The desired expectation $E[s^{T_1}]$ equals $\frac{1-\sqrt{1-s^{2}}}{s}$ . QED.

Final answer

QED.

Marking scheme

The following is the rubric for this probability theory problem.

1. Checkpoints (max 7 pts total)

Score exactly one chain | take the maximum subtotal among chains; do not add points across chains.

Chain A: First-Step Analysis / Generating Function Method (Official Solution Path)

Law of total expectation setup (1 pt):
Correctly write the conditional expectation expression based on the first step $S_1$ .
For example: $\phi(s) = \frac{1}{2} E[s^{T_1} \mid S_1=1] + \frac{1}{2} E[s^{T_1} \mid S_1=-1]$ .
Recursive structure analysis (2 pts):
Identify that given $S_1=-1$ , reaching state 1 is equivalent to the sum of two independent processes: "from $-1$ to $0$ , then from $0$ to $1$ ."
Explicitly derive that the corresponding generating function term is $s \cdot \phi(s)^2$ (where $s$ accounts for the time cost of the first step, and $\phi^2$ represents the convolution of the subsequent two stages).
*Note: If the student directly writes the correct quadratic equation, this logic is implicitly included and earns full marks.*
Establishing the quadratic equation (1 pt):
Write the complete equation for $\phi(s)$ , such as $\phi(s) = \frac{1}{2}s + \frac{1}{2}s \phi(s)^2$ or the rearranged form $s\phi^2 - 2\phi + s = 0$ .
Solving the equation (1 pt):
Correctly solve using the quadratic formula to obtain $\phi(s) = \frac{1 \pm \sqrt{1-s^2}}{s}$ .
Root selection and justification (2 pts):
[max 2]
Correctly select the minus sign ( $\frac{1 - \sqrt{1-s^2}}{s}$ ) and provide sufficient mathematical justification (e.g., $\phi(s) \to 0$ as $s \to 0^+$ , or series convergence/boundedness analysis). (2 pts)
Correct selection but insufficient justification (e.g., only stating "probability cannot exceed 1" without verifying the other root is indeed greater than 1, or only checking the value at $s=1$ which cannot distinguish the two roots). (1 pt)

Chain B: Martingale Approach

Constructing the martingale (2 pts):
Construct a process of the form $M_n = s^n \lambda^{S_n}$ and set up the martingale condition $E[M_{n+1} \mid \mathcal{F}_n] = M_n$ .
Characteristic equation solution (2 pts):
Derive the characteristic equation $s(\lambda + \lambda^{-1}) = 2$ and solve for $\lambda = \frac{1 \pm \sqrt{1-s^2}}{s}$ .
Optional stopping theorem application (1 pt):
Apply the optional stopping theorem (OST) to obtain $E[s^{T_1} \lambda^{S_{T_1}}] = 1$ (implicitly or explicitly using $M_0=1$ ).
Result derivation and root selection (2 pts):
Substitute $S_{T_1}=1$ to get $\phi(s) = 1/\lambda$ (or the corresponding form), and based on convergence/boundedness, select the correct value of $\lambda$ to match the answer given in the problem.

Total (max 7)

2. Zero-credit items

Merely copying the definitions or conditions from the problem statement.
Only writing general mathematical definitions (such as the definition of expectation or PGF) without performing any specific computation for this problem.
Claiming to use the "reflection principle" but failing to derive the specific distribution formula for $P(T_1=n)$ , and not performing the subsequent summation.
Giving the correct conclusion without any derivation process ("look-and-guess").

3. Deductions

Logical gap (Penalty -2): When setting up the equation, omitting the time cost factor $s$ for the first step, e.g., incorrectly writing $\phi = \frac{1}{2}s + \frac{1}{2}\phi^2$ (missing $s$ in the second term) or $\phi = \frac{1}{2} + \frac{1}{2}\phi^2$ (missing all $s$ factors), leading to an essentially incorrect equation.
Incorrect root determination (Penalty -1): In Step 4, retaining the plus-sign solution ( $\frac{1 + \sqrt{1-s^2}}{s}$ ) as part of the final answer without discarding it.
Variable confusion (Penalty -1): Confusing the random variable $T_1$ with its expectation/generating function value, e.g., writing $T_1 = \dots$ instead of $E[s^{T_1}] = \dots$ .
Computational error (Penalty -1): A simple algebraic sign error when solving the quadratic equation (e.g., writing the denominator incorrectly), leading to a slightly different final result.

Probability Theory – Problem 43: Prove that for