a probabilistic paradox on string

kinaba @kinaba

「0/1 の無限ビット列をランダムに作ります。先頭から見てってビット列 w が現れる最初のインデックスの期待値を e(w) とします。e(000) と e(001) は等しい？等しくない？」 これ面白いなー

kinaba @kinaba

わざわざクイズにするからには答えは「等しくない」で、e(001) の方が小さいんですけど、当然明らかに等しい気がするので、"A probabilistic paradox on strings" として今読んでいる本に紹介されてた

kinaba @kinaba

実験をしましょう http://codepad.org/eFoZp14m

kinaba @kinaba

ああ、部分ビット列と言わないと誤解が生じるか。言っても subsequence と sublist の違い的なそれがややこしいか。まあとにかく http://codepad.org/eFoZp14m これが言いたいことです。

kinaba @kinaba

@koizuka 要はrotateして自分と一致することがあればあるほど長くなります。e(0000)＞e(0101)＞e(0111) なはず

kinaba @kinaba

@random_oracle Analytic Combinatorics http://bit.ly/fHZM2X に載ってました。特にこういうクイズ本なわけではなく単に例題として出ただけなんですが、本論の方もこれとは別の意味でとても面白いです

kinaba @kinaba

http://twitter.com/kinaba/statuses/31675351834820608 rotateしてじゃないや、shiftして重なってる部分が同じなら同じほどというかつまり自己相関が云々

kinaba @kinaba

まあ皆Analytic Combinatorics http://bit.ly/fHZM2X を読むとよいのです。配列a[1..N]の並替えのうち途中でperm(a[1..K])+perm(a[K+1..N])と前後に分離できちゃうのは何通り？的な問いに異常にエレガントに答える書