EngineeringMathmatics Chaprter 6

Overview

6장에서는 Probabilistic Methods에 대해 다룬다. 확률론적 방법은 어떠한 것의 존재성을 보일 때 직접적인 구성을 하지 않고도 확률적인 논증을 통해 존재성을 증명하는 방법이다.

6.1. The Basic Counting Argument

어떠한 것의 존재성을 보일 때 존재할 확률 > 0 임을 보이면 존재성을 증명할 수 있다.

Example: 단색 그래프

완전그래프를 $K_n$ 이라고 하자.

Claim: 완전그래프 $K_n$의 부분그래프 $K_k$를 고려하자. 만약 $\binom{n}{k} 2^{1-\binom{k}{2}} < 1$ 이면 2가지 색을 이용해서 $K_n$의 간선을 색칠할 때, 단색 그래프가 아닌 $K_k$를 만드는 색칠법이 존재한다.

Proof:
단색 그래프일 확률은 $2 \times 2^{-\binom{k}{2}} = 2^{1-\binom{k}{2}}$ 이다. 부분 그래프의 개수는 $\binom{n}{k}$ 이므로 union bound를 취하면 단색 그래프가 존재할 확률은 최대 $\binom{n}{k} 2^{1-\binom{k}{2}}$ 이다. Claim이 말하는 것은 단색 그래프가 존재할 확률이 1보다 작다는 것인데, 그러면 여사건을 통해 단색 그래프가 존재하지 않는 경우가 존재함을 알 수 있다.

6.2. The Expectation Argument

만약 $\mathbb{E}[X] = \mu$ 라면 $X$가 $\mu$보다 크거나 같은 값이 존재한다.

Example: Max-SAT 문제

Max-SAT은 주어진 boolean expression에서 만족하는 clause의 최대 개수를 구하는 문제이다. 여기서 clause는 or 연산으로 연결된 literal들의 집합이다.
예를 들어 $F=(x_1 \lor \lnot x_2) \land (\lnot x_1 \lor x_3 \lor x_4)$ 라는 boolean expression이 있을 때, clause는 $(x_1 \lor \lnot x_2)$ 와 $(\lnot x_1 \lor x_3 \lor x_4)$ 이다.

Claim: $m$개의 clause로 이루어진 boolean expression $F$에 대해서, 어떤 변수 조합은 적어도 $\frac{m}{2}$개의 clause를 만족시킨다.

Proof:
각 clause의 변수 개수를 $k_i$ 라고 하자.
그러면 i번째 clause가 만족할 확률은 $1 - \frac{1}{2^{k_i}}$ 이다.
만족되는 clause의 개수를 $X$ 라고 하면

\[\mathbb{E}[X] = \sum_{i=1}^{m} \left(1 - \frac{1}{2^{k_i}}\right) \ge \sum_{i=1}^{m} \frac{1}{2} = \frac{m}{2}\]

따라서 $\mathbb{E}[X] \ge \frac{m}{2}$ 이므로 $X$가 $\frac{m}{2}$보다 크거나 같은 값이 존재한다.

6.3. Derandomization

조건부 확률을 이용해서 무작위 알고리즘을 결정론적 알고리즘으로 바꾸는 방법이다.

Example: Max-Cut 문제

6.2에서 다룬 방법으로 Max-Cut 문제에서 Max-Cut의 크기가 적어도 $\frac{m}{2}$ 인 cut이 존재함을 유도할 수 있다.
이제 이 무작위 알고리즘을 결정론적 알고리즘으로 바꾸는 방법을 알아보자.

Claim: 그래프 $G=(V,E)$에 대해서, 어떤 cut의 크기가 적어도 $\frac{m}{2}$ 이다. 그리고 그 cut을 만드는 알고리즘은 다음과 같다.

proof:
induction으로 증명한다.
$C$를 Cut의 수로 정의하고, $x_i$를 $i$번째로 선택된 vertex라고 하자.
예를 들어 cut으로 $A$, $B$로 vertices가 나누어지고, $i$번째로 선택된 vertex가 $A$에 속한다면 $x_i = A$ 이다.
1) base case.
$\mathbb{E}[C] = \mathbb{E}[C | x_1 ]$
처음 vertex를 $A$에 넣든 $B$에 넣든 cut의 기대값은 같다.
2) induction step.
우리의 알고리즘이 동작하려면 inductive step에서

