STA Chapter1 part2 - nsasakiの勉強メモ

Point-set diameter

distance matrix -> 距離行列について
配列iと配列jの距離を記述（iとjの距離がDij）

>対称行列である（iとjの距離＝jとiの距離）

以下を満たす

$d_{ii} = 0$
$d_{ij} \ge 0$
$d_{ij} \le d_{ik} + d_{kj}$

入力：　m×m距離行列d
目的：　直径 $\hat{d} \overset{\underset{\mathrm{def}}{\;}}{=} max_{u,v} d(u,v)$ を求める。

$x \in V$ を適当に取る
d(x,y) が最大となるyを選ぶ
z=d(x,y)として出力する。

行列全部を調べるとm×m回かかるが、これはm回調べるだけでよい。
すなわち $O \left( \sqrt{\mathrm{input \: size}} \right)$ ですむ。
この際zの取りうる値は
$\frac{\hat{d}}{2} \le z \le \hat{d}$
である。
右の不等式は定義より明らか。左の不等式の証明は
$\hat{d} = d(a,b) \le d(a,x) + d(x,b) \le d(x,a) + d(x,b) \le d(x,y) + d(x,y) = 2z.$
となる。

Sequence monotonicity

入力：　 $x_{1},\cdots ,x_{n}$ 要素の集合（半順序つき）
目的：　単調？　すなわち、 $x_{1}\le x_{2}\le \cdots \le x_{n}$

この問題から以下のように設定を変更する。

入力：　 $x_{1},\cdots ,x_{n}$ 要素の集合（半順序つき）
目的：　単調に近い（ε-close)　すなわち、大きさ(1-ε)nの単調増加部分列がある。
例　n = 5 ε = 2/5　で　1 4 2 5 3という列、ここで1 　 2 　 3　は大きさ3の単調部分列

BPPのtester

if $x_{1},\cdots ,x_{n}$ が単調 then 3/4の確率で正解を出す。
if $x_{1},\cdots ,x_{n}$ が大きさ(1-ε)nの単調増加部分列がない。 then 3/4の確率で失敗を出す。

ここでいう3/4は本質的にあまり意味がなく、1/2より大きく1より小さければよい。
というのもテストを定数回繰り返し正解と失敗のうち、多いほうが問題に対する入力の答えとなるため。

単純なアイディア１

ランダムにi＜jを満たすi,jをとり $x_{i} < x_{j}$ をみたすか調べる。
$\Omega(\sqrt{(n})})$ かかる。*1

理由：

$\underbrace{c, c-1, \dots, 1},\underbrace{2c, 2c-1, \dots, c+1},\dots, \dots, \dots,\underbrace{n, n-1, \dots, n-c+1}.$
という風に並んでいるときを考えると、これは失敗としたい。
しかし、 $\underbrace{\cdots}$ でくくった部分の二点をとらない限り正解を出す。
$c = \sqrt{n}$ とすると、長さ $\sqrt{n}$ のブロックが $\sqrt{n}$ 個存在する。
すなわち、同じブロック内の二点を選ぶ確率は $\frac{1}{\sqrt{n}}$
ゆえに $\sqrt{n}$ 以上必要。
※弱点は全体的な変化を見る確率が高いために局所的な変化に気付きにくい。

単純なアイディア2

ランダムにiを選んで $x_{i} < x_{i+1}$ をみたすか調べる。
これもあまりうまくいかない。

理由：

$\underbrace{1, 2, \dots, n/c},\underbrace{1, 2, \dots, n/c},\dots, \underbrace{1, 2, \dots, n/c}.$
という風に並んでいるときを考えると、これは失敗としたい。
しかし、 $\underbrace{\cdots}$ でくくった部分の境目をとらない限り正解を出す。
この部分をとる確率はc/n.このため、線形時間かかるためよろしくない。
※弱点は局所的な変化を見る確率が高いために全体的な変化がわからない。

これら二つをうまく組み合わせられないだろうか？というのが次のアイディア
と、その前に今後使う記号の説明。
'[n]'は1からnまでの整数の集合
' $x \in_{R} S$ 'は集合Sの中からランダムに選んだものがx

解決策*2

Repeat-O(1/ε)times
$x_{1}, \cdots , x_{n}$ の二分木*3の葉集合Lを考える。
$i \in_{R} L$ でとる。
$x_{i}$ からルートへのぼる。
途中で通った $x_{j}$ の集合 $X_{j}$
$x_{i}$ から操作中に $\mathcal{a < b \; and \;} x_{a} < x_{b}$ となったら失敗。
badな葉の個数がε|L|個以上の場合、正解とする確率は1/4以下
$\left( 1 - \frac{\epsilon |L|}{|L|} \right)^{\frac{c}{\epsilon}} = \left( 1 - \epsilon \right)^{\frac{c}{\epsilon}} \le exp{-c} \le \frac{1}{4}$
※
$1 + x \le exp{x}$ は恒等的に成立する。（右辺引く左辺の関数を考えるとわかる）
ここで $x = -\epsilon$ を代入し、辺々 $\frac{c}{\epsilon}$ 乗すればよい。