黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

「カドカワドワンゴから"カドカワ"を含む文字列ができる確率」について

「カドカワドワンゴから1文字ずつ非復元抽出/復元抽出して"カドカワ"を含む文字列ができる確率を求めてみた(唯物是真 @Scaled_Wurm) 」の記事を読んでいたところ、"カドカワドワンゴ"の文字を並び替えに関する確率の問題が紹介されていた。これを読み、確率の問題の解き方について復習した内容を書いた。暇な方は是非読んで欲しい。

例の記事の素晴らしい点

例の記事の素晴らしい所は、問題を解くための漸化式の組み方が紹介されている事だ。ここで漸化式とはある状態n(自然数)における項a_nが、状態(n-1)以前の項の関数として定まる事を言い、例えばa_n=2*a_(n-1),a_(n+2)=a_(n+1)+a_n 等がこれに当たる。

漸化式はプログラムに落とし込みやすいというメリットがあり、どういう状況でどう落とし込むのかを知って大変勉強になった。落とし込む代表的な手法として動的計画法というものがあり、どれくらいの計算量か?と言う所まで説明がされていたのもよかった。

非復元抽出の場合

さてここから復習した内容を紹介する。統計などで調査対象のとなる数値,属性等の源泉となる集合全体を母集団、その一部の調査対象のとなる数値,属性等を抽出したものを標本と言う。

このとき非復元抽出とは、母集団から標本を選ぶ場合に、1つの個体を選んだ後にその個体を母集団の中に戻さずに繰り返して行って標本を選ぶ方法の事を言う。以下、非復元抽出の場合の問題を紹介する。

文字列"カドカワドワンゴ"をランダムに並び替えた時、その文字列中に"カドカワ"が連続して含まれる確率を求めよ。但し、各文字は区別して考えるものとする。

解法

文字列全体の並べ方は8!通り考えられる。次にその文字列中に"カドカワ"が連続して含まれる場合の数を考える。手始めにカドカワを一かたまりと考える。ここでカドカワを入れる箇所を^で表すと右のようになる。このとき「^ド^ワ^ン^ゴ^」と^の箇所で5通り。そして、ドワンゴの4文字の並べ方で4!通り。カ、ド、ワは2文字あるので区別して考えると2^3通り。これより求める確率は5*4!*2^3/8! = 1/42(答)

復元抽出の場合における問題

今度は復元抽出の場合の問題を見てみよう。復元抽出とは、母集団から標本を選ぶ場合に、1つの個体を選んだ後にその個体を母集団の中に戻す事を繰り返して行って標本を選ぶ方法の事を言う。

"カドカワドワンゴ"のそれぞれの文字が書かれた8枚のカードがある。カードをシャッフルして1枚引き元に戻す試行を8回繰り返す。引いた8枚のカードの文字を順番に並べた時に"カドカワ"という文字が連続して含まれる確率を求めよ。但し各カードは区別して考え、カドカワカドカワ...のように2回以上カドカワの文字が含まれる場合は考えないものとする。

解法

この8回の試行において、カドカワが1回以上連続で出る事象をA_1と定義し、その確率P(A_1)を考える。例えば8枚のカードを1回引き、カ、ド、ワの文字の引く確率はそれぞれ2/8 = 1/4となる。まず4回連続でカドカワが出る確率は、p=(1/4)^4 = 1/256。次にカドカワをひとまとまりとして考え、残りの4文字の「^○^○^○^○^」の^の位置で5通りある。最後にこれらを掛け合わせ、P(A_1) = 5 * 1/256 = 5 * 5/256を得る。

さて、カドカワカドカワが2回以上連続で出る事象をA_2とすると、P(A_2) = (1/4)^8 = 1/65536となる。このとき事象A_1と事象とA_2の関係は以下の図のようになる。よって文字列カドカワが含まれる確率P(A_1- A_2) = P(A_1) - P(A_2) = 256*5/65536 - 1/65536 = 1279/65536(答)


f:id:program_study:20150604001314p:plain

元のブログで文字数が増えると計算が難しくなると書いてある理由は、A_1に内包される集合の数が増えて計算が大変になるからだと納得した。

包除原理

最後にこうした複数の集合の和集合を求める原理として、包除原理というものがあるらしい。wikipediaによれば集合A_1,,,,,,A_nを有限集合としたとき、以下の式が成立する事を言う。


f:id:program_study:20150604001342p:plain

この原理はプログラムのコンテスト対策の本にも書いてあって、アルゴリズムを覚えて行く上で重要そうだ。ちなみにn=2の場合がFizzBuzz問題に当たるなど、様々な状況に当てはめると見通しが良くなる場合がある。

高校受験、大学受験時代から確率の問題は苦手で、やっぱり何も見ないでやると間違えるから怖い。本記事が高校受験生や大学受験生のみなさんの参考になればと思う次第である。