MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.