Generating Functions of 1D Random Walk

Question

Define $\displaystyle F(s) = \sum_{n=0}^\infty f_ns^n$, where $f_n= P($ the first return to the origin at time $n)$. Suppose $F^{(n)}(s) = \displaystyle \sum_{k=0}^\infty f_k^{(n)} s^k$, where $f_k^{(n)}$ denotes the probability of the $n$th return to the origin at time $k$, prove that $F^{(n)}(s)=[F(s)]^n$

We defined the notation $F^{(n)}$ as $F$ composed with itself $n$ times.

Here are some results that I have proved that may or may not be helpful (not in order):

1. Let $u_n = P ($the walk returns to the origin at time $ n)$ and $U(s), s \in [0,1)$ be the generating function corresponding to $u_n$. Then $U(s) = (1-s^2)^{-\frac{1}{2}}$

2. For any $n \in \mathbb{N}$, we have ${{2n \choose n} \cdot (\frac{1}{2})^{2n}} = (-1)^n {-\frac{1}{2} \choose n}$

3. $U(s) = \frac{1}{1-F(s)}=1- \frac{1}{F(s)}$

4. If the random walk is asymmetric with forward probability $p$ and backward probability $q$ and $p+q=1$, then the probability of a return to the origin in finite time is $1-|p-q|$.

5. $F'(1)=\infty$ when $p=q=\frac{1}{2}$. That is, the expected waiting time until the first return to the origin is infinite.

Answer 1

Without using facts about generating functions (since it wasn't covered in 251).

$$ \textbf{Base case: n=1} $$

This follows directly from definition. So assume the proposition is true for n.

$$ \textbf{Induction step: n+1} $$

First note that the probability of the $n+1$th return to the origin at time $k$ is equal to the probability of first return to the origin at time $k-2$ times the probability of $n$th return to the origin at time $2$, and so on. In other words,

$$ f_k^{(n+1)} = \sum_{i=0}^{k} f_i^{(n)}f_{k-i} $$

Therefore,

$$ \begin{aligned} F^{(n+1)}(s) &= \sum_{k=0}^{\infty} f_k^{(n+1)}s^k \\ &= \sum_{k=0}^{\infty}\sum_{i=0}^{k}f_i^{(n)}f_{k-i} s^k \\ &= \sum_{i=0}^{\infty}\sum_{k=i}^{\infty}f_i^{(n)}f_{k-i} s^k \\ &= \sum_{i=0}^{\infty} f_i^{(n)}s^i\sum_{k=0}^{\infty} f_k s^{k} \\ &= \left[F(s)\right]^{n}\left[F(s)\right] \end{aligned} $$

By induction, we prove that our proposition is true for all $n+1\in \mathbb{N}$ given that it is true for $n$.

Useful tips:

For changing the order of summation, it is often useful to first set it up as an inequality, e.g. for the above example, we notice that:

$0\leq i\leq k\leq \infty$.

That means we can split it up into:

$0\leq i\leq k$ and $i\leq k\leq \infty$

but also

$0\leq i\leq \infty$ and $i\leq k\leq \infty$

which still fully describes the relationship between the 4 numbers.

Let me know if there are any issues or errors with this answer.

Answer 2

If $T_1,T_2,...$ are return times to the origin then (it is well known that) $T_1,T_2-T_1,...,T_{n+1}-T_n,...$ are independent and identically distributed. The sum of the first $n$ of these i.i.d. random variables is $T_n$. Now use the following basic fact:

If $U$ and $V$ are independent then the generating function of $U+V$ is the product of the generating functions of $U$ and $V$.