Markov chains & Monte Carlo

Replace an expectation you can't compute with an average over random draws. If $X_i$are i.i.d.,

The law of large numbers guarantees convergence; the CLT gives the $1/\sqrt{N}$ error bars. The remarkable part: that rate does not depend on the dimension. A grid costs$O(h^{-d})$ points to hold resolution $h$ in $d$dimensions; Monte Carlo doesn't care. This is the other side of the curse of dimensionality from the L² deep dive — when space is too big to grid, you sample it instead.

$\pi$ — darts. Throw points uniformly in the unit square; the fraction landing in the quarter disk $x^2+y^2\le 1$ is the area ratio$\pi /4$:

$e$ — uniforms until you cross 1. Let$N=\min \{n:U_1+\cdots +U_n>1\}$ with $U_i\sim \mathrm{Unif}(0,1)$. A small miracle: $\mathbb{E}[N]=e$. Average the stopping counts.

$\gamma$ — the Euler–Mascheroni constant. Use the integral identity and read it as an expectation over an exponential:

That expectation is worth seeing. The integrand $e^{-x}(-\ln x)$ is positive left of $x=1$ and slightly negative to the right; the small positive remainder is exactly$\gamma$. Slide the upper limit and watch the signed area settle onto it.

Simulation can estimate a number to many digits, but it can never prove that number is irrational — no finite sample distinguishes an irrational from a rational sitting nanometers away. This is a place to be honest: experiment suggests, proof decides. The proof is the classic descent — assume $\sqrt{2}=p/q$ in lowest terms, then

contradicting "lowest terms." What computation can show honestly: the continued fraction$\sqrt{2}=[1;2,2,2,\dots ]$ never terminates or falls into a rational, and by Weyl's theorem the fractional parts $\{n\sqrt{2}\}$ equidistribute on $[0,1)$ — something no rational multiple ever does. Evidence points; the argument settles it.

A Markov chain forgets everything but its current state:

The row-stochastic matrix $P$ pushes the distribution forward,${\pi }_{n+1}={\pi }_{n}P$. A stationary distribution is a fixed point,$\pi P=\pi$ — a left eigenvector with eigenvalue 1 (the spectral theme again). Under irreducibility and aperiodicity, the chain forgets its start entirely:${\pi }_n\to \pi$ regardless of where it began.

To sample a target $\pi$ you can only evaluate up to a constant, build a Markov chain whose stationary distribution is $\pi$, then run it. The trick that guarantees stationarity is detailed balance:

Metropolis–Hastings proposes a move and accepts it with probability

where only the ratio of $\pi$ appears, so the unknown normalizing constant cancels. This is the engine under Bayesian posteriors — the bridge to QBism and decision theory (P2): beliefs you can actually compute with, not just write down.

The $1/\sqrt{N}$ rate is slow — halving the error costs four times the samples. So sharpen the estimator, not the sample size:

• Importance sampling — draw where $f$ is large, reweight by the density ratio.
• Control variates — subtract a correlated quantity of known mean. The optimal coefficient is ${\beta }^{\star }=\mathrm{Cov}(f,g)/\mathrm{Var}(g)$ — the very projection from the L² deep dive.
• Antithetic variates — pair $U$ with $1-U$; the negative correlation cancels variance.
• Stratification — sample each region in proportion, removing between-stratum noise.
• Quasi-Monte Carlo — low-discrepancy sequences (Sobol, Halton) reach error $\sim (\log N{)}^d/N$, beating $1/\sqrt{N}$.

The building blocks underneath: inverse-transform sampling $X=F^{-1}(U)$ and rejection sampling — both ways of bending uniform noise into the shape you want.

An honest answer, since you asked. There is no standard "$q$-Monte Carlo," but the neighbors are real: quantum walks are the unitary cousin of the random walk, and quantum Monte Carlo is a genuine (and different) family of methods for sampling quantum systems in physics. So the random walk has a quantum analog; the Monte Carlo method doesn't have a clean $q$-deformation.

The $p$-adic side is firmer: p-adic (ultrametric) probability and random walks are a real, if specialized, field — p-adic Brownian motion, ultrametric diffusion, hierarchical relaxation (Vladimirov–Volovich–Zelenov; Khrennikov). Distances are non-Archimedean, so "nearby" means "in the same fine branch of a tree," and diffusion happens across that tree. It sits right next to the p-adic shelf in the program — Koblitz and friends — and it's where this deep dive quietly hands off to the number-theory thread.