\[\mathbb{E}[C | x_1, x_2, ..., x_{i-1}] \le \mathbb{E}[C | x_1, x_2, ..., x_{i-1}, x_i]\]

를 보장해야 한다. 그래야 cut의 기댓값이 감소하지 않고 우리의 목표인 $\frac{m}{2}$ 이상을 달성할 수 있기 때문이다.
$\mathbb{E}[C | x_1, x_2, …, x_{i-1}, x_i]$는 결국 $x_i$가 $A$냐 $B$냐에 따라 달라진다.
따라서 $\mathbb{E}[C | x_1, x_2, …, x_{i-1}, x_i=A]$와 $\mathbb{E}[C | x_1, x_2, …, x_{i-1}, x_i=B]$ 중 큰 값을 선택해나가면 된다.
따라서 induction이 성립하고, 우리의 알고리즘은 cut의 크기가 적어도 $\frac{m}{2}$ 임을 보장한다.

6.4. Sample and Modify

Random한 구조를 Sample한 후, 그것을 Modify해서 원하는 성질을 갖도록 만드는 방법이다.

Example: 독립된 Subset 찾기

Claim: 그래프 $G=(V,E)$에서 $|V|=n$, $|E|=m$ 일 때, $G$의 독립된 subset $S$ 중에서 $|S| \ge \frac{n^2}{4m}$ 인 것이 존재한다.

Proof:
평균 degree를 $d = \frac{2m}{n}$ 라고 하자. 그리고 아래와 같은 Sample and Modify 알고리즘을 생각하자.

1. 각 vertex를 $\frac{1}{d}$ 확률로 선택해서 삭제해버린다.
2. 남은 vertex들로 이루어진 그래프에서, edge를 양 끝 vertex와 함께 삭제해버린다.

이렇게 하면 남은 vertex들은 독립된 subset을 이룰 것이다. 이제 이 random model이 주어진 확률 조건과 어떻게 연결되는지 살펴보자.
첫번째 과정에서 $X$를 최종적으로 남은 vertex의 개수라고 하고 $Y$를 최종적으로 남은 edge의 개수라고 하자.

\[\begin{align*} \mathbb{E}[X] &= n \times \frac{1}{d} = \frac{n}{d} \\ \mathbb{E}[Y] &= \frac{nd}{2} \times \left(\frac{1}{d}\right)^2 = \frac{n}{2d} \\ \mathbb{E}[X - Y] &= \frac{n}{d} - \frac{n}{2d} = \frac{n}{2d} = \frac{n^2}{4m} \end{align*}\]

$X-Y$는 두번째 과정에서 남은 vertex의 개수이고 이것의 기댓값이 $\frac{n^2}{4m}$ 이므로, subset $S$ 중에서 $|S| \ge \frac{n^2}{4m}$ 인 것이 존재한다.

Example: Existance of Girth

Girth(안둘레)는 그래프에서 사이클의 길이 중 최소값을 의미한다.

Claim: 임의의 정수 $k \ge 3$에 대해서, $G=(V,E)$가 $|V|=n$, $|E| = \frac{1}{4} n^{1 + \frac{1}{k}}$ 이고, Girth가 적어도 $k$ 인 그래프가 존재한다.

Proof:
마찬가지로 Sample and Modify 후 기댓값을 계산하는 방법을 사용한다.

1. $G \in G_{n,p}$를 샘플한다. $p = n^{\frac{1}{k} - 1}$ 로 정의한다.
2. cycle의 길이가 $k$보다 작은 cycle을 한 edge를 지움으로써 없앤다.

첫번째 과정에서 edge의 개수를 $X$, 길이가 $k-1$이하의 cycle의 개수를 $Y$ 라고 하자.
길읻가 $i$인 cycle이 발생할 확률은 $p^i$ 이므로 각각의 기댓값을 계산하면

\[\begin{align*} \mathbb{E}[X] &= \binom{n}{2} p = \frac{1}{2} \left(1- \frac{1}{n}\right)n^{1 + \frac{1}{k}} \\ \mathbb{E}[Y] &= \sum_{i=3}^{k-1} \binom{n}{i} \frac{(i-1)!}{2} p^i \le \sum_{i=3}^{k-1} n^i p^i = \sum_{i=3}^{k-1} n^{\frac{i}{k}} \le k n^{1- \frac{1}{k}} \end{align*}\]

