Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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. $\;$ –  Ricky Demer Apr 20 '12 at 9:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.