論文翻訳: Min-Wise Independent Permutations (Extended abstract)

Andrei Z. Broder^*   Moses Charikar^†   Alan M. Frieze^‡   Michael Mitzenmacher^§  

Abstract

我々は並べ換えの min-wise 独立族 (min-wise independent families of permutations; 最小値独立置換族) という概念を定義して研究する。任意の集合 \(X \subseteq [n]\) と任意の \(x \in X\) に対して、\(\mathcal{F}\) で \(\pi\) をランダムに選んだとき、\[ \pr\left(\min \{ \pi(X) \} = \pi(x) \right) = \frac{1}{|X|} \] が成り立つとき、\(\mathcal{F} \subseteq S_n\) は min-wise 独立 (min-wise independent) であると言う。言い換えると、任意の固定集合 \(X\) のすべての要素が、\(\pi\) の下での \(X\) の像の最小要素である確率が等しいと言うことを要求している。

我々の研究の動機は、AltaVista Web インデックスのソフトウェアが重複に近い文書を検出しフィルタリングするために実際に使用しているアルゴリズムに、このような族が (いくつかの緩和の下で) 不可欠であるという事実だった。しかし調査の過程でこの概念に関連する興味深く挑戦的な理論的問題を発見した。そのうちのいくつかについての解決策を提示し、残りの未解決問題はリスト化している。

Table of Contents

1. Abstract
2. 1 導入
3. 2 厳密 Min-Wise 独立性
   1. 2.1 非一様分布の厳密問題
4. 3 近似問題
   1. 3.1 実存的上限
   2. 3.2 一様族に対する下限
   3. 3.3 非一様族に対する下限
5. 4 線形および pairwise 独立族
   1. 4.1 一般的な上限と下限
   2. 4.2 線形族、上限と下限
6. 5 Acknowledgements
7. References
8. 翻訳抄

• ^*Digital SRC, 130 Lytton Avenue, Palo Alto, CA 94301, USA. E-mail: broder@pa.dec.com.
• ^†Computer Science Department, Stanford University, CA 94305, USA. E-mail: moses@cs.stanford.edu. Part of this work was done while this author was a summer intern at Digital SRC. Supported by the Pierre and Christine Lamond Fellowship and in part by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation.
• ^‡Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA. Part of this work was done while this author was visiting Digital SRC. Supported in part by NSF grant CCR9530974. E-mail: af1p@andrew.cmu.edu
• ^§Digital SRC, 130 Lytton Avenue, Palo Alto, CA 94301, USA. E-mail: michaelm@pa.dec.com.

1 導入

ハッシュ化スキームの古典的な解析では、使用されるハッシュ関数がランダムであるという仮定を伴うことが多い。より正確には、ある母集団 \(\mathcal{U}\) に属するキーは、\(\mathcal{U} \to [M]\) となるすべての関数の中からある関数 \(h\) を一様にランダムに選ぶことで、サイズ \(M\) の表にハッシュ化されるという仮定である。(表記 \([M]\) は集合 \(\{0,\ldots,M-1\}\) を表している。これはいささか非標準的ではあるが我々の目的に適している。) このような関数を特定するだけでも通常の利用可能なストレージを遙かに超える \(|\mathcal{U}| \log(M)\) ビットを必要とするため、この仮定は現実的ではない。

幸いほとんどのケースでヒューリスティックハッシュ関数はランダムハッシュ関数に期待される挙動に非常に近い振る舞いをするが、厳密な確率的保証が必要な場合がある。具体的には、様々な適応的ハッシュスキームではある一定の性質を持つハッシュ関数が一定の期待時間内に見つかることを仮定している。これは、適切な関数が見つかるまですべての可能な関数から一様にランダムに関数を選ぶ場合には成り立つが、探索をより少ない関数群に限定した場合には必ずしも成立しない。

このような状況から Carter と Wegman [8] はユニバーサルハッシュ (universal hash) という概念にたどり着いた。\(h\) をハッシュ関数の族 \(\mathcal{H}\) から一様にランダムに選ばれた要素とすると、任意の異なる要素のペア \(x_1,x_2\in\mathcal{U}\) に対して \[ \begin{equation} \pr\left(h(x_1)=h(x_2)\right) \le \frac{1}{|M|} \label{e1} \end{equation} \] となるとき \(\mathcal{H}\) は弱ユニバーサル (weakly universal) と呼ばれ、任意の異なる要素のペア \(x_1,x_2\in\mathcal{U}\) と任意の \(y_1,y_2\in[M]\) に対して \[ \begin{equation} \pr\left(h(x_1)=y_1 \mbox{ and } h(x_2)=y_2\right) = \frac{1}{|M|^2} \label{e2} \end{equation} \] であれば (強) ユニバーサル (strongly universal) または pair-wise 独立 (pair-wise independent) と呼ばれる。多くの場合、\(h\) がすべての可能な関数から一様にランダムに選ばれるという仮定よりもむしろ \(h\) がユニバーサルな族から一様にランダムに選ばれるという弱い仮定の下で様々なハッシュ化スキームの分析が終えられていることが判明している。言い換えると限定されたランダム性で十分である。さらに、現実に実装することが容易な \(O(|M|^2)\) サイズのユニバーサルな族が存在する。このように、ユニバーサルハッシュ関数は適用的ハッシュスキームの設計に非常に有用であり (例えば [7, 9] 参照)、実際に商用の高パフォーマンス製品で使用されている (例えば [13] 参照)。それだけでなく、pair-wise 独立の概念は重要なり論的応用がある。(Luby と Wigderson [11] による素晴らしい調査を参照されたい)。

関数よりも置換 (permutations) で考える方が便利なことも多い。\(S_n\) を \([n]\) のすべての置換の集合とする。\(x_1 \ne x_2\) かつ \(y_1 \ne y_2\) である任意の \(\{x_1,x_2,y_1,y_2\} \subseteq [n]\) に対して \[ \begin{equation} \pr\left(\pi(x_1) = y_1 \mbox{ and } \pi(x_2) = y_2\right) = \frac{1}{n(n-1)} \label{e3} \end{equation} \] であるとき、置換族 \(\mathcal{F} \subseteq S_n\) は pair-wise 独立 (pair-wise independent) であると言う。

同様に、\(\mathcal{F}\) からランダムに選ばれた \(\pi\) と任意の集合 \(X \subseteq [n]\) と任意の \(x \in X\) に対して \[ \begin{equation} \pr\left(\min\{\pi(X)\} = \pi(x)\right) = \frac{1}{|X|} \label{e4} \end{equation} \] であるとき、この論文では \(\mathcal{F} \subseteq S_n\) は厳密 min-wise 独立 (exactly min-wise independent) (または意味が明確な場合は単に min-wise 独立 (min-wise independent)) であると言う。言い換えると、任意の固定集合 \(X\) のすべての要素が \(\pi\) の下で \(X\) の像の最小要素になる確率が均等であることを要求する。特に断らない限り \(\pi\) は \(\mathcal{F}\) から一様にランダムに選ばれるものとする。さもなければ \(\pi\) は偏った分布 \(\mu\) で選ばれていると言う。一様分布は実際に表現するのが容易であるためこの設定において自然である。

