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?

Improve this question
$\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$
    – Johan Wästlund
    Commented 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
    Commented Apr 20, 2012 at 9:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .