シャッフルバッグ

毎回選び直すと起きる偏り

出る物が数種類あるとき、毎回どの種類も等しい確率で選び直す引き方がある。以下ではこれを純粋な乱数と呼ぶ。純粋な乱数では 1 回ごとの選び方が前の結果によらないので、同じ種類が続くことも、ある種類がしばらく出ないことも起きる。

N 種類から選ぶとき、ある回の次にまた同じ種類が出る確率は、何が出た後でも 1/N である。4 種類なら 25% である。ある回から数えてその後の 2 回も同じ種類になる確率も 1/16（6.25%）ある。

ある種類が出てから次に出るまでにほかの種類が出た回数を、以下では出ない間と呼ぶ。0 回は続けて出たことを表す。純粋な乱数で出ない間が g 回以上になる確率は (1 - 1/N)^g である。4 種類なら 10 回以上が 5.6%、16 回以上でも 1.0% ある。

デモの上の段は 4 種類の純粋な乱数である。同じシードで 6000 回引くと、出ない間は最長 31 回だった。段に並べている 24 個の列を 6000 回の中で 1 つずつずらして数えると、7 割近くの列で同じ種類が 3 回以上続いている。

この偏りは乱数の作り方が悪いから起きるのではない。毎回を独立に選ぶ限り、どれほどよい乱数を使っても上の確率で起きる。「同じものばかり続く」「欲しいものが出ない」という感想はこの偏りから生まれる。

袋から引く

偏りを抑えるには、出る物をあらかじめ決まった数だけ用意しておき、それを使い切るまで引く。シャッフルバッグは、各種類を決まった数ずつ袋に入れて混ぜ、空になるまで順に引いて空になったら詰め直して混ぜる引き方である。カードの山札を 1 枚ずつめくり、めくり終えたら混ぜ直すのと同じ仕組みになる。

袋に各種類を 1 つずつ入れると、N 回引くたびにどの種類もちょうど 1 回ずつ出る。そのため、出ない間と、同じ種類が続く長さに上限が付く。

• 出ない間の上限：最も長くなるのは、ある種類が袋の最初に出て次の袋の最後に出たときである。あいだには最初の袋の残りの N - 1 個と、次の袋のそれまでの N - 1 個が挟まるので、最長は 2N - 2 回になる。4 種類なら 6 回、6 種類なら 10 回である。
• 続く長さの上限：1 つの袋の中に同じ種類は 1 つしかないので、続くのは袋の最後と次の袋の最初が同じ種類になったときだけで、最長は 2 回である。

ある種類が出た次の回にまた同じ種類が出るのは、その種類が袋の最後で次の袋の最初もその種類だったときだけなので、その割合は 1/N² になる。4 種類なら純粋な乱数の 25% に対して 6.25% である。デモの 6000 回では、上の段が 24.2%、下の段が 6.8% だった。

デモの下の段は 4 種類を 1 つずつ入れた袋である。縦の線が袋の境目で、同じ種類が 2 回続くのは境目をまたいだ所だけである。各段の「次に出る確率」の行を見ると、下の段では袋から引いた種類が、その袋が空になるまで 0% になる。

出る確率は変えずに、出方の偏りを抑える

シャッフルバッグは各種類が出る確率を変えずに、出方の偏りだけを抑える。長く引き続ければ、どちらの引き方でも各種類はほぼ 1/N ずつ出る。デモの 6000 回では、上の段で 4 種類が 1453〜1573 回ずつ、下の段でちょうど 1500 回ずつ出た。出ない間の平均も同じで、どちらも N - 1 回（4 種類なら 3.0 回）になるので、下のグラフの破線は 2 つの段でそろっている。

違うのは出ない間のばらつきである。純粋な乱数では、出ない間は 0 回が最も多く、長くなるほど少しずつ減りながらどこまでも続く。各種類 1 つずつの袋では、0 回から 2N - 2 回までの範囲に収まり、真ん中の N - 1 回が最も多い山の形になる。純粋な乱数で出ない間が 2N - 1 回以上になる割合は (1 - 1/N)^(2N - 1) で、3〜6 種類のどれでも 13% ほどである。袋にすると、この長い間がなくなる。0 回（続けて出た回）も減って、そのぶん真ん中の長さが増える。

袋を大きくしたとき

袋に各種類を M 個ずつ入れると、1 つの袋の中でも同じ種類が続けて出ることがある。上限の求め方は 1 つずつのときと同じで、続く長さは最長 2M 回、出ない間は最長 2M(N - 1) 回になる。4 種類なら 2 つずつで 4 回と 12 回、3 つずつで 6 回と 18 回、5 つずつで 10 回と 30 回である。

袋を大きくするほど、出方は純粋な乱数に近づく。デモの 4 種類で 6000 回引くと、ある種類が出た次の回にまた同じ種類が出る割合は 1 つずつで 6.8%、2 つずつで 15.0%、3 つずつで 18.5%、5 つずつで 20.0% である。入れる数を増やすほど、この割合は上の段の 24.2% に近づいていく。出ない間が 7 回以上になる割合も 0%、8.1%、10.8%、12.1% と増え、上の段の 13.6% に近づく。上限に届く並びはまれである。5 つずつの袋では出ない間の最長は 21 回で、上限の 30 回に届かなかった。

入れる数で偏りをどれだけ残すかを決められる。続く長さと出ない間を短く抑えたいなら 1 つずつにし、多少の偏りを残したいなら 2〜3 つずつに増やす。

次に出る物が読めること

袋の中身は引いた物を数えていればわかる。各種類 1 つずつの袋では、袋の最後の 1 つはその袋でまだ出ていない種類に決まる。そのため、N 回に 1 回は次に出る物が確実に読める。袋の残りを覚えて残っている種類の 1 つを言い当てるなら、当たる割合は (1 + 1/2 + … + 1/N) / N で、4 種類なら 52% になる。純粋な乱数では何を覚えていても 25% のままである。デモの「次に出る確率」の行はこの読みを数字で見せている。

袋を大きくすると読みにくくなる。デモの 4 種類で 6000 回数えると、次に出る物が確実に読める回は 1 つずつで 25.0%、2 つずつで 14.2%、5 つずつで 6.3% だった。袋の残りから最も出やすい種類を言い当てる割合も 52%、47%、41% と下がるが、5 つずつでも純粋な乱数の 25% より高い。

読ませたいか読ませたくないかで、袋の大きさを選ぶ。

• 読ませたい場面：次の物を読んで先の手を考える遊び（落ちてくるブロックを積む、など）では、読めることが遊びの一部になる。各種類 1 つずつの小さな袋にする。
• 読ませたくない場面：敵の出現や報酬のように次を読まれると身構える必要がなくなる場面では、2〜3 つずつに増やして袋を大きくする。

袋の境目で続くのを避ける

各種類 1 つずつの袋でも、境目では同じ種類が 2 回続くことがある。これも避けたいときは、詰め直した袋の最初が直前に出た種類と同じなら、袋の中のほかの種類の物と入れ替える。入れ替えても袋の中身は変わらないので、各種類が出る割合も出ない間の最長 2N - 2 回も変わらない。

// 1 つ引く。袋が空なら、各種類を copies 個ずつ入れて混ぜる
function draw(): Kind {
  if (bag.length === 0) {
    for (const kind of KINDS) for (let i = 0; i < copies; i++) bag.push(kind);
    shuffle(bag); // どの並びも等しい確率になる混ぜ方にする
    // 境目で続けないなら、最初に引く物が直前と同じとき、ほかの種類の物と入れ替える
    if (avoidRepeat && bag[0] === last) swapWithOtherKind(bag, 0);
  }
  last = bag.shift()!;
  return last;
}

天井との違い

「天井」も運の偏りを抑える仕組みである。天井は外れが決まった回数続いたら次を必ず当たりにし、それまでの 1 回ごとの当たりの確率は変えない。シャッフルバッグは袋 1 つの中の当たりの数を決める。

1% で当たる物を例に比べる。純粋な乱数では、当たりから次の当たりまでに 198 回以上外れる割合が 0.99^198 で 13.7% ある。袋にするなら、当たり 1 つと外れ 99 個を入れた 100 個の袋にする。100 回引くたびにちょうど 1 回当たり、外れが続くのは最長 198 回になる。ただし、当たりを引いた後はその袋が空になるまで当たりが出ないことも決まる。天井を使い、99 回続けて外れたら 100 回目を必ず当たりにすると、外れが続くのは最長 99 回で止まる。1 回ごとの確率は 1% のままなので、天井で当たる回のぶんだけ当たりの割合は 1.58% に上がる。

当たりの割合を決めたいなら袋を使い、外れが続く長さを短く抑えたいなら天井を使う。