[math-fun] Probability a biased random walk returns to start point
Consider a random walk on a D-dimensional cubic lattice (all nearest neighbors equally likely at next timestep). It is well known that if D<=2 the walk eventually returns to its startpoint with probability=1, while if D>=3 the return probabilities R obey 0<R<1. Now let us BIAS the random walk so that the expected motion after 1 step, is nonzero. (All 1-step probabilities independent identical and time- and space-independent.) In we still always walk only to nearest neighbors, then I claim that the return probability is always strictly below 1, in any dimension. Now if we permit walk-steps to go to NON-nearest neighbors, then it gets more interesting because probability distributions whose variances are infinite, or whose means are undefined, could be considered. For example, if in each dimension you walk to a Cauchy-distributed point centered at current location (fixed up so it is discrete not continuous...), then I claim the return probability R is 1 in 1 dimension but 0<R<1 in dimensions>=2. But I nevertheless claim that if the expected hop exists and is nonzero, then in any dimension the return probability is strictly below 1. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
The 1D version of the third paragraph is in Feller, vol. 1. On 2012-08-29, at 12:03 PM, Warren Smith wrote:
Consider a random walk on a D-dimensional cubic lattice (all nearest neighbors equally likely at next timestep). It is well known that if D<=2 the walk eventually returns to its startpoint with probability=1, while if D>=3 the return probabilities R obey 0<R<1.
Now let us BIAS the random walk so that the expected motion after 1 step, is nonzero. (All 1-step probabilities independent identical and time- and space-independent.)
In we still always walk only to nearest neighbors, then I claim that the return probability is always strictly below 1, in any dimension.
Now if we permit walk-steps to go to NON-nearest neighbors, then it gets more interesting because probability distributions whose variances are infinite, or whose means are undefined, could be considered. For example, if in each dimension you walk to a Cauchy-distributed point centered at current location (fixed up so it is discrete not continuous...), then I claim the return probability R is 1 in 1 dimension but 0<R<1 in dimensions>=2.
But I nevertheless claim that if the expected hop exists and is nonzero, then in any dimension the return probability is strictly below 1.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Dan Asimov -
Warren Smith