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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.