# Simple Random Walks

I am having trouble understanding the proof of the first return identity. \bigskip

Let $f_n = {{P(S_1 \neq0, S_2 \neq0,...,S_{(n-1)} \neq 0, S_n = 0)}}$, i.e the probability that the simple random walk first returns back to the origin at step $n.$ \bigskip

Let $U_n = P(S_n = 0)$. Then the first return identity states that $$U_n = \sum_{k=0}^{n}{f_{k}U_{n-k}}$$ \bigskip

Now the proof goes like this; Define $A_n = {\{S_n = 0}\}, B_k = {{P(S_1 \neq0, S_2 \neq0,...,S_{(k-1)} \neq 0, S_k = 0)}}.$ \medskip

Then $A_n = \bigcup \limits_{k=1}^{n}{A_{n}\cap B_{k}}$, and since the events are disjoint we can calculate the probabilities by summing, then the rest of the proof is pretty easy to follow. But I don't understand how we can partition $A_n$ in this way. Isn't $A_n \cap B_k = A_n \cap B_n?$ \bigskip

I also do not understand the proof of the recurrence probability, which is the probability that the SRW returns to the origin at some point $n$, i.e the event ${\{S_n = 0 , n \geq 1}\}$, the proof then states that this event is equal to the following; $\bigcup\limits_{n=1}^{\infty}${first return to 0 occurs at step n}, and I also don't understand this.

Any help would be appreciated.

Probably in the proof $B_k$ refers to the event of first return at step $k$, not the probability of the event.

For your first point: If you say that $A_n \cap B_k = A_n\cap B_n$ what you are saying is that the walk returns to zero for the first time at step $k$ and ends up at zero at step $n$, if and only if the walk returns to zero for the first time at step $n$ (and per force is zero at step $n$). You can easily see that there are at least some possibilities of returning to zero before step $n$ ($k<n$) and somehow returning to zero again at step $n$. So the answer to your "isn't" question is no.

As to your second question, let's translate it into English:

The probability that the walk ever returns to zero is the sum over possible times of first return of the probabilities that the first return is at that time.

For this to be true, two things must be verified:

(1) If the walk ever returns to zero, there must be a first time it returns to zero.

(2) The events "walk's first return to zero happens at time at time $k$" and "walk's first return to zero happens at time at time $j$" are mutually exclusive for $j\neq k$.

The first statement is obvious.

The second is clear if you realize that once the walk returns to zero for the first time (if it does), it is no longer possible for the first return to occur at any later time.