Let with . Define with . Let . Prove that .

Stochastic Processes Solution – Problem 29: Prove that

Question

Let $\xi_1, \ldots, \xi_n \overset{\mathrm{iid}}{\sim} \xi$ with $\mathbb{P}(\xi=-1)=\mathbb{P}(\xi=1)=\frac{1}{2}$ . Define $S_n = S_0 + \sum_{i=1}^{n} \xi_i$ with $S_0 = 0$ . Let $T_1 = \min\{n : S_n = 1\}$ . Prove that $\mathbb{E}[s^{T_1}] = \frac{1 - \sqrt{1-s^2}}{s}$ .

Step-by-step solution

Step 1. Define the generating function and analyze the first-step decomposition. Let $G(s) = \mathbb{E}[s^{T_1}]$ (generating function, domain $|s| \le 1$ ), where $T_1 \ge 1$ is the first hitting time of 1. Decompose $T_1$ by conditioning on the first increment $\xi_1$ : - If $\xi_1 = 1$ , then $S_1 = 1$ , $T_1 = 1$ , contributing $\frac{1}{2}s$ . - If $\xi_1 = -1$ , then $S_1 = -1$ . By symmetry, the time from $-1$ to return to $0$ has the same distribution as $T_1$ , and then from $0$ to reach $1$ is another independent copy $T_1'$ . So the total time is $1 + T_{-1 \to 0} + T_1'$ , with $T_{-1 \to 0}$ and $T_1'$ independent and each distributed as $T_1$ .

Step 2. Establish the functional equation for the generating function. By the product property of generating functions for independent sums: $\mathbb{E}[s^{T_{-1 \to 0} + T_1'}] = G(s)^2$ . The second case contributes $\frac{1}{2}s \cdot G(s)^2$ . Combining: $G(s) = \frac{1}{2}s + \frac{1}{2}s G(s)^2.$

Step 3. Solve the quadratic equation and select the valid root. $sG(s)^2 - 2G(s) + s = 0$ . By the quadratic formula ( $a=s, b=-2, c=s$ ): $G(s) = \frac{1 \pm \sqrt{1 - s^2}}{s}.$ Select the root using boundary behavior: as $s \to 0^+$ , $T_1 \ge 1$ so $s^{T_1} \to 0$ , hence $G(s) \to 0$ . - Positive sign: $\frac{1 + \sqrt{1-s^2}}{s} \to +\infty$ , invalid. - Negative sign: $\frac{1 - \sqrt{1-s^2}}{s} \approx \frac{s^2/2}{s} = s/2 \to 0$ , valid.

Step 4. Verify existence of the generating function. Since the symmetric random walk is recurrent, $\mathbb{P}(T_1 < \infty) = 1$ , and for $|s| \le 1$ , $|s^{T_1}| \le 1$ . By dominated convergence, $G(s)$ is finite and continuous, confirming the selected root.

Final answer

QED.

Marking scheme

The following is the grading rubric. Based on the official solution (first-step analysis), but also allowing a valid combinatorial/series approach.

1. Checkpoints (max 7 pts total)

Score exactly one chain (Chain A is expected / Chain B is alternate).

Chain A: First Step Analysis

State decomposition and probability analysis (3 pts)
Correctly write the contribution from $\xi_1=1$ : $\frac{1}{2}s$ . [1 pt]
Analyze the $\xi_1=-1$ case: identify the two phases $-1 \to 0$ and $0 \to 1$ . [1 pt]
Key step: Use homogeneity and independence to show the time from $-1$ to $1$ equals the sum of two independent copies of $T_1$ , giving contribution $\frac{1}{2}s G(s)^2$ . [1 pt]
Establish the functional equation (1 pt)
Write $G(s) = \frac{1}{2}s + \frac{1}{2}s G(s)^2$ (or equivalently $sG^2 - 2G + s = 0$ ). [1 pt]
Algebraic solution (1 pt)
Solve via the quadratic formula to get $G(s) = \frac{1 \pm \sqrt{1-s^2}}{s}$ . [1 pt]
Root selection and boundary verification (2 pts)
Core logic: State that the generating function properties (e.g., $G(s) \to 0$ as $s \to 0$ ) determine the sign. [1 pt]
Correctly verify the negative-sign root satisfies the condition and the positive-sign root does not. [1 pt]
*Note: If only "discard the positive root" is stated without any reason, this section gets 0 pts.*

Chain B: Combinatorics/Series Summation

Distribution derivation (3 pts): Use the reflection principle or combinatorial methods to derive $P(T_1=n)$ (typically involving Catalan number forms). [3 pts]
Series construction (1 pt): Write $G(s) = \sum P(T_1=n) s^n$ and substitute. [1 pt]
Series summation (3 pts): Use the generalized binomial theorem ( $\sqrt{1-x}$ Taylor expansion) to compute the sum and derive the target formula. [3 pts]

Total (max 7)

2. Zero-credit items

Only copying known conditions, definitions, or the final conclusion without derivation.
Not establishing the functional equation or series, directly claiming $G(s)$ satisfies the formula.
Using $s=1$ to select the root ( $s=1$ gives $(G-1)^2=0$ , both roots coincide at 1, so this cannot distinguish them; this is a logical error).

3. Deductions

Missing root selection or wrong reason: Solving both roots then circling the correct answer without any selection justification. (-2 pts)
Logical gap: In Chain A, not mentioning " $-1 \to 1$ equals two independent identically distributed processes" and directly writing $G^2$ . (-1 pt)
Sign error: Coefficient sign error in the quadratic but subsequent logic correct. (-1 pt)

Stochastic Processes – Problem 29: Prove that