# Which random walk can generate gamma distribution in the limit?

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.

• 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. – Mateusz Kwaśnicki Sep 21 '19 at 5:32
• @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. – Iosif Pinelis Sep 23 '19 at 14:15
• @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 ? – david Sep 23 '19 at 15:10
• @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$. – Mateusz Kwaśnicki Sep 23 '19 at 19:19
• @MateuszKwaśnicki Thank you for the clarification. – david Sep 24 '19 at 0:20

## 2 Answers

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$$.

• 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). – david Sep 20 '19 at 18:05
• 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$. – Carlo Beenakker Sep 20 '19 at 18:28
• Thank you for the clarification – 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.

• Thank you. Condition "Letting now $p\uparrow1$, so that $q\downarrow0$ " is interesting. – david Sep 20 '19 at 19:12
• @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. – Iosif Pinelis Sep 20 '19 at 19:30
• 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 ? – david Sep 20 '19 at 20:57
• @david : Yes, this can be done and is now done in the answer. – Iosif Pinelis Sep 20 '19 at 21:28
• Thank you again. – david Sep 20 '19 at 22:04