Sign up ×
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|cite|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

2 Answers 2

up vote 5 down vote accepted

Let $X_1,X_2,\dots$ be independent identically distributed random variables representing the successive jumps of the particle. Let $M_n$ be the position of the particle at time $n\in\{0,1,\dots\}$, so that $M_0=0$ and $M_n=\max(0,M_{n-1}+X_n)$ for $n\in\{1,2,\dots\}$. Let now $F_n(x):=\mathbb{P}(M_n\le x)$ for real $x$. Then $F_0(x)=\mathrm{I}\{x\ge0\}$ and $F_n(x)=\frac{\mathrm{I}\{x\ge0\}}{1+r}\,\int_{-r}^1 F_{n-1}(x-y)\,dy$ for all real $x$ and $n\in\{1,2,\dots\}$. In particular, the probability in question is $P_{n,r}=\mathbb{P}(M_n=0)=F_n(0)$.

The work in Mathematica notebook at n=1,2,3 (the corresponding pdf file at n=1,2,3 - pdf) shows that the expression $$\frac{\left(\frac{3r}{1+r}\right)_{n-1}}{(1+r)\left(2r\right)_{n-1}},\quad r\geq 1,$$ which you most recently proposed for $P_{n,r}$, is incorrect already for $n=3$ (and $r\ne1$), even though it seems pretty close to the correct one.

I doubt that there is such a simple closed form expression for $P_{n,r}$. However, using Spitzer's identity and work done in c.f. of X_+, one can obtain an integral expression for the generating function of $P_{n,r}$: $$ (*)\qquad \sum_{n=0}^\infty P_{n,r}z^n= \frac1{\sqrt{1-z}}\exp \Big(\frac1{2 \pi i}\,\int_0^{\infty } \ln\frac{(r+1) u-z (e^{i r u}-e^{-i u})}{(r+1) u-z (e^{i u}-e^{-i r u})} \, \frac{du}{u}\Big) $$ for complex $z$ with $|z|<1$. To obtain (*), one can start with formula (23) in c.f. of X_+, analytically extend it to complex $s$ with $\tau:=\Im s\ge0$, and then let $\tau\to\infty$. Alternatively, one can start with the second displayed formula on page 159 (with $\lambda=0$) in Spitzer 1960 and then reason as in c.f. of X_+; here one should also have in mind statement (2.4) on page 155 in Spitzer 1960.

In particular, it easily follows from (*) that your expression for $P_{n,r}$ is correct in the symmetric case, when $r=1$, but apparently only in this case.

Addendum: Even though there does not seem to be a simple closed form expression for $P_{n,r}$, an explicit but rather complicated expression for $P_{n,r}$ can be obtained from (*). Indeed, expand the logarithm back in powers of $z$. Then use the Cauchy integral theorem to see that for natural $n$ $$\frac1{\pi i}\int_0^\infty\frac{f(u)^n-f(-u)^n}u\,du =1-2a_n,$$ where $$f(u):=\mathbb{E}e^{iuX_1}=\frac{e^{iru}-e^{-iu}}{i(r+1)u}$$ for $u\ne0$ and $$a_n:=a_{n,r}:=\frac1{2n}\Big[1+\frac1{n!}\sum_{j=0}^n(-1)^j \binom nj \Big(\frac n{r+1}-j\Big)^n\,\text{sign}\Big(\frac n{r+1}-j\Big)\Big].$$

It follows from (*) that for complex $z$ with $|z|<1$ $$\sum_{n=0}^\infty P_{n,r}z^n=\exp\sum_{k=1}^\infty a_k z^k =\prod_{k=1}^\infty\exp(a_k z^k) =\prod_{k=1}^\infty\sum_{q=0}^\infty \frac{a_k^q z^{kq}}{q!},$$ whence $$P_{n,r}=\sum\prod_{k=1}^n\frac{a_k^{q_k}}{q_k!},$$ where the sum is taken over all $n$-tuples $(q_1,\dots,q_n)$ of nonnegative integers such that $1q_1+2q_2+\dots+nq_n=n$. In particular, for $n=0$ the set of all such $n$-tuples is the singleton set $\{\emptyset\}$, and, as usual, $\prod_{k=1}^0\ldots:=1$, so that $P_{0,r}=1$. Also, $$P_{1,r}=a_1=a_{1,r},\quad P_{2,r}=a_2+a_1^2/2!, \quad P_{3,r}=a_3+a_1a_2+a_1^3/3!. $$ Substituting here the expressions for the $a_k$'s, one sees that the above results for $n=1,2,3$ agree with the ones previously found in the Mathematica notebook at n=1,2,3 (the corresponding pdf file at n=1,2,3 - pdf) by iterative integration.

share|cite|improve this answer
added an explicit expression for the probability in question –  Iosif Pinelis Apr 6 at 4:19

Not an answer, but I was exploring a similar random walk, so I thought I would include an image of a simulation. In my walk, each step is of a random length drawn from a normal distribution with mean $\mu=0$ and $\sigma=1$. So $x_{i+1} = x_i + \cal{N}$$(0,1)$ if that is nonnegative, and otherwise $x_{i+1}=0$.

Vertical axis is $x_i$; horizontal $i$, the number of steps. The walk wanders rather far from zero.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.