1D Random Walk

Random Walk and Probability: Complete Derivations

The one-dimensional random walk is the fundamental model used to teach probability theory in statistical mechanics. It illustrates how microscopic randomness leads to macroscopic predictability (diffusion). Below is the rigorous, step-by-step derivation of every mathematical result in this model, from the binomial distribution to the Gaussian continuum limit.

1. The 1D Random Walk Model

Consider a particle moving along a 1D axis (lattice) with step length \( \ell \).

• Total Steps: \( N \)
• Step Right: Probability \( p \)
• Step Left: Probability \( q \)
• Normalization: \( p + q = 1 \)

2. Defining Position and Variables

Let:

• \( n_1 \): Number of steps to the right.
• \( n_2 \): Number of steps to the left.

The Constraints

1. The total number of steps is fixed:

\[ N = n_1 + n_2 \]

2. The net displacement \( x \) is the difference in steps multiplied by the step length:

\[ x = (n_1 - n_2)\ell \]

We define an integer variable \( m \) to represent the net difference in steps:

\[ m \equiv n_1 - n_2 \quad \implies \quad x = m\ell \]

Solving for \( n_1 \) and \( n_2 \)

We have a system of two linear equations:

(1) \( n_1 + n_2 = N \)
(2) \( n_1 - n_2 = m \)

Step 1: Add equation (1) and (2):

\[ (n_1 + n_2) + (n_1 - n_2) = N + m \] \[ 2n_1 = N + m \] \[ n_1 = \frac{N+m}{2} \]

Step 2: Subtract equation (2) from (1):

\[ (n_1 + n_2) - (n_1 - n_2) = N - m \] \[ 2n_2 = N - m \] \[ n_2 = \frac{N-m}{2} \]

3. The Probability Distribution

Probability of a Single Sequence

Consider a specific sequence of steps (e.g., Right, Right, Left...). Since steps are independent, we multiply probabilities:

\[ P_{\text{seq}} = \underbrace{p \cdot p \dots p}_{n_1 \text{ times}} \cdot \underbrace{q \cdot q \dots q}_{n_2 \text{ times}} = p^{n_1} q^{n_2} \]

Multiplicity (Counting Sequences)

How many distinct sequences result in exactly \( n_1 \) right steps and \( n_2 \) left steps? This is a combinatorics problem: choosing \( n_1 \) slots for right steps out of \( N \) available slots.

\[ \text{Number of ways} = \binom{N}{n_1} = \frac{N!}{n_1! \, n_2!} \]

Total Probability \( W_N(n_1) \)

The total probability is the product of the probability per sequence and the number of sequences:

\[ W_N(n_1) = \frac{N!}{n_1! \, n_2!} p^{n_1} q^{n_2} \]

This is the Binomial Distribution.

Position Probability \( P_N(m) \)

Substitute \( n_1 = \frac{N+m}{2} \) and \( n_2 = \frac{N-m}{2} \) into the equation above:

\[ P_N(m) = \binom{N}{\frac{N+m}{2}} p^{\frac{N+m}{2}} q^{\frac{N-m}{2}} \]

4. Statistical Averages (Generating Function Method)

To find the mean and variance without summing complex series, we use the derivative trick on the normalization condition:

\[ \sum_{n_1=0}^N W_N(n_1) = (p+q)^N = 1 \]

Derivation of the Mean \( \overline{n_1} \)

Step 1: Take the derivative of the sum with respect to \( p \):

\[ \frac{\partial}{\partial p} \sum_{n_1=0}^N \binom{N}{n_1} p^{n_1} q^{N-n_1} = \frac{\partial}{\partial p} (p+q)^N \]

Step 2: Apply the derivative to the term \( p^{n_1} \) inside the sum:

\[ \sum_{n_1=0}^N \binom{N}{n_1} (n_1 p^{n_1-1}) q^{N-n_1} = N(p+q)^{N-1} \]

Step 3: Multiply the entire equation by \( p \):

\[ \sum_{n_1=0}^N n_1 \left[ \binom{N}{n_1} p^{n_1} q^{N-n_1} \right] = p N (p+q)^{N-1} \]

The term in brackets is \( W_N(n_1) \). The sum is the definition of the mean \( \overline{n_1} \). Since \( p+q=1 \):

\[ \overline{n_1} = Np(1)^{N-1} \implies \overline{n_1} = Np \]

Derivation of the Variance \( (\delta n_1)^2 \)

We need the second moment \( \overline{n_1^2} \). We start by differentiating twice, but it's easier to use the operator \( p \frac{\partial}{\partial p} \) twice.

Step 1: Differentiate the result of the first derivative again (before multiplying by p):

\[ \frac{\partial}{\partial p} \left( \sum \binom{N}{n_1} n_1 p^{n_1-1} q^{N-n_1} \right) = \frac{\partial}{\partial p} \left( N(p+q)^{N-1} \right) \]

Step 2: This is algebraically complex because \( q \) depends on \( p \) if we strictly enforce \( p+q=1 \) later. A cleaner way is treating \( p \) and \( q \) as independent variables until the end, or acknowledging \( \overline{n_1^2} - \overline{n_1}^2 \). The standard result is:

\[ \overline{n_1^2} = (Np)^2 + Npq \]

Step 3: Calculate Variance:

