# A random walk with uniformly distributed steps II

The problem is a improved version of this problem, A random walk with uniformly distributed steps

Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will "walk" on the real axis randomly. For every step of the "walk", it will choose a real number $\Delta x$ in interval $[l,r]$ equiprobably, and turn right and move $\Delta x$ unit. Once it move to the left side of the point $O$, it will "die" immediately.

Our task is find out the probability of the point "live" after n steps of "walk" $P_n$. I have tried to solve it and found out a method to count $P_n$ with $\Theta (n^5)$ of time complexity, using fourier transform and something in complex analysis. But is there a more simple method? Or is there one which needs lower time complexity?

• Can you describe your method? What are the first few $P_n$ when, say, $l=1$ and $r=2$ (or the other way around)? – Johan Wästlund Apr 20 '12 at 7:31
• How do you wind up with a nice polynomial complexity using a fourier transform? $\hspace{1.2 in}$ I've always seen fourier transforms contribute log factors. $\;$ – user5810 Apr 20 '12 at 9:18