0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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
    Commented Sep 21, 2019 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
    Commented Sep 23, 2019 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
    Commented Sep 23, 2019 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
    Commented Sep 23, 2019 at 19:19
  • $\begingroup$ @MateuszKwaśnicki Thank you for the clarification. $\endgroup$
    – david
    Commented Sep 24, 2019 at 0:20

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Sep 20, 2019 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
    Commented Sep 20, 2019 at 18:28
  • $\begingroup$ Thank you for the clarification $\endgroup$
    – david
    Commented Sep 20, 2019 at 19:22
0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .