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

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, if the particle would otherwise move left of the origin, the particle is set back at the origin before the next step.

Given $r$, can a closed expression be derived for the probability $P_{n,r}$ of the particle being at the origin after step $n$? Can an expression be derived for the centered variance $E_{n,r}(X^2)$?

This is a variation of a problem featured here, where instead of the particle "dying" upon crossing the origin it is simply set at the origin and allowed to continue. Also, I am asking about the probability of it simply being at the origin at the $n$th step, not whether it has at some point been there.

Being only a graduate, all I've managed to do is conjecture what the expression might be for particular cases. Inspired by the excellent answers to the original problem, I directly simulated the problem to find the probabilities and presumed they were given by a rational expression $\frac{N_r(n)}{(1+r)^n n!}$. Surprisingly, my results indicated that the numerator was likely an integer in these cases. My conjectures as to the numerator for those particular cases are:

  • $r=0$: $N_0(n)=n!$ (Known precisely, since $P_{n,0} = 1$ for all $n$)
  • $r=1$: $N_1(n) = (2n-1)!!$
  • $r\rightarrow\infty$: $N_r(n)\rightarrow (n+1)^{n-1}$

Edit: The conjecture for the case when $r$ gets arbitrarily large has been changed. There was a typo. (I was considering its similarity to Cayley's Formula and typed that out instead!)

At this point I'm lost. Your consideration is appreciated.

Update: I've managed to derive a stronger conjecture for the expression for the "re-center" probability:

$$P_{n,r}=\left(\frac{a}{c}\right)^n\frac{\Gamma(1+\frac{d}{a}) \Gamma(1+\frac{b}{a}+n)}{\Gamma(1+\frac{b}{a}) \Gamma(1+\frac{d}{c}+n)}$$

I have made no progress in determining the dependence of the four variables $a$, $b$, $c$, $d$ on the parameter $r$, except in the obvious cases when $r=0$ and $r=1$. If this expression suggests any accessible combinatorial argument I'd be happy to hear it.

Second Update: I have a closed form conjecture for the "re-center" probability when $r \geq 1$:

$$P_{n,r}=\frac{\left(\frac{3r}{1+r}\right)_{n-1}}{(1+r)\left(2r\right)_{n-1}}, r\geq 1$$

This expression uses the rising Pochhammer symbol. It appears to fail for $r<1$ for whatever reason.

share|improve this question
A comment: your construction, where moves beyond the origin go to the origin instead, is not the same as conditioning the particle to stay non-negative. –  Nate Eldredge Jun 22 '13 at 11:39
I'm not sure what the difference is if this a discrete-time process, but I removed that statement all the same to avoid any confusion there might be. –  Nick Broderick Jun 22 '13 at 12:49
One way to think about the difference is through simulation. To get your process (which is a type of "reflected" process), just generate the steps and push the walk up to 0 every time it goes negative. To get a sample of the process conditioned to stay non-negative, you generate the steps, but if the walk goes negative, you throw away that whole run, and start over again. (This may be an inefficient way to sample but it may be a helpful way to think about it). If you the difference still isn't clear, you could even generate some samples for, say, r=1/2 and n=40 - they look quite different! –  James Martin Jun 22 '13 at 17:26
I see. I didn't realize the phrase "conditioned" carried that connotation. I definitely understand and appreciate the difference! Thank you. It's just as well I removed that phrasing, then. –  Nick Broderick Jun 22 '13 at 17:46
There doesn't seem to be a lot of activity surrounding this question -- no references offered, suggestions given or answers attempted. Is there something I can do to improve the question? –  Nick Broderick Jul 3 '13 at 14:52

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.