確率的方法

数学において、確率的方法は非構成的な方法であり、主に組合せ論で使用され、ポール・エルデシュによって開拓され、指定された種類の数学的対象の存在を証明するために使用されます。指定されたクラスからオブジェクトをランダムに選択した場合、結果が指定された種類になる確率が0より厳密に大きいことを示すことによって機能します。証明には確率が使用されますが、最終的な結論は確実に決定され、エラーが発生することはありません。

この方法は現在、数論、線型代数、実解析などの数学の他の分野、およびコンピューターサイエンス（ランダムな丸めなど）や情報理論にも応用されています。

導入

オブジェクトのコレクション内のすべてのオブジェクトが特定のプロパティを持たない場合、コレクションからランダムに選択されたオブジェクトがそのプロパティを持つ確率はゼロになります。

同様に、確率が（厳密に）1 未満であることを示すことで、規定された特性を満たさないオブジェクトの存在を証明できます。

確率的方法を使用する別の方法は、あるランダム変数の期待値を計算することです。ランダム変数が期待値よりも小さい値を取ることができることが示されれば、ランダム変数が期待値よりも大きい値を取ることもできることが証明されます。

あるいは、確率的方法は、計算された期待値以上の値を持つサンプル空間内の目的の要素の存在を保証するためにも使用できます。そのような要素が存在しないということは、サンプル空間内のすべての要素が期待値未満であることを意味し、矛盾が生じるためです。

確率的方法で使用される一般的なツールには、マルコフの不等式、チェルノフ境界、ロヴァースの局所補題などがあります。

エルデシュによる2つの例

エルデシュ以前にも確率的手法で定理を証明した人はいたが（例えば、多数のハミルトン閉路を含むトーナメントが存在するという1943年のセレの結果）、この手法を使った最も有名な証明の多くはエルデシュによるものである。以下の最初の例は、ラムゼー数 $R$ $($ $r$ $,$ $r$ $)$ の下限を証明する1947年のそのような結果の1つについて述べている。

最初の例

$n$ 頂点の完全グラフがあるとします $。n$ の値が十分小さい場合、グラフの辺を2 色 (赤と青など) で着色することができ、 $r$ 頂点に単色 (すべての辺が同じ色) の完全サブグラフが存在しないことを示します。

これを行うには、グラフをランダムに色付けします。各エッジを、赤になる確率が 1/2、青になる確率が 1/2 で独立して色付けします $。r$ 頂点 $上$ $の$ 単色サブグラフの予想数は次のように計算します。

グラフの任意の頂点集合について、頂点間のすべての辺が同じ色である場合は変数を $1に、そうでない場合は$ $0$ に定義します。単色 -サブグラフの数は、すべての可能なサブセットの合計であることに注意してください。任意の個別の集合について、の期待値は、内のすべての辺が同じ色である確率です。 $S_{r}$ $r$ $X(S_{r})$ $r$ $r$ $X(S_{r})$ $S_{r}$ $S_{r}^{i}$ $X(S_{r}^{i})$ $C(r,2)$ $S_{r}^{i}$

E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}

(係数 $2$ は、色が 2 つあるためです)。

これは、選択可能なサブセットのいずれに対しても当てはまります。つまり、範囲は 1 からです。 $したがって$ 、全体の合計は $C(n,r)$ $i$ $C(n,r)$ $E[X(S_{r}^{i})]$ $S_{r}^{i}$

\sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.

期待値の合計は合計の期待値（変数が独立であるかどうかに関係なく）なので、合計の期待値（すべての単色サブグラフの期待数）は $r$

E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.

この値が $1未満の場合に何が起こるか考えてみましょう。単色$ $r$ サブグラフの期待数は厳密に $1未満であるため、単色$ $rサブグラフの数が厳密に$ $1$ 未満であるという条件を満たす着色が存在します。このランダム着色における単色 $r$ サブグラフの数は非負の整数であるため、 $0$ でなければなりません( $0は$ $1$ 未満の唯一の非負の整数です)。したがって、

E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}}1

（これは、例えば、 $n = 5$ および $r = 4の場合に成り立つ）、単色の$ $r$ 部分グラフが存在しない着色が存在するはずである。^[a]

ラムゼー数の定義により、これは $R (r, r)が$ $n$ より大きくなければならないことを意味します。特に、 $R (r, r) は$ $r$ とともに少なくとも指数関数的に増加する必要があります。

この議論の弱点は、完全に非構成的であるということである。この議論は、（例えば） $（1.1） r$ $頂点上の完全グラフのほぼすべての彩色に単色のr$ 部分グラフが含まれないことを証明しているが、そのような彩色の明示的な例は示していない。そのような彩色を見つける問題は、50年以上も未解決のままである。

^
同じ事実は、単純な計数議論を使って確率なしで証明することができます。
- rサブグラフの総数はです。 ${n \choose r}$
- 各rサブグラフにはエッジがあり、さまざまな方法で色付けできます。 ${r \choose 2}$ $2^{r \choose 2}$
- これらの色付けのうち、そのサブグラフにとって「不適切な」色付けは 2 つだけです (すべての頂点が赤、またはすべての頂点が青の色付け)。
- したがって、ある（少なくとも 1 つの）サブグラフにとって不適切な着色の総数は最大です。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$
- したがって、の場合、どのサブグラフに対しても「悪い」色付けではない色が少なくとも 1 つ存在する必要があります。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}}1$

2番目の例