以下に説明するように、AltaVista Web インデックス作成ソフトウェア [12] で実際に使われている重複に近い文書を検出しフィルタリングするアルゴリズムにこのような族が (いくつかの緩和の下で) 不可欠であるという事実がこの定義の動機となっている。

Web [4] はその誕生以来、指数関数的な成長を遂げており、その結果として同一またはそれに近い文書が拡散している。実験によれば Web 上で公開されている文書の 20% 以上が重複またはそれに近いものであることが示されている。これらの文書は、何気なく (例えば人気文書のローカルコピーやミラーリング)、悪意を持って (例えば "スパマー" や "ロボットトラップ")、または誤って (スパイダーミス) 発生したものである。いずれにせよこれらはインデックス作成ソフトウェアにとって 2 つの理由で深刻な問題である。一つ目は重複したインデックス作成は高価なリソースを浪費すること、二つ目はユーザがクエリーに対して "ほぼ同じ" 文書を参照することにほとんど興味を示さないことである。

この非公式な概念は、文字列に対して定義された標準的な距離 (Hamming, Levenshtein など) ではうまく捉えられないようである。さらに、通常これらの距離の計算には pairwise 比較が必要であるが、非常に大規模な文書群ではこれは実現不可能であり、文書ごとのサンプリング機構が必要である。

この問題は shingling と呼ばれる処理によって集合の交差問題に還元できることが判明した (詳細は [6, 5] 参照)。shingling によってそれぞれの文書 \(D\) は関連する集合 \(S_D\) を得る。ここで議論のために \(S_D\) を自然数の集合と見なす (\(S_D\) の大きさは \(D\) の単語数とほぼ等しい)。2 つの文書 \(A\) と \(B\) の類似度 \(r(A,B)\) は \[ r(A,B) = \frac{|S_A \cap S_B|}{|S_A \cup S_B|} \] と定義される。実験によると類似度が高い (つまり 1 に近い) ことは "重複に近い" または "ほぼ同じ" という非公式な概念をよく捉えているようである。

2 つの文書の類似度を計算するためには、各文書に対して比較的小さな固定サイズのスケッチを保持していれば十分である。写像はかなり高速に計算でき (文書サイズに対して線形)、2 つの写像があれば対応する文書の類似度はスケッチのサイズに対して線形時間で計算できる。

これは次のように行われる。対象のすべての文書を \(S_D \subseteq \{1,\ldots,n\}\) とする (実際には \(n=2^{64}\))。\([n]\) の置換集合である \(S_n\) 上で \(\pi\) が一様にランダムに選ばれるとする。このとき \[ \begin{equation} \pr\left(\min\{\pi(S_A)\} = \min\{\pi(S_B)\}\right) = \frac{|S_A \cap S_B|}{|S_A \cup S_B|} = r(A,B) \label{e5} \end{equation} \] である。したがって、例えば 100 個の独立したランダムな置換 \(\pi_1,\ldots,\pi_{100}\) を選択することができる。各文書 \(D\) に対してリスト \[ \bar{S}_A = \left(\min\{\pi_1(S_A)\}, \min\{\pi_2(S_A)\},\ldots,\min\{\pi_{100}(S_A)\}\right) \] を保存する。そして \(\bar{S}_A\) と \(\bar{S}_B\) の対応する要素がいくつ共通しているかを計算することで \(A\) と \(B\) の類似度を容易に推定することができる。

実際には前述のハッシュ化の場合と同様に \(S_n\) において \(\pi\) をランダムに選ぶことは不可能であるという悲しい現実に対処しなければならない。そこで、min-wise 独立は式 (\(\ref{e5}\)) が成立するために必要かつ十分であるため、式 (\(\ref{e4}\)) で与えられる min-wise 独立条件を満たすより小さな置換の族を検討することになる。

実際にはある種の緩和を許容することができる。第一に、小さな相対誤差を受け入れることができる。\(\mathcal{F}\) からランダムに選んだ \(\pi\) と任意の集合 \(X \subseteq [n]\) と任意の \(x \in X\) に対して、\[ \begin{equation} \left| \pr\left(\min\{\pi(X)\} = \pi(x)\right) - \frac{1}{|X|} \right| \le \frac{\epsilon}{|X|} \label{e6} \end{equation} \] であるとき、\(\mathcal{F} \subseteq S_n\) は近似 min-wise 独立 (approximately min-wise independent) であると言う。言い換えると、任意の固定集合 \(X\) のすべての要素が \(\pi\) の下で \(X\) の像の最小値になる確率がほぼ等しいことを要求している。近似 min-wise 独立の族を用いて類似性を評価する際に生じる期待相対誤差は \(\epsilon\) より小さい。

第二に、対象の集合は通常 \(n\) より小さい (前述の状況では \(n=2^{64}\) に対して典型的な大きさは 1000 である)。\(\mathcal{F}\) からランダムに選択した \(\pi\) と \(|X| \le k\) となるような任意の集合 \(X \subseteq [n]\) と任意の \(x \in X\) に対して \[ \begin{equation} \pr\left(\min\{\pi(X)\} = \pi(x)\right) = \frac{1}{|X|}, \ \ |X| \le k \label{e7} \end{equation} \] であるとき、\(\mathcal{F} \subseteq S_n\) は制限 min-wise 独立 (restricted min-wise independent) であると言う。

最後の第三に、族 \(\mathcal{F}\) の分布が一様かそうでないかで定性的には異なる結果になることが判明した。

最終的に、我々は実用的な置換の族に興味がある。そこでまず様々な条件の組み合わせを満たす最小の族の大きさはどの程度かを調べる。最小サイズが指数関数的であれば実用的な解が存在しないことは明らかである。厳密 min-wise 特性は一般に指数関数的なサイズを必要とするが、近似的な特性は多項式サイズの族で満たすことができると判明している。Table 2 にその結果の概要を示す。表中の他の項目が示唆する以上の境界がない項目には "?" を、自明でない境界が存在しない項目には "???" と記した。

我々は反対方向からソフトウェアで簡単に実装できる様々な族がどの程度の性能を提供できるかを研究している。実用的な実装がある pair-wise 独立族を検討している。特に我々が線形変換を対象としているのは、AltaVista の実装で使用されており、ある状況下では他の pair-wise 独立族よりも優れた性能を発揮することが知られているためである ([1] 参照)。

この性能を評価する方法は、集合 \(X\) を考慮し \(X\) の写像の最小の分布を調べることである。最小になる可能性が最も高いものと最も低いものの 2 つの要素を調べれば、他のすべての要素は極値の間の確率で最小になるため十分である。我々は、対象とする性質に対して \(X\) が最悪の集合 (一様から最も遠い) となるように選ばれる場合と、\(X\) が一様にランダムに選ばれる場合 (この場合 \(X\) のランダムな選択に対する境界の期待値を探す) の 2 つの状況を考慮する。我々の答えの概要は Table 2 の通りであり、ここで "?" と "???" の使用に関して以前と同じ規則に従う。

2 厳密 Min-Wise 独立性

このセクションでは厳密 min-wise 独立である族の大きさの境界を与える。まず下限を求め、族 \(\mathcal{F}\) の大きさが \(n\) に対して指数関数的に増加する必要があることを示す。

