Розглянемо ненаправленої регулярний (у кожної вершини однакова ступінь) зв'язний граф. Нас буде цікавити поведінка випадкових блукань на (випадкове блукання - це такий простий процес: встає в якусь вершину, а потім кілька разів вибираємо випадкове ребро і йдемо по ньому). Нехай - розподіл ймовірностей на вершинах. Як же виглядає розподіл ймовірностей після одного кроку випадкового блукання? Дуже просто: це буде вектор, де - матриця суміжності, поділена на.
Так як регулярний, то стаціонарний розподіл випадкового блукання буде рівномірним. У відповідного вектори всі компоненти будуть рівні - будемо позначати його.
Ми будемо цікавитися швидкістю збіжності розподілу на вершинах до рівномірного. Наприклад, нехай ми хочемо оцінити. Для цього розглянемо наступну важливу характеристику:
Виявляється, що чим менше, тим швидше розподіл сходиться до рівномірного. Але для початку давайте встановимо зв'язок між і власними числами.
Так як симетрична, то у неї є ортонормованій базис з власних векторів. Позначимо його, а відповідні власні числа. Будемо вважати, що.
Матриця стохастична (всі елементи невід'ємні, сума будь-якого рядка і будь-якого стовпчика - одиниця), а у стохастичних матриць, як нескладно зрозуміти, власні числа по модулю не перевищують. Ми значить, що у є нерухома точка - вектор. Таким чином, можна вважати, що і.
Виявляється, що . Дійсно, підпростір векторів, які ортогональні одно лінійної оболонці. А розтягує вектори з цього підпростору не більше, ніж на.
Тепер займемося оцінкою швидкості збіжності розподілу до рівномірного (). Так як - розподіл ймовірностей, то можна уявити його у вигляді, де. Тепер зробимо таку просту оцінку:
Останній перехід вірний, так як підпростір векторів, ортогональних, єінваріантні для. Залишилося помітити, що так як, то, а, значить,.
Таким чином, отримуємо таку оцінку:
.
Отже, якщо ми хочемо довести, що випадкове блукання швидко сходиться до рівномірного розподілу, то треба доводити, що досить мало.
Виявляється, що вірно таке твердження: якщо у зв'язкового графа в кожній вершині є петля, то (ми доведемо цей факт в наступному пості). Звідси нескладно отримати, що випадкове блукання довжини з високою ймовірністю відвідує всі вершини графа.