PCP 7 — Expanders: góc nhìn xác suất

8.d. Spectral expanders và tốc độ hội tụ của random walks trên expanders

Trong bài này chúng ta sẽ chứng minh rằng một đồ thị có spectral gap lớn thì “tương đương” với tốc độ hội tụ của một random walk trên đồ thị càng cao. (Sở dĩ ta để tương đương trong ngoặc kép là vì một chiều chứng minh cần thay đổi đồ thị một chút.)

8.d.1. Random walk trên đồ thị $d$ -regular, điều kiện hội tụ

Hầu hết những kết quả ta sẽ chứng minh trong đề mục này đúng cho cả các đồ thị không regular, nhưng chúng ta chỉ phát triển các kết quả trên các đồ thị $d$ -regular cho tiện. Xét một đồ thị $d$ -regular $G$ với adjacency matrix $\bf A$ . Định nghĩa $\hat {\bf A} = \frac 1 d {\bf A}$ . Ma trận $\hat {\bf A}$ còn được gọi là normalized adjacency matrix, và nó cũng chính là transition probability matrix của chuỗi Markov trên đồ thị $G$ . Ở đây, chúng ta không cần biết lý thuyết về chuỗi Markov để hiểu bài này. Nếu bạn muốn biết thêm về chuỗi Markov thì tôi giới thiệu quyển Markov Chains của Norris. Về random walks trên các đồ thị thì bài này của Laci Lovasz là một bài tổng hợp tốt, và quyển sách của Doyle và Snell (miễn phí) là kinh điển, tuy hơi cũ.

Để bắt đầu một random walk trên một đồ thị thì trước hết ta chọn một đỉnh của đồ thị làm khởi điểm theo một phân bố xác suất $\pi = \pi^{(0)}$ nào đó: $\pi^{(0)}_v$ là xác suất mà đỉnh $v$ là đỉnh khởi đầu. Đương nhiên $0 \leq \pi^{(0)}_v \leq 1, \forall v$ và $\sum_v \pi^{(0)}_v = 1$ . Khi đang ở một đỉnh $v$ ở bước này thì đến bước kế tiếp ta chọn ngẫu nhiên một một đỉnh kề với $v$ (với xác suất $1/d$ ) và “bước qua” bên đó. Gọi $\pi^{(t)}$ là phân bố xác suất của random walk ở thời điểm $t$ , nghĩa là $\pi^{(t)}_v$ là xác suất mà chúng ta ở đỉnh $v$ sau $t$ bước. Dễ thấy rằng phân bố xác suất ở thời điểm $t+1$ là

$\displaystyle \pi^{(t+1)} = \hat {\bf A} \pi^{(t)}.$

Trong lý thuyết chuỗi Markov, phương trình trên gọi là phương trình Chapman-Kolmogorov, đơn giản là ứng dụng công thức tính conditional probability.

Bài tập: chứng minh công thức Chapman-Kolmogorov trên.

Bài tập: công thức có còn đúng không nếu đồ thị $G$ là đồ thị có hướng? Nếu không đúng thì phải sửa làm sao cho đúng?

Từ đó ta có:

$\displaystyle \pi^{(t)} = \hat {\bf A}^t \pi, \ \forall t \geq 0$

Như đã viết trong bài Trị đặc trưng và vector đặc trưng, hễ nhìn thấy lũy thừa của các ma trận, đặc biệt là các ma trận thực và đối xứng, thì ta phải nghĩ ngay đến các vector và trị đặc trưng. Gọi $\hat \lambda_1 \geq \dots \geq \hat \lambda_n$ là bộ eigenvalues của $\hat {\bf A}$ và $\lambda_1 \geq \dots \geq \lambda_n$ là bộ eigenvalues của $\bf A$ . Dễ thấy rằng $\hat \lambda_i = \frac 1 d \lambda_i$ , và hơn nữa $\hat \lambda_i$ và $\lambda_i$ có cùng các eigenvectors. Gọi các eigenvectors trực chuẩn tương ứng là ${\bf u}_1, \dots, {\bf u}_n$ . Trong bài PCP 6 chúng ta đã chứng minh rằng ${\bf u}_1 = {\bf 1}/\sqrt n$ .

Đến đây, biểu diễn $\pi$ thành tổ hợp tuyến tính của các vectors ${\bf u}_i$ , ta có $\pi = \sum_{i}\alpha_i {\bf u}_i$ , trong đó $\alpha_i = \langle \pi, {\bf u}_i \rangle$ . Từ đó, suy ra $\alpha_1 = 1/\sqrt n$ (Bài tập: tại sao?) và vì thế

