Before solving, we must state the problem carefully. The key subtlety is how to take the limit p → ∞.
A binary word A of length p with k zeros and (p−k) ones is a lattice path in the rectangle k × (p−k): each zero is a ↑ step, each one is a → step. The evolution (random 01 → 10 swaps) moves this path toward the sorted word 1p−k0k.
If k stayed fixed while p → ∞, the density of zeros k/p → 0 gives a trivial limit (all ones, no dynamics). Both the number of zeros (kp) and ones (p − kp) must grow proportionally with p. Geometrically, the rectangle k × (p−k) inflates in both dimensions; in macroscopic coordinates (rescaled by p), it converges to an α × (1−α) rectangle.
The empirical density of ones near position x in Ap must converge to a fixed macroscopic initial profile u₀ : [0,1] → [0,1].
Bits → x: The word has p sites indexed i = 0, …, p−1, with bit wi ∈ {0,1} at each site. We map site index i to macroscopic position x = i/p ∈ [0,1]. So the discrete lattice {0, 1/p, 2/p, …, 1} becomes the continuum [0,1] as p → ∞. Each bit contributes a point mass: wi at x = i/p.
Role of smoothing radius r: Raw bits give a spiky profile (0 or 1 at each site). To obtain a smooth density u₀(x), we average over a symmetric window of radius r = ⌊p/divisor⌋ sites centered at each position. r is mesoscopic: large enough (r ≫ 1) to average out bit-level noise, small enough (r ≪ p) to resolve macroscopic features. In rescaled units, 1/p ≪ r/p ≪ 1. Any such window yields the same macroscopic limit; the app uses r = ⌊p/15⌋ by default.
The total fraction of ones is (p − kp)/p → 1 − α. This is checked in the stats panel: compare ∫u₀ with 1 − α.
Under the above scaling, the averaged density of ones at macroscopic position x and time s converges to the entropy solution of the inviscid Burgers equation:
The macroscopic time is s = steps / k(p−k) ∈ [0, 1]. The stochastic averaging IS the entropy condition: it selects compression shocks, forbids expansion shocks.
From u at s to u at s+Δs: Discrete: Each micro-step performs one random 01→10 swap (TASEP). After one swap, s increases by 1/k(p−k); the density profile changes locally. Average over many realizations → u(x,s). Continuum: The PDE gives ∂u/∂s = −∂x[u(1−u)]. The implicit formula u(x,s) = f(ξ) with x = ξ + (1−2f(ξ))·s propagates u forward: for s+Δs, solve x = ξ + (1−2f(ξ))(s+Δs) for ξ, then u(x,s+Δs) = f(ξ). Characteristics carry values unchanged until they cross (shock).
🔬 What does "density of ones near position x" actually mean? In the app, getSmoothedU0 uses a symmetric moving-average window of radius r = ⌊p/15⌋ sites centered at each position. This is a mesoscopic scale: 1/p ≪ r/p ≪ 1 (each window contains many bits, but is still small relative to [0,1]). Any window satisfying this constraint gives the same macroscopic profile as p→∞. Rigorously, no window is needed: the requirement is weak convergence of the empirical measure (1/p)∑ wi δi/p to u₀(x)dx, meaning ∑ wi φ(i/p) / p → ∫u₀ φ dx for all continuous test functions φ.
💡 Traffic analogy: Think of ones as cars on a highway and zeros as empty spaces. Density u = fraction of road occupied. When traffic is heavy (u near 1), cars jam; when light (u near 0), few cars = little flow. Maximum throughput at u = ½. The conservation law says no cars are created or destroyed — the total ∫u₀ = 1 − α is conserved for all time.
Summary table of key quantities:
| Symbol | Meaning | Example |
|---|---|---|
| x | Position in word (rescaled to [0,1]) | x = i/p |
| s | Macroscopic time (fraction completed) | s = steps/k(p−k) |
| α | Limiting zero fraction k/p → α | α = 0.4 → 40% zeros |
| u(x,s) | Density of ones at (x, s) | u = 0.8 → 80% ones |
| f(ξ) | Shorthand for initial data: f(ξ) ≡ u₀(ξ) | f(0.3) = u₀(0.3) |
| J(u) | Flux = u(1−u) (swap rate) | J(0.5) = 0.25 (max) |
| c(u) | Characteristic speed = 1−2u | c(0.8) = −0.6 (left) |
| v | Excess density = u − ½ | v = 0.3 when u = 0.8 |
| ξ | Origin of characteristic reaching (x,s) | Solve implicit eq. |
| tb_anal | Breaking time (continuum) = 1/(2·max f′) | tb_anal = 0.5 for f = x |
| tb_disc | Breaking time (discrete) = from smoothed word in app | tb_disc ≈ 0.05 for Analytical u₀ |
| ẋshock | Shock speed = 1 − uL − uR | 1−0.9−0.3 = −0.2 |
Our conservation law can be solved exactly. Here is the complete analytical chain — from the equation to the implicit solution to the breaking time.
Conservation law with flux J(u) = u(1−u). Characteristic speed c(u) = 1 − 2u.
Centering around v = 0 (the 50/50 mix). v > 0 = excess ones (moves left), v < 0 = deficit (moves right).
Each point ξ on the x-axis sends a straight-line characteristic carrying u = f(ξ) = u₀(ξ).
For each (x,s), invert to find ξ, then u = f(ξ). This is exact — valid until characteristics cross.
Fastest characteristics catch slower ones at time tb. After tb: entropy condition (Rankine–Hugoniot) selects the shock solution. Shock speed: ẋ = 1 − uL − uR.
tb_anal = continuum formula (1/(2·max f′)). tb_disc = from smoothed discrete word in app. For steps: tb = 0. For rarefaction: tb = ∞.
| Path | tb_anal | tb_disc |
|---|---|---|
| 1. 0ᵏ1ᵖ⁻ᵏ | 0.00 | ≈ 0.07 |
| 2. ½-evolved | N/A | from app (varies) |
| 3. Shock (uL>uR) | 0.00 | ≈ 0.00 |
| 4. Rarefaction (uL<uR) | ∞ | typically ∞ |
| 5. Ramp ↑ u₀=x | 0.50 | ≈ 0.50 |
| 6. Ramp ↓ u₀=1−x | ∞ | typically ∞ |
| 7. Analytical u₀ | 0.40 | often ≈ 0.05 |
| 8. Scattered | N/A | from app (varies) |
| 9. Random | N/A | from app (varies) |
Step: u₀ = 0 for x < 0, u₀ = 1 for x ≥ 0. Discontinuity ⇒ tb_anal = 0.00, tb_disc ≈ 0.07. Shock exists from s = 0. The high-density side (ones) and low-density side (zeros) meet at a sharp interface that propagates rightward as the word evolves toward the sorted state.
Random mix of swaps from initial — roughly halfway to sorted. No closed-form u₀. tb_anal: N/A. tb_disc: from app (varies). The profile is typically smooth with moderate gradients; whether a shock forms depends on the particular realization. Run the app to see the characteristics and shock trajectory.
Step uL ≈ 0.8, uR ≈ 0.2 at x₀ ≈ 0.5. Since uL > uR (compression), shock exists from s = 0 ⇒ tb_anal = 0.00, tb_disc ≈ 0.00. Shock speed: 1 − 0.8 − 0.2 = 0 (stationary!). Symmetric case uL + uR = 1: flux is equal on both sides, so the shock doesn't move. u(x,s) = 0.8 for x < 0.5, 0.2 for x > 0.5 (all s).
Step uL ≈ 0.2, uR ≈ 0.8. Expansion (uL < uR) is forbidden by the entropy condition → replaced by a rarefaction fan. tb_anal = ∞, tb_disc: typically ∞. No shock ever forms — characteristics diverge. The profile spreads out smoothly; density decreases on the left and increases on the right as the fan develops.
f(ξ) = ξ, so f′ = +1 everywhere ⇒ tb_anal = 0.50, tb_disc ≈ 0.50. Profile steepens, then breaks. u(x,s) = (x−s)/(1−2s), valid for s < 0.50. At s = 0.25: u = 2x − 0.5 (twice as steep). At s = 0.50: denominator → 0 (vertical cliff → shock forms). After tb, a shock emerges and propagates.
f(ξ) = 1−ξ, so f′ = −1 < 0 everywhere ⇒ tb_anal = ∞, tb_disc: typically ∞. No shock ever forms — characteristics diverge. u(x,s) = (1+s−x)/(1+2s). At s = 0: u = 1−x ✓. Slope flattens from −1 to −1/(1+2s). As s → ∞: u → ½ everywhere (complete mixing).
u₀ = 0 (x≤0), x/a (0<x<a), 1 (x≥a), a = 0.80. Ramp slope 1/a = 1.25 ⇒ tb_anal = 0.40. tb_disc: often ≈ 0.05 (discrete artifacts at ramp boundaries). Before shock: u = 0 (x≤s), (x−s)/(a−2s) (s<x<a−s), 1 (x≥a−s). After shock: u = 1 (x<0.40), 0 (x>0.40). Shock forms at s = 0.40, then stays at x = 0.40 (stationary: uL=1, uR=0 ⇒ speed = 0).
Random permutation of the sorted word — zeros and ones thoroughly mixed. No closed-form u₀. tb_anal: N/A. tb_disc: from app (varies). The profile is typically noisy; local steep gradients may produce an early tb_disc. Run the app to observe the evolution and shock formation (if any).
Random number of swaps from initial — each realization differs. No closed-form u₀. tb_anal: N/A. tb_disc: from app (varies). The profile can resemble ½-evolved (smooth) or develop steep regions; tb_disc depends on the random path chosen. Try multiple runs to see the variability.
Drag the time slider. Left: characteristics in the (x,s) plane. Right: exact density profile u(x,s) via the implicit formula. Optional MC overlay.
Each colored trace is a single random realization — one possible sequence of 01→10 swaps. They jitter wildly. Yet their average (white) locks onto the exact Burgers solution (gold). This is the hydrodynamic limit — a deterministic PDE materializing from microscopic noise.
Individual paths (5 faint colored traces): each is one random sequence of swaps from A. They fluctuate because each chooses different random swaps.
MC average (white bold line): at each time step s, we run nAvg independent random TASEP realizations from A (each does s random 01→10 swaps). The average at site i is (1/nAvg)∑ wn[i] over realizations. The displayed line is this raw average smoothed with radius r = ⌊p/divisor⌋ for fair comparison with Burgers. As nAvg grows, the white line converges to the true expectation.
Exact Burgers (gold dashed): the PDE solution. As p → ∞, the average must converge to this. Watch it happen.
Sample random continuations from A. Compare with the exact Burgers solution at 4 time slices.
Fix macroscopic shape u₀, embed in words of increasing p with kp/p → α. Watch MC → Burgers. L² error ∝ 1/√p.
Getting started: Read 📐 Formulation for the precise setup. Then Exact Solution for the analytical chain and worked examples. Then ⭐ Explorer to see it in action — drag the time slider and watch shocks form and propagate.