定理 1. \(\mathcal{F}\) を min-wise 独立とする。このとき \(|\mathcal{F}|\) は最小でも数 \(1,2,\ldots,n\) の最小公倍数 (lcm) と同じ大きさであり、したがって \(|\mathcal{F}| \ge e^{n-o(n)}\) である。

証明. \(X\) を \(|X|=j\) とする \([n]\) の部分集合とする。\(X\) の各要素は族 \(\mathcal{F}\) の下で同じ回数だけ最小にならなければならないため、\(j\) は \(|\mathcal{F}|\) を除算しなければならない。これはすべての \(j \in \{1,2,\ldots,n\}\) で成立するため、\(\{1,2,\ldots,n\}\) の lcm は \(|\mathcal{F}|\) を除算しなければならない。最初の \(n\) 個の数の lcm が大きさ \(e^{n-o(n)}\) であることは整数論ではよく知られた事実である [3, p.76]。∎

備考 1. この証明は制限 min-wise 独立族に対する \(e^{k-o(k)}\) の下限も与えている。またこの証明では \(\mathcal{F}\) のメンバーが異なることを要求していないことに注意。したがって \(\mathcal{F}\) がいくつかの置換の重複を含んでいても定理は成立する。

ここで \(4^n\) より小さい大きさの min-wise 独立族を説明する。これは \(n!\) の自明な境界よりもかなり小さく、上記で与えられた下限と同じ形式である。

定理 2. \(4^n\) より小さい大きさの min-wise 独立族 \(\mathcal{F}\) が存在する。

証明. まず便宜上、ある \(r\) に対して \(n=2^r\) と仮定する。置換の族を段階的に再帰的に構築する。第 1 段階では集合 \([n]\) を上半分と下半分に等分する。この第 1 段階では集合を分割する方法は \(\binom{n}{n/2}\) 通りである。これらはそれぞれ正確に \(n/2\) 個の 1 を含む \(n\)-ビット列で記述できる。要素 \(i\) はビット列の \(i\) 番目の位置が 1 である場合にのみ上半分に入る。次に各半分を等分する。この場合も \(n/4\) 個の 1 を含む \(n/2\) 個のビット列を選べば良い。このような列は \(\binom{n/2}{n/4}\) 個存在する。重要なのは、各等分に同じ列を使用することである。第 \(i\) 段階では集合をそれぞれ \(n/2^{i-1}\) の大きさの \(2^{i-1}\) 個に分割している。このとき \(n/2^i\) 個の 1 を含む \(n/2^{i-1}\) 個のビット列を選択し、この列を用いて \(2i-1\) 個の部分のそれぞれを分割する。このようにして各部分のサイズが 1 になるまで続ける。このプロセスは自然な方法で集合の置換を生成し、最上位の要素は置換の中で最も小さい数字が与えられることになる。

各要素が正しい確率で最小となるという性質は計算によって直接検証することができる。より直感的に言えば、\([n]\) を 2 つに分割したとき \(X\) のすべての要素が上半分または下半分に移動する可能性が等しく、さらに現在上半分にある \(X\) のすべての要素は (帰納法により) 最終的に \(X\) の最上位の要素となる可能性も等しくなる。\(X\) の要素が上半分にない場合、すべて下半分にあり、これも (帰納法により) すべてが最終的に最上位になる可能性が等しくなる。

この族の置換の数は \[ \prod_{i=1}^{\log n} \binom{n/2^{i-1}}{n/2^i} \] である。簡単な計算でこの族の大きさは \(4^{n-O(\log^2 n)}\) であることが分かる。

\(n\) が 2 のべき乗であるという仮定は簡単に取り除くことができる。これは勤勉な読者への課題として残しておく。∎

2.1 非一様分布の厳密問題

我々は一様分布に対する結果に焦点を当てるが、ここで興味深い結果を示す。定理 1 の下限は非一様分布を用いることで破ることができる。

定理 3. 最大で \(n 2^{n-1}-1\) の大きさの族 \(\mathcal{F}\) が存在し、関連づけられた分布 \(\mu\) を持つそのような \(\mathcal{F}\) は min-wise 独立である。

証明. 定理を満足する \(\mathcal{F}\) と \(\mu\) を求める線形計画法 (linear program) を書くことができる。置換 \(\pi \in S_n\) のそれぞれに対して \(\mu\) による \(\pi\) の重みを表す変数 \(x_\pi\) を用意する。すべての \(X \subset [n]\) とすべての \(x \in X\) に対してに対し、\(\pr(\min\{\pi(X)\}=\pi(x))=\frac{1}{|X|}\) という条件を変数 \(x_\pi\) の線形方程式として表す。合計 \(\sum_{k=1}^n k\cdot\binom{n}{k}=n2^{n-1}-1\) 個の制約がある。この系は明らかに実行可能解をもち (\(S_n\) の要素を一様にランダムに選択する、つまりすべての \(\pi\in S_n\) に対して \(x_\pi = 1/n!\) とする)、したがって最大で \(m\cdot 2^{n-1}-1\) 個の非ゼロ変数を持つ基本的な実行可能解を持つ。この解は定理の条件を満たす族をもたらす。∎

備考 2. これは推論 1 の下限を上回るが、族の大きさはまだ \(n\) の指数関数的であり、我々はセクション 3.3 でほぼ厳密な下限を証明する。また制限 min-wise 独立性の場合、これと同じ構成で \(\sigma_{j=1}^k j\cdot\binom{n}{j}\) の上限が得られる。

3 近似問題

厳密問題では指数関数的な大きさの族が必要なので近似の問題に目を向ける。

3.1 実存的上限

確率論的手法 [2] により、\(S_n\) からランダムな置換の数を選ぶだけで近似 min-wise 独立な族の大きさの実存的上限を得ることができる。証明は簡単なので省略する。

定理 4. 近似 min-wise 独立であるサイズ \(O(\frac{n^2}{\epsilon^2})\) の族が存在し、近似かつ制限 min-wise 独立であるサイズ \(O(\frac{k^2 \log(n/k)}{\epsilon^2})\) の族が存在する。

実際、\(S_n\) から一様にランダムに選ばれた大きさ \(O(\frac{n^2}{\epsilon^2})\) の置換の族は高い確率で近似 min-wise 独立になる。このことは冒頭で述べた文書の類似性の問題に対する適切な解決策を提供するように思われる。しかし実際には、\(S_n\) からのランダムな置換を都合良く表現することができないため、この結果は我々の助けにはならない。前述のように \(n\) 個の要素に対するランダムな置換を表すには \(\Omega(n \log n)\) ビットを必要とし、実際には \(n=2^{64}\) である。このことからセクション 4 で単純な線形置換を検討することにする。

3.2 一様族に対する下限

一様確率分布の族に対して \(n^2 (1-\sqrt{8\epsilon})\) の下限を証明する。これにより実存的な上限における \(n^2\) 項を改善できないことが分かる。

定理 5. \(\mathcal{F}\) を近似 min-wise 独立族とすると \(|\mathcal{F}| \ge n^2 (1 - \sqrt{8\epsilon})\) である。

