My Math Forum  

Go Back   My Math Forum > High School Math Forum > Algebra

Algebra Pre-Algebra and Basic Algebra Math Forum

LinkBack Thread Tools Display Modes
December 24th, 2015, 11:09 PM   #1
Joined: Nov 2012

Posts: 55
Thanks: 0

Elementary proof of the 1D simple random walk "infinite crossing" theorem

There's a famous result that says a 1 dimensional simple random walk on Z with p = q = 1/2 will cross every point an infinite number of times. I came up with a very elementary proof, but I'm not sure if it's rigorous enough. Could I get some critique? I feel I'm missing something important that could make it fully rigorous.

Here is the proof:

Lemma 1: The random walk starting from the space 0 returns to 0 with probability 1.


Let p(n), for n = 1 ,2 ,3,... be the probability that the walk eventually crosses the origin, 0 from the space |n| (this is the modulus function. We make no distinction between the space -n and n since the probability of returning to 0 from both is the same.)

From the space n, it has probability 1/2 of moving to the space "n-1" and "n+1" respectively, from which it has p(n-1) and p(n+1) chance of returning respectively. So we have

p(n) = (1/2)(p(n-1) + p(n+1)), for n = 2, 3, 4, ... or

p(n+2) = 2p(n+1) - p(n) for n = 1, 2, 3, ... [after rearranging and shifting the index] (eq 1)

Now, note that we have a special case for p(1). From the space "1", it has probability 1/2 of returning to the origin, and probability 1/2 of moving to space "2". So we have

p(1) = (1/2)(1 + p(2)).


p(2) = 2p(1) - 1 - (eq 2)

We claim that p(1) = 1, and indeed all the p(n) are equal to 1 and hence the walk always returns to "0". We prove this by contradiction.

Assume p(1) =/= 1. Then since probabilities are between 1 and 0, we can write p(1) = 1 - x, for some x, 0 < x =< 1.

It can be proven from eq 1 and 2 by induction that

p(n) = 1 - nx for n = 1, 2, 3, ...

But then our probabilities would eventually reach zero or a negative number, both of which are contradictions. (to see that the probabilities are all non-zero, note that the sequence of n steps left brings the walk back to the origin with probability 2^-n > 0.)

So p(1) = 1, and from eq 1 all the p(n) are also 1, as was to be shown.

Corollary: The walk crosses the origin an infinite number of times

Our lemma guarantees it will return once, at which point the walk starts again from "0", so our lemma applies again and again, and as such it crosses the origin an infinite number of times, since the walk is infinite.

Proof of the main theorem:

To extend the proof to all arbitrary points, note that from any point "b", the probability it eventually crosses another arbitrary point "a" is p(|b - a|). (think of it as shifting the origin to a, so the point b in relation to the new origin is now |b-a|). This is 1 from our previous lemma, since |b - a| is just p(n) for some n.

Since the walk is guarenteed to return to "a" from any other point, the same logic as in the corollary applies, and it crosses any arbitrary point "a" an infinite number of times.

Last edited by Bromster; December 24th, 2015 at 11:43 PM.
Bromster is offline  

  My Math Forum > High School Math Forum > Algebra

elementary, infinite crossing, proof, random, simple, theorem, walk

Thread Tools
Display Modes

Similar Threads
Thread Thread Starter Forum Replies Last Post
Euler's book "Introduction to Analysis of the Infinite" gelatine1 Math Books 1 April 14th, 2015 11:22 PM
how "random" are online "random" spinners? skynet Probability and Statistics 1 June 18th, 2014 01:26 PM
A "simple" application of dirac delta "shift theorem" SedaKhold Calculus 0 February 13th, 2012 12:45 PM
Conjecture on "proof on proofs" for infinite cases Eureka Number Theory 6 January 29th, 2012 03:28 AM
sample exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 02:54 PM

Copyright © 2019 My Math Forum. All rights reserved.