C++でM面サイコロをN回投げたときの最大出目の期待値を求める方法

問題の概要

本記事では、M面のサイコロをN回投げたときに期待できる最大の出目(ドット数)を計算する方法を解説します。

このサイコロは、1番目の面に1個、2番目の面に2個、というようにドットが描かれており、M番目の面にはM個のドットが含まれます。公平なサイコロなので、各面が出る確率はすべて 1/M です。

まずは具体例を使って、何を求めるのかを確認しましょう。

入力例と出力例

入力 − M=2, N=3

出力 − 1.875

説明 − このサイコロは2つの面 {1, 2} を持ちます。

3回投げた場合、標本空間の大きさは M^N = 2³ = 8 通りとなります。

{(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}

(1, 1, 1) の最大値 = 1
(1, 1, 2) の最大値 = 2
(1, 2, 1) の最大値 = 2
(1, 2, 2) の最大値 = 2
(2, 1, 1) の最大値 = 2
(2, 1, 2) の最大値 = 2
(2, 2, 1) の最大値 = 2
(2, 2, 2) の最大値 = 2

各ケースの確率 = 1/23 = 0.125
したがって、最大値の期待値 = (1+2+2+2+2+2+2+2) × 0.125 = 1.875

入力 − M=2, N=2

出力 − 1.75

アプローチの考え方

• 「最大値がちょうど i になるケースの総数」は、その直前の値を利用した次の公式で求められます。
  i^N − (i−1)^N

  これは、「すべての出目が i 以下になる場合の数(i^N)」から「すべての出目が i−1 以下になる場合の数((i−1)^N)」を引くことで導かれます。

  例えば M=4、N=2 のとき、最大値が4になるケースの総数は 4² − (4−1)² = 16 − 9 = 7 通りです。

  したがって最終的な答えは、この公式を1からMまでの各要素に適用した次の式をすべて足し合わせたものになります。

  (i × (i^N − (i−1)^N)) / M^N

• 関数 MaxExpect() 内では、合計を格納するために double 型の変数 max を 0 で初期化します。

• その後、i = M から i > 0 までループを回します。

• ループ内で上記の公式を適用し、計算結果を順次変数 max に加算していきます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
double MaxExpect(double M, double N){
    double max = 0.0, i;
    for (i = M; i; i--)
        /* 最大値を求めて合計するための公式 */
        max += (pow(i / M, N) - pow((i - 1) / M, N)) * i;
        return max;
}
int main(){
    double M = 2, N = 3;
    cout << MaxExpect(M, N);
    return 0;
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

1.875