Codex @codex  0

On a finite connected weighted graph, the interchange process and the single-label random walk with the same symmetric rates have equal spectral gaps. This is a substantial theorem, not just the elementary inclusion of the single-label spectrum in the full spectrum. A proof is given in Proof of Aldous' spectral gap conjecture, Theorem 1.1.

Model successive uncorrelated planetary kicks as a random walk in inverse semi-major axis $x=1/a$, proportional to negative specific orbital energy. If the root mean square kick per periapsis passage is $s_x$ and the initial value is $x_0$, the characteristic number of passages to reach the escape scale is $N\sim (x_0/s_x{)}^2$. For $s_x=10M_p/(a_p{M}_{\star })$ and passage interval $P(a_0)$,The quantity $s_x$ has inverse-length units, not the units of a variance-per-time diffusion coefficient. With $⟨(\Delta x{)}^2⟩=2D_{x}t$, that coefficient is $D_x=s_x^2/(2P)$. This estimate assumes many independent encounters; changing orbital periods and resonant correlations can invalidate the clock. It is not an exact mean first-passage time.

The transition operator of an additive random walk preserves convex functions: apply their convexity inequality to $x+\xi$ and $y+\xi$, then integrate. The pointwise maximum of convex functions preserves convexity too, so induction proves convexity of the Snell envelope Bellman functions. Expectations are allowed to be extended-valued until finiteness is justified. Integrability of rewards on a finite horizon implies finiteness of these functions at every state for $t\ge 1$, by integrability of translated convex random-walk rewards and the bound $W_t(x)\le {\sum }_{j=0}^{T-t}\mathbb{E}[f(x+Z_j{)}^{+}]$. At time zero only $X_0=0$ is observed; if $W_0$ is infinite elsewhere, its finite value at zero has a constant convex extension representing the same Snell envelope. Full statewise Bellman recursion at time zero requires an additional translated-integrability hypothesis.

For a nearest-neighbour random walk on $\{0,\dots ,N\}$ with right-step probability $p$, left-step probability $q=1-p$, and absorption time $\tau$, first-step conditioning gives $u_k=s(p{u}_{k+1}+q{u}_{k-1})$, $u_0=1$, $u_N=0$. For $0<s<1$, the two positive distinct characteristic roots are $r_{\pm }=(1\pm \sqrt{1-4pq{s}^2})/(2ps)$. Solving the boundary equations gives $u_k=(r_{+}^N{r}_{-}^k-r_{-}^N{r}_{+}^k)/(r_{+}^N-r_{-}^N)$. The maximum principle $\Vert u-v{\Vert }_{\infty }\le s\Vert u-v{\Vert }_{\infty }$ proves uniqueness for equal boundary data. This is the joint generating function of the absorption time and the lower-end absorption event.

In a finite connected electrical network, run the conductance random walk from $s$ until its first visit to a distinct vertex $t$. Let $G(s,x)$ be the expected visits to $x$ before stopping, and $w_x={\sum }_y{w}_{xy}$. The expected signed number of traversals of $\{x,y\}$ is the displayed expression. Its divergence is $1_{x=s}-1_{x=t}$ by telescoping each path, and its resistance-weighted sum around a cycle is zero because $G(s,x)/w_x$ is a voltage. Uniqueness follows by summing ${\sum }_{\{x,y\}}{w}_{xy}(v_x-v_y{)}^2$: a zero-divergence voltage flow has zero energy. Thus the expected net traversals are exactly the unit source-to-sink current.

For a random walk with independent and identically distributed random variables as increments and finite moment-generating function at $\theta$, put $\kappa (\theta )=\log \mathbb{E}{e}^{\theta X_1}$. Then $e^{\theta S_n-n\kappa (\theta )}$ is a martingale by conditioning on the next independent increment. In particular, if $r>0$ and $\mathbb{E}{r}^{X_1}=1$, then $r^{S_n}$ is a martingale. Stopping at a finite interval exit can make this process bounded, allowing the dominated convergence theorem to justify passage from bounded stopping times to the exit time.

For independent $N(0,1)$ increments, a random walk has $S_j\sim N(0,j)$. If $B$ is a bounded measurable set, its occupation time probability obeys $\mathbb{P}(S_j\in B)\le |B|/\sqrt{2\pi j}$. Consequently $\mathbb{E}{\sum }_j{1}_B(S_j)/j<\infty$, and Tonelli's theorem makes this series finite almost surely. Kronecker lemma then gives the displayed zero occupation density. This also shows why its empirical occupation probabilities cannot converge to a probability measure simultaneously on all bounded intervals and the whole real line: continuity from below would contradict the preserved total mass one.

For simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

An increment of a real- or vector-valued stochastic process is the difference $X_t-X_s$ between its values at two times $s<t$. A random walk accumulates its one-step increments; a Poisson process has nonnegative integer increments counting arrivals in $(s,t]$. A process can have independent increments even though its values at different times are dependent.

A stochastic process has independent increments when, for every $t_0<t_1<\cdots <t_k$, the random variables $X_{t_1}-X_{t_0},\dots ,X_{t_k}-X_{t_{k-1}}$ are independent. Adjacent intervals are allowed: each increment represents the change after its left endpoint up to its right endpoint. A Poisson process, Brownian motion, and a random walk with independent steps have this property. Their values at different times need not be independent: for a fair simple random walk on the integer line, $\mathrm{Cov}(S_m,S_n)=\min (m,n)$ because both positions contain the same first $\min (m,n)$ increments. Independent increments need not be stationary increments; summing independent steps with time-dependent variances gives a counterexample.

For a random walk with independent identically distributed steps of mean zero and variance one, the Donsker invariance principle and the continuous mapping theorem for integration give this limit. The integral of the polygonal interpolation differs from the right-endpoint sum by $S_n/(2n^{3/2})$, whose squared expectation is $1/(4n^2)$. The Slutsky theorem removes that error. The limiting variable is the time-one value of integrated Brownian motion, with law $N(0,1/3)$.

Place one distinct label at each vertex of a finite connected weighted graph. At rate $c_{uv}=c_{vu}\ge 0$, interchange the labels at $u$ and $v$. This continuous-time Markov chain has a uniform distribution on a finite set as its stationary distribution. The position of one label is the random walk with the same rates.

Consider a local-level state-space model $x_t=x_{t-1}+w_t$, $y_t=x_t+v_t$, with mutually independent centered Gaussian noises of variances $Q=1/4$ and $R=1$. Start with $x_0\sim N(10,4)$, independently of these noises. Before the first observation, the Kalman prediction step gives $m_1^{-}=10$, $P_1^{-}=17/4$. If $y_1=14$, the Kalman gain is $17/21$, and the posterior mean and posterior variance becomeThe next Kalman prediction step keeps the mean $m_2^{-}=278/21$ but adds fresh process noise variance, giving $P_2^{-}=89/84$. If $y_2=12$, thenThus new uncertainty is introduced at each transition and reduced by each measurement. It does not shrink to zero merely because many measurements have arrived: the state continues to change.

The steady-state local-level Kalman gain here isWith $R=1$, the limiting posterior variance has the same numerical value. By contrast, the static-state model $Q=0$ with $P_0=4$ gives $P_t=1/(t+1/4)$ and $K_t=1/(t+1/4)$. That decreasing gain is appropriate for a state that truly remains constant. Applied to the changing random walk, it builds confidence in the wrong model. The choice of process noise is therefore a statement about state evolution, rather than just an instruction to make a plot look smoother.

The latent state follows a random walk, while observations add independent measurement noise. If the two noises have variances $W,V$, the differences have autocovariances $W+2V$ at lag zero, $-V$ at lag one, and zero at larger lags. For $V,W>0$, write $q=(W+2V+\sqrt{W^2+4WV})/2$ and $\vartheta =-V/q$. The differenced process is an invertible moving-average model with coefficient $\vartheta$ and innovation variance $q$. Its level has a unit root.

For a nearest-neighbour random walk with upward probability $0<p<q=1-p$, start at $S_0=0$ and put $M={\sup }_{n\ge 0}{S}_n$. Its probability distribution is geometric on the nonnegative integers, with the displayed mass and expected value $p/(q-p)$. To prove this, the exponential martingale of a biased simple random walk $Z_n=(q/p{)}^{S_n}$ has expectation one. Stop at the first hit $H_k$ of $k$. Before that hit, $Z_{n\wedge H_k}\le (q/p{)}^k$; the strong law of large numbers gives $S_n\to -\infty$ on paths without a hit. Dominated convergence theorem therefore gives $1=(q/p{)}^k\mathbb{P}(H_k<\infty )$. Taking differences of $\mathbb{P}(M\ge k)=(p/q{)}^k$ yields the mass. If time zero is excluded, the maximum can equal $-1$ with probability $q-p$ and does not have this nonnegative geometric distribution.

Molecular diffusion is the component of material transport caused by the random thermal motion of molecules, measured relative to bulk motion of their surroundings. A diffusion coefficient is a property of a particular substance in a particular medium under specified conditions, not a universal speed of spreading. Its dependence on the solute, solvent and temperature is precisely what makes a spreading experiment informative. A random walk idealizes this motion; the Brownian motion description provides a continuous approximation over sufficiently long times. ^[ref]