$Y$의 계산에서 $\binom{n}{i}$은 $i$개의 vertex를 선택하는 경우의 수이고, $(i-1)!$는 선택된 vertex의 순서, $\frac{1}{2}$는 cycle의 방향성을 고려한 것이다.

따라서 두번째 과정 이후 남은 edge의 개수의 기댓값은

\[\mathbb{E}[X - Y] \ge \frac{1}{2} \left(1- \frac{1}{n}\right)n^{1 + \frac{1}{k}} - k n^{1- \frac{1}{k}} \ge \frac{1}{4} n^{1 + \frac{1}{k}}\]

6.5. Second Moment Method

Second Moment Method는 확률변수의 분산을 이용해서 확률변수가 특정 값에 가까이 있을 확률을 구하는 방법이다. Chebyshev 부등식에서 아래의 유용한 형태를 얻을 수 있다. (단, $X$는 정수인 확률변수)

\[\Pr(X=0) \le \frac{\text{Var}(X)}{\mathbb{E}[X]^2}\]

유도는 chebyshev 부등식에서 $\Pr(X=0) \le \Pr(|X - \mathbb{E}[X]| \ge \mathbb{E}[X])$ 임을 이용하면 된다.

Example: Threshold behavior in Random Graphs

Claim: $G \in G_{n,p}$ 에 대해서, $p = o(n^{-2/3})$ 이면 $G$가 길이가 4인 clique을 가질 확률이 0에 수렴하고, $p = \omega(n^{-2/3})$ 이면 $G$가 길이가 4인 clique을 가질 확률이 1에 수렴한다.
(little o, little omega 정의 참고)

Proof:
길이가 4인 clique의 개수를 $X$ 라고 하자. 그리고 $X_{i}$를 $i$번째 길이가 4인 clique이 존재하는지 나타내는 indicator 변수라고 하자.
i.e.

\[\begin{align*} X &= \sum_{i} X_i \\ X_i &= \begin{cases} 1 & \text{if $i$번째 길이가 4인 clique이 존재} \\ 0 & \text{otherwise} \end{cases} \end{align*}\]

일단 $X$의 기댓값은 $\mathbb{E}[X] = \binom{n}{4} p^6$ 이다. 그 이유는 길이가 4인 clique을 만들기 위해서는 4개의 vertex를 선택하고, 4개의 vertex로 clique을 만들기 위해서는 6개의 edge가 필요하기 때문이다.

1. $p = o(n^{-2/3})$ 일 때
   이 경우에는 $\mathbb{E}[X]$가 0에 수렴하므로 자명하다. (6.2. The Expectation Argument)
   
2. $p = \omega(n^{-2/3})$ 일 때
   이 경우에는 $\mathbb{E}[X]$가 무한대로 발산한다. 그러나, 이것만을 가지고 $X$의 확률이 1에 수렴함을 알 수 없다.
   따라서 Second Moment Method를 이용해서 $\Pr(X=0) = o(1)$ 임을 보이자.
   이를 위해서는 $\text{Var}(X)$를 계산해야 하기에 lemma를 하나 사용하자.

Lemma: $\text{Var}(Y) \le \mathbb{E}[Y] + \sum_{i \ne j} \text{Cov}(Y_i, Y_j)$

이를 활용하면, $\text{Var}(X) = \text{Var}(\sum_i^{\binom{n}{4}} X_i)$에서 $\text{Var}(X) \le o(\mathbb{E}[X]^2)$ 임을 보일 수 있다.

따라서 $\Pr(X=0) \le \frac{\text{Var}(X)}{\mathbb{E}[X]^2} = o(1)$ 이고, $X$가 0이 아닐 확률이 1에 수렴한다.

6.6. Conditional Expectation Inequality

0과 1만을 가지는 확률변수 $X_i$와 $X=\sum_{i=1}^{n} X_i$에 대해서,

\[\Pr\left( X > 0 \right) \ge \sum_{i=1}^{n} \frac{\Pr(X_i=1)}{\mathbb{E}[X | X_i=1]}\]

증명은 $Y= \frac{1}{X}$인 확률변수를 정의한 후, 다음과 같이 전개하면 된다. (마지막은 Jensen’s inequality 이용)

