Комбинаторная головоломка для подсчета: бросьте 20, 8-гранных кубиков, какова вероятность получения как минимум 5 кубиков одинакового значения

Question

Предположим, что в игре выпадает 20 8-гранных кубиков, что дает 8 ^ 20 возможных результатов. Чтобы рассчитать вероятность того или иного события, мы поделили количество способов, которыми это событие может произойти, на 8 ^ 20.

Можно рассчитать количество способов получить ровно 5 кубиков значения 3. (20 выбрать 5) дает нам количество заказов 3. 3. ^ 15 дает нам количество способов, которыми мы не можем получить значение 3. на 15 рулонов.

number of ways to get exactly 5, 3's = (20 choose 5)*7^15.

Ответ также может быть рассмотрен как сколько способов я могу переставить строку 3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0 (20 выбираем 5), умноженное на общее количество значений, равных нулю (при условии 7 допустимых значений) 7 ^ 15 (это правильно).

• Вопрос 1: Как рассчитать количество способов получить ровно 5 кубиков одного и того же значения (то есть для всех значений кубиков). Примечание: если я просто наивно использую свой первый ответ выше и умножу bt 8, я получу огромное количество двойного счета?

  Я понимаю, что мог бы решить для каждого из случаев (5 1), (5, 2), (5, 3), ... (5, 8) суммировать их (более просто 8 * (5 1) ). Затем вычтите сумму числа перекрытий (5 1-х) и (5 2-х), (5 1-х) и (5 3-х) ... (5 1-х) и (5, 2-х) и ... и (5, 8-х) но это кажется чрезвычайно грязным. Я хотел бы обобщить это таким образом, что масштабируется до большого числа выборок и большого числа классов.

• Как рассчитать количество способов получить не менее 5 кубиков одинакового значения?

  То есть 111110000000000000000 или 11110100000000000002 или 11111100000001110000 или 11011211222222223333, но не 00001111222233334444 или 000511512252363347744.

Я ищу ответы, которые либо объясняют математику, либо указывают на библиотеку, которая поддерживает это (модули esp python). Дополнительные баллы за детали и примеры.

Answer 1

Я предлагаю вам потратить немного времени на написание симуляции Монте-Карло и дать ей поработать, пока вы будете выполнять математику вручную. Надеемся, что симуляция Монте-Карло сойдется до того, как вы закончите с математикой, и вы сможете проверить свое решение.

Немного более быстрый вариант может включать создание SO-клона для математических вопросов.

Answer 2

Двойной счет можно решить с помощью принципа включения / исключения

Я подозреваю, что это выходит:

Choose(8,1)*P(one set of 5 Xs) 
- Choose(8,2)*P(a set of 5 Xs and a set of 5 Ys) 
+ Choose(8,3)*P(5 Xs, 5 Ys, 5 Zs) 
- Choose(8,4)*P(5 Xs, 5 Ys, 5 Zs, 5 As)

P(set of 5 Xs) = 20 Choose 5 * 7^15 / 8^20
P(5 Xs, 5 Ys) = 20 Choose 5,5 * 6^10 / 8^20

И так далее. Это не решает проблему «больше, чем 5 одинаковых», как если бы вы просто суммировали результаты, примененные к 5,6,7..20; Вы бы перебрали случаи, когда у вас есть, скажем, 10 1 и 5 8.

Вы могли бы, возможно, применить исключение включения снова, чтобы придумать второй ответ; Итак, P (не менее 5) = P (один набор из 20) + ... + (P (один набор из 15) - 7 * P (набор 5 из 5 кубиков)) + ((P (один набор из 14) - 7 * P (один набор из 5 из 6) - 7 * P (один набор из 6 из 6)). Создание исходного кода для этого оказывается более сложным.

Answer 3

Эта проблема действительно сложна, если вам нужно ее обобщить (получите точную формулу).

Но в любом случае, позвольте мне объяснить алгоритм. Если вы хотите знать

количество способов получить ровно 5 кости одинакового значения

Вы должны перефразировать вашу предыдущую проблему, как

рассчитать количество способов получить ровно 5 кубиков со значением 3 И нет другое значение может повторяться ровно 5 раз

Для простоты давайте назовем функцию F (20,8,5) (5 кубиков, все значения) первым ответом, а F (20,8,5,3) (5 кубиков, значение 3) вторым. Мы имеем F (20,8,5) = F (20,8,5,3) * 8 + (события, когда более одного значения повторяется 5 раз)

Так что, если мы можем получить F (20,8,5,3), все должно быть довольно просто, не так ли? Ну ... не так много ...

Сначала давайте определим некоторые переменные: X1, X2, X3 ..., Xi, где Xi = количество раз, когда мы получаем кости i

Тогда:

F(20,8,5)/20^8 = P(X1=5 or X2=5 or ... or X8=5, with R=20(rolls) and N=8(dice number))

, P (утверждение) является стандартным способом записи вероятности.

мы продолжаем:

F(20,8,5,3)/20^8 = P(X3=5 and X1<>5 and ... and X8<>5, R=20, N=8) 
F(20,8,5,3)/20^8 = 1 - P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7)  
F(20,8,5,3)/20^8 = 1 - F(15,7,5)/7^15