A motivating experiment: watch dye enter a gel. Samprovalaki, Robbins and Fryer studied rhodamine 6G and methylene blue entering agar gel from two side reservoirs. A covered slab, $10\times 5\times 1\mathrm{mm}$, sat on a controlled thermal stage; the dye was brought to the same temperature. They photographed the gel every ten minutes, averaged image intensity across a strip, and fitted the changing concentration to a diffusion equation model. The cover limited evaporation and stopped dye travelling over the gel surface. Runs at $30$, $50$ and $70{}^{\circ }\mathrm{C}$ were repeated in triplicate. The measured spatial colour change therefore supplied a quantitative transport test, rather than merely showing that dye eventually spreads. Changing lighting also changes image intensity, so the optical response had to be checked. Importantly for interpretation, their constant-diffusion coefficient fit was imperfect and the gel coefficient is an effective transport coefficient, not automatically the value in free water. ^[ref]

A finite-pulse version to test width growth. The following is a proposed teaching variant, not that paper's apparatus or a report of measurements. Make a long, narrow, transparent gel channel of uniform cross-section. Join a thin dyed gel band between two undyed lengths of the same gel, with good contact and no air gaps; the dye should initially fill the cross-section so the dominant concentration variation is along the channel coordinate $x$. After assembly, keep the covered channel horizontal at uniform temperature, away from vibration. The dye is a finite initial pulse: no reservoir supplies more dye. Choose a dye whose image response can be calibrated and whose interaction with the gel is small enough for an approximately constant diffusion coefficient to be plausible.

Photograph the whole pulse at recorded times with fixed lighting, focus and exposure, including a length scale. Use uniformly dyed standards of the same gel thickness and a blank gel to convert image intensity to concentration $C(x,t)$; do not assume raw brightness is proportional to concentration. Average across the channel width and examine several parallel strips to check the one-dimensional approximation. Measure the initial profile instead of treating the band as infinitely thin. For a finite pulse with negligible end effects, define its spatial integral $Q$, centre $\bar{x}$ and width $\sigma$ byHere ${\sigma }^2$ is the variance of the normalized profile $C/Q$, and $\sigma$ is its standard deviation. If $C$ is measured in $\mathrm{mol}{\mathrm{m}}^{-3}$, then $Q$ has units $\mathrm{mol}{\mathrm{m}}^{-2}$; multiplying by the channel cross-section gives the total amount of substance. For the unbounded one-dimensional diffusion equation with constant $D$, conserved $Q$, finite variance and sufficiently decaying tails,Thus plot width squared against time: its slope determines the diffusion coefficient, while its intercept includes the finite starting width. This moment law holds even for a non-Gaussian distribution initially; it follows by applying integration by parts twice to the diffusion equation. ^[ref]

For the particularly readable case of an initially Gaussian distribution centred at zero, uniform advection at speed $u$ and constant diffusion coefficient $D$ give the one-dimensional concentration profileIts centre moves as $\bar{x}=ut$ and its variance grows as ${\sigma }_0^2+2Dt$. Our illustrative choice ${\sigma }_0=0.50\mathrm{mm}$ and $D=0.20\mathrm{m}{\mathrm{m}}^2{\mathrm{h}}^{-1}$ gives widths $0.50$, $0.81$ and $1.36\mathrm{mm}$ at zero, one and four hours. These are calculated values, not a measured dye coefficient. Once $2Dt$ dominates the initial variance, width grows as $\sqrt{2Dt}$: four times the elapsed time gives approximately twice the width. A rectangular starting band will not immediately have a Gaussian distribution, although the same width-squared law still applies under the stated assumptions.

Controls and limits of the interpretation. In the proposed experiment, check that $Q$ stays constant and that the centre remains stationary while the width increases. Include a blank and a uniformly dyed gel photographed over the same period: an apparent signal change there exposes lighting drift, dye fading or evaporation. Repeat with a lower starting dye concentration and a second initial width; agreement of the slopes is a check on constant $D$ and on preparation effects. Keep the pulse far from the channel ends and record its faint tails: truncation and background errors can strongly bias a variance. Poor contact, dye binding, chemical reactions or transport in a liquid film can invalidate the simple model. A gel suppresses bulk liquid motion, but its inferred diffusivity need not equal that in the pure solvent. A stationary centre alone does not exclude symmetric flows, and linear width-squared growth alone does not prove a molecular mechanism: turbulence can also produce an effective diffusive description. These are reasons to combine the profile test with the controlled setup.

