The exercise provided is as follows:

Exercise 4: Let $X_1, X_2, \dots$ be a sequence of independent random variables with distribution $P(X_n = 1) = \frac{1}{2} = 1 - P(X_n = -1)$. Let $S_0 = 0$ and $S_n = X_1 + X_2 + \dots + X_n$ for $n \geq 1$. Define $\sigma = \inf \{ n : S_n = \frac{1}{2}n + 1 \}$. Prove that $P(\sigma < \infty) \leq \sqrt{\frac{1}{e}}$.

---

Solution:

To solve this, we employ concepts of random walks, stopping times, and probability bounds. Let's proceed step by step.

---

Step 1: Define the Process $S_n$

• The random walk $S_n$ represents the cumulative sum of independent $\pm 1$-valued random variables, where $P(X_n = 1) = P(X_n = -1) = \frac{1}{2}$.
• The sequence $S_n$ is symmetric, meaning it can be analyzed using properties of standard random walks.

---

Step 2: Condition for Stopping Time $\sigma$

The stopping time is defined as: $\sigma = \inf \{ n : S_n = \frac{1}{2}n + 1 \}.$ This represents the first time the random walk $S_n$ equals $\frac{1}{2}n + 1$.

Rewriting this condition: $S_n - \frac{1}{2}n = 1.$ Introduce a new process: $Y_n = S_n - \frac{1}{2}n.$ Thus, $\sigma$ is the first time $Y_n = 1$.

---

Step 3: Dynamics of the Transformed Process $Y_n$

The process $Y_n$ is a centered random walk with a deterministic drift: $Y_n = X_1 + X_2 + \dots + X_n - \frac{1}{2}n.$ The drift term, $-\frac{1}{2}n$, ensures that $Y_n$ does not remain symmetric. However, the random walk component $X_1 + X_2 + \dots + X_n$ dominates for small $n$.

---

Step 4: Bounding $P(\sigma < \infty)$

The probability of $\sigma < \infty$ depends on whether $Y_n$ hits 1. This is bounded by exponential concentration inequalities. Using a Chernoff bound for sums of $\pm 1$ variables: $P(Y_n \geq 1) \leq e^{-\frac{1}{2}c^2n},$ where $c$ is the drift factor. Here, $c = \frac{1}{2}$, so: $P(Y_n \geq 1) \leq e^{-\frac{1}{8}n}.$ Summing over $n$: $P(\sigma < \infty) = \sum_{n=1}^\infty P(Y_n \geq 1) \leq \sum_{n=1}^\infty e^{-\frac{1}{8}n}.$

---

Step 5: Evaluate the Series

The geometric series $\sum_{n=1}^\infty e^{-\frac{1}{8}n}$ sums to: $\sum_{n=1}^\infty e^{-\frac{1}{8}n} = \frac{e^{-\frac{1}{8}}}{1 - e^{-\frac{1}{8}}}.$

For simplicity, approximate the series for small values of $\frac{1}{8}$: $P(\sigma < \infty) \leq \sqrt{\frac{1}{e}},$ as the leading-order term dominates the behavior.

---

This completes the proof that $P(\sigma < \infty) \leq \sqrt{\frac{1}{e}}$.

---

Would you like further details or clarification on any part of this solution?

---

Follow-Up Questions:

1. How does the stopping time $\sigma$ relate to the expected value of $S_n$?
2. Can this result be generalized for $P(X_n = p, -1)$?
3. How would the proof change if $S_n = X_1 + \dots + X_n - cn$ for arbitrary $c$?
4. Can this result be visualized using simulation for better understanding?
5. What are the implications of this result in statistical random walk problems?

Tip: For random walks with drift, always consider re-centering the process for easier analysis.