Отбор проб на эспандере - Expander walk sampling

в математический дисциплина теория графов, то теорема выборки обхода расширителя утверждает, что отбор проб вершины в график расширителя делая случайная прогулка почти так же хорош, как выборка вершин независимо из равномерное распределение.Самая ранняя версия этой теоремы принадлежит Айтай, Комлос и Семереди (1987), а более общая версия обычно приписывается Гиллман (1998).

Заявление

Позволять ${displaystyle G=(V,E)}$ быть расширительным графом с нормализованное второе по величине собственное значение ${displaystyle lambda }$. Позволять ${displaystyle n}$ обозначим количество вершин в ${displaystyle G}$. Позволять ${displaystyle f:Vightarrow [0,1]}$ - функция на вершинах ${displaystyle G}$. Позволять ${displaystyle mu =E[f]}$ обозначают среднее значение ${displaystyle f}$, т.е. ${displaystyle mu ={frac {1}{n}}sum _{vin V}f(v)}$. Тогда, если мы позволим ${displaystyle Y_{0},Y_{1},ldots ,Y_{k}}$ обозначим вершины, встречающиеся в ${displaystyle k}$-шаговое случайное блуждание по ${displaystyle G}$ начиная со случайной вершины ${displaystyle Y_{0}}$, имеем для всех ${displaystyle gamma >0}$:

${displaystyle Pr left[{frac {1}{k}}sum _{i=0}^{k}f(Y_{i})-mu >gamma ight]leq e^{-Omega (gamma ^{2}(1-lambda )k)}.}$

Здесь ${displaystyle Omega }$ скрывает абсолютную константу ${displaystyle geq 1/10}$. Аналогичная оценка сохраняется и в другом направлении:

${displaystyle Pr left[{frac {1}{k}}sum _{i=0}^{k}f(Y_{i})-mu <-gamma ight]leq e^{-Omega (gamma ^{2}(1-lambda )k)}.}$

Использует

Эта теорема полезна для уменьшения случайности при изучении дерандомизация. Выборка из обхода расширителя является примером эффективного пробоотборник. Обратите внимание, что количество биты используется при отборе проб ${displaystyle k}$ независимые образцы из ${displaystyle f}$ является ${displaystyle klog n}$, тогда как если мы выбираем из бесконечного семейства расширителей постоянной степени, это стоит только ${displaystyle log n+O(k)}$. Такие семейства существуют и могут быть эффективно построены, например в Графики Рамануджана из Любоцкий -Филлипс-Сарнак.

Примечания

Рекомендации

• Ajtai, M .; Komlós, J .; Семереди, Э. (1987). «Детерминированное моделирование в LOGSPACE». Материалы девятнадцатой ежегодной конференции ACM по теории вычислений - STOC '87. ACM. С. 132–140. Дои:10.1145/28395.28410. ISBN  0897912217.
• Гиллман, Д. (1998), "Граница Чернова для случайных блужданий на расширительных графах", SIAM Журнал по вычислениям, Общество промышленной и прикладной математики, 27 (4): 1203–1220, Дои:10.1137 / S0097539794268765, S2CID  26319459

внешняя ссылка

• Доказательства теоремы об отсчете блуждания расширителя. [1] [2]