
Algebra PreAlgebra and Basic Algebra Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 24th, 2015, 11:09 PM  #1 
Member 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. Proof: 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 "n1" and "n+1" respectively, from which it has p(n1) and p(n+1) chance of returning respectively. So we have p(n) = (1/2)(p(n1) + 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)). Rearranging, 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 nonzero, 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 ba). 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. 

Tags 
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"...help  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 exerimentneed help finding "statistic" and "result"  katie0127  Advanced Statistics  0  December 3rd, 2008 02:54 PM 