\[\begin{align*} \Pr(X > 0) &= \mathbb{E}[XY] \\ &= \sum_{i=1}^{n} \mathbb{E}[X_i Y] \\ &= \sum_{i=1}^{n} \Pr(X_i=1) \mathbb{E}[Y | X_i=1] \\ &\ge \sum_{i=1}^{n} \frac{\Pr(X_i=1)}{\mathbb{E}[X | X_i=1]} \end{align*}\]

Example: Revisiting the threshold behavior in Random Graphs

부등식을 적용하기 위해 $\mathbb{E}[X | X_i=1]$ 을 계산해야 한다.

\[\begin{align*} \mathbb{E}[X | X_i=1] &= 1 + \sum_{j \ne i} \Pr(X_j=1 | X_i=1) \\ &= 1 + \left( \binom{n-4}{4} p^6 + 4 \binom{n-4}{3} p^6 + 6 \binom{n-4}{2} p^5 + 4 \binom{n-4}{1} p^3 \right) \\ \end{align*}\]

따라서

\[\Pr(X > 0) \ge \frac{\binom{n}{4} p^6}{1 + \left( \binom{n-4}{4} p^6 + 4 \binom{n-4}{3} p^6 + 6 \binom{n-4}{2} p^5 + 4 \binom{n-4}{1} p^3 \right)}\]

그리고 $p = \omega(n^{-2/3})$ 일 때 우변이 1에 수렴함을 알 수 있다.

여기서 $4 \binom{n-4}{3} p^6$와 같은 항들은 $X_i$와 $X_j$가 공유하는 edge의 개수에 따라 나눈 것이다.
예를 들어 $4 \binom{n-4}{3} p^6$는 $X_i$와 $X_j$가 1개의 edge를 공유하는 경우이다.
계산 방식은 간선을 확정짓고 나머지 vertex를 선택하는 방식이다.
$X_i$와 $X_j$가 1개의 edge를 공유하는 경우, $X_i$의 4개의 vertex 중 2개를 선택해서 간선을 확정짓고, 나머지 vertex 2개를 $n-4$개에서 선택하는 방식이다.

6.7 Lovász Local Lemma

Lovász Local Lemma(LLL)는 여러 사건들이 독립적이지 않을 때도 어떤 사건이 모두 일어나지 않을 확률이 양수임을 보장하는 방법이다.

$E_1, E_2, …, E_n$이 피하고 싶은 사건들이고, 각 사건 $E_i$가 최대 $d$개의 사건들과만 의존적이라고 하자.
만약 $4pd \le 1$ 이면, $\Pr(\bigcap_{i=1}^{n} \overline{E_i}) > 0$ 이다. (p는 각 사건의 최대 확률)

proof:
induction으로 증명한다.
1) base case.
$\Pr(E_1) \le p \le \frac{1}{4d}$
2) induction step.
$\Pr(E_i | \bigcap_{j=1}^{k} \overline{E_j}) \le 2p$
를 보이자.
$E_i$가 의존적인 사건들을 $S$라고 하자. 그러면

\[\Pr(E_i | \bigcap_{j=1}^{k} \overline{E_j}) = \Pr(E_i | \bigcap_{j \in S} \overline{E_j} \cap \bigcap_{j \notin S} \overline{E_j}) = \Pr(E_i | \bigcap_{j \in S} \overline{E_j})\]

이고,

\[\Pr(E_i | \bigcap_{j \in S} \overline{E_j}) = \frac{\Pr(E_i \cap \bigcap_{j \in S} \overline{E_j})}{\Pr(\bigcap_{j \in S} \overline{E_j})} \le \frac{\Pr(E_i)}{\Pr(\bigcap_{j \in S} \overline{E_j})}\]

이다.
induction 가정에 의해 $\Pr(\bigcap_{j \in S} \overline{E_j}) \ge (1 - 2p)^d \ge \left(1 - \frac{1}{2d}\right)^d \ge \frac{1}{2}$ 이므로,
$\Pr(E_i | \bigcap_{j=1}^{k} \overline{E_j}) \le 2p$ 임을 알 수 있다.
따라서 induction이 성립하고,

\[\Pr(\bigcap_{i=1}^{n} \overline{E_i}) = \prod_{i=1}^{n} (1 - \Pr(E_i | \bigcap_{j=1}^{i-1} \overline{E_j})) \ge (1 - 2p)^n > 0\]

임을 알 수 있다.

Example: k-SAT 문제

# TODO