証明. \(|\mathcal{F}|=f\) とする。\(\mathcal{F}\) の少なくとも \(f/n\) 個の置換に対して \(\pi(a)=1\) となる (つまり \(a\) は置換の次に小さい) ようなある要素 \(a\) が存在するはずである。このような \(a\) を特定し \(z \le f/n\) の置換を考える。\(z\) の値は後で選ぶことにする。これらの \(z\) 個の置換において最小の要素として現れる要素の集合を \(Z\) とし (すなはちこれらの \(z\) 個の置換の少なくとも 1 つについて \(\pi(b)=0\) である場合にのみ \(b \in Z\))、\(S = [n] - Z\) とする。明らかに \(a \in S\) であり \(|S| \ge n-z\) である。\(\pi(a)\) が \(\pi(S)\) の最小要素になる置換 \(\pi \in \mathcal{F}\) がいくつ存在するかを考える。これは少なくとも \(\pi(a)=0\) のときと、\(\pi(a)=1\) だが \(S\) にない要素が \(\pi\) の下で像 0 を持つような前述の \(z\) 個の置換のときに発生する。しかし \(\mathcal{F}\) は近似 min-wise 独立の族であることから、少なくとも \(\frac{f}{n}(1-\epsilon)\) に対して \(\pi(a)=0\) であり、同じ理由で \(\pi(a)\) は最大でも \(\frac{f}{|S|}(1+\epsilon)\le\frac{f(1+\epsilon)}{n-z}\) 個の置換に対して \(S\) の最小要素となり得る。したがって \[ \frac{f(1-\epsilon)}{n} + z \le \frac{f(1+\epsilon)}{n-z} \] となる。この式を \(f\) について解き \(z\) (\(z=\sqrt{2\epsilon} f/n\)) について (おおむね) 最適化すると \[ f \ge n^2 \frac{1-\sqrt{2\epsilon}}{1+\sqrt{2\epsilon}-\epsilon} \] が得られる。以上を単純化すると \(|\mathcal{F}|\) の下限は \(n^2 (1-\sqrt{8\epsilon})\) となる。∎

3.3 非一様族に対する下限

我々は、関連する確率分布 \(\mu\) を持つ非一様族でも、任意の近似 min-wise 独立の族の大きさに関する下限を証明する。この下限の証明はセクション 2.1 で得られた \(n2^{n-1}-1\) の上限に非常に近い、非均一な厳密 min-wise 独立の族の下限をもたらしている。

定理 6. \(\mathcal{F}\) を、条件次第で確率分布 \(\mu\) が関連付けられている近似 min-wise 独立の族とすると、任意の \(r\lt n\) に対して \(|\mathcal{F}| \ge \frac{(n-r)\binom{n}{r}}{1+\epsilon 2^r\binom{n}{r}}\) である。

証明. 要素 \(a\) と \(a \not\in Z\) となる集合 \(Z = \{x_1,x_2,\ldots,x_r\} \subseteq [n]\) を特定する。\(\pi(Z)\) のすべての要素を任意の順序で \(\pi\) の \(r\) 個の最小要素とし (つまり \(\pi(Z)=[r]\))、\(a\) を \((r+1)\) 番目の最小要素として持つ (つまり \(\pi(a)=r+1\)) \(\mathcal{F}\) に置換 \(\pi\) が存在するとき、我々はペア \((Z,a)\) を満たされている (satisfied) とする。\(\mathcal{F}\) が近似 min-wise 独立の族であるためにはほとんどのペア \((Z,a)\) が満たされていなければならず、実際、\(\mathcal{F}\) が厳密 min-wise 独立族であるためにはすべてのペア \((Z,a)\) が満たされていなければならないことを示す。

\(Y=[n]-Z\) とする。定義により \(a \in Y\) である。集合 \(Y_i=Y \cup x_i\) を考え、\(\pi(a)\) が \(\pi(Y_i)\) の最小要素である頻度を数える。分布 \(\mu\) の下で \(\mathcal{F}\) からある置換を選んだときに \(a\) が \(\pi(S)\) の最小である事象を \(B_S\) とする。\(B=\bigcup_{i=1}^r B_{Y_i}\) とすると \(B \subseteq B_Y\) となり、したがって \(\pr(B_Y - B) = \pr(B_y) - \pr(B)\) である。一方、\(B_Y - B\) という事象はまさに \((Z,a)\) を満たす事象である。

ここで包含排除原理 (inclusion-exclusion principle) を利用して \(\pr(B) = \pr(\bigcup_{i=1}^r B_{Y_i})\) を算出する。次のような事実を理解しておくと有用である。まず \(a \in S_2 \subseteq S_1\) であれば \(B_{S_1} \subseteq B_{S_2}\)、\(a \in S_1 \cap S_2\) であれば \(B_{S_1} \cap B_{S_2}\) である。次に近似 min-wise 独立の定義により \(\frac{1-\epsilon}{|S|} \le \pr(B_S) \le \frac{1+\epsilon}{|S|}\) である。これを意味が明らかなところで省略して \(\pr(B_S) = \frac{1\pm\epsilon}{|S|}\) とする。第三に、\(i\) 個の異なる \(Y_i\) の和は大きさが \(n-r+i\) であり、したがって \[ \begin{eqnarray*} \pr(B) & = & \pr(B_{Y_1}) + \pr(B_{Y_2}) + \cdots + \pr(B_{Y_n}) \\ & & - \pr(B_{Y_1} \cap B_{Y_2}) - \cdots \\ & & + \pr(B_{Y_1} \cap B_{Y_2} \cap B_{Y_3}) + \cdots \\ & = & \pr(B_{Y_1}) + \pr(B_{Y_2}) + \cdots + \pr(B_{Y_n}) \\ & & - \pr(B_{Y_1 \cup Y_2}) - \cdots + \pr(B_{Y_1 \cup Y_2 \cup Y_3}) + \cdots \\ & = & \sum_{i=1}^r (-1)^{i+1} \binom{r}{i} \frac{1 \pm \epsilon}{n - r + i} \end{eqnarray*} \] したがって \[ \begin{eqnarray*} \pr(B_Y - B) & = & \frac{1 \pm \epsilon}{n-r} - \sum_{i=1}^r (-1)^{i+1} \binom{r}{i} \frac{1 \pm \epsilon}{n - r + i} \\ & = & \sum_{i=0}^r (-1)^i \binom{r}{i} \frac{i \pm \epsilon}{n - r + i} \\ & = & \sum_{i=0}^r (-1)^i \binom{r}{i} \frac{1}{n - r + i} \pm \epsilon \sum_{i=0}^r \binom{r}{i} \frac{1}{n - r + i} \end{eqnarray*} \] 上記の式の第 1 項を評価するためには \(\epsilon\) が 0 のとき \(\pr(B_Y - B)\) と等しいことに注意すること。つまりこの項は厳密 min-wise 独立な族に対して \((Z,a)\) が満たされる確率である。これは \(n\) と \(r\) にのみ依存し、検討中の族には依存しないことに注意! 特に、集合族 \(S_n\) に対して \((Z,a)\) が満たされる確率を計算することで簡単に算出することができる。したがって組み合わせ論的恒等式 \[ \sum_{i=0}^r (-1)^i \binom{r}{i} \frac{1}{n - r + i} = \frac{1}{(n - r) \binom{n}{r}} \] を得る。この代数的導出のヒントは [10 の式 1.2.6.24] である。

