# Simple Random Walk Property

Define $$S_n = \Sigma_{i=0}^n X_n$$, where $$X_n = \pm1$$ with probability $$1/2$$ for each case.

I am trying to show that for a walk of length $$2n -2k$$ starting at $$0$$, the probability that it does not hit $$0$$ at all (except its start point) is the same as the probability that it ends at $$0$$.

Formally, I am trying to show that $$P(S_1, S_2, ...S_{2n-2k}\neq 0) = P(S_{2n-2k} = 0).$$

I have a "hand-wavy" proof. Call the set of walks of length $$2n-2k$$ that do not revisit zero $$G$$, and the set of walks that end at zero $$H$$. We can form a bijection $$G \rightarrow H$$ by taking a walk in $$G$$ and reflecting it across the horizontal line $$y=S_{0.5(2n-2k)} = S_{n-k}$$, since doing so will guarantee that such walk ends at $$0$$. Since such bijection exists, the probabilities that members of these sets occur must be equal.

First of all, is this logic correct, and secondly, is there a way to make this more formal?

• Proving that the function you describe really is a bijection is a good start! – Greg Martin Mar 11 at 22:22
• Is $X_n = \pm 1$ with probability $1/2$ each, or $0$ or $1$ with probability $1/2$ each? – Brian Tung Mar 11 at 22:23
• It's the first. I've made the appropriate edit in the question. – lithium123 Mar 12 at 1:55