drift velocity of continuum limit of biased discrete random walk doesn't match gaussian

Question

I am confused about the drift velocity of the continuum limit of a biased random walk, and for some reason, I cannot find any derivation online where a discrete biased random walk is extended to the continuum limit as a Gaussian. I'm expecting a Gaussian centered on $vt$, where $v = 2p-1$ and $p$ is the probability of moving by $+1$ in one step in the discrete case. However, when I write down the Gaussian form, I get something different, and I'm not sure why.

For a random walk with probability $p$ of going $+1$ every step and $1-p$ of going $-1$, the probability of getting to point $k$ after $m$ steps is

$$ Q(m,k)=p^{\frac{m+k}{2}}(1-p)^{\frac{m-k}{2}}\left(\begin{array}{c} m\\ \frac{m+k}{2} \end{array}\right). $$

This is easy to understand. For large $m$, the binomial factor peaks strongly at $k = 0$, so we can expand it about there, and we get a factor going as

$$ \frac{2^m}{\sqrt{2\pi m}}\exp\left(\frac{-k^{2}}{2m}\right) $$

which looks fine at first. (For $p=1/2$, the $2^m$ factor is eventually cancelled, and we correctly end up with a normalized Gaussian.) However, since in the discrete case, the expectation value of movement after a single step is $2p-1$, and the expected movement after $m$ steps is $(2p-1)m$, I'm expecting something like

$$ \frac{1}{\sqrt{2\pi m}}\exp\left(\frac{-[k-(2p-1)m]^{2}}{2m}\right). $$

(lets ignore, for a moment, the fact that for $p \neq 1/2$, the variance in the denominator is no longer $m$.) The coefficient of the $k^1$ term in the exponent should then be proportional to $2p-1$. However, if I just naively take the factors of $p$ and $1-p$ in the expression for $Q(m,k)$ above, I instead get

$$ \left(\frac{p}{1-p}\right)^{\frac{k}{2}}=\exp\left[\frac{k}{2}\ln\left(\frac{p}{1-p}\right)\right]. $$

Why does the coefficient next to the $k$ in this expression look so different from what I'm expecting? Am I wrong to be expecting the coefficient to simply be $2p-1$, or is the drift velocity not the same in the continuum limit as it is in the discrete case?

Answer 1

(OP here) I realized that the key is that the distance and time increments must be kept track of; they cannot just be set to 1, because they must approach zero in a particular way in the continuum limit.

In particular, we must write $p$ as

$$p = \frac{1+r}{2}$$

and $r$ must approach zero in a certain way. To see this, we write down the master equation for $Q(m, k)$:

$$Q(m+1,k)=\frac{1+r}{2}Q(m,k-1)+\frac{1-r}{2}Q(m,k+1)$$

which is intuitive, because the walker has a $p$ chance of coming in from the left (if it is there in the first place) and a $1-p$ chance of coming in from the right (if it is there in the first place).

Now let the distance interval be $\ell$, i.e $x_{k+1} = x_k + \ell$ and the time interval be $\tau$, i.e. $t_{m+1} = t_m + \tau$. Expanding the master equation,it is straightforward to obtain

$$\frac{\Delta Q}{\Delta t}\tau=\left(\frac{\ell^{2}}{2\tau}\right)\frac{\Delta^{2}Q}{\Delta x^{2}}-\left(\frac{r\ell}{\tau}\right)\frac{\Delta Q}{\Delta x}$$

where

$$\frac{\Delta Q}{\Delta t}\equiv\frac{Q(m+1,k)-Q(m,k)}{\tau}$$

and

$$\frac{\Delta Q}{\Delta x}\equiv\frac{Q(m,k+1)-Q(m,k-1)}{2\ell}$$

and

$$\frac{\Delta^{2}Q}{\Delta x^{2}}\equiv\frac{Q(m,k+1)+Q(m,k-1)-2Q(m,k)}{\ell^{2}}$$

We then make the identification that in the continuum limit, we have

$$\frac{\ell^{2}}{2\tau}\rightarrow D,\;\frac{r\ell}{\tau}\rightarrow v$$

Now we start from the expression for $Q$ and show that it reaches a Gaussian with drift velocity $v$. We first have

$$Q(m,k)=\begin{cases} \left(\frac{1+r}{2}\right)^{\frac{m+k}{2}}\left(\frac{1-r}{2}\right)^{\frac{m-k}{2}}\left(\begin{array}{c} m\\ \frac{m+k}{2} \end{array}\right) & m+k\,\mathrm{even}\,\mathrm{and}\,m\geq\left|k\right|\\ 0 & \mathrm{otherwise} \end{cases}$$

The log of the $k$ part of the first two factors is given by

$$\frac{k}{2}\ln\left(\frac{1+r}{1-r}\right)\approx\frac{k}{2}\ln\left(1+2r\right)\approx kr=\frac{k\ell\left(\frac{r\ell}{2\tau}\right)2\tau}{\ell^{2}}=\frac{vx}{2D},$$

and the log of the $m$ part of the first two factors is given by

$$\frac{m}{2}\left[\ln\left(1+r\right)+\ln\left(1-r\right)\right]=\frac{-mr^{2}}{2}=\frac{-(m\tau)\frac{r^{2}\ell^{2}}{\tau^{2}}2\tau^{2}}{4\tau\ell^{2}}=\frac{-v^{2}t}{4D}.$$