\(\epsilon\) の係数の大きさは最大で \(\frac{2^r}{n-r}\) である。したがって \[ \begin{equation} \frac{1}{(n-r)\binom{n}{r}} + \epsilon\frac{2^r}{n-r} \ge \pr(B_Y - B) \ge \frac{1}{(n-r)\binom{n}{r}} - \epsilon\frac{2^r}{n-r} \label{e8} \end{equation} \] である。

\(\pr(B_Y-B) \le \frac{1}{(n-r)\binom{n}{r}}+\epsilon\frac{2^r}{n-r}\) より、任意のペア \((Z,a)\) を満たす置換の総確率質量は最大で \(p=\frac{1}{(n-r)\binom{n}{r}}+\epsilon\frac{2^r}{n-r}\) である。したがって、ある置換を満たすペア \((Z,a)\) の数は少なくとも \(1/p\) でなければならない。しかしすべての置換はちょうど 1 つの \((Z,a)\) ペアを満たす。これは、少なくとも \(1/p\) 個の置換が存在する必要があることを意味し、つまり族の大きさは少なくとも \(\frac{(n-r)\binom{n}{r}}{1+\epsilon 2^r\binom{n}{r}}\) である。∎

推論 1. \(\mathcal{F}\) を、条件次第で関連する確率分布 \(\mu\) を持つ厳密 min-wise 独立の族とすると、\(|\mathcal{F}| \ge \lceil\frac{n}{2}\rceil\binom{n}{\lfloor n/2\rfloor}\) となる。

証明. 定理 6 の結果に \(\epsilon=0\) と \(r=\lfloor\frac{n}{2}\rfloor\) を代入する。∎

実際、定理 6 はさらに強い推論を証明している: 式 (\(\ref{e8}\)) は \((Z,a)\) を満たす確率が \(\epsilon \lt 1/2^r \binom{n}{r}\) である限り肯定的であることを示している。したがって、このような \(\epsilon\) を持つ任意の近似 min-wise 独立族では、すべての \(\binom{n}{r}(n-r)\) 個の可能なペア \((Z,a)\) が満たされるため、少なくともその数の置換が存在することになる。これは \(r = \lfloor\frac{n}{2}\rfloor\) で最大となり、したがって推論 1 の境界は指数関数的に小さい \(\epsilon\) を持つ近似族に対しても成立する。

4 線形および pairwise 独立族

ここで実際に使用される可能性が最も高い置換の動作である線形変換に焦点を当てる。特に、要素の母集団がある素数 \(p\) に対して \([p]\) であり、置換の族が (\(a\ne 0\) である) \(\pi(x)=ax+b \bmod p\) の形式のすべての置換で与えられる状況に注目する。線形変換は表現が容易で効率的に計算できるため実際の適用に適している。我々の結果では、この置換の族は min-wise 独立ではないものの多くの実用的な状況において十分なパフォーマンスであることを示唆している。

4.1 一般的な上限と下限

線形置換の結果はかなりの計算を必要とするためここですべての結果の証明は行わない。まず、線形変換だけではなく任意の置換の pairwise 独立な族に対して成り立つ単純な下限から始める。我々の結果の多くはこの形式と取っている。

定理 7. \(|X| = k\) となる任意の \(X \subseteq [n]\) と任意の \(x \in X\) に対して、\(\pi\) が置換の pairwise 独立の族から選ばれるのであれば \[ \pr\left(\min\{\pi(X)\} = \pi(x)\right) \gt \frac{1}{2(k-1)} \] である。

証明. 集合 \(X=\{x_0,\ldots,x_{k-1}\}\) を考える。\(\pi(x_0)\) が \(\pi(X)\) の最小要素であることを定理が要求する回数だけ示す。\(\pi(x_0)=z\) とすると、\(\pi\) が pairwise 独立族から選ばれるなら \(\pr(\pi(x_i) \lt z \;|\;\pi(x_0)=z) = z/n\) である。\(\pi\) が \(x_i\) を \(\pi(x_0)\) より小さいものにマップする確率は \(z/n\) であるため、\(\pi\) が \(X\) の任意の要素を \(\pi(x_0)\) より小さいものにマップする確率は最大で \((k-1)z/n\) であり、したがって \(\pi(x_0)\) は少なくとも \(1-(k-1)z/n\) の確率で \(\pi(X)\) の最小値である。これは \(0 \le z \le \lfloor\frac{n}{k-1}\rfloor\) に対して非負である。したがって \[ \begin{eqnarray*} \pr(\min\{\pi(X)\} = \pi(x_0)) & \ge & \frac{1}{n}\sum_{z=0}^{\lfloor n/(k-1)\rfloor} \left(1-\frac{(k-1)z}{n}\right) \\ & \gt & \frac{1}{2(k-1)} \end{eqnarray*} \] となる。∎

我々は問題の線形計画法の定式化に基づき \(O(1/\sqrt{k})\) である置換の pairwise 独立族に対して \(\pr(\min\{\pi(X)\}=\pi(x))\) の上限を得た。我々の最初の証明に続いて Piotr Indyk がこの上限をより簡単に証明することを提案した。

4.2 線形族、上限と下限

線形変換を具体的に考えることでさらなる境界を導き出すことができる。例えば、線形変換の族は任意の定数 \(\epsilon\) に対して近似 min-wise 独立でさえないことを示すことができる。ここではこの結果をスケッチする。

定理 8. \([p]\) の部分集合として集合 \(X_k=\{0,1,\ldots,k\}\) を考える。\(k,p\to\infty\), \(p \gg k\) として、\(\pi\) を (\(a\ne 0\) となる) \(\pi(x)=ax+b \bmod p\) の形のランダムに選んだ線形変換とすると \[ \pr(\min\{\pi(X)\}=\pi(0)) \sim \frac{3}{\pi^2} \frac{\ln k}{k} \] である。

証明. この証明ではファレイ数列 (Farey series) に関するいくつかの基本的な事実を用いる。まずファレイ数列の定義といくつかの基本的な事実を思い出すこと。より詳しくは通常の整数論の教科書に載っている。

定義 1. 次数 \(k\) のファレイ数列は、母数が最大 \(k\) である 1 未満のすべての既約分数からなり、その数は昇順で構成される。

\(\frac{n_1}{d_1}\) と \(\frac{n_2}{d_2}\) を第 \(k\) 次ファレイ数列の連続する 2 つの分散とすると

1. \(n_2d_1-n_1d_2=1\)
2. \((d_1,d_2)=1\)
3. 高次ファレイ数列の \(\frac{n_1}{d_1}\) と \(\frac{n_2}{d_2}\) の間に挿入される最初の分数は \(\frac{n_1+n_2}{d_1+d_2}\) である。

