Марковская цепь описывает то, что случайно перемещается между несколькими положениями, причём вероятность следующего перехода зависит только от текущего положения и никак не от того, каким путём в него попали. Андрей Марков предложил эту идею в 1906 году отчасти чтобы разрешить спор: считалось, что закон больших чисел требует независимых событий, а он хотел показать, что зависимые тоже могут ему подчиняться. Ради доказательства он подсчитал чередование гласных и согласных на двадцати тысячах букв «Евгения Онегина» — поэтому первым применением теории оказалась поэзия, а не физика.
Именно «беспамятность» такого процесса делает его поддающимся расчёту и приводит к замечательному результату. Если запустить большинство цепей надолго, доля времени, проведённого в каждом положении, устанавливается на определённых значениях, которые уже не зависят от точки старта, — это стационарное распределение. Насколько быстро это происходит — отдельный вопрос с вполне практическим ответом, а цепи, которые вообще не забывают начало, потому что жёстко ходят по кругу или застревают в тупике, как раз и составляют интересные исключения.
Идея подошла к огромному числу предметов: очереди у кассы, погода, настольные игры, кредитные рейтинги, износ оборудования, последовательности генов и поведение игрока, который делает ставки до разорения или до цели. Первоначальный алгоритм ранжирования Google рассматривал случайно кликающего посетителя как такую цепь и брал её стационарное распределение как меру важности страницы, а методы выборки, на которых держится значительная часть современной статистики и физики, намеренно строят цепь со стационарным распределением, равным искомому ответу, и просто дают ей поработать.