Wikipedia:Reference desk/Archives/Mathematics/2019 November 28

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 28

What is the average number of steps in a 2 dimensional random walk before you hit the origin again?

This seems like an easy question because the chances are very high of returning immediately to the origin. However, once the random walk moves a bit away from the origin it might take incredible number of steps to return again.

So taking into account those cases, too, what is the total number of average steps before hitting the origin again? — Preceding unsigned comment added by 37.76.19.40 (talk) 20:43, 28 November 2019 (UTC)

Even for a one-dimensional, symmetric random walk, the expected return time is infinite, so it will be for a two-dimensional walk too, even though both are recurrent (return to the origin with probability 1). –Deacon Vorbis (carbon • videos) 21:19, 28 November 2019 (UTC)

can you prove it for me? I'm surprised by that answer. — Preceding unsigned comment added by 37.76.5.129 (talk) 22:06, 28 November 2019 (UTC)

If we let X denote the random variable denoting the number of steps to reach the origin for the first time again after the initial state (one-dimensional here), then it can be shown that $P(X=2n)=2C_{n-1}(1/2)^{2n},$ where $C_{n}$ is the nth Catalan number. The generating function for the Catalan numbers is:

$C_{0}+C_{1}x+C_{2}x^{2}+\cdots ={\frac {1-{\sqrt {1-4x}}}{2x}}.$

Then the probability of recurrence is

$2C_{0}(1/2)^{2}+2C_{1}(1/2)^{4}+2C_{2}(1/2)^{6}+\cdots ,$

From the generating function, we can show

$f(x)=2C_{0}x^{2}+2C_{1}x^{4}+2C_{2}x^{6}+\cdots =1-{\sqrt {1-4x^{2}}}.$

Then the probability of recurrencce is $f(1/2)=1.$ Next,

$xf'(x)=(2)(2C_{0}x^{2})+(4)(2C_{1}x^{4})+(6)(2C_{2}x^{6})+\cdots ={\frac {4x^{2}}{\sqrt {1-4x^{2}}}}.$

Plugging in $x=1/2$ is precisely the expected value of X, but this series diverges here (which you can see by directly plugging into the formula for the sum, or by using some series tests, more rigorously. This doesn't prove recurrence for the 2-D case, but it does show that if it is recurrent, then the expected recurrence time is infinite. I don't know any elementary proofs of recurrence in 2-D, but I suspect it can be done. As a side note, in three dimensions and higher, random walks are no longer recurrent. –Deacon Vorbis (carbon • videos) 22:34, 28 November 2019 (UTC)

This last result in known as Pólya’s Theorem; I don't think we have an article on but Googling "Pólya’s Theorem Random Walk" turns up some relevant sources on-line. (Btw, do we really not have an article? Seems to me it meets notability criteria.) --RDBury (talk) 01:48, 29 November 2019 (UTC)

thanks a lot (though I had a bit of trouble following the math). I am really shocked you said that in 3 dimensions it isn't recurrent (which you defined in your first comment as meaning it returns to origin with probability 1.) Can't we show it is probability 1 like this: at any point regardless of distance you could go straight to the origin by the shortest path. So the only way not to *ever* return is to take an infinite series of bets that you will not next proceed straight back to the origin, and lose all of them. Surely the chance of losing all of an infinite number of nonzero chances can't be exactly 0. How can an infinite sum of small positive reals become exactly 0? Maybe I am misinterpreting, and you could somehow show me in a more intuitive way why in 3 dimensions it is not recurrent. (It is possible my thinking in this paragraph isn't too rigorous, so if it doesn't make sense, don't try too hard to figure it out :).) — Preceding unsigned comment added by 37.76.100.215 (talk) 01:45, 29 November 2019 (UTC)

Non-recurrence doesn't mean the probability of returning to the origin is 0; it means the probability is less than 1. This probability can be stated as an infinite sum of positive reals (although it takes a bit more care than how you set it up), and this sum has a value strictly between 0 and 1 (in the case of 3 dimensions or higher).--163.47.115.82 (talk) 04:06, 29 November 2019 (UTC)

all right! Thanks. — Preceding unsigned comment added by 37.76.115.13 (talk) 04:58, 29 November 2019 (UTC)

One last extra info that I figured out while playing around with this for anyone who's interested: for the 1-D case, not only is $E(X)$ infinite, but so is $E({\sqrt {X}}).$ However, $E(X^{\alpha })$ will at least be finite for $\alpha <1/2.$ On the other hand, the 2-D case is worse: if you can believe the asymptotic formula given in OEIS: A054474 (and that I didn't misread it or mangle the computation), $E(X^{\alpha })$ doesn't exist for any positive $\alpha$ at all! Worse yet, even $E(\log X)$ is infinite, which is pretty horrendous. However, $E((\log X)^{\alpha })$ will at least be finite for $\alpha <1.$ –Deacon Vorbis (carbon • videos) 05:05, 29 November 2019 (UTC)

Shizuo Kakutani famously said of the 3-D case, "A drunk man will find his way home, but a drunk bird may get lost forever." [1] has a description but pasting that phrase into a search engine finds many more articles about the topic. 67.164.113.165 (talk) 08:10, 29 November 2019 (UTC)