\(\pi(0)\) が \(\{\pi(X_k)\}\) の最小要素である回数の割合を計算するために、まず乗数 \(a\) を持つすべての変換 \(\pi\) を考えてみよう。\(z_a=\min_{i=1,\ldots,k}\{-a\!\cdot\!i\bmod p\}\) とすると、\(\pi(0)\) は \(\pi=ax+b\bmod p\) で \(b\lt z_a\) (\(z_a\) は正であることに注意!) のときだけ最小となり、\(b\) の他の値では最小要素の写像は \(\pi(0)=b\) の後ろにあることになる。

したがって、0 が \(\{\pi(X_k)\}\) の最小要素である回数の割合を求めるには \(\frac{1}{p}\min_{i=1,\ldots,k}\{-a\!\cdot\!i\bmod p\}\) の期待値を求めれば十分で、これは都合良く \(\frac{1}{p}\min_{i=1,\ldots,k}\{a\!\cdot\!i\bmod p\,|\,i=1\ldots k\}\) の期待値でもある。我々は後者の式に注目する。

乗数 \(a\) の値を 1 から \(p-1\) まで増加させると何が起きるか考えてみよう。\(0,\ldots,p-1\) の数字が円の周りに時計回りに配置されていると考えると便利である。集合 \(X_k\) から数値 \(1,\ldots,k\) に対応する \(k\) 個のトークンを考える。各 \(i\) について、\(a\!\cdot\!i\bmod p\) は時刻 \(a\) における \(k\) 番目のトークンの位置と見なす。トークン \(i\) は位置 \(i\) から始まる。乗数 \(a\) の値を 1 から \(p-1\) まで増加させるとすべてのトークンは円の周りを時計回りに移動するがその速度は異なる。トークン \(i\) は時間刻みごとに \(i\) ステップ移動する。

\(p\) が \(k\) より十分に大きい場合、この運動は連続的であると考えることができる。つまり円周が 1 となるように円を拡大縮小する。\(f=\frac{a}{p}\) とすると、乗数 \(a\) のときの円周上の原点からのトークン \(i\) の距離は \(fi\) の分数部分となる。これ以降、このトークンの運動は "時刻" \(f\) が 0 から 1 まで連続的で一様に増加すると考える。\(f\) が 0 から 1 まで一様に増加するにつれ、原点に最も近いトークンの平均距離を計算する必要がある。ここでの距離は円周に沿って時計回りの距離として測定される。この平均距離は (漸近的に) \(\frac{1}{p}\min_{i=1,\ldots,k}\{a\!\cdot\!i\bmod p\}\) であり、我々が計算したい項である (近似は低次の項だけに影響するため、漸近的にこの近似は正しい答えをもたらす)。

トークンが転々に到達するたびに原点に最も近いトークンが変化する。これは、\(f\) の値が \(1\le n\lt d\le k\) となる整数 \(n\) および \(d\) に対して \(\frac{n}{d}\) のとき、速度 \(d\) のトークンが原点に到達した時点で起きる。したがって原点に最も近いトークンが変化する時刻はまさに分母が最大でも \(k\) の適切な (1 未満の) 分数、すはなち次数 \(k\) もファレイ数列の項となる。\(\frac{n_1}{d_1}\) と \(\frac{n_2}{d_2}\) を次数 \(k\) のファレイ数列の連続する 2 つの分数とする。\(\frac{n_1}{d_1}\le f\le\frac{n_2}{d_2}\) のとき速度 \(d_1\) のトークンが最も原点に近い。この時間間隔は長さ \(\frac{n_2}{d_2}-\frac{n_1}{d_1}=\frac{1}{d_1d_2}\) である。この時間間隔の間、トークンは原点をスタートし速度 \(d_1\) で移動する。したがってこの時間間隔におけるトークンの原点からの平均距離は \(\frac{1}{2}\!\cdot\!d_1\!\cdot\!\frac{1}{d_1d_2}=\frac{1}{2d_2}\) となる。

区間全体の平均距離を求めるには連続するファレイ分数のすべての組に対して適切な加重和を取れば良い。以上により各区間 \([\frac{n_1}{d_1},\frac{n_2}{d_2}]\) は \(\frac{1}{d_1d_2}\cdot\frac{1}{2d_2}=\frac{1}{2d_1d_2^2}\) となる。

得られた和の単純な形式を見つけるために \(X=\{0,1\}\) の適切な和から初めて集合 \(X_k\) まで構築する。別の方法として、\(j-1\) 次のファレイ数列から \(j\) 次のファレイ数列への積み上げで和がどう変化するかを考え、それを使って次数 \(k\) のファレイ級数の適切な和を導くこともできる。\(j\) 次ファレイ数列は \(j-1\) 次ファレイ数列に \((a,j)=1\) となる \(\frac{a}{j}\) 形式の分数をすべて適切な位置で加算することによって導かれる (\(\gcd(a,j)\) の標準的な省略形 \((a,j)\) を使っていることに注意)。これに対応して新しい分数が挿入されるすべての区間で総和への寄与が変化する。\(\frac{n_1}{d_1}\) と \(\frac{n_2}{d_2}\) の間に分数が挿入されたとする。このとき挿入される分数は \(\frac{n_1+n_2}{d_1+d_2}\) でなければならない。ここで \(d_1+d_2=k\) である。挿入される前、この区間の寄与は \(\frac{1}{2d_1d_2^2}\) であったものが、挿入後は \(\frac{1}{2d_1(d_1+d_2)^2}+\frac{1}{2(d_1+d_2)d_2^2}\) となる。したがってその変化は \[ \frac{1}{2d_1(d_1+d_2)^2} + \frac{1}{2(d_1+d_2)d_2^2}-\frac{1}{2d_1d_2^2} \\ = \frac{d_2^2+d_1(d_1+d_2)-(d_1+d_2)^2}{2d_1(d_1+d_2)^2d_2^2} \\ = \frac{-1}{2(d_1+d_2)^2d_2} \] \(d_1+d_2=j\) であることに注意。さらに \((j,d_2)=1\) である。実際、\((a,j)=1\) であるすべての \(a\) に対して \(d_1+d_2=j\) および \(d_2=a\) であるような 2 つの連続するファレイ分数 \(\frac{n_1}{d_2}\) と \(\frac{n_2}{d_2}\) が存在する。したがって次数 \(j-1\) から次数 \(j\) のファレイ数列を構築することによって生じる総和の変化は \(\frac{-1}{2j^2}\sum_{(a,j)=1,1\le a\le j}\frac{1}{a}\) となる。次数 1 のファレイ数列での適切な総和の値は明らかに \(\frac{1}{2}\) である。したがって次数 \(k\) のファレイ数列の値は \[ \frac{1}{2}\left(1-\sum_{j=2}^k\frac{1}{j^2}\sum_{(a,j)=1,1\le a\le j}\frac{1}{a}\right) \]

ここから、この式の値を漸近的に評価するだけで定理を得ることができる。読者には明らかに退屈な代数的な詳細は割愛する。∎

定理 8 は、ランダムな線形変換を用いた場合にある要素が最小となる集合を \(\Omega(\frac{\log k}{k})\) で見つけることが可能であることを示している。同様に、\(\pi(\lfloor(k-1)/2\rfloor)\) が漸近的に \(\pi(X_k)\) の最小要素であることを、確率 \(\frac{12\ln 2}{\pi^2k} \approx \frac{0.843}{k}\) で示すことができる。この結果はランダムな線形変換を用いたときに要素が最小になる確率が \(\frac{1}{k}\) より小さくなることを示す例となる。