$\displaystyle \pi^{(t)} = \hat {\bf A}^t\pi = \sum_i \alpha_i \hat {\bf A}^t {\bf u}_i = \sum_i \alpha_i \hat \lambda_i^t = \frac{\bf 1}{n} + \sum_{i=2}^n \alpha_i \hat \lambda_i^t$ .

Do đó, nếu $|\lambda_i|<1, \forall i \geq 2$ thì $\lim_{t \to \infty} \pi^{(t)} = \frac{\bf 1}{n}$ bất kể khởi điểm có phân bố gì. Chú ý rằng $\frac{\bf 1}{n}$ chính là cái phân bố đều (uniform distribution). Chúng ta vừa chứng minh được chiều thuận của định lý sau đây. Điều kỳ kiệu là chiều nghịch cũng đúng.

Điều kiện hội tụ của random walk trên đồ thị

Cho $G$ là một đồ thị $d$ -regular. Định nghĩa $\hat \lambda(G) = \max\{ |\hat \lambda_2|, |\hat \lambda_n| \}$ . Ta có $\hat \lambda(G) <1$ nếu và chỉ nếu

$\displaystyle \lim_{t \to \infty} \pi^{(t)} = \frac{\bf 1}{n}$ , bất kể phân bố khởi điểm là gì.

Chứng minh. Bây giờ chúng ta chứng minh chiều nghịch, nghĩa là nếu $\lim_{t \to \infty} \pi^{(t)} = \frac{\bf 1}{n}$ bất kể phân bố khởi điểm, thì $\hat\lambda(G)<1$ . Chỉ cần chứng minh $\hat \lambda_2<1$ và $\hat \lambda_n>-1$ là đủ. Từ bài PCP 6, và quan hệ $\hat \lambda_i = \frac 1 d \lambda_i$ , ta biết $\hat\lambda_2<1$ nếu và chỉ nếu $G$ là đồ thị liên thông, và $\hat \lambda_n>-1$ nếu và chỉ nếu $G$ không phải là đồ thị bipartite.

Trước hết, giả sử $G$ không liên thông, ta sẽ chứng minh rằng tồn tại hai phân bố khởi điểm khác nhau làm cho random walk hội tụ về hai trạng thái cân bằng khác nhau. Các bài tập sau đây “mạnh” hơn cần thiết, nhưng có giá trị mô phạm; các bạn không quen với chuỗi Markov nên làm thử:

Bài tập: Giả sử tồn tại vector $\pi = \lim_{t \to \infty} \pi^{(t)}$ . Chứng minh rằng $\pi$ là một distribution, nghĩa là $\sum_i \pi_i=1$ và $0 \leq \pi_i \leq 1$ . Ngoài ra, chứng minh rằng $\hat {\bf A}\pi = \pi$ , nghĩa là $\pi$ là một $1$ -eigenvector. Một phân bố $\pi$ thỏa mãn $\hat {\bf A}\pi = \pi$ thì được gọi là một phân bố cân bằng.

Bài tập: dùng định lý Perron-Frobenius, chứng minh rằng luôn tồn tại một phân bố cân bằng $\sigma$ , cho dù $G$ không phải là đồ thị regular.

Bài tập: gọi $\sigma$ là một phân bố cân bằng. Chứng minh rằng nếu $\pi^{(0)} = \sigma$ , nghĩa là nếu trạng thái khởi đầu là một phân bố cân bằng, thì $\lim_{t \to \infty} \pi^{(t)} = \sigma$ .

Như vậy, đến đây ta chỉ cần chứng minh rằng nếu $G$ không liên thông thì có ít nhất hai phân bố cân bằng khác nhau là được. Nếu $G$ không liên thông thì $1$ -eigenspace của $\hat {\bf A}$ có dimension $\geq 2$ . Đặt $\sigma = \frac{\bf 1}{n}$ thì đây là một phân bố cân bằng do $G$ là $d$ -regular. Gọi ${\bf y}$ là một $1$ -eigenvector bất kỳ độc lập tuyến tính với $\sigma$ . Với bất kỳ hệ số $c$ nào, ta có $\hat{\bf A}(c \sigma + {\bf y}) = c\sigma + {\bf y}$ bởi vì $\sigma$ cũng là một $1$ -eigenvector. Với $c$ đủ lớn thì $c\sigma+{\bf y} \geq 0$ . Sau khi normalize, ta kết luận rẳng tồn tại một phân bố cân bằng $\tau = \alpha(c \sigma + {\bf y})$ . Phân bố này khác $\sigma$ bởi vì $\sigma$ và $\bf y$ là độc lập tuyến tính.

