唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

カドカワドワンゴから1文字ずつ非復元抽出/復元抽出して"カドカワ"を含む文字列ができる確率を求めてみた

最近KADOKAWA・DWANGOがカドカワになるというニュースがありました

KADOKAWAとドワンゴの経営統合を内外に強く示すため、両社の音を組み合わせたという。「カ」：KADOKAWAのKA、「ド」：ドワンゴのド、「カ」：KADOKAWAのKA、「ワ」：ドワンゴのワになる

このニュースをみて以下のような2つの問題を考えてみたので、解いてみます


非復元抽出版


"カドカワドワンゴ"のそれぞれの文字をカードにしてシャッフルしたあとに何枚か取り出して"カドカワ"という文字が連続して出てくる確率を考えてみます
\(n\)枚取り出した時に"カドカワ"という文字が連続してを\(P(n)\)とします
\(n \le 3\)では"カドカワ"ができないので\(4 \le n \le 8\)について考えます

解法1

まずは中学校で習ったような基本的な解法でやります
まず文字のすべての並べ方は\(\frac{8!}{(8-n)!}\)通りです
次に"カドカワ"を含む場合を考えます
"カドカワ"が一つのまとまりとして必ず含まれていると考えると、"カドカワ"の位置が\(n-3\)通り、残りの文字の並べ方は\(\frac{(8-4)!}{(8-n)!}=\frac{4!}{(8-n)!}\)通り
"カドカワ"の"カ"、"ド"、"ワ"はそれぞれ\(2\)枚ずつあるので\(2^3=8\)倍して、整理すると\((n-3)\times\frac{4!}{(8-n)!}\times8\)
これを全体の並び方の数で割ると確率が出せて、\(P(n)=\frac{n-3}{7\times 6\times 5}\)となる
よって\(P(8)=\frac{1}{42}\)

解法2

次に同じ問題を包除原理を使って解いてみます(こっちのほうが計算が簡単で、復元抽出の方でも使います
前に以下の記事でも使いましたが、集合同士の和集合の大きさを求める方法です

基本的に\(|A \cup B| = |A| + |B| - |A \cap B|\)の一般化です
集合の数が増えた時には、組み合わせる集合を増やしながら足すのと引くのとを交互に繰り返していけばよいです
\(|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|\)
集合が\(n\)個の場合
$$\Biggl|\bigcup_{i=1}^n A_i\Biggr| = \sum_{k = 1}^{n} (-1)^{k+1} \left( \sum_{1 \leq i_{1} < \cdots < i_{k} \leq n} \left| A_{i_{1}} \cap \cdots \cap A_{i_{k}} \right| \right)$$

ある位置で"カドカワ"が始まる事象について考えると、同時に違う位置で"カドカワ"が始まることはありえないので結局単純にそれぞれの場所の確率を足し合わせればよいことになります
ある位置で"カドカワ"が始まる確率を\(p=\frac{2\times 1\times 2 \times 1}{8 \times 7 \times 6 \times 5}=\frac{1}{7 \times 6 \times 5}\)とおくと
\(P(n)\)は\(n-3\)通りの\(p\)を足し合わせればよいので\(P(n)=(n-3)p=\frac{n-3}{7\times 6\times 5}\)となります

復元抽出版


"カドカワドワンゴ"のそれぞれの文字をカードにしてシャッフルしたあとに1枚取り出して山札に戻す、という手順を何回か繰り返した時に"カドカワ"という文字が連続して出てくる確率を考えてみます

解法1

\(8\)文字の場合について上でやったのと同様に包除原理で考えてみます
ある場所から"カドカワ"が始まる確率\(p=\frac{1\times 1\times 1 \times 1}{4 \times 4 \times 4 \times 4}=\frac{1}{256}\)
非復元抽出の場合と同様に\(n-3\)倍すると、今回は\(n=8\)なので\(\frac{5}{256}\)となります
ただし\(8\)文字の場合には"カドカワカドカワ"のように"カドカワ"が\(2\)箇所に出現する場合があるのでその確率\(\frac{1}{65536}\)を引かなければいけません
よって\(P(8)=\frac{5}{256} - \frac{1}{65536} = \frac{1279}{65536}\)

\(8\)文字の場合は今回のように簡単に求めることができましたが、もっと文字数が長くなってくると"カドカワ"が何箇所にも出現する場合を考えないといけなくなり、包除原理でも計算がどんどん難しくなっていきます

解法2

今度は漸化式を書いて動的計画法で計算してみます
\(i\)文字目より前に"カドカワ"が出現せずに\(i\)文字目の位置で"カドカワ"の\(j\)文字目になっている確率を\(p_i(j)\)とします
\(i\)文字目の確率がわかっている時に\(i+1\)文字目の確率は以下のようになります
\(p_{i+1}(4) = \frac{1}{4} p_{i}(3)\)
\(p_{i+1}(3) = \frac{1}{4} p_{i}(2)\)
\(p_{i+1}(2) = \frac{1}{4} (p_{i}(1) + p_{i}(3))\)
\(p_{i+1}(1) = \frac{1}{4} (p_{i}(0) + p_{i}(1) + p_{i}(3))\)
\(p_{i+1}(0) = \frac{1}{4} (3p_{i}(0) + 2p_{i}(1) + 3p_{i}(2) + 2p_{i}(3)) - p_{i+1}(4)\)

最初の状態では\(p_0(0)=1\)となり、この数式を順に計算していけばそれぞれの確率が求められます
この時\(P(n)=\sum_i^n p_i(4)\)
行列の積の形になったので、繰り返し二乗法を使えば\(O(\log n)\)ぐらいで計算できるはず
(計算式が合っているか不安なので、間違っていたら教えていただけると嬉しいです)

試しに\(200\)文字まで計算してみてもおよそ\(54\)%ぐらいの確率でしか"カドカワ"の文字列は出現しません
f:id:sucrose:20150601000013p:plain

まとめ

"カドカワドワンゴ"からランダムに取り出して"カドカワ"が出現する確率は結構低い
ちなみに非復元抽出でも復元抽出でも「カドカワ」が出てくる確率のほうが「ドワンゴ」よりも高いです

ソースコード

# -*- coding: utf-8 -*-
from fractions import Fraction

N = 8
M = N + 1

dp = [[0]*5 for i in xrange(M)]

dp[0][0] = 1
for i in xrange(1, M):
    weight = [
        [3, 2, 3, 1],
        [1, 1, 0, 1],
        [0, 1, 0, 1],
        [0, 0, 1, 0],
        [0, 0, 0, 1],
    ]
    for j in xrange(4, -1, -1):
        for k in xrange(4):
            dp[i][j] += Fraction(1, 4) * weight[j][k] * dp[i - 1][k]

print float(sum([dp[i][4] for i in xrange(M)])), sum([dp[i][4] for i in xrange(M)])

"""
from pylab import *
import matplotlib.font_manager
data = []
cum = 0
for i in xrange(M):
    cum += dp[i][4]
    data.append(cum)
xlabel('n')
ylabel('probability')
prop = matplotlib.font_manager.FontProperties(fname=r'C:\Windows\Fonts\meiryo.ttc', size=14)
title(u'"カドカワドワンゴ"から$n$文字復元抽出して"ドワンゴ"を含む文字列を引き当てる確率', fontproperties=prop)
plot(xrange(M), data)
show()
"""