線形変換は一見すると最悪な挙動を示すが、ランダムな集合に対して良好な性能を示すため実際には応用に適していると考えている。大きさ \(k\) の集合 \(X=\{x_0,\ldots,x_{k-1}\}\) に対して \(F(X)\) を \(\max_i \frac{|\{\pi|\min\{\pi(X)\}=\pi(x_i)\}|}{p(p-1)}\) とする。つまり \(F(X)\) は、最小になる可能性が最も高い要素が実際に最小となる置換の割合である (そして最悪の場合は \(F(X)\ge\frac{3}{\pi^2}\frac{\ln k}{k}\) であることが分かっている)。大きさ \(k\) のすべての集合から \(X\) を一様にランダムに選んだときの \(F(X)\) の期待値は、\(k,p\to\infty\) として \((1+1/\sqrt{2})/k+O(1/k^2)\) で収束できることを証明する。この意味で線形変換はランダム集合に対して近似 min-wise 独立である。

定理 9. \(k,p\to\infty\), \(p\gg k^2\) として、\({\bf E}_X[F(X)]\) の上限は \((1+1/\sqrt{2})/k+O(1/k^2)\) に束縛される。

証明. 次のように定義する。\[ f_i(X) = \frac{|\{\pi\,|\,\min\{\pi(X)\}=\pi(x_i)\}|}{p(p-1)} \] また \[ g_i(z,X) = \frac{|\{\pi\,|\,\min\{\pi(X)\}=\pi(x_i)\mbox{ and }\pi(x_i)=z\cdot p\}|}{p-1} \] つまり \(i\) 番目の要素を \(zp\) にマップする置換の部分集合を考える。このとき \(g_i\) は \(i\) 番目の要素が最小となる置換の割合である。

以下では、母数の大きさ \(p\) が十分に大きいため、\(z\) が \(1/p\) の離散的なジャンプではなく、単位円上で 0 から 1 まで連続的に変換することができると仮定する。この単純化により多くの低次の項を無視することができる。同様に、\(p\) は \(k\) に比べて十分に大きいとすることで、\(X\) の \(k\) 個の値は置換 (with replacement) によって選択され、結果は漸近的に同等になると仮定できる。

我々が束縛したい値は \[ F(X) = {\bf E}_X[\underset{i=0,\ldots,k-1}{\max}f_i(X)] \] である。ここで \({\bf E}_X\) は期待値が集合 \(X\) のランダムな選択に対するものであることを表すのに使う。また次の関係があることにも注意: \[ f_i(X) = \int_0^1 g_i(z,X)dz \]

\(f_i(X)\) が平均 \(\mu\) と分散 \(\sigma^2\) であるとする (平均と分散はすべての \(f_i\) に対して同じであることに注意)。\(F(X)\) を束縛するためには、いくつかの同一分布の確率変数 (identically distributed random variables) の最大値を期待値に対する単純な束縛を利用する。

補題 1. \(X_1,X_2,\ldots,X_k\) を平均 \(\mu\)、分散 \(\sigma^2\) の同一分布確率変数とすると、\[ {\bf E}[\underset{i=1,\ldots,k}{\max}X_i] \le \mu + \sigma\sqrt{k} \]

証明. 次に等価であることを示す。\[ \left({\bf E}[\underset{i=1,\ldots,k}{\max}X_i-\mu]\right)^2 \le k\sigma^2 \] \[ \begin{eqnarray*} \left({\bf E}[\underset{i=1,\ldots,k}{\max}X_i-\mu]\right)^2 & \le & {\bf E}\left[(\underset{i=1,\ldots,k}{\max}X_i-\mu)^2\right] \\ & \le & {\bf E}\left[\underset{i=1,\ldots,k}{\max}(X_i-\mu)^2\right] \\ & \le & {\bf E}\left[\sum_{i=1,\ldots,k}(X_i-\mu)^2\right] \\ & \le & \sum_{i=1,\ldots,k}{\bf E}\left[(X_i-\mu)^2\right] \\ & = & k\sigma^2 \end{eqnarray*} \]   ∎

対称性により \({\bf E}_X[f_i(X)]=1/k\) であることは明らかである。したがって \(F\) の上限を求めるには \(f_i(X)\) の分散である \(\sigma^2\) を束縛すれば良い。具体的には我々は \(f_0(X)\) の分散を束縛する。

役に立つ表記法をいくつか定義しておく。\(\pi_{a,z}\) は \(ax_0+b=z\cdot p \bmod p\) となるような一意の線形置換を表すとする。つまり \(\pi_{a,z}\) は \(x_0\) を \(z\cdot p\) にマップする乗数 \(a\) による線形置換である。\(M_a(z,X)\) を \(\min\{\pi_{a,z}(X)\}=\pi_{a,z}(x_0)\) のとき 1 となる指標確率変数 (indicator random variable) とする。したがって \(g_0(z,X)=\frac{1}{p}\sum_a M_a(z,X)\) となる。これで \(f_0\) の分散はちょうど次のようになる。\[ \begin{eqnarray*} \sigma^2 & = & {\bf E}_X\left[(f_0(X) - {\bf E}_X[f_0(X)])^2\right] \\ & = & {\bf E}_X\left[ \left(\int_0^1 g_0(z,X)dz - {\bf E}_X\left[ \int_0^1 g_0(z,X)dz \right]\right)^2 \right] \\ & = & {\bf E}_X\left[ \left(\int_0^1 (g_0(z,X) - {\bf E}_X\left[g_0(z,X)\right]) dz\right)^2 \right] \\ & = & \frac{1}{p^2} {\bf E}_X\left[\left(\int_0^1\left( \sum_a M_a(z,X) - {\bf E}_X\left[ \sum_a M_a(z,X) \right]\right)dz\right)^2\right] \\ & = & \frac{1}{p^2} {\bf E}_X\left[\left(\int_0^1\sum_a\left( M_a(z,X) - {\bf E}_X\left[ M_a(z,X) \right]\right)dz\right)^2\right] \end{eqnarray*} \]

\(\mu_a(z)={\bf E}_X[M_a(z,X)]\) とする。この定義から、他のランダムに選択された \(k-1\) 個の要素の写像はそれぞれ \(z\cdot p\) より大きい確率 \(1-z\) を持っているため、\(\mu_a(z)=(1-z)^{k-1}\) となることが明らかである。

したがって上記の最後の行の続きは、\[ \begin{eqnarray} \sigma^2 & = & \frac{1}{p^2}{\bf E}_X\left[\left(\int_0^1\sum_a\left(M_a(z,X)-{\bf E}_X[M_a(z,X)]\right)dz\right)^2\right] \nonumber \\ & = & \frac{1}{p^2}{\bf E}_X\left[\int_{z=0}^1\int_{y=0}^1\left(\sum_{a_1,a_2}(M_{a_1}(z,X)-\mu_{a_1}(z)) \times (M_{a_2}(y,X)-\mu_{a_2}(y))\right)dy\;dz\right] \nonumber \\ & = & \frac{1}{p^2}\int_{z=0}^1\int_{y=0}^1\left(\sum_{a_1,a_2}\left( {\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)] - \mu_{a_1}(z)\mu_{a_2}(y) \right)\right)dy\;dz \label{e9} \end{eqnarray} \]

