Семплирование экспандера

---

В математической дисциплине теории графов теорема выборки экспандерного блуждания интуитивно утверждает, что выборка вершин в графе-расширителе путем выполнения относительно короткого случайного блуждания может имитировать выборку вершин независимо от равномерного распределения . Самая ранняя версия этой теоремы принадлежит Ajtai, Komlós & Szemerédi (1987) , а более общая версия обычно приписывается Gillman (1998) .

Позвольте быть n-вершинным расширительным графом с положительно взвешенными ребрами, и пусть . Позвольте обозначить стохастическую матрицу графа, и пусть быть вторым по величине собственным значением . Позвольте обозначать вершины, встречающиеся в шаге случайного блуждания на старте в вершине , и позвольте . Где${\ Displaystyle G = (В, Е)}$${\ Displaystyle А \ подмножество V}$${\ Displaystyle Р}$${\ Displaystyle \ лямбда _ {2}}$${\ стиль текста Р}$${\ displaystyle y_ {0}, y_ {1}, \ ldots, y_ {k-1}}$${\ Displaystyle (к-1)}$${\ Displaystyle г}$${\ Displaystyle у_ {0}}$${\ textstyle \ пи (А): =}$ ${\ displaystyle \ lim _ {k \ rightarrow \ infty} {\ frac {1} {k}} \ sum _ {i = 0} ^ {k-1} \ mathbf {1} _ {A} (y_ {i })}$${\ textstyle \ mathbf {1} _ {A} (y) {\ begin {case} 1, & {\ text {if}} y \ in A \\ 0, & {\ text {иначе}} \ end { случаи}}}$

---