Kế tiếp, ta chứng minh rằng nếu $G$ là bipartite thì giới hạn $\displaystyle \lim_{t \to \infty} \pi^{(t)}$ không luôn tồn tại. Giả sử $G=(U,V;E)$ . Do $G$ là $d$ -regular, dễ thấy rằng $|U|=|V|$ . Gọi $\pi^U$ là phân bố mà các đỉnh trong $U$ được gán xác suất $1/|U|$ , và $\pi^V$ là phân bố mà các đỉnh trong $V$ được gán xác suất $1/|V|$ . Nếu ta bắt đầu random walk bằng $\pi^U$ thì random walk sẽ giao động giữa $\pi^U$ và $\pi^V$ , không hội tụ.

QED

8.d.2. Random walk trên đồ thị $d$ -regular, tốc độ hội tụ

Chúng ta quan tâm hơn đến tốc độ hội tụ của random walk. Làm thế nào để đo tốc độ hội tụ về phân bố đều ${\bf 1}/n$ ? Về mặt xác suất, hàm khoảng cách (distance function) tự nhiên nhất có lẽ là total variation distance. Cho hai phân bố $P$ và $Q$ trên một không gian xác suất hữu hạn $\Omega$ , total variation distance giữa $P$ và $Q$ là $\max_{S \subset \Omega} |P(S) - Q(S)|$ . Khi $\Omega$ là hữu hạn, không khó chứng minh được rằng $\max_{S \subset \Omega} |P(S) - Q(S)| = \frac 1 2 \|P-Q\|_1$ . (Bài tập: chứng minh điều này, nghĩa là total variation distance bằng một nửa $l_1$ -norm, khi $\Omega$ hữu hạn.) Như vậy, để đo tốc độ hội tụ, chúng ta có thể đo khoảng cách $\|\pi^{(t)} - {\bf 1}/n\|_1$ xem nó tiến đến $0$ nhanh như thế nào.

Định lý. (Hội tụ theo $l_1$ ) Định nghĩa ${\bf u} = {\bf 1}/n$ cho tiện. Ta có $\|\pi^{(t)}-\mathbf u\|_1 \leq \sqrt n \hat\lambda^t$

Nhờ bất đẳng thức Cauchy-Schwarz, chúng ta chỉ cần chứng minh định lý sau đây là đủ

Định lý (Hội tụ theo $l_2$ ) $\|\pi^{(t)}-\mathbf u\|_2 \leq \hat\lambda^t$

Chứng minh. Chú ý rằng $\|\pi^{(t)}-\mathbf u\|_2 = \|\hat{\mathbf A}^t\pi^{(0)} - \mathbf u\|_2 = \|\hat{\mathbf A}^t(\pi^{(0)} - \mathbf u)\|_2 = \|\hat{\mathbf A}^t\mathbf v\|_2$ . Trong đó, $\mathbf v = \pi^{(0)} - \mathbf u$ vuông góc với $\mathbf u$ and $\|\mathbf v\|_2 \leq 1$ . (Bài tập: tại sao ${\bf v}$ vuông góc với ${\bf u}$ và có chiều dài $\leq 1$ ?). Kế hoạch của chúng ta sẽ là chứng minh rằng

$\displaystyle \| \hat {\bf A}^t {\bf v}\|_2 \leq \hat \lambda \| \hat {\bf A}^{t-1} {\bf v}\|_2 \leq \dots \leq \hat\lambda^{t-1} \| \hat {\bf A} {\bf v}\|_2 \leq \hat\lambda^t \|{\bf v}\|_2 \leq \hat\lambda^t$

Để chứng minh điều này, trước hết ta chứng minh rằng mỗi lần ta nhân $\hat{\mathbf A}$ với một vector $\mathbf y$ vuông góc với $\mathbf u$ , chúng ta “co rút” chiều dài của $\mathbf y$ lại một tỉ lệ ít nhất là $\hat\lambda$ . Cụ thể hơn, xét vector $\bf 0 \neq y \perp u$ thì

$\displaystyle \|\hat{\bf A}{\bf y}\|_2 = \sqrt{\langle \hat{\bf A}{\bf y}, \hat{\bf A}{\bf y} \rangle} = \sqrt{\langle {\bf y}, \hat{\bf A}^2{\bf y} \rangle} = \|{\bf y}\|_2 \sqrt{R_{\hat{\bf A}^2}({\bf y})} \leq \hat \lambda \|{\bf y}\|_2$

