Fisher-Yates法

配列をシャッフルする際に用いられるアルゴリズムとして，Fisher-Yates法は非常に有名なのではないでしょうか．

Fisher-Yates法によるシャッフルアルゴリズムは，以下のようなコードになります．

def shuffle(array):
    for i in range(len(array)):
        r = random.randint(i, len(array) - 1)
        tmp = array[i]
        array[i] = array[r]
        array[r] = tmp
    return array

ときたま，Fisher-Yates法のアルゴリズムを以下のように実装しているコードを見かけます．

def shuffle(array):
    for i in range(len(array)):
        r = random.randint(0, len(array) - 1)
        tmp = array[i]
        array[i] = array[r]
        array[r] = tmp
    return array

しかし，このコードは厳密なシャッフルを行えないため，間違いがあるコードです．

今回は，なぜこのコードが間違っているのか，ということを，配列の長さが$3$の場合を例にして証明してみたいと思います．

証明すること

まず，配列の長さ$N$を$N=3$とします．

シャッフルコードが正しいアルゴリズムになっているなら，配列の$i$番目の要素がシャッフル実行後に$j$番目となっている確率は，偏りなく均等になっているはずです．

つまり，配列の$i$番目の要素が，$j$番目となっている確率を$p_{i,j}^{(N)}$とすると，$p_{i,j}^{(N)}=\frac{1}{N}$となっているはずです．

しかし，間違ったコードの書き方では，この確率に偏りが生じてしまいます．

以降では，間違ったコードを実行した場合の確率$p_{i,j}^{(N)}$を計算し，実際に偏りが生じてしまっていることを示します．

$p_{i,j}^{(N)}$の導出

$p_{i,j}^{(N)}$を計算するために，コードのループ部分を$n\in\{1,2,3\}$回実行した後に，$i$番目の要素が$j$番目となっている確率を$p_{i,j}^{(n)}$とし，この確率を順々に計算していきます．

$p_{i,j}^{(n)}$の漸化式

まず，順々に計算を行っていくために，$p_{i,j}^{(n)}$の漸化式を導出します．

$p_{i,j}^{(n)}$は，$p_{i,j}^{(n-1)}$を用いると，以下のように表すことができます．

$$p_{i,j}^{(n)}= \begin{cases} \frac{1}{N} & (j=n) \\ p_{i,j}^{(n-1)}\frac{N-1}{N} + p_{i,n}^{(n-1)}\frac{1}{N} & (j\neq n) \end{cases}$$

上の式では，$j=n$の場合と，$j\neq n$の場合で場合分けをしています．

これは，$n$番目に入れ替える対象がまさに$j$番目であるというケースと，それ以外とで分けて考えている，ということです．

$j=n$の場合，それまでに配列のどのインデックスにいようとも，入れ替えられる対象として選ばれた場合，$n$回目のループ実行後に$j$番目の要素となることができます．

したがって，$j=n$の場合，入れ替えられる対象として選ばれる確率$\frac{1}{N}$が$p_{i,j}^{(n)}$になります．

一方で$j\neq n$の場合，$n$回目のループ実行前に既に$j$番目にいるか，$n$回目のループ実行前に$n$番目にいる，という２つの条件のいずれかを満たしていなければなりません．

前者の条件を満たしている場合，$j$番目の要素が入れ替えられる対象として選ばれることがなければ，$n$回目のループ実行後に$j$番目の要素となることができます．

前者の条件を満たす確率は$p_{i,j}^{(n-1)}$であり，$j$番目の要素が入れ替えられる対象として選ばれる確率は$\frac{1}{N}$なので，前者の条件を満たし$n$回目のループ実行後に$j$番目の要素となる確率は$p_{i,j}^{(n-1)}\frac{N-1}{N}$となります．

後者の条件を満たしている場合，$j$番目の要素が入れ替えられる対象として選ばれれば，$n$回目のループ実行後に$j$番目の要素となることができます．

