Hi, I'm Manan. I write up what I'm learning — mostly reinforcement learning, learning over graphs, and Bayesian machine learning. These are working notes, so expect proofs, algorithms, and code alongside the prose.
Exact inference in a graphical model is, in the worst case, intractable — yet for many graphs we can compute marginals efficiently by pushing sums inside products. This post builds variable elimination from first principles: the factor algebra, the elimination ordering, a correctness proof, and a small reference implementation you can fold open below.
There's really only one idea here: every concentration bound is one of two moves — bound a moment generating function, or turn your quantity into a sum of martingale differences and bound MGFs one coordinate at a time. A guided tour from Markov and Chernoff through Hoeffding, Bennett, and Bernstein; negative association and limited independence; martingales, Azuma, Freedman, and McDiarmid; and finally the stochastic travelling salesman problem, where each tool is stress-tested and most of them fail.