The rest is just an unbiased Gaussian. Combining everything, we have

$$Q(m,k)=\frac{\ell}{\sqrt{4\pi Dt}}\exp\left(\frac{-x^{2}}{4Dt}+\frac{vx}{2D}-\frac{v^{2}t}{4D}\right).$$

Conveniently, the exponent is a perfect square. Writing $Q(m,k)=f(t, x)dx$ and making the indentification $dx = \ell$, we have

$$f(x,t)=\frac{1}{\sqrt{4\pi Dt}}\exp\left[\frac{-(x-vt)^{2}}{4Dt}\right].$$

It also can be shown with a fair amount of algebra that this expression satisfies

$$\frac{\partial f}{\partial t}=D\frac{\partial^{2}f}{\partial x^{2}}-v\frac{\partial f}{\partial x},$$

exactly.

Answer 2

Your $\left( p \over 1-p \right)^{k/2}$ term is difficult to expand: $p$ is not necessarily close to 0 or 1 and $k$ is not necessarily a large number. But your expected limiting form of the distribution is correct, so hopefully we can show that the factors of $Q(m,k)$ that aren't the binomial coefficient will `compensate' algebraically for that stubborn term, and that we can find a more useful expression for $Q$.

It is true that ${ m \choose {m+k \over 2}}$ is concentrated about $k=0$, but we expect the full expression for $Q(m,k)$ to be concentrated about $k = m(2p-1)$, so let's define a new variable $\ell := k - m(2p-1)$. You can probably see where this is going, but I'll include the details. I've gone a little light with the exposition, just adding a note on each step after I display it - if it isn't totally clear leave a comment!

Note that $(m+k)/2 = mp + \ell/2$ and $(m-k)/2 = m(1-p) - \ell/2$. We'll use Stirling's approximation: \begin{eqnarray*} Q(m,k) & = & { m \choose (m+k)/2} p^{(m+k)/2} (1-p)^{(m-k)/2} \\\\ & & \text{by definition;} \\ & = & {m^m \over \left(m+k \over 2\right)^{(m+k)/2}\left(m-k \over 2\right)^{(m-k)/2}}\sqrt{4 m \over 2\pi(m+k)(m-k)} p^{(m+k)/2} (1-p)^{(m-k)/2} + l.o.t. \\\\ & & \text{ by Stirling;} \\ & = & { m^m p^{mp+\ell/2} (1-p)^{m(1-p)-\ell/2} \over \left(mp+\ell/2\right)^{mp+\ell/2}\left(m(1-p)-\ell/2\right)^{m(1-p)-\ell/2}}\sqrt{m \over 2\pi(mp+\ell/2)(m(1-p)-\ell/2)} + l.o.t. \\\\ && \text{substituting in } \ell; \\ & = & \left(mp \over mp + \ell/2 \right)^{mp+\ell/2} \left(m(1-p) \over m(1-p) - \ell/2 \right)^{m(1-p)-\ell/2}\sqrt{1 \over 2\pi mp(1-p)} + l.o.t. \\\\ & & \text{by rearranging and removing the non-leading terms in the square root;} \\ & = & \left(1 + {\ell/2 \over mp} \right)^{-mp}\left(1 - {\ell/2 \over m(1-p)} \right)^{-m(1-p)} \left({mp \over mp + \ell/2} { m(1-p) - \ell/2 \over m(1-p) } \right)^{\ell/2} (2\pi m p (1-p))^{-1/2} + l.o.t. \\ & \to & e^{-\ell/2}\cdot e^{\ell/2}\cdot \left({m^2p(1-p) - \ell mp/2 \over m^2p(1-p) + \ell m (1-p)/2} \right)^{\ell/2} \left(2\pi m p(1-p) \right)^{-1/2} + l.o.t. \\\\ && \text{since we're taking } m \text{ to be large and } \lim_{n\to\infty} \left(1 + {x\over n}\right)^{n \pm x} = e^x. \\ \end{eqnarray*} In the above I drop some terms that are of order $1/m$, simply writing $l.o.t.$ for lower order terms. The final goofy looking piece is just $\exp(-\ell^2/4mp(1-p))$ as we'd hope. This is because for small $x$ we can expand $\log(1-x)$ as $-x - x^2/2 - \dots$, giving \begin{eqnarray*} \left( m^2 p(1-p) - \ell mp/2 \over m^2 p (1-p) + \ell m (1-p)/2 \right)^{\ell/2} & = & \exp\left( {\ell \over 2} \log \left( 1 - {\ell /2 \over m p (1-p) - \ell (1-p)/2} \right) \right) \\ & = & \exp\left( \ell^2/4mp(1-p)\right), \end{eqnarray*} which gives $$ Q(m,k) = {1 \over \sqrt{2\pi}} {1 \over \sqrt{mp(1-p)}} \exp\left(-{(k-m(2p-1))^2 \over 4mp(1-p)} \right) + l.o.t. $$ as desired.

Now, I'm not one hundred percent confident on the constants here; you notice that we have an unwanted (?) factor of 2 out front. But this at least should give you some faith that the drift of the discrete process behaves as we'd expect.