рекурсивно:

F(15,8,5) = F(15,7,5,1) * 7  
P(X1=5 or X2=5 or X4=5 or X5=5 or X6=5 or X7=5 or X8=5, R=15, N=7) = P(X1=5 and X2<>5 and X4<>5 and .. and X8<>5. R=15, N=7) * 7

---

F(15,7,5,1)/7^15 = 1 - F(10,6,5)/6^10 F(10,6,5) = F(10,6,5,2) * 6

---

F(10,6,5,2)/6^10 = 1 - F(5,5,5)/5^5
F(5,5,5) = F(5,5,5,4) * 5

Ну тогда ... F (5,5,5,4) - это количество способов получить 5 кубиков со значением 4 в 5 бросках, например, ни один другой кубик не повторяется 5 раз. Есть только 1 выход из 5 ^ 5. Вероятность тогда составляет 1/5 ^ 5.

F (5,5,5) - это количество способов получить 5 кубиков любого значения (из 5 значений) за 5 бросков. Это очевидно 5. Вероятность тогда 5/5 ^ 5 = 1/5 ^ 4.

F (10,6,5,2) - это количество способов получить 5 кубиков со значением 2 в 10 бросках, например, ни один другой кубик не повторяется 5 раз. F (10,6,5,2) = (1-F (5,5,5) / 5 ^ 5) * 6 ^ 10 = (1-1 / 5 ^ 4) * 6 ^ 10

Ну ... я думаю, что это может быть неправильно в какой-то части, но в любом случае, вы поняли идею. Я надеюсь, что смогу сделать алгоритм понятным.

редактирование: Я сделал несколько проверок и понял, что вам нужно добавить несколько случаев, когда вы получаете более одного значения, повторенного ровно 5 раз. У тебя нет времени, чтобы решить эту часть, ты ...

Answer 4

Точное распределение вероятностей Fs, i суммы i s-сторонних костей может быть рассчитано как повторяющаяся свертка распределения вероятностей одиночного кристалла с самим собой.

, где для всех и 0 в противном случае.

http://en.wikipedia.org/wiki/Dice

Answer 5

Полагаю, вы можете использовать формулу x вхождений в n событиях как:

P = вероятность ^ n * (n! / ((N - x)! X!))

Таким образом, окончательный результат будет суммой результатов от 0 до n.

Я не вижу простого способа объединить его в один шаг, который был бы менее беспорядочным. Таким образом, у вас есть формула, изложенная в коде, а также. Возможно, вам придется написать собственный метод факториала.

  float calculateProbability(int tosses, int atLeastNumber) {
    float atLeastProbability = 0;
    float eventProbability = Math.pow( 1.0/8.0, tosses);
    int nFactorial = factorial(tosses);

    for ( i = 1; i <= atLeastNumber; i++) {
      atLeastProbability += eventProbability * (nFactorial / (factorial(tosses - i) * factorial(i) );
    }
  }

Answer 6

Вот о чем я думаю ...

Если бы у вас было всего 5 кубиков, у вас было бы только восемь способов получить то, что вы хотите.

Для каждого из этих восьми способов работают все возможные комбинации остальных 15 кубиков.

Итак - я думаю, что ответ: (8 * 8 15) / 8 20

(Ответ хотя бы на 5 одинаков.)

Answer 7

Рекурсивное решение:

Prob_same_value(n) = Prob_same_value(n-1) * (1 - Prob_noone_rolling_that_value(N-(n-1)))