後者の条件を満たす確率は$p_{i,n}^{(n-1)}$であり，$j$番目の要素が入れ替えられる対象として選ばれる確率は$\frac{1}{N}$なので，後者の条件を満たし$n$回目のループ実行後に$j$番目の要素となる確率は$p_{i,j}^{(n-1)}\frac{1}{N}$となります．

結局，$j\neq n$の場合，これら２つの確率を足し合わせて，$p_{i,j}^{(n)}$は$p_{i,j}^{(n)}=p_{i,j}^{(n-1)}\frac{N-1}{N}+p_{i,j}^{(n-1)}\frac{1}{N}$と計算されます．

漸化式が導出できたので，あとは$n=1$から順々に計算を行っていきましょう．

$n=1$の場合の計算

(1) $i=1$の時

$$p_{1,j}^{(1)}=\frac{1}{N}$$

(2) $i>1$の時

$$\begin{aligned} p_{i,j}^{(1)}&= \begin{cases} \frac{1}{N} & (j=1) \\ p_{i,j}^{(0)}\frac{N-1}{N}+p_{i,1}^{(0)}\frac{1}{N} & (j\neq 1) \end{cases}\\ &= \begin{cases} \frac{1}{N} & (j=1) \\ 0 & (j>1 \wedge j\neq i) \\ \frac{N-1}{N} & (j>1 \wedge j=i) \end{cases} \end{aligned}$$

$n=2$の場合の計算

(1) $i=1$の時

$$p_{1,j}^{(2)}=\frac{1}{N}$$

(2) $i=2$の時

$$\begin{aligned} p_{2,j}^{(2)}&= \begin{cases} \frac{1}{N} & (j=2) \\ p_{2,j}^{(1)}\frac{N-1}{N} + p_{2,2}^{(1)}\frac{1}{N} & (j\neq 2) \end{cases}\\ &= \begin{cases} \frac{1}{N} & (j=2) \\ \frac{1}{N}\frac{N-1}{N}+\frac{N-1}{N}\frac{1}{N} & (j=1) \\ \frac{N-1}{N}\frac{1}{N} & (j>2) \end{cases} \end{aligned}$$

(3) $i>2$の時

$$\begin{aligned} p_{i,j}^{(2)}&= \begin{cases} \frac{1}{N} & (j=2) \\ p_{i,j}^{(1)}\frac{N-1}{N} + p_{i,2}^{(1)}\frac{1}{N} & (j\neq 2) \end{cases}\\ &= \begin{cases} \frac{1}{N} & (j=2) \\ \frac{1}{N}\frac{N-1}{N} & (j=1) \\ 0 & (j>2 \wedge j\neq i) \\ \frac{N-1}{N}\frac{N-1}{N} & (j>2 \wedge j=i) \end{cases} \end{aligned}$$

$n=3$の場合の計算

(1) $i=1$の時

$$p_{1,j}^{(3)}=\frac{1}{N}$$

(2) $i=2$の時

$$\begin{aligned} p_{2,j}^{(3)}&= \begin{cases} \frac{1}{N} & (j=3) \\ p_{2,j}^{(2)}\frac{N-1}{N} + p_{2,3}^{(2)}\frac{1}{N} & (j\neq 3) \end{cases}\\ &= \begin{cases} \frac{1}{N} & (j=3) \\ \frac{1}{N}\frac{N-1}{N} + \frac{N-1}{N}\frac{1}{N}\frac{1}{N} & (j=2) \\ (\frac{1}{N}\frac{N-1}{N} + \frac{N-1}{N}\frac{1}{N})\frac{N-1}{N} + \frac{N-1}{N}\frac{1}{N}\frac{1}{N} & (j=1) \\ \frac{N-1}{N}\frac{1}{N}\frac{N-1}{N} + \frac{N-1}{N}\frac{1}{N}\frac{1}{N} & (j>3) \end{cases} \end{aligned}$$

(3) $i=3$の時

$$\begin{aligned} p_{3,j}^{(3)}&= \begin{cases} \frac{1}{N} & (j=3) \\ p_{3,j}^{(2)}\frac{N-1}{N} + p_{3,3}^{(2)}\frac{1}{N} & (j\neq 3) \end{cases} \\ &= \begin{cases} \frac{1}{N} & (j=3) \\ p_{3,2}^{(2)}\frac{N-1}{N}+\frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j=2) \\ p_{3,1}^{(2)}\frac{N-1}{N}+\frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j=1) \\ p_{3,j}^{(2)}\frac{N-1}{N}+\frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j>3) \\ \end{cases} \\ &= \begin{cases} \frac{1}{N} & (j=3) \\ \frac{1}{N}\frac{N-1}{N} + \frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j=2) \\ \frac{1}{N}\frac{N-1}{N}\frac{N-1}{N} + \frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j=1) \\ \frac{N-1}{N}\frac{N-1}{N}\frac{1}{N} & (j>3) \end{cases} \end{aligned}$$

(4) $i>3$の時

$$\begin{aligned} p_{i,j}^{(3)}&= \begin{cases} \frac{1}{N} & (j=3) \\ p_{i,j}^{(2)}\frac{N-1}{N} + p_{i,3}^{(2)}\frac{1}{N} & (j\neq 3) \end{cases} \\ &= \begin{cases} \frac{1}{N} & (j=3) \\ p_{i,2}^{(2)}\frac{N-1}{N} & (j=2) \\ p_{i,3}^{(2)}\frac{N-1}{N} & (j=1) \\ p_{i,j}^{(2)}\frac{N-1}{N} & (j>3) \end{cases} \\ &= \begin{cases} \frac{1}{N} & (j=3) \\ \frac{1}{N}\frac{N-1}{N} & (j=2) \\ \frac{1}{N}\frac{N-1}{N}\frac{N-1}{N} & (j=1) \\ 0 & (j>3 \wedge j\neq i) \\ \frac{N-1}{N}\frac{N-1}{N}\frac{N-1}{N} & (j>3 \wedge j=i) \end{cases} \end{aligned}$$

$N=3$の場合における$p_{i,j}^{(N)}$の導出

$n=3$までの確率を計算することができたので，これを使って$N=3$とした場合の確率$p_{i,j}^{(N)}$の式を計算してみましょう．

主に3.4節の式に$N=3$を代入すればよいのですが，$N=3$の場合は$i>3$や$j>3$になることがありえないため，式をもうすこし簡潔に書けるようになります．

(1) $i=1$の時

$$p_{1,j}^{(3)}=\frac{1}{3}$$

(2) $i=2$の時

$$\begin{aligned} p_{2,j}^{(3)}&= \begin{cases} \frac{1}{3} & (j=3) \\ \frac{8}{27} & (j=2) \\ \frac{10}{27} & (j=1) \end{cases} \end{aligned}$$

(3) $i=3$の時

$$\begin{aligned} p_{3,j}^{(3)}&= \begin{cases} \frac{1}{3} & (j=3) \\ \frac{10}{27} & (j=2) \\ \frac{8}{27} & (j=1) \end{cases} \end{aligned}$$

$i=1$に関しては確率に偏りがないことが分かりますが，$i=2,3$に関しては確率に偏りが生じていることが分かります．

これでは配列の要素の初期順によって結果に偏りが生じるため，偏りなく均等にシャッフルを行いたいという意図に反してしまっています．

配列のシャッフルコードを書く場合には，確率に偏りが生じていないか実験してみてデバッグをしてみるのが良いでしょう．

最後に

本当は$N$が任意の値の場合の確率の式を導出したかったのですが，イマイチ規則性が分からなかったので$N=4$の計算をしている途中で断念してしまいました．

そのうち任意の$N$に対する式を導出するつもりです，そのうち．．．