ここで最後の項を束縛する。これにより分散が束縛され定理が導かれる。これを行うために \({\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)]\) の代替表現を導出し適切に束縛できるようにする。

\[ q_{a_1,a_2}(z,y) = \pr_{x\in[p]}(\pi_{a_1,z}(x) \gt y\cdot p \mbox{ and } \pi_{a_2,y}(x) \gt z\cdot p) \] とすると、\[ {\bf E}_X[M_{a_1}(z,X) M_{a_2}(y,X)] = (q_{a_1,a_2}(z,y))^{k-1} \] であり、やはり \(X\) の他の \(k-1\) 個の項は一様にランダムに選ばれるからである。

このように、束縛したい値を \(q_{a_1,a_2}\) 項の \((k-1)\) 乗の和として表現した。次の補題は、この \(q_{a_1,a_2}\) 項の我が一定であることを示す。\((k-1)\) 乗の合計の取り得る最大値は、和の項が極値を取るときに発生するため、これらの結果を併せると \(\sum_{a_1,a_2}{\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)]\) を束縛することができる。

補題 2. \[ \sum_{a_1,a_2}q_{a_1,a_2}(z,y) = p^2(1-z)(1-y) \]

証明. 次のような実験を考えてみよう。3 つの値 \(a_1,a_2,x\in[p]\) を独立かつ一様にランダムに選ぶ。実験は \(\pi_{a_1,z}(x)\gt y\cdot p\) と \(\pi_{a_2,y}(x)\gt z\cdot p\) の両方が成立すれば成功である。成功の確率は明らかに \((1-z)(1-y)\) である。総和 \(\sum_{a_1,a_2}p\cdot q_{a_1,a_2}(z,y)\) は実験が成功した \(p^2\) 個のトリプル \((a_1,a_2,x)\) の個数であり、補題を支持する。∎

\(q_{a_1,a_2}\) 項の総和は固定であるため \(q_{a_1,a_2}\) が極値を取るとき総和 \(\sum_{a_1,a_2}{\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)]\) は最大となる。ここで \(z\ge y\) と仮定すると \(q_{a_1,a_2}(z,y)\in[1-z-y,1-z]\) である (もちろん \(q_{a_1,a_2}(z,y)\ge 0\) なので \(z+y\gt 1\) の場合に上記の範囲は正しくないかもしれない)。そこで簡単な計算で次の境界が得られる (\(z+y\le 1\) の場合)。\[ \sum_{a_1,a_2}{\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)] \le p^2(z(1-z)^{k-1}+(1-z)(1-z-y)^{k-1}) \] \(z\le 1/2\) の範囲でこの境界を使うことにする。\(z\gt 1/2\) において \(q_{a_1,a_2}(z,y)\le 1-z\le 1/2\) が成立する。したがって \[ \sum_{a_1,a_2}{\bf E}_X[M_{a_1}(z,X)M_{a_2}(y,X)] \le p^2(1/2^{k-1}) \]

この境界を (\(\ref{e9}\)) に代入すると次を得る: \[ \begin{eqnarray*} \sigma^2 & = & \frac{1}{p^2}{\bf E}_X\left[\int_{z=0}^1\int_{y=0}^1\left(\sum_{a_1,a_2}\left(M_{a_1}(z,X)M_{a_2}(y,X)-\mu_{a_1}(z)\mu_{a_2}(y)\right)\right)dy\;dz\right] \\ & = & \frac{2}{p^2}\int_{z=0}^1\int_{y=0}^z\left( z(1-z)^{k-1}+(1-z)(1-z-y)^{k-1}-(1-z)^{k-1}(1-y)^{k-1} \right) dy\;dz \\ & & + 2\int_{z=1/2}^1\int_{y=0}^z\frac{1}{2^{k-1}}dy\;dz \\ & \le & 2\int_{z=0}^{1/2}\int_{y=0}^z\left( z(1-z)^{k-1}+(1-z)(1-z-y)^{k-1}-(1-z)^{k-1}(1-y)^{k-1} \right)dy\;dz \\ & & + 2\int_{z=1/2}^1\int_{y=0}^z\frac{1}{2^{k-1}}dy\;dz \end{eqnarray*} \]

定理 1 を証明にするにはこの積分を計算して分散を束縛するだけで良い。この計算は簡単で \[ \sigma^2 \le \frac{1}{2k^3}+O(1/k^4) \] である。これにより定理 9 が証明される。∎

シミュレーションの結果、実際にはランダム集合 \(X\) に対する線形変換の族の振る舞いはこれよりも遙かに優れていることを示唆していた。\(F(X)\) の期待値は漸近的に \(1/k\) に収束すると推測される。

また定理 9 は実際にはすべての pairwise 独立族に対して非常に素直に一般化されることに注意。表記は若干難しくなるが証明は同じ経路をたどる。

5 Acknowledgements

The authors thank Noam Elkies for enlightening discussions regarding Farey series.

References

1. N. Alon, M. Dietzfelbinger, P. B. Miltersen, E. Petrank, and G. Tardos. Is linear hashing good? In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 465–474, El Paso, Texas, 4–6 May 1997.
2. N. Alon and J. H. Spencer. The Probabilistic Method. JohnWiley and Sons, 1992.
3. T. M. Apostol. Introduction to Analytic Number Theory. Springer-Verlag, 1976.
4. T. Berners-Lee, R. Cailliau, A. Loutonen, H. F. Nielsen, and A. Secret. The world-wide web. Communications of the ACM, 37(8):76–82, 1994.
5. A. Z. Broder. On the resemblance and containment of documents. In Proceedings of Compression and Complexity of SEQUENCES 1997. To appear.
6. A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig. Syntactic clustering of the Web. In Proceedings of the Sixth InternationalWorld Wide Web Conference, pages 391–404, 1997.
7. A. Z. Broder and A. R. Karlin. Multilevel adaptive hashing. In Proceedings of the First Annual ACMSIAM Symposium on Discrete Algorithms, pages 43–53, San Francisco, California, 22–24 Jan. 1990.
8. J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, Apr. 1979.
9. M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. M. auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738–761, Aug. 1994.
10. D. E. Knuth. The Art of Computer Programming, Vol. I: Fundamental Algorithms. Addison-Wesley, second edition, 1973.
11. M. Luby and A. Wigderson. Pairwise independence and derandomization. Technical Report TR-95-035, International Computer Science Institute, Berkeley, California, 1995.
12. R. Seltzer, E. J. Ray, and D. S. Ray. The Alta Vista Search Revolution : How to Find Anything on the Internet. McGraw-Hill, 1996.
13. R. J. Souza, P. Krishnakumar, C. M. O¨ zveren, R. J. Simcoe, B. A. Spinney, R. E. Thomas, and R. J. Walsh. GIGAswitch: A high-performance packet-switching platform. DIGITAL Technical Journal, 6(1):9–22, 1994.

翻訳抄

1. BRODER, Andrei Z., et al. Min-wise independent permutations. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. p. 327-336.