1959 年のエルデシュの論文 (下記の参考文献を参照) では、グラフ理論における次の問題が取り上げられています。正の整数 $g$ と $k が$ 与えられたとき、少なくとも $gの長さの$ サイクルのみを含み、 $G$ の彩色数が少なくとも $k$ であるようなグラフ $G$ は存在するでしょうか。

$このようなグラフは任意のg$ と $k$ に対して存在することが示され、その証明はかなり簡単です。 $nが非常に大きい場合、$ $n$ 頂点のランダムグラフ $Gを考えます。ここで、$ $Gのすべての辺は確率$ $p$ $=$ $n$ $1/$ $g$ $-1$ で存在します。正の確率で、 $G は$ 次の 2 つの特性を満たすことを示します。

性質1.

G には、長さが

g

未満であるサイクルが最大で

n / 2 個

含まれる。

証明。X $を$ $g$ 未満の長さの閉路の数とする。n $頂点$ の完全グラフにおける長さ $i$ の閉路の数は

{\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}

そして、それらのそれぞれは確率 $p$ $i$ $でG$ に存在する。したがって、マルコフの不等式により、

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).

したがって、十分に大きい

nの場合、特性 1 は

1/2 を

超える確率で成立します。

性質 2.

G

にはサイズの独立集合が含まれない。

\lceil {\tfrac {n}{2k}}\rceil

証明。Y $を$ $G$ 内の最大の独立集合の大きさとする。明らかに、

\Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),

いつ

y=\left\lceil {\frac {n}{2k}}\right\rceil \!.

したがって、十分に大きい

nの場合、特性 2 は

1/2 を

超える確率で成立します。

$n$ が十分に大きい場合、これらの特性のイベントは互いに素ではあり得ないため、分布のグラフが両方の特性を持つ確率は正になります (もし素であれば、その確率の合計は 1 を超えます)。

ここでトリックが登場します。G に $はこれら 2 つの特性があるため、$ $G$ から最大で $n /2 個の頂点を削除して、長さが少なくとも$ $g$ の閉路のみを含む頂点上の新しいグラフ $G'$ を取得できます。この新しいグラフには、サイズの独立集合がないことがわかります。G $'$ は少なくとも $k 個の$ 独立集合にのみ分割できるため、彩色数は少なくとも $k$ です。 $n'\geq n/2$ $\left\lceil {\frac {n'}{k}}\right\rceil$

この結果は、グラフの彩度数の計算がなぜそれほど難しいのかについてのヒントを与えます。グラフに多くの色が必要になる局所的な理由 (小さなサイクルなど) がない場合でも、彩度数は依然として任意に大きくなる可能性があります。

参照

追加リソース

組合せ論における確率的手法、MIT OpenCourseWare

参考文献

アロン・ノガ、スペンサー・ジョエル・H. (2000)。 確率的手法（第2版）。ニューヨーク：ワイリー・インターサイエンス。ISBN 0-471-37046-0 。
Erdős, P. (1959). 「グラフ理論と確率」. Can. J. Math . 11 : 34–38. doi : 10.4153/CJM-1959-003-9 . MR 0102081. S2CID 122784453.
Erdős, P. (1961). 「グラフ理論と確率 II」. Can. J. Math . 13 : 346–352. CiteSeerX 10.1.1.210.6669 . doi :10.4153/CJM-1961-029-9. MR 0120168. S2CID 15134755.
J. マトウシェク、J. ヴォンドラック。確率的手法。講義ノート。
アロン、N およびクリベレヴィッチ、M (2006) 極限的および確率的組合せ論
エリシャコフ I.、構造理論における確率的手法：材料のランダム強度、ランダム振動、座屈、ワールドサイエンティフィック、シンガポール、ISBN 978-981-3149-84-7、2017年
Elishakoff I.、Lin YK、Zhu LP、「音響励起構造の確率的および凸型モデリング」、Elsevier Science Publishers、アムステルダム、1994 年、VIII + pp. 296、ISBN 0 444 81624 0

脚注

[1] 同じ事実は、単純な計数議論を使って確率なしで証明することができます。
rサブグラフの総数はです。 ${n \choose r}$

各rサブグラフにはエッジがあり、さまざまな方法で色付けできます。 ${r \choose 2}$ $2^{r \choose 2}$

これらの色付けのうち、そのサブグラフにとって「不適切な」色付けは 2 つだけです (すべての頂点が赤、またはすべての頂点が青の色付け)。

したがって、ある（少なくとも 1 つの）サブグラフにとって不適切な着色の総数は最大です。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$

したがって、の場合、どのサブグラフに対しても「悪い」色付けではない色が少なくとも 1 つ存在する必要があります。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}}1$

[2] rサブグラフの総数はです。 ${n \choose r}$

[3] 各rサブグラフにはエッジがあり、さまざまな方法で色付けできます。 ${r \choose 2}$ $2^{r \choose 2}$

[4] これらの色付けのうち、そのサブグラフにとって「不適切な」色付けは 2 つだけです (すべての頂点が赤、またはすべての頂点が青の色付け)。

[5] したがって、ある（少なくとも 1 つの）サブグラフにとって不適切な着色の総数は最大です。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}$

[6] したがって、の場合、どのサブグラフに対しても「悪い」色付けではない色が少なくとも 1 つ存在する必要があります。 $2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}}1$

導入

エルデシュによる2つの例

最初の例

2番目の例

参照

追加リソース

参考文献

脚注

関連するトピック

数学

非構成的な

組合せ論で使用され、

ポール・エルデシュ