Sen(Qian)’s Memo

前回は 📄(講義ノート)乱択アルゴリズム第10回 です。

前回やったこと。

分布$p$からサンプル可能の時、

• 高い確率で$p=u=(1/n, \cdots)$であるときは受理
• 高い確率で$||p-u||>\epsilon$なら拒否

まず、補題として、$p=u \Rightarrow ||p||_2^2=1/n$が成り立つ。ってそれはそうである。

この時、$||p-u||_1 > \epsilon \Rightarrow ||p||_2^2 > 1/n + \epsilon^2 / n$が成り立つ。

衝突確率は$||p||_2^2 = \sum_{i \in [n]} p(i)^2$である。

これを踏まえてアルゴリズムを考える。$s$回サンプリングして、衝突回数を$k$とする。

衝突回数の割合、つまり$k/_{s}C_2$を$||p||_2^2$の推定値として使う。

もし、$k/{}_{s}C_2 - 1/n \geq \epsilon^2/n$ならば拒否する。そうでなければ受理をするというアルゴリズム。

今回の授業の内容。

$\mathbb{E}[X] = ||p||_2^2$とする。目標は、以下が成り立つこと。ある定数$C$があるとき、サンプリングしたものが、$\delta$以上ずれる確率はたかだか$1/3$であるという。

チェビシェフの不等式を使うと、以下が成り立つ。

ここで、$V[X] = V[\sum_{1 \leq a < b \leq s} X_{ab}]$。総和の中の$X_{ab}$は、$a$番目と$b$番目のサンプルが一致するという意味。

分散の書き換えをまず行う。分散は独立(今回の場合は$a,b$が互いに独立)でない限り、簡単に分解できない。

面倒なことになるが、$\mathbb{E}[]^2$については丁寧に展開することができる。後ろの項も同様に展開できる。

これについて、$a,b,a^\prime, b^\prime$についての総和で見ると、打ち消し合える。

よう分からんが成り立つらしい。

$O(\frac{\sqrt{n}}{\epsilon^2})$のサンプルアルゴリズム。

1. $m=C\sqrt{n}/\epsilon^2$として、$10m$回サンプルして、同じ要素が3回現れたら、拒否する。
2. $k \sim Poi(m)$とする。
3. $k$回サンプリングsして、2回以上サンプリングされた要素の数を数える。
4. この数が$(1+\epsilon/2)m^2/n$を超えたら拒否、それ以外ならば受理

以上のようなアルゴリズムになる。

これがなぜ正当？

• $m p(i) << 1$とする。
• $X_i$は、$i$番目の要素がサンプリングされた回数である。これは$Poi(mp(i))$から得ている。
  • $X_i$は互いに独立である。
• $Y_i$は、$i$番目の要素が2回以上サンプリングされたら1、それ以外が0。

分布が一様であるか？どうかを応用して、2つの分布が同じ分布かどうかを検査できる。

$p$が既知の分布$q$と一致するか？

まず、$q$が$K$で理参加できる、つまり$\forall i, q(i) = k_i / K, k_i \in \mathbb{R}$と書けるとする。

$q$からのサンプルは、そのように離散化させたもののなかで、対応区間を選ぶのと等しい。