Выборка обхода расширителя

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

Заявление

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

(Известно что почти все траектории $y_{0},y_{1},\ldots ,y_{k-1}$ сходится к некоторой предельной точке, ${\textstyle \pi (A)}$, как ${\textstyle k\rightarrow }$${\textstyle \infty }$.)

Теорема утверждает, что для взвешенного графа $G=(V,E)$ и случайное блуждание $y_{0},y_{1},\ldots ,y_{k-1}$ где $y_{0}$ выбирается начальным распределением ${\textstyle \mathbf {q} }$, для всех $\gamma >0$, мы имеем следующую оценку:

$\Pr \left[{\bigg |}{\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})-\pi (A){\bigg |}\geq \gamma \right]\leq Ce^{-{\frac {1}{20}}(\gamma ^{2}(1-\lambda _{2})k)}.$

Где $C$ зависит от $\mathbf {q} ,G$ и $A$.

Теорема дает оценку скорости сходимости к $\pi (A)$ относительно длины случайного блуждания, что дает более эффективный метод оценки $\pi (A)$ по сравнению с независимой выборкой вершин $G$.

Доказательство

Для доказательства теоремы дадим несколько определений, за которыми последуют три леммы.

Позволять ${\it {{w}_{xy}}}$ быть весом края $xy\in E(G)$ и пусть ${\textstyle {\it {{w}_{x}=\sum _{y:xy\in E(G)}{\it {{w}_{xy}.}}}}}$ Обозначим через ${\textstyle \pi (x):={\it {{w}_{x}/\sum _{y\in V}{\it {{w}_{y}}}}}}$. Позволять ${\textstyle {\frac {\mathbf {q} }{\sqrt {\pi }}}}$ быть матрицей с записями ${\textstyle {\frac {\mathbf {q} (x)}{\sqrt {\pi (x)}}}}$ , и пусть ${\textstyle N_{\pi ,\mathbf {q} }=||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}}$.

Позволять $D={\text{diag}}(1/{\it {{w}_{i})}}$ и $M=({\it {{w}_{ij})}}$. Позволять ${\textstyle P(r)=PE_{r}}$ где ${\textstyle P}$ стохастическая матрица, ${\textstyle E_{r}={\text{diag}}(e^{r\mathbf {1} _{A}})}$ и ${\textstyle r\geq 0}$. Затем:

$P={\sqrt {D}}S{\sqrt {D^{-1}}}\qquad {\text{and}}\qquad P(r)={\sqrt {DE_{r}^{-1}}}S(r){\sqrt {E_{r}D^{-1}}}$

Где $S:={\sqrt {D}}M{\sqrt {D}}{\text{ and }}S(r):={\sqrt {DE_{r}}}M{\sqrt {DE_{r}}}$. Как $S$ и $S(r)$ симметричны, имеют действительные собственные значения. Поэтому, поскольку собственные значения $S(r)$ и $P(r)$ равны, собственные значения ${\textstyle P(r)}$ реальны. Позволять ${\textstyle \lambda (r)}$ и ${\textstyle \lambda _{2}(r)}$ быть первым и вторым по величине собственным значением ${\textstyle P(r)}$ соответственно.

Для удобства обозначений пусть ${\textstyle t_{k}={\frac {1}{k}}\sum _{i=0}^{k-1}\mathbf {1} _{A}(y_{i})}$, ${\textstyle \epsilon =\lambda -\lambda _{2}}$, ${\textstyle \epsilon _{r}=\lambda (r)-\lambda _{2}(r)}$, и пусть $\mathbf {1}$ быть вектором «все 1».

Лемма 1

$\Pr \left[t_{k}-\pi (A)\geq \gamma \right]\leq e^{-rk(\pi (A)+\gamma )+k\log \lambda (r)}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}$

Доказательство:

По Маркова неравенству

${\begin{alignedat}{2}\Pr \left[t_{k}\geq \pi (A)+\gamma \right]=\Pr[e^{rt_{k}}\geq e^{rk(\pi (A)+\gamma )}]\leq e^{-rk(\pi (A)+\gamma )}E_{\mathbf {q} }e^{rt_{k}}\end{alignedat}}$

