(おそらく既存の結果として知られているほどの簡単なものですが, そういうのを調べず私が個人的に見つけた証明を載せているので, もし関連結果 or よりスマートな証明をご存知の方がいらしたら教えていただければ幸いです).
この定理を使えば, 有限加法族に対する条件付き期待値を具体的に構成することが出来ます.
(有限でない場合は無理です)
登録:
コメントの投稿 (Atom)
Håstadのスイッチング補題
回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...
-
0. 概要 本記事では ランダムグラフ理論の動機と応用 ランダムグラフ理論のさわり ランダムグラフの面白い定理 について書きます. 1. ランダムグラフ理論の動機と応用 ランダムグラフ理論の主な動機としては 「とある性質Pを満たすグラフ... -
0. 概要 グラフマイナー定理とは 有限グラフの全体は, マイナー順序によってよい擬順序になっている (well-quasi-ordered) という定理です. ...さてこれは何を言ってるんでしょうか. 本記事では現代のグラフ理論において最も重要な定理の一つで... -
1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに 全点対最短経路 ( APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと...
0 件のコメント:
コメントを投稿