From: Dennis Paul Himes Subject: Re: Random Walks... Date: Mon, 04 Oct 1999 13:45:34 -0400 Newsgroups: sci.math Keywords: Different types of random walks on Z^n Chas F Brown apparently wrote (although I missed the original post): > > This is bugging me... > > Consider two types of random walks in an N dimensional space, starting > at the origin: > > A) For each "step", for *each* dimension, flip a coin; heads means move > +1 in that dimension, tails means move -1 in that dimension. > > B) For each "step", randomly select *one* dimension; flip a coin; heads > means move +1 in that dimension, tails means move -1 in that dimension. > > For N = 1, the probabilty that we will return to the origin at least > once after t steps approaches 1.0 for both A and B. > > What about for N > 1? Is it the same in each case for scenarios A and B? For N = 2 the two cases are isomophic, with (x,y) in case B mapping to (x+y,x-y) in case A. A move of +-(1,0) maps to +-(1,1) and a move of +-(0,1) maps to +-(1,-1). I don't think this generalizes to higher dimensions. ------------------------------------------------------------------------------ Dennis Paul Himes <> dennis@sculptware.com http://www.connix.com/~dennis/dennis.htm Disclaimer: "True, I talk of dreams; which are the children of an idle brain, begot of nothing but vain fantasy; which is as thin of substance as the air." - Romeo & Juliet, Act I Scene iv Verse 96-99 ============================================================================== From: hrubin@odds.stat.purdue.edu (Herman Rubin) Subject: Re: Random Walks... Date: 3 Oct 1999 11:28:34 -0500 Newsgroups: sci.math In article , Jo Sir wrote: >Chas F Brown a crit dans le message : >37F5159D.5CCFCD2F@batnet.com... >: This is bugging me... >: Consider two types of random walks in an N dimensional space, starting >: at the origin: >: A) For each "step", for *each* dimension, flip a coin; heads means move >: +1 in that dimension, tails means move -1 in that dimension. >: B) For each "step", randomly select *one* dimension; flip a coin; heads >: means move +1 in that dimension, tails means move -1 in that dimension. >: For N = 1, the probabilty that we will return to the origin at least >: once after t steps approaches 1.0 for both A and B. >: What about for N > 1? Is it the same in each case for scenarios A and B? >: It looks to me like in case A the probability always approaches 1.0 - is >: that correct? >Scenario B is the one which is commonly referred to as a multidimensional >random walk. I know that for n >= 3, all states in this Markov chain are >transient, whence the probability that the "random walker" will ever return >to the origin is not 1. For n = 2, the states of the chain are recurrent, so >the "random walker" will eventually return to the origin with probability 1. This is correct. >Scenario A is different as it is a combination of n independent linear >random walks and not a "true" n-dimensional random walk. In this case, all >states in the chain are recurrent (if my fast calculations are right...) >whence the "random walker" will eventually return to the origin with >probability 1. This is NOT correct. It would be if the random walk is ergodic, but fails for null recurrent. A null recurrent Markov process is one in which the probability p_i of return at time i approaches 0, but the sum is infinite. In both cases, p_i is O(i^{-n/2}), so n <= 2 is the necessary and sufficient condition for recurrence. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399 hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558