Problem 909: Random Walk Return Probability

Mathematical Analysis

Counting Paths

Theorem. $R(2n) = \binom{2n}{n} \cdot 2^{-2n}$.

Proof. A walk of $2n$ steps consists of $r$ steps to the right and $l = 2n - r$ steps to the left. The position at time $2n$ is $r - l = 2r - 2n$. For this to equal 0, we need $r = n$. The number of such paths is $\binom{2n}{n}$ (choosing which $n$ steps go right). Each path has probability $2^{-2n}$. $\square$

Evaluation at $n = 10$

Simplification. Compute $\gcd(184756, 1048576)$.

$1048576 = 2^{20}$ and $184756 = 4 \times 46189$. Since $46189$ is odd (its prime factorization is $46189 = 7 \times 13 \times 509$):

Central Binomial Coefficient

The central binomial coefficient $\binom{2n}{n}$ has the generating function:

and the asymptotic:

This gives the well-known asymptotic for the return probability:

Consequences of (3)

Theorem (Polya’s Recurrence). The symmetric random walk on $\mathbb{Z}$ is recurrent: the walker returns to the origin with probability 1.

Proof. The expected number of returns is $\sum_{n=1}^{\infty} R(2n) \sim \sum_{n=1}^{\infty} \frac{1}{\sqrt{\pi n}} = \infty$. Since returns are not independent, we use the stronger result: the probability of eventual return is $\sum_{n=1}^{\infty} f_{2n}$ where $f_{2n}$ is the first-return probability, and $f_{2n} = R(2n) - \sum_{k=1}^{n-1} f_{2k} R(2(n-k))$. By the relation between the generating functions: $F(x) = 1 - 1/G(x)$ where $G(x) = \sum R(2n) x^n = (1-4x)^{-1/2}$. At $x = 1/4$: $G(1/4) = \infty$, so $F(1/4) = 1$, proving recurrence. $\square$

First-Return Probability

The first-return probability $f_{2n}$ satisfies:

This follows from the ballot problem / cycle lemma.

Verification Table

The approximation $1/\sqrt{\pi n}$ is remarkably accurate even for small $n$.

Higher-Dimensional Generalization

In $d$ dimensions, $R_d(2n) = \left(\binom{2n}{n} / (2d)^{2n}\right) \cdot (\text{multinomial factor})$. The walk is recurrent iff $d \le 2$ (Polya, 1921).

Complexity Analysis

• Direct computation: $O(n)$ to compute $\binom{2n}{n}$ and $\gcd$.
• Stirling approximation: $O(1)$ for an approximate answer.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 909: Random Walk Return Probability
 *
 * R(2n) = C(2n, n) / 4^n.  For n = 10: R(20) = 184756 / 1048576.
 * Reduce to lowest terms: 46189 / 262144.  Answer: p + q = 308333.
 *
 * Two methods:
 *   1. Direct computation with gcd reduction
 *   2. Iterative C(2n,n) with 2-adic valuation tracking
 *
 * Key result: R(2n) ~ 1/sqrt(pi*n) (Stirling). The walk on Z is recurrent
 * because sum R(2n) diverges.
 */

int main() {
    int n = 10;

    // Compute C(2n, n)
    long long num = 1;
    for (int i = 1; i <= n; i++) {
        num *= (n + i);
        num /= i;
    }
    // num = C(20, 10) = 184756

    long long den = 1LL << (2 * n);  // 4^n = 2^{2n} = 1048576

    long long g = __gcd(num, den);
    long long p = num / g;  // 46189
    long long q = den / g;  // 262144

    // Verify
    assert(p == 46189);
    assert(q == 262144);
    assert(__gcd(p, q) == 1);  // fully reduced

    cout << p + q << endl;  // 308333

    // Verify small cases
    // R(2) = C(2,1)/4 = 2/4 = 1/2, p+q = 3
    assert(__gcd(2LL, 4LL) == 2);

    // R(4) = C(4,2)/16 = 6/16 = 3/8, p+q = 11
    long long g2 = __gcd(6LL, 16LL);
    assert(6 / g2 == 3 && 16 / g2 == 8);

    return 0;
}

"""
Problem 909: Random Walk Return Probability

Symmetric random walk on Z starting at 0. R(2n) = probability of being
at 0 after 2n steps. Find R(20) = p/q in lowest terms, compute p + q.

Key formula: R(2n) = C(2n, n) / 4^n
Asymptotic:  R(2n) ~ 1 / sqrt(pi * n)

Methods:
    1. Direct computation with gcd reduction
    2. Exact combinatorial verification
    3. Monte Carlo simulation (verification)
"""

from math import comb, gcd, sqrt, pi
import random

def return_prob_exact(n: int):
    """Compute R(2n) = C(2n,n) / 4^n as reduced fraction (p, q)."""
    num = comb(2 * n, n)
    den = 4 ** n
    g = gcd(num, den)
    return num // g, den // g

def solve(n: int = 10):
    """Return p + q where R(2n) = p/q reduced."""
    p, q = return_prob_exact(n)
    return p + q

def return_prob_brute(n: int) -> float:
    """Count paths of 2n steps returning to 0, brute-force for small n."""
    count = 0
    total = 0
    # Enumerate all 2^(2n) paths (only feasible for small n)
    for mask in range(1 << (2 * n)):
        pos = 0
        for step in range(2 * n):
            if mask & (1 << step):
                pos += 1
            else:
                pos -= 1
        if pos == 0:
            count += 1
        total += 1
    return count / total

def return_prob_monte_carlo(n: int, trials: int = 500000) -> float:
    """Estimate R(2n) by simulation."""
    random.seed(42)
    returns = 0
    for _ in range(trials):
        pos = 0
        for _ in range(2 * n):
            pos += random.choice([-1, 1])
        if pos == 0:
            returns += 1
    return returns / trials

# Solve
ans = solve(10)

# Verify known values
assert return_prob_exact(1) == (1, 2)   # R(2) = 1/2
assert return_prob_exact(2) == (3, 8)   # R(4) = 3/8
assert return_prob_exact(3) == (5, 16)  # R(6) = 5/16

# Verify with brute force for small n
for test_n in [1, 2, 3, 4]:
    p, q = return_prob_exact(test_n)
    brute = return_prob_brute(test_n)
    assert abs(p / q - brute) < 1e-12, f"n={test_n}: exact={p/q}, brute={brute}"

# Verify specific answer
p, q = return_prob_exact(10)
assert p == 46189 and q == 262144
assert ans == 308333

print(ans)