Wikipedia:Reference desk/Archives/Mathematics/2019 May 23

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.

May 23

How to find the stationary distribution of a random walk on real numbers?

Start at the point $(1/2,1/2)$. At each time step, choose a point uniformly at random from $(0,0),(0,1),(1,0),(1,1),(1/2,1/2)$, and then move half way from the current position to the chosen point.

In other words, at each time step transition from $(x,y)$ to one of ${(x/2,y/2),(x/2,(y+1)/2),((x+1)/2,y/2),((x+1)/2,(y+1)/2),((x+1/2)/2,(y+1/2)/2)}$.

After $n$ time steps measure the distance from the starting position.

What is the distribution of distances as $n\rightarrow \infty$? What is the expected distance?

I understand how to find stationary distributions for finite Markov chains, but this is a bit beyond me. What topics would be needed to answer this, or is there a general approach to answer questions of this form? 98.190.129.147 (talk) 23:41, 23 May 2019 (UTC)

What you're describing is similar to the chaos game. There are several closely related examples there, but not quite the one you're describing exactly. I suspect it might be worth it to just write a program to see if there's anything interesting as a result (often you get something self-similar from such a process). I'm not sure how to analyze a description like that systematically, but there might be some better refs at that article. –Deacon Vorbis (carbon • videos) 00:24, 25 May 2019 (UTC)

I did a plot of the cumulative distribution function for the x-variable alone; it's not that hard to compute for values of the form p/2ⁿ where n is small. Judging from the roughish appearance of the graph the cdf is fractal in nature, something like a smoothed version of the Cantor function. It would follow that the distribution has no density function in the normal sense. The average position is obviously (1/2, 1/2), and from that the average displacement is 0, but the average distance is a more difficult calculation even you just look at horizontal or vertical distance. Given a closed form for the distribution is unlikely, I think your best bet is to use a Monte Carlo method to get an estimate for something like the average distance. --RDBury (talk) 13:37, 25 May 2019 (UTC)