CS Compendium · Part II — Discrete Mathematics, Logic & Probability for CS
The discrete and probabilistic mathematics computer science actually runs on: counting and structure, logic, and the stochastic processes that let a machine predict. This part is seeded from the strand with the most immediate gravity for the Stack — Markov chains — because ranking (search), sampling (probabilistic estimates), and sequence prediction all reduce to the same object: a memoryless walk and its stationary distribution.
Why this strand is the seed
A blank "all of discrete math" tree would be a skeleton. Following the compendium's discipline — grow from real gravity, don't fabricate breadth — Part II starts where the Stack pulls: the Markov-chain family. It underpins Hub / kode-rag search (PageRank-style ranking), any probabilistic estimate in the data and AI layers (Monte Carlo / MCMC), and connects directly to the AI Compendium's language-model lineage. The topic is also the subject of a widely-shared Veritasium essay ("the strange math that predicts almost anything"), which makes it a natural, self-contained first chapter set.
The map of this part
| Doc | Content | Status |
|---|---|---|
01-markov-chains-and-stochastic-prediction |
The Markov–Nekrasov feud, the law of large numbers for dependent events, the Eugene Onegin analysis, the formal chain (transition matrix, memorylessness, Chapman–Kolmogorov), stationary distributions & the ergodic theorem, mixing time & the "seven shuffles" cutoff | seeded (real content) |
02-monte-carlo-and-mcmc |
Estimation by random sampling; the Manhattan-Project origin (Ulam, von Neumann, ENIAC); MCMC, Metropolis, Metropolis–Hastings, Gibbs; why it samples nearly every probabilistic model | seeded (real content) |
03-pagerank-and-the-web-as-a-markov-chain |
The random surfer, PageRank as a stationary distribution, damping/teleportation & Perron–Frobenius, power iteration; why it beat keyword search | seeded (real content) |
04-graphs-and-combinatorics |
Counting, graphs, recurrences | planned |
05-logic-for-cs |
Propositional/first-order logic, proof, SAT | planned |
Reference vs decision (no duplication)
This part holds knowledge ("what the mathematics says"). A Koder Stack decision that stands on it — which ranking signals kode-rag folds in, which sampler a probabilistic component uses — lives in engineering canon (an RFC or component ticket) that cites the section here. One fact, one home.