はじめに
多分はじめて競技プログラミングの記事をかきます。ashiato45です。気にする方のために始めに申しますと、私はAtCoder水色ですので「黄未満のやつの書いた記事なんか読むだけ時間の無駄。」という方はお引き取りください。
追記(4/5)
コメントでid:sugarknri さんが解説1の解説をしてくださいました！
これは何？
F - Surrounded Nodesは「期待値の線形性」を使って最終的に木DPに落ちるのですが、そこに到達するまでの期待値の考察は、確率の独立性に関する落とし穴があるよねと思っています。参加記や公式解説を読んでも誰もそのことに言及してないのであれこれ僕がおかしいんですか誰か教えてくださいっていう記事です。
あと、公式解説や他の方の説明を読んでも木DPに落とすまでがピンと来てないという方の役に立つかもしれません。
経緯
e869120さんの力作記事に
qiita.com
というのがありこれを解いていたのですが、どうしても上記ABC149Fの解説2がよくわからなくて困ってしまいました。
2、3日ぐらい考えたらわかった気がしたしACもしたので共有します。
解説1は余計わかんないです。
偽証明
AtCoderの解説2は初っ端からこのようになっています:
期待値の線形性から、各頂点vについて、vがSに属しかつ白く塗られているような確率を計算し、その合計を求めればよいです。
というのですが、この後「vがSに属し」の話しかせず、白の条件の話をしないのです。これは白の条件が明らかだと皆思っているからなのだと思われますし、解説放送を見てもそんな感じがします。
ちなみに、解説1のスタートはこうなっています:
求めるものは「Sの頂点の個数-黒く塗られた頂点の個数」と等しいです。期待値の線形性から、それぞれの項の期待値が求まればよいです。黒く塗られた頂点の個数の期待値は明らかにN/2です。Sの頂点の個数の期待値を考えます。
これでもいきなりSが出てくるのが結局わからないのですが、つまるところ、問題にある「Tの各頂点を、それぞれ独立に確率 1/2 で黒く、確率 1/2 で白く塗り、」というところから1/2で割って、そこからスタートしているように見えます。この考え方を数式的に表わしてみるとこんな感じになります。ここで、どの要素が何に依存しているかをはっきりされるために、次のような記号をもちいます。
: Tの塗り分け方。いま考えている確率空間の根源事象ですね。問題文の独立性の仮定よりどのxも出方は同様に確からしいです。
: Tをxで塗ったときに定まるSを、xが決まってはじめて定まるものだということを強調してこう書きます。
:
を頂点とし、xを塗り分け方としたとき、頂点vが白く塗られているなら1、そうでないなら0を返す関数。
- χ(P): 命題Pが成立しているときに1、そうでないときに0をとります。指示関数といいます。
すると、求めたかったのはの穴開き度の期待値だったので、
さあこれで各頂点について、すなわちvが
に入っている確率を求めればよく、そのためには解説にあるように「vがSに含まれるための必要十分条件は…」を考えはじめればよい、ように見えます。
が、上の変形はいろいろ間違っています。
「かつ」をかけ算に直す
上の「「かつ」をかけ算に直す？」でやっているのは結局のところ確率変数X,YについてE[XY]=E[X]E[Y]なのですが、これは一般には成り立ちません。
例えばロシアンルーレットをやっていて、Xが「一人目で死亡のとき1、そうでないとき0」、Yが「二人目で死亡のとき1、そうでないとき0」という確率変数だと思いましょう。
するとXとY両方が1となることはないのですからE[XY]=0ですが、他方E[X]=E[Y]=1/6ですから*1、確かに成り立っていません。
E[XY]=E[X]E[Y]は、確率変数XとYが独立である、という仮定があるなら成立することが知られています。フォーマルにはp(X=x, Y=y)=p(X=x)p(Y=y)という条件で、直感的には「片方の確率変数が取る値を知ったとしても、もう片方の確率変数の出方が偏ったりしない」ということを意味します。例えば、先のロシアンルーレットなら「一人目が死んだ」とわかった、つまりX=1ならば二人目は絶対に安全でY=0が100%と、元のY=1が1/6、Y=0が5/6という確率分布から「偏って」しまいます。反対に「一人目が死ななかった」、つまりX=0だとわかったならば、二人目が死ぬ確率は1/5になりましたから何も知らなかったときより緊張感が増すことになります。
今回、「」と「vは塗り分けxで白」は独立でしょうか*2。
これは実は独立ではありません。なぜなら、今回の問題のSの「黒く塗られた頂点を全て含む」という定義からvが塗り分けxで黒だと分かったときは、が100%成立してしまうからです。
ですから、当然このかけ算をわけることはできず、またそこを1/2と切り分けて先に進んでしまうことはできないのです。
ちなみに、ランダムにSを取ってきたときに(まずそれが意味不明ですが)、そこにあらわれる白黒も平均|S|/2ぐらいでしょうと仰るかたもいるかもしれませんが、それも同様の理由で意味不明です。
でもこれ結局正しいじゃん
確かに最後に得られる式は正しいのですが過程が間違っています。推論を正しく進めるには、解説2にある次の考察がカギになります:
頂点vについて、Tからvを取り除いてできる部分木たちを
とします。このとき、vがSに含まれるための必要十分条件は、
たちのうち少なくとも2つが黒く塗られた頂点を含むこと
と言っているのですが、これは大変玄人向けで正確には次のようになります:
「vが白く塗られている条件のもので、vがSに含まれるための必要十分条件は、たちのうち少なくとも2つが黒く塗られた頂点を含むこと」です。論理の講義を思いだしてみて、かつxを強調すればこれはこうなります:
すると、たちはvを含まないのでvとは関係なく、これら2つの事象は独立になります！この変形をしてはじめて先の推論を正しく進めることができます:
これではじめて、木に集中してものを考えることができるはずで、あとは解説どおりです(ここからはここからで木DPになれてないと苦しいのですが)。
おわりに
そういうわけで、解説のギャップ埋めみたいなことをしてみました。多分強い人はこのあたりのことが直感的にわかるのだと思うのですが、私ぐらいだと面くらいましたしひょっとしたら自力で解けた人でも「まあ大体1/2だし1/2で割っとけばいいっしょ～」という方もいたのではないかなと思います。こういうのを考えるのが競技に強くなるのに重要かどうかは知りませんが、納得いかないので考えてみました。