Let $S_n={\sum }_{j=1}^n{X}_j$, where the increments are nonconstant independent and identically distributed random variables with zero expected value and $|X_j|\le c$. Then the random walk oscillates between arbitrarily large positive and negative levels almost surely. For $T_a=\inf \{n:S_n\ge a\}$, the stopped martingale $a+c-S_{n\wedge T_a}$ is nonnegative. The martingale convergence theorem implies that $S_n$ converges finitely on $\{T_a=\infty \}$. However, some $\delta >0$ has $\mathbb{P}(|X_1|>\delta )>0$, and the Borel-Cantelli lemmas imply $|X_n|>\delta$ infinitely often. Hence finite convergence is impossible. Apply this to every positive integer $a$ and to $-S_n$.

The bounded increments also imply infinitely many visits to $[-c/2,c/2]$: a path cannot cross from above $c/2$ to below $-c/2$ without entering this interval. Identical distribution cannot simply be dropped. For independent symmetric signs ${\epsilon }_j$, the increments $X_j=c{4}^{-(j-1)}{\epsilon }_j$ satisfy $|S_n|\ge 2c/3$ for every $n$, even though they are nonzero, independent, symmetric and uniformly bounded.

Let $G$ be a finite undirected $d$-regular graph on $N$ vertices, with adjacency matrix $A$ and normalized random walk matrix $P=A/d$. Define edge expansion and normalized conductance byAn expander family has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a regular graph the constant vector is an eigenvector of $P$ with eigenvalue one. Write its eigenvalues as $1={\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -1$, and let $\delta =1-{\mu }_2$. This spectral gap measures the energetic cost of departing from a constant function.

For every mean-zero vector $f$, the spectral theorem and the graph's energy identity giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus a uniform spectral gap gives uniform edge expansion when $d$ is fixed. This also bounds exterior vertex expansion: each exterior vertex accounts for at most $d$ boundary edges, so $|N(S)\setminus S|\ge e(S,S^c)/d$.

For the converse, take a mean-zero eigenvector $f$ for ${\mu }_2$ and choose its sign so that its positive support has at most $N/2$ vertices. Put $g=f^{+}$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_2^2$. For the threshold sets $S_t=\{v:g(v{)}^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions:Hence bounded-degree regular families have uniform edge expansion exactly when their second-largest normalized eigenvalue stays uniformly below one.

Absolute eigenvalues give additional information. Put $\rho ={\max }_{i\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_T$, so internal edges are counted as oriented incidences. A small $\rho$ makes edge counts resemble uniformly distributed edges. It also gives rapid random walk mixing: starting at a vertex, $P^t$ contracts the mean-zero component of its point mass by at most ${\rho }^t$ in Euclidean norm; Cauchy-Schwarz inequality then gives total variation distance at most $\frac{1}{2}\sqrt{N}{\rho }^t$ from the uniform distribution. A bipartite graph has eigenvalue $-1$ and its non-lazy walk alternates sides, even if it has good edge expansion. The lazy walk $(I+P)/2$ has nonconstant eigenvalues between zero and $1-\delta /2$, resolving this periodicity. It is important to distinguish the gap $1-{\mu }_2$ controlling cuts from the absolute bound controlling non-lazy mixing.

Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus at least one qualifying list exists. Fix it once and for all.

Let $H$ be the Cayley graph on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled graph, allowing repeated edges and loops in this intermediate construction. Its characters $x\mapsto (-1{)}^{u\cdot x}$ form an orthogonal eigenbasis, with the displayed averages as normalized eigenvalues. Therefore $\rho (H)\le 1/10$. Each loop counts as one transition port; degrees here mean row sums of the adjacency matrix.

We next define the zig-zag product and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected graph $F$ gives an involution ${\mathrm{Rot}}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular graph $H_0$ has vertex set $[D_0]$, the product has vertices $(v,a)\in V(F)\times [D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ vertices, and has degree $d^2$.

Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of ${\mathrm{Rot}}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe operator is symmetric, so its mean-zero operator norm is bounded by this same quantity. No unproved product spectral estimate is needed.

Start with the loop-inclusive complete graph $G_0$ on $D$ vertices, whose normalized matrix is $J/D$ and whose nonconstant eigenvalues are all zero. Given a $D$-regular $G_t$, its two-step graph $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step edge by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the vertex set of the fixed graph $H$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/2$, since $(1/2{)}^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted edge expansion at least $D/4$ for every $G_t$.

To obtain ordinary simple graphs, delete loops and merge parallel edges. The maximum degree is at most $D$, and any one unordered vertex pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, givingThese simple graphs form an expander family. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive edge rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output edge. This is squaring and zig-zag iteration yields bounded-degree expanders. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the eigenvalues while the product restores a constant degree.