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

 Algebra Pre-Algebra and Basic Algebra Math Forum

 December 24th, 2015, 10: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 "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)). 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 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 10:43 PM.

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

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post gelatine1 Math Books 1 April 14th, 2015 10:22 PM skynet Probability and Statistics 1 June 18th, 2014 12:26 PM SedaKhold Calculus 0 February 13th, 2012 11:45 AM Eureka Number Theory 6 January 29th, 2012 02:28 AM katie0127 Advanced Statistics 0 December 3rd, 2008 01:54 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top