\[ (\delta n_1)^2 = \overline{n_1^2} - (\overline{n_1})^2 \] \[ (\delta n_1)^2 = (N^2 p^2 + Npq) - (Np)^2 \] \[ (\delta n_1)^2 = Npq \]

Variance in Displacement \( x \)

Since \( x = m\ell = (2n_1 - N)\ell \), the variance of \( x \) relates to \( n_1 \):

\[ (\delta x)^2 = \overline{(x - \bar{x})^2} = \ell^2 \overline{(2n_1 - N - (2\bar{n}_1 - N))^2} \] \[ (\delta x)^2 = \ell^2 \overline{(2n_1 - 2\bar{n}_1)^2} = 4\ell^2 \overline{(n_1 - \bar{n}_1)^2} \] \[ (\delta x)^2 = 4\ell^2 (\delta n_1)^2 \]

Substituting \( (\delta n_1)^2 = Npq \):

\[ (\delta x)^2 = 4 Npq \ell^2 \]

5. Derivation of Gaussian Approximation (Stirling's Method)

We want to approximate \( \ln W_N(n_1) \) for large \( N \). We use Stirling's approximation:

\[ \ln N! \approx N \ln N - N \]

The log of the probability is:

\[ \ln W = \ln N! - \ln n_1! - \ln(N-n_1)! + n_1 \ln p + (N-n_1) \ln q \]

Step 1: The First Derivative (Finding the Maximum)

We treat \( n_1 \) as continuous. Differentiating \( \ln W \) with respect to \( n_1 \):

\[ \frac{d \ln W}{dn_1} \approx - \frac{d}{dn_1}(n_1 \ln n_1 - n_1) - \frac{d}{dn_1}((N-n_1)\ln(N-n_1) - (N-n_1)) + \ln p - \ln q \]

Using \( \frac{d}{dx}(x \ln x - x) = \ln x \):

\[ \frac{d \ln W}{dn_1} \approx -\ln n_1 + \ln(N-n_1) + \ln p - \ln q = \ln \left( \frac{N-n_1}{n_1} \frac{p}{q} \right) \]

Set derivative to zero to find the peak \( \overline{n_1} \):

\[ \frac{N-\overline{n_1}}{\overline{n_1}} \frac{p}{q} = 1 \implies p(N-\overline{n_1}) = q\overline{n_1} \] \[ pN - p\overline{n_1} = q\overline{n_1} \implies pN = (p+q)\overline{n_1} \]

Since \( p+q=1 \), we recover \( \overline{n_1} = Np \).

Step 2: The Second Derivative (The Width)

Differentiate \( \ln \left( \frac{N-n_1}{n_1} \frac{p}{q} \right) \) with respect to \( n_1 \):

\[ \frac{d^2 \ln W}{dn_1^2} = \frac{d}{dn_1} [ \ln(N-n_1) - \ln n_1 + \text{const} ] \] \[ = -\frac{1}{N-n_1} - \frac{1}{n_1} \]

Evaluate this at the peak \( n_1 = Np \) (and \( N-n_1 = Nq \)):

\[ B_2 = -\frac{1}{Nq} - \frac{1}{Np} = -\frac{p+q}{Npq} = -\frac{1}{Npq} \]

Step 3: Taylor Expansion and Exponentiation

Expand \( \ln W \) about the peak \( n_1 = Np \). Let \( \eta = n_1 - Np \):

\[ \ln W(n_1) \approx \ln W(Np) + \frac{1}{2} B_2 \eta^2 \] \[ \ln W(n_1) \approx \text{const} - \frac{\eta^2}{2Npq} \]

Exponentiating gives the Gaussian form:

\[ W(n_1) \propto \exp \left( -\frac{(n_1 - Np)^2}{2Npq} \right) \]

The normalization constant \( A \) is found by integral \( \int_{-\infty}^{\infty} A e^{-x^2/2\sigma^2} dx = 1 \). Here \( \sigma^2 = Npq \). The result is \( A = \frac{1}{\sqrt{2\pi Npq}} \).

6. Continuum Limit: The Diffusion Equation

We transform the discrete probability \( P(m) \) to a continuous probability density \( P(x) \).

• Substitute variable: \( x = m\ell \).
• Substitute drift: \( \bar{x} = N(p-q)\ell \).
• Substitute variance: \( \sigma_x^2 = 4Npq\ell^2 \).

The Gaussian becomes:

\[ P(x, t) = \frac{1}{\sqrt{2\pi \cdot 2Npq\ell^2}} \exp \left[ -\frac{(x - \bar{x})^2}{2 \cdot 2Npq\ell^2} \right] \]

Consider the unbiased case (\( p=q=1/2 \)) where \( \bar{x}=0 \):

\[ P(x, t) = \frac{1}{\sqrt{2\pi N \ell^2}} \exp \left( -\frac{x^2}{2N\ell^2} \right) \]

Let \( t = N\tau \) (time) and \( D = \frac{\ell^2}{2\tau} \). Then \( N\ell^2 = \frac{t}{\tau} \ell^2 = 2Dt \). Substituting \( 2Dt \) into the equation:

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

This function is the fundamental solution (Green's function) to the Diffusion Equation:

\[ \frac{\partial P}{\partial t} = D \frac{\partial^2 P}{\partial x^2} \]