Где $E_{\mathbf {q} }$ это ожидание $x_{0}$ выбрано в соответствии с распределением вероятностей $\mathbf {q}$. Поскольку это можно интерпретировать путем суммирования по всем возможным траекториям $x_{0},x_{1},...,x_{k}$, следовательно:

$E_{\mathbf {q} }e^{rt}=\sum _{x_{1},x_{2},...,x_{k}}e^{rt}\mathbb {q} (x_{0})\Pi _{i=1}^{k}p_{x_{i-1}x_{i}}=\mathbf {q} P(r)^{k}\mathbf {1}$

Объединение двух результатов доказывает лемму.

Лемма 2

Для $0\leq r\leq 1$,

$(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}\leq (1+r)N_{\pi ,\mathbf {q} }$

Доказательство:

В качестве собственных значений $P(r)$ и $S(r)$ равны,

${\begin{aligned}(\mathbf {q} P(r)^{k}\mathbf {1} )/\lambda (r)^{k}&=(\mathbf {q} P{\sqrt {DE_{r}^{-1}}}S(r)^{k}{\sqrt {D^{-1}E_{r}}}\mathbf {1} )/\lambda (r)^{k}\\&\leq e^{r/2}||{\frac {\mathbf {q} }{\sqrt {\pi }}}||_{2}||S(r)^{k}||_{2}||{\sqrt {\pi }}||_{2}/\lambda (r)^{k}\\&\leq e^{r/2}N_{\pi ,\mathbf {q} }\\&\leq (1+r)N_{\pi ,\mathbf {q} }\qquad \square \end{aligned}}$

Лемма 3

Если $r$ действительное число такое, что $0\leq e^{r}-1\leq \epsilon /4$,

$\log \lambda (r)\leq r\pi (A)+5r^{2}/\epsilon$

Краткое изложение доказательства:

Мы, Тейлор, расширяем ${\textstyle \log \lambda (y)}$ о точке ${\textstyle r=z}$ получить:

$\log \lambda (r)=\log \lambda (z)+m_{z}(r-z)+(r-z)^{2}\int _{0}^{1}(1-t)V_{z+(r-z)t}dt$

Где $m_{x}{\text{ and }}V_{x}$ являются первой и второй производными $\log \lambda (r)$ в $r=x$. Мы показываем, что $m_{0}=\lim _{k\to \infty }t_{k}=\pi (A).$ Затем мы докажем, что (i) ${\textstyle \epsilon _{r}\geq 3\epsilon /4}$ с помощью манипуляций с матрицами, а затем докажите (ii) $V_{r}\leq 10/\epsilon$ используя (i) и оценку Коши из комплексного анализа.

Результаты в совокупности показывают, что

${\begin{aligned}\log \lambda (r)=\log \lambda (0)+m_{0}r+r^{2}\int _{0}^{1}(1-t)V_{rt}dt\leq r\pi (A)+5r^{2}/\epsilon \end{aligned}}$

Построчное доказательство можно найти у Гилмана (1998) [1]

Доказательство теоремы

Объединив лемму 2 и лемму 3, получаем, что

$\Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+r)N_{\pi ,\mathbf {q} }e^{-k(r\gamma -5r^{2}/\epsilon )}$

Интерпретируя показатель степени в правой части неравенства как квадратичную величину $r$ и минимизируя выражение, мы видим, что

$\Pr[t_{k}-\pi (A)\geq \gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}$

Подобная граница

$\Pr[t_{k}-\pi (A)\leq -\gamma ]\leq (1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }e^{-k\gamma ^{2}\epsilon /20}$

выполняется, следовательно, установка $C=2(1+\gamma \epsilon /10)N_{\pi ,\mathbf {q} }$ дает желаемый результат.

Использование

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

Ссылки

• Аджтай, М.; Комлос, Дж.; Семереди, Э. (1987). «Детерминистическое моделирование в LOGSPACE». Материалы девятнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '87. АКМ . стр. 132–140. дои : 10.1145/28395.28410 . ISBN  0897912217 .
• Гиллман, Д. (1998). «Оценка Чернова для случайных блужданий по экспандерным графам». SIAM Journal по вычислительной технике . 27 (4). Общество промышленной и прикладной математики: 1203–1220. дои : 10.1137/S0097539794268765 . S2CID   26319459 .
• Дуб, Дж.Л. (1953), Стохастические процессы , том. Теорема 6.1, Уайли