Blog
No posts match that tag.
-
The leading digit of a power of two
Posted on:Thirty of the first hundred powers of two begin with 1. The limiting frequency of leading digit d is log10(1 + 1/d), by Weyl equidistribution; scale invariance extends the law to Benford.
-
Percolation
Posted on:Keep each edge of a grid with probability p and ask whether a path crosses the grid. The answer flips at a sharp threshold, exactly 1/2 on the square lattice by self-duality.
-
The curve of fastest descent
Posted on:The wire carrying a sliding bead between two points in the least time is a cycloid arc, not the straight line. Optics finds it, convexity proves it, and the same arc is the tautochrone.
-
Euler's identity
Posted on:e^{iπ} + 1 = 0 is the θ = π case of Euler's formula e^{iθ} = cos θ + i sin θ, the point on the unit circle at angle θ. Three derivations: geometric, as a limit, and by power series.
-
Shattering and the VC dimension
Posted on:The VC dimension of a class of yes/no rules is the largest set of points it can label in every way. Past it, the labelings stop doubling, and that single integer governs learnability.
-
The Hanson–Wright inequality
Posted on:A quadratic form in independent random variables concentrates around the trace: a Gaussian tail near the mean via the Frobenius norm, an exponential tail further out via the operator norm.
-
Covering the sphere with ε-nets
Posted on:An ε-net replaces the sphere by finitely many directions, so a supremum over all unit vectors reduces to a finite union bound. Worked out on the operator norm of a random matrix.
-
Sudakov minoration, or how big a maximum must be
Posted on:Sudakov minoration lower-bounds the expected maximum of many Gaussians: if no two are too alike, the maximum is at least of order ε√(log N). The engine behind many impossibility proofs.
-
Bias-variance is a Pythagorean decomposition
Posted on:MSE = bias² + variance is the Pythagorean theorem in L²: a constant bias and a mean-zero residual are orthogonal, so their squared lengths add.
-
Voronoi tessellations and Lloyd's algorithm
Posted on:Generators partition the plane into cells, each closer to its generator than to any other. Lloyd's algorithm moves each generator to its cell's centroid and converges to k-means.
-
Pólya's recurrence theorem
Posted on:Simple random walk returns to the origin with probability one in one and two dimensions, but not in three. The transition reduces to the convergence of a single series.
-
High-dimensional Gaussians live on a sphere
Posted on:The bell-curve picture says Gaussian samples live near the mean. In high dimensions almost all the mass lies in a thin shell at radius √d: density and mass are not the same thing.
-
Central Limit Theorem - why sums become Gaussian
Posted on:Adding random variables convolves their densities, and convolution smooths. A geometric look at the central limit theorem, with a slider over the number of summands.
-
Why hypercubes look spiky
Posted on:Counting the corners of an n-cube by Hamming weight gives a binomial distribution; plotted as a cross-section, it recovers the spiky cube of the textbooks.
-
Heisenberg uncertainty as Fourier duality
Posted on:The uncertainty principle is not a measurement artifact but a property of any wave: a packet narrow in x is spread in p, and σx · σp ≥ ℏ/2 with equality exactly for Gaussians.
-
The 100 prisoners problem
Posted on:100 prisoners each seek their own number in 100 boxes, opening at most 50. Random guessing succeeds once in a nonillion; following cycles succeeds about 31% of the time.
-
Optimal message passing on sparse graphs
Posted on:Our NeurIPS 2023 paper: the asymptotically Bayes-optimal classifier for node classification on sparse contextual stochastic block models, and what it implies for graph neural networks.
-
Marchenko-Pastur and the Wigner semicircle
Posted on:The eigenvalue histogram of a large random matrix converges to a deterministic shape: Marchenko-Pastur for sample covariance matrices, the Wigner semicircle for symmetric i.i.d. entries.
-
Stein's paradox
Posted on:In three or more dimensions the sample mean is dominated everywhere by a shrinkage estimator. The reason is the Gaussian shell, and the idea is a precursor of ridge regression.
-
The Newton fractal
Posted on:Newton's method on a polynomial is a dynamical system on the complex plane: almost every start converges to some root, and the basins of attraction have fractal boundaries.
-
Nearest neighbor breaks in high dimensions
Posted on:In high dimensions, all pairwise distances become essentially equal. Nearest and farthest neighbor are no longer meaningfully different. A short geometric tour of the curse of dimensionality.
-
Effects of graph convolutions in multi-layer networks
Posted on:Our ICLR 2023 paper: graph convolutions provably lower the feature-signal threshold for node classification, and two convolutions help much more than one.
-
Fast and online palindrome counting
Posted on:An efficient algorithm for online palindrome counting using the palindrome tree of Rubinchik and Shur: the problem, the data structure, and the implementation.
-
Lunch with Donald Knuth
Posted on:Reflections on a lunch meeting with Donald Knuth. Covers his thoughts on P vs NP, advice on life and curiosity, and his recent mathematical interests in families of sets.
-
An analogy for the Doppler effect
Posted on:A simple analogy to explain the Doppler effect using the concept of throwing balls between two people. Designed to make the physics concept intuitive and accessible to a layperson.
-
St. Petersburg paradox
Posted on:A coin-toss game whose expected winnings are infinite, and why nobody would pay much to play: expectation against intuition, resolved by practical constraints.
-
Common join algorithms
Posted on:An overview of common join algorithms used in database systems, including Nested Loop, Hash Join, and Sort-Merge Join. Explains the logic, implementation details, and time complexities of each.
-
Implementing PEGASOS
Posted on:A detailed guide on implementing PEGASOS (Primal Estimated sub-GrAdient SOlver for SVM). Explains the mathematical derivation, the stochastic gradient descent approach, and the algorithm's steps.
-
Weird but awesome Javascript
Posted on:The Javascript runtime from the inside: the single thread, the call stack, the event loop, and the callback queue that together handle asynchronous work.
-
Some more #P complete problems
Posted on:A discussion on #P-Complete problems, specifically #SAT and counting 3-colorings in a graph. Includes proofs of their completeness and relevant reductions.
-
The complexity class of #P problems
Posted on:An in-depth look at the complexity class #P, based on Valiant's work. Focuses on the problem of computing the permanent of a binary matrix.
-
Machine level obfuscation
Posted on:A demonstration of how to obfuscate strings in C using floating-point numbers and machine endianness. Includes a code example that prints "ILOVEYOU" through seemingly random double values.
-
First interview experience
Posted on:A personal account of my first face-to-face interview experience at Microsoft. Covers the written rounds, technical questions on linked lists and binary trees, and the final interview rounds.