Cần giải thích bất đẳng thức cuối cùng rõ hơn một chút. Lưu ý rằng $R_{\hat{\bf A}^2}({\bf y})$ là cái Rayleigh quotient của ma trận $\hat{\bf A}^2$ . Các eigenvalues của ma trận này là bình phương các eigenvalues của $\hat{\bf A}$ . Dễ thấy rằng $\hat\lambda^2$ là eigenvalue lớn nhì của $\hat{\bf A}^2$ . Từ đó ta có bất đẳng thức cuối, vì $\bf y$ vuông góc với eigenvector thứ nhất. (Nhớ lại định lý tính eigenvalues bằng Rayleigh quotients trong bài trước.)

Bài tập: chứng minh rằng với mọi số nguyên $j \geq 0$ thì vector ${\bf y} = \hat{\bf A}^j{\bf v}$ vuông góc với $\bf u$ .

Từ kết quả bài tập, áp dụng bất đẳng thức $\|\hat{\bf A}{\bf y}\|_2 \leq \hat \lambda \|{\bf y}\|_2$ đệ qui $t$ lần là xong.

QED

8.d.3. Tốc độ hội tụ và spectral expanders

Chúng ta đã thấy rằng $\hat\lambda(G)$ càng xa $1$ thì tốc độ hội tụ của random walk càng lớn.

Định nghĩa. (Spectral expander) Một $(n,d,\alpha)$ -spectral expander là một đồ thị $d$ -regular $G$ có $n$ đỉnh thỏa $\hat \lambda(G) \leq \alpha$ . Ta cần $(n,d,\alpha)$ -spectral expanders với $\alpha$ càng nhỏ càng tốt.

Nếu $G$ là một $(n,d,\alpha)$ -spectral expander với $\alpha < 1$ là một hằng số thì $d-\lambda_2 \geq d\alpha$ ; do đó spectral gap của $G$ cũng lớn.

Ngược lại, nếu $G$ có spectral gap bị chặn dưới bởi một hằng số, ví dụ $d-\lambda_2 \geq \beta>0$ , thì … chưa chắc $G$ đã là một spectral expander; nguyên nhân chính là $d-\lambda_2>0$ không nhất thiết dẫn tới $\hat\lambda_n>-1$ . Nói cách khác, một đồ thị liên thông thì không liên quan đến tính bipartite của nó. May mà có một cách rất đơn giản để “sửa” $G$ lại để cho nó chắc chắn không là bipartite. Chúng ta thêm các self-loops vào tất cả các đỉnh của $G$ . Nói các khác, cộng $1$ vào mỗi entry trên đường chéo của ${\bf A}$ . Gọi $\lambda'_i$ là các trị đặc trưng mới (sau khi thêm self-loops), có thể thấy rằng $\lambda'_i = \lambda_i+1, \forall i$ và $\hat \lambda'_i = \frac{\lambda_i+1}{d+1}$ . Từ đó, $\hat \lambda'_2 \leq \frac{d+1-\beta}{d+1}$ . Và, $\hat \lambda'_n \geq \frac{-d+1}{d+1}$ . Do đó, $\hat\lambda'$ cách “xa” $1$ và $G$ (sau “sửa chữa”) là một spectral expander.

8.e. “Giam cầm” random walk trên expanders rất là khó.

Bây giờ chúng ta thảo luận một ứng dụng rất quan trọng của expanders từ góc nhìn xác suất. Ứng dụng này đại khái nói rằng, xác suất mà một random walk ở mãi trong một tập đỉnh nhỏ sẽ giảm theo hàm mũ.

Gọi $G$ là một $(n,d,\alpha)$ -spectral expander, và $B$ là một tập đỉnh của $G$ sao cho $|B| \leq \beta n$ . Giả sử ta thực hiện một random walk trên đồ thị $G$ , bước $t$ bước, với phân bố khởi điểm là phân bố đều (uniform distribution). Xác suất mà chúng ta không thăm đỉnh nào ngoài $B$ là bao nhiêu?

Định lý (Khó “giam cầm” random walk trên expander). Gọi $(B,t)$ là sự kiện mà cái random walk bị giam giữ trong tập $B$ trong toàn bộ $t$ bước. Ta có, $\text{Prob}\left[(B,t)\right] \leq \sqrt\beta (\alpha + (1-\alpha)\beta)^t$ . Do đó, nếu $\alpha, \beta < 1$ thì xác suất “giam cầm” này giảm theo hàm mũ.

Chứng minh. Gọi $\mathbf P = (p_{ij})$ là ma trận “chiếu vào $B$ “, nghĩa là $p_{ii} = 1, \forall i \in B$ và $p_{ij}=0$ với mọi $i,j$ khác. Ta có:

