Let's break the problem into its components step by step and address the parts.

Part (i)

We are tasked to show that for $n > 1$, $P(T_0 = n) = P(T_1 = n-1).$

Approach:

The random walk $S_n = X_1 + X_2 + \dots + X_n$, where $X_i$ are independent with: $P(X_i = 1) = \frac{1}{2}, \quad P(X_i = -1) = \frac{1}{2}.$

1. Law of Total Probability: Using $X_1$, the first step, we can write: $P(T_0 = n) = P(X_1 = 1) P(T_0 = n | X_1 = 1) + P(X_1 = -1) P(T_0 = n | X_1 = -1).$

2. Conditions:

   • If $X_1 = 1$, $S_1 = 1$, which means $S_n$ will need to return to 0 in the remaining $n-1$ steps. Thus: $P(T_0 = n | X_1 = 1) = P(T_1 = n-1).$
   • If $X_1 = -1$, $S_1 = -1$, which makes it impossible for $S_n = 0$ in $n > 1$. So: $P(T_0 = n | X_1 = -1) = 0.$

3. Simplification: Substituting into the total probability: $P(T_0 = n) = P(X_1 = 1) P(T_1 = n-1) + P(X_1 = -1)(0).$ With $P(X_1 = 1) = \frac{1}{2}$: $P(T_0 = n) = \frac{1}{2} P(T_1 = n-1).$

Since $T_1$ also depends on symmetric random walks, we know $P(T_1 = n-1)$ implicitly absorbs the $\frac{1}{2}$ probability.

Part (ii)

We need to show that: $G_0(t) = t G_1(t).$

Generating Functions:

The generating function for $T_0$ is defined as: $G_0(t) = \sum_{n=1}^\infty P(T_0 = n) t^n.$

Similarly, for $T_1$: $G_1(t) = \sum_{n=1}^\infty P(T_1 = n) t^n.$

From part (i), we know: $P(T_0 = n) = P(T_1 = n-1), \quad n > 1.$

1. Express $G_0(t)$ Using $G_1(t)$: For $n > 1$, $G_0(t) = \sum_{n=1}^\infty P(T_0 = n) t^n.$ Using $P(T_0 = n) = P(T_1 = n-1)$ for $n > 1$: $G_0(t) = t \sum_{n=1}^\infty P(T_1 = n) t^n.$

2. Simplification: Recognizing the series for $G_1(t)$: $G_0(t) = t G_1(t).$

Part (iii)

We need the generating function for $T_a = \min \{ n > 1 : S_n = a \}$, where $a > 1$.

Generating Function $G_a(t)$:

For $T_a$, the random walk must reach $a$ for the first time at step $n$. This is equivalent to a generalization of $G_1(t)$, accounting for reaching $a$ instead of 1.

Using similar arguments and symmetry, we generalize $G_1(t)$ to $G_a(t)$. The recurrence relationship can be shown as: $G_a(t) = t G_{a-1}(t),$ with boundary conditions from the random walk's behavior.

Thus: $G_a(t) = t^a G_0(t).$

Summary:

• (i) $P(T_0 = n) = P(T_1 = n-1)$ using the law of total probability.
• (ii) $G_0(t) = t G_1(t)$ by substituting generating function definitions.
• (iii) $G_a(t) = t^a G_0(t)$, where $a > 1$, generalizes the behavior.

Would you like further details on any part of this derivation or related concepts? Here are some follow-up questions for exploration:

1. How does the symmetry of random walks affect these probabilities?
2. What are other applications of generating functions in probability?
3. Can you derive the explicit form of $G_0(t)$ in terms of $t$?
4. How do these probabilities relate to recurrence in Markov chains?
5. What changes if the probabilities for $X_i = \pm 1$ are unequal?

Tip: Generating functions are powerful tools for encoding sequences, especially in problems involving first-hitting times!