1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Can you describe your method? What are the first few $P_n$ when, say, $l=1$ and $r=2$ (or the other way around)? $\endgroup$ Apr 20, 2012 at 7:31
  • $\begingroup$ 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. $\;$ $\endgroup$
    – user5810
    Apr 20, 2012 at 9:18

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.