$\displaystyle \text{Prob}\left[(B,t)\right] = \|(\mathbf{P\hat A})^t\mathbf{Pu}\|_1 = \|(\mathbf{P\hat AP})^t\mathbf{Pu}\|_1 \leq \sqrt n \|(\mathbf{P\hat AP})^t\mathbf{Pu}\|_2$

Bài tập: chứng minh đẳng thức thứ nhất.

Đẳng thức thứ hai là do ma trận $\mathbf P$ là idempotent. Bất đẳng thức cuối cùng là theo Cauchy-Schwarz. Để chặn $\text{Prob}\left[(B,t)\right]$ chúng ta cần biết ma trận $\mathbf{M = P\hat AP}$ co rút chiều dài một vector cỡ bao nhiêu sau mỗi lần nhân ma trận này vào vector. (Cái “mẹo” này chúng ta đã dùng trong phần trước.) Với mỗi vector $\mathbf y \neq {\bf 0}$ , ta có

$\displaystyle \frac{\|\mathbf{My}\|}{\|\mathbf y\|} = \sqrt{R_{\bf M^2}({\bf y})} \leq \sqrt{\lambda_1({\bf M}^2)} = \lambda_1({\bf M}) = \max_{\mathbf z\neq \mathbf 0} \frac{\mathbf z^T\mathbf{Mz}}{\mathbf z^T\mathbf z}$

Đến đây, xét một vector $\mathbf z \neq {\bf 0}$ bất kỳ. Đặt $\mathbf{x = Pz}$ . Thì, $\mathbf z^T\mathbf{Mz} = \mathbf z^T\mathbf{P\hat APz} = \langle \mathbf{\hat Ax, x} \rangle$ . Trước hết, biểu diễn $\mathbf x$ thành tổ hợp tuyến tính của các eigenvectors trực chuẩn của $\mathbf{\hat A}$ : $\mathbf x = c_1\mathbf u_1 + c_2 \mathbf u_2 + \cdots c_n \mathbf u_n$ . Định nghĩa thành phần song song $\mathbf x^{\|} = c_1\mathbf u_1$ với eigenvector thứ nhất, và thành phân vuông góc $\mathbf x^{\perp} = \mathbf{x-x^{\|}}$ . Ta có,

$\displaystyle \langle \mathbf{\hat Ax, x} \rangle = \langle \mathbf{\hat A x^{\|}} + \mathbf{\hat A x^{\perp}}, \mathbf x^{\|} + \mathbf x^{\perp} \rangle = \|\mathbf x^{\|}\|^2 + \langle \mathbf{\hat A x^\perp, x^\perp} \rangle$

Cái mẹo lần trước cho ta:

$\displaystyle \langle \mathbf{\hat A x^\perp, x^\perp} \rangle = \|\mathbf x^\perp\|^2 \frac{\langle \mathbf{\hat A x^\perp, x^\perp} \rangle}{\|\mathbf x^\perp\|^2} \leq \hat\lambda \|\mathbf x^\perp\|^2 \leq \alpha \left( \|{\bf x}\|^2 - \|\mathbf x^{\|}\|^2\right)$

Áp dụng bất đẳng thức Cauchy-Schwarz, ta có $\|\mathbf x^{\|}\|^2 = c_1^2 = \langle \mathbf x, \mathbf u_1\rangle^2 \leq \beta \|\mathbf x\|^2$ , và do đó

$\displaystyle \langle \mathbf{\hat Ax, x} \rangle \leq \alpha\|\mathbf x\|^2 + (1-\alpha)\|\mathbf x^\|\|^2 \leq (\alpha + (1-\alpha)\beta)\|\mathbf x\|^2 \leq (\alpha + (1-\alpha)\beta)\|\mathbf z\|^2$

Vì thế, mỗi lần chúng ta nhân $\mathbf M$ vào vector $\mathbf y$ (có nghĩa là áp dụng phép biến đổi tuyến tính tương ứng vào $\bf y$ ) chúng ta giảm chiều dài của $\bf y$ một tỉ lệ ít nhất là $(\alpha + (1-\alpha)\beta)$ . Chúng ta sẽ áp dụng $t$ lần, và vector đầu tiên $\mathbf{Pu}$ có chiều dài $\sqrt{\beta/n}$ . Định lý đã được chứng minh xong.

QED

Lần tới, chúng ta sẽ xét một vài ví dụ về ứng dụng của định lý trên và của expanders trong việc tiết kiệm random bits và khuếch đại gap trong các PCP reductions.

PCP 7 — Expanders: góc nhìn xác suất

One Comment

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý