In the proof that symmetric random walks end up regressing to the origin with probability $1$, I have found this didactic post on-line, where the power series of the probability mass function of the first pass through zero is expressed in closed form, and evaluated at $x=1$:

Manipulating $F(x)$ gives us more insights. First, setting $x= 1$ we see that

$\large F(1)=\displaystyle \sum_{n=1}^\infty f_n= 1 - \sqrt{1-4pq}=1-\color{red}{|p-q|}$

The sum of all the $f_n$ is simply the probability that the random walk ever returns to the origin. Thus, with probability $|p-q|$, the walk will never return to the origin.

The question is, where does $|p-q|$ come from? And why is $x$ actualized to $1$, when the $x$ "variable" in generating functions is often compared to just a clothesline to aid in counting?

  • $\begingroup$ Since $p+q=1$ therefore $\sqrt{1-4p}=\sqrt{(p+q)^2-4pq}=\sqrt{p^2+q^2-2pq}=\sqrt{|p-q|^2}=|p-q|$. $\endgroup$ Apr 5 '20 at 12:01

For the first question, since $p+q=1$ it follows that $$ (p-q)^2=p^2-2pq+q^2=p(1-q)-2pq+q(1-p)=p+q-4pq=1-4pq $$ Therefore taking a square root yields $\sqrt{1-4pq}=|p-q|$.

For the second question, while generating functions can be regarded as formal power series, they can also be viewed as defining an analytic function in some neighborhood of zero. There is then no problem with evaluating the function in this neighborhood. A probability generating function for a random variable $X$ taking values in $\mathbb{N}\cup\{0,\infty\}$ will always converge at $x=1$ because the sum is just $\mathbb{P}(X<\infty)$.

  • $\begingroup$ Out of burning curiosity... The derivation at the top... Is it part of what could be considered mathematical culture, or you had to think about it? $\endgroup$ Jul 6 '16 at 12:19
  • 1
    $\begingroup$ I had to think about it the first time I saw it, but since then I've remembered the trick. $\endgroup$ Jul 6 '16 at 15:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.