Symmetric random walk, its probability distribution is binomial coefficient, in the continuous limit, is Gaussian distribution:

$\displaystyle e^{- x^{2}}$

What kind of random walk, its probability distribution, in the limit, is Gamma distribution:

$\displaystyle xe^{- x}$ for $x \geqslant 0$ ?

or simpler, an exponential distribution:

$\displaystyle e^{- x}$ for $x \geqslant 0$ ?

We are looking for something as simple as a random walk at discrete time, in the continuous limit, exponential factor $e^{-x}$ factor shows up. At each step, rules to guide random walk should be as simple as possible. If possible, we would like each step of the random walk to be a iid (independent and identically distributed) random variable. Is this possible ?

Thank you.

  • $\begingroup$ I.i.d. random walk clearly cannot converge to re-scaled Gamma distribution: if $a_n X_n$ converged to $\Gamma(p,q)$, then $a_{2n} X_{2n} = a_{2n} (X_n + (X_{2n} - X_n))$ would have converged to $\Gamma(2p,\tilde{q})$ rather than $\Gamma(p, q)$. In fact, i.i.d. random walks can only converge to stable distributions. $\endgroup$ – Mateusz Kwaśnicki Sep 21 '19 at 5:32
  • $\begingroup$ @MateuszKwaśnicki : However, the gamma distribution, just as any other infinitely divisible distribution en.wikipedia.org/wiki/Infinite_divisibility_(probability), is of course (the limit of) the distribution of the sum of the row of iid random variables (r.v.'s) in a triangular array en.wikipedia.org/wiki/…. So, here the only problem is to show that those iid r.v.'s can be made to take values only in a lattice in $\mathbb R$; of course, this discrete-to-continuous problem is a not a big one. $\endgroup$ – Iosif Pinelis Sep 23 '19 at 14:15
  • $\begingroup$ @MateuszKwaśnicki, You said that $a_{2n} X_{2n} = a_{2n} (X_n + (X_{2n} - X_n))$ would have converged to $\Gamma(2p,\tilde{q})$, what is $\tilde{q}$ here ? $\endgroup$ – david Sep 23 '19 at 15:10
  • $\begingroup$ @david: $a_n X_n$ and $a_n (X_{2n} - X_n)$ are independent and converge in distribution to $\Gamma(p,q)$. Thus, $a_n X_{2n} = a_n (X_n + (X_{2n} - X_n))$ converges in distribution to $\Gamma(2p,q)$. Since $a_{2n} X_{2n}$ also converges in distribution, the sequence $a_{2n} / a_n$ necessarily has a finite limit $b$. It follows that $a_{2n} X_{2n}$ converges in distribution to $\Gamma(2p, bq)$. That is, $\tilde{q} = b q$. $\endgroup$ – Mateusz Kwaśnicki Sep 23 '19 at 19:19
  • $\begingroup$ @MateuszKwaśnicki Thank you for the clarification. $\endgroup$ – david Sep 24 '19 at 0:20

You can use a simple random walk with a drift term $\mu(x)$, which has a probability distribution $p(x)$ that in the continuum limit satisfies the Fokker-Planck equation. The stationary solution is $$p(x)\propto \exp\left(2\int_0^x \mu(x')\,dx'\right).$$ So the desired $p(x)\propto xe^{-x}$ for $x>0$ is obtained from $$\mu(x)=\frac{1}{2} \left(\frac{1}{x}-1\right)$$ with an absorbing boundary condition at $x=0$.

| cite | improve this answer | |
  • $\begingroup$ Why does $\mu(x)$ have $\frac{1}{x}$ term, what does this mean ? In the discrete case, can this give something simple ? (We know symmetric random walk is very simple). $\endgroup$ – david Sep 20 '19 at 18:05
  • $\begingroup$ a drift term $\mu(x)$ just means that you add to each random walk step an increment $\delta x = \mu(x)$; so for large $x$ the drift term $\mu(x)=(x^{-1}-1)/2$ drives you back to the origin (which gives the $e^{-x}$ tail), while for small $x$ the drift pushes you away from the absorbing boundary at $x=0$. $\endgroup$ – Carlo Beenakker Sep 20 '19 at 18:28
  • $\begingroup$ Thank you for the clarification $\endgroup$ – david Sep 20 '19 at 19:22

This example is indeed "as simple as a random walk at discrete time", and even simpler than that. Indeed, for $p\in(0,1)$ and natural $r$, let $X_{p,r}$ denote the number of failures before the $r$th success in a infinite series of independent Bernoulli trials with success probability $p$ in each trial. Then $X_{p,r}$ has the negative binomial distribution with parameters $p$ and $r$, with the characteristic function (c.f.) $f_{p,r}$ given by the formula $$f_{p,r}(t)=Ee^{itX_{p,r}}=\frac1{(1-(e^{it}-1)p/q)^r} \tag{1} $$ for real $t$, where $q:=1-p$. Letting now $p\uparrow1$, so that $q\downarrow0$, we see that for real $t$ $$Ee^{itqX_{p,r}}=\frac1{(1-(e^{iqt}-1)p/q)^r}\to\frac1{(1-it)^r}. $$ That is, the distribution of $qX_{p,r}$ converges to the gamma distribution with shape parameter $r$ and scale parameter $1$.

If one wishes, for each natural $n$ one can write $X_{p,r}$ as $Y_1+\cdots+Y_n$, where $Y_1,\dots,Y_n$ are iid random variables and each $Y_i$ has negative binomial distribution with parameters $p$ and $r/n$, with the c.f. $f_{p,r/n}$, where $f_{p,r}$ is as in (1) -- so that $f_{p,r}=f_{p,r/n}^n$. (By expanding $$f_{p,s}(t)=(1/q-e^{it}p/q)^{-s} $$ into powers of $e^{it}$, it is easy to see that $f_{p,s}$ is the c.f. of a probability distribution for any real $s>0$.) So, the distribution of each $Y_i$ may be (sort of) thought of as the distribution of the number of failures before we have $r/n$ successes -- even if $r/n$ is not an integer.

| cite | improve this answer | |
  • $\begingroup$ Thank you. Condition "Letting now $p\uparrow1$, so that $q\downarrow0$ " is interesting. $\endgroup$ – david Sep 20 '19 at 19:12
  • $\begingroup$ @david : Multiplying $X_{p,r}$ by $q$ means time re-scaling, namely, replacing the unit time step in the original Bernoulli series by time step $q$. Letting then $q$ be small means that we make the time step small and, simultaneously and accordingly, make the failure probability small at each of the small time steps. $\endgroup$ – Iosif Pinelis Sep 20 '19 at 19:30
  • $\begingroup$ Can $qX_{p,r}$ be written as the sum of iid random variables ? such as: $qX_{p,r} = x_1 + x_2 + ... + x_n$ where each $x_k$ is a random variable ? $\endgroup$ – david Sep 20 '19 at 20:57
  • $\begingroup$ @david : Yes, this can be done and is now done in the answer. $\endgroup$ – Iosif Pinelis Sep 20 '19 at 21:28
  • $\begingroup$ Thank you again. $\endgroup$ – david Sep 20 '19 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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