Markov Chains Are the Original Language Models (elijahpotter.dev)

This piece repurposes a student-era essay arguing that Markov chains are the “original” language models and demonstrates a toy auto-completion system implemented in Rust and compiled to WebAssembly. The author frames the exploration through a personal AI-hype arc — from fascination to skepticism to wanting to rebuild from first principles — then walks through how a simple Markov approach can predict next words and be used for autocomplete. The write-up is both a primer and a cautionary tale: Markov models are interpretable, lightweight, and easy to run locally, but they have hard limits when used for free-form text generation. Technically, the implementation tokenizes text into a vocabulary (map word -> index), counts transitions between successive tokens (stored in HashMaps for speed), and converts those counts into a column-stochastic transition matrix by normalizing columns with their sums (equivalently multiplying by an inverse-diagonal matrix). Predicting the next word is just multiplying a one-hot vector (current word) by the transition matrix; multi-step forecasts use repeated multiplication or matrix exponentiation. The article highlights the central limitation: Markov chains converge to a stationary distribution, so naive sampling quickly loses diversity. A simple randomized diagonal tweak failed in the author’s experiments, underscoring why higher-order models, longer contexts, or neural approaches are needed for coherent, non-convergent generation despite the pedagogical and practical value of Markov baselines.