Какова вероятность того, что из 25 случайных чисел от 1 до 100 самое высокое появляется более одного раза?

Во многих онлайн-играх, когда игроки выполняют сложное задание, иногда дается специальная награда, которую может использовать каждый, кто выполнил задание. обычно это верховое животное (способ транспортировки) или другой предмет тщеславия (предметы, которые не улучшают характеристики персонажа и в основном используются для настройки внешнего вида).

Когда такая награда дается, наиболее распространенный способ определить, кто получает награду, это через случайные числа. В игре обычно есть специальная команда, которая генерирует случайное (вероятно, псевдослучайное, не крипто-безопасное случайное) число от 1 до 100 (иногда игрок может выбрать другой спред, но 100 является наиболее распространенным). Каждый игрок использует эту команду, все игроки могут видеть, кто что бросил, и предмет вручается тому, кто бросает наивысший. В большинстве игр даже есть встроенная система, в которой игроки просто нажимают кнопку, а когда все нажимают на кнопку, игра делает все остальное автоматически.

Иногда некоторые игроки генерируют одинаковое большое количество, и никто не побеждает их. это обычно решается теми игроками, восстанавливающими их числа, пока не будет уникального наибольшего числа.

Мой вопрос заключается в следующем: предположим, что генератор случайных чисел может генерировать любое число от 1 до 100 с одинаковой вероятностью. Предположим, что у вас есть группа из 25 игроков, каждый из которых генерирует 1 число с таким генератором случайных чисел (каждый со своим начальным числом). У вас будет 25 чисел от 1 до 100, без ограничений по количеству игроков, выбрасывающих определенный номер, и без связи между числами. Какова вероятность того, что наибольшее количество сгенерированных генерируется более чем одним игроком? Другими словами, какова вероятность галстука?

probability random-generation Nzall
источник

World of Warcraft, а?

Behacad

да, это равномерное случайное число, как указано в вопросе (любое число от 1 до 100 включительно имеет одинаковую вероятность.

Nzall

Хороший вопрос, но мне кажется, что это плохой способ выбрать победителя. Просто перечислите игроков каким-либо образом (можно сказать «имена в алфавитном порядке» или перемешайте его и покажите всем список, или отсортируйте другим способом), и выберите случайное число от 1 до 25. Число, соответствующее игроку, выигрывает.

Тим С.

Нубс, используй ДКП!

Давор

Предложение: для случайной выборки

из

нам нужно вычислить

используя то, что мы знаем из теории статистики порядка.

X_{1}, \dots, X_{25}

$X_1,\dots,X_{25}$

U {1, \dots, 100}

$\textrm{U}\{1,\dots,100\}$

P (X_{(24)} < X_{(25)})

$P(X_{(24)}<X_{(25)})$

Дзен

Ответы:

Позволять

будет верхним пределом вашего диапазона, в вашем случае. $x$ $x=100$
будет общим количеством розыгрышей, в вашем случае. $n$ $n=25$

Для любого числа количество последовательностей из чисел с каждым числом в последовательности равно . Из этой последовательности число, не содержащее s, равно , а число, содержащее один равно . Следовательно, число последовательностей с двумя или более s равно $y\le x$ $n$ $\le y$ $y^n$ $y$ $(y-1)^n$ $y$ $n(y-1)^{n-1}$ $y$ Общее число последовательностей из чисел с наибольшим числом содержащих не менее двух s, равно

y^{n} - (y - 1)^{n} - n (y - 1)^{n - 1}

$y^n - (y-1)^n - n(y-1)^{n-1}$

n

$n$

y

$y$

y

$y$

\begin{aligned} \sum_{y = 1}^{x} (y^{n} - (y - 1)^{n} - n (y - 1)^{n - 1}) & = \sum_{y = 1}^{x} y^{n} - \sum_{y = 1}^{x} (y - 1)^{n} - \sum_{y = 1}^{x} n (y - 1)^{n - 1} \\ = x^{n} - n \sum_{y = 1}^{x} (y - 1)^{n - 1} \\ = x^{n} - n \sum_{y = 1}^{x - 1} y^{n - 1} \end{aligned}

$\begin{align} \sum_{y=1}^x \left(y^n - (y-1)^n - n(y-1)^{n-1}\right) &= \sum_{y=1}^x y^n - \sum_{y=1}^x(y-1)^n - \sum_{y=1}^xn(y-1)^{n-1}\\ &= x^n - n\sum_{y=1}^x(y-1)^{n-1}\\ &= x^n - n\sum_{y=1}^{x-1}y^{n-1}\\ \end{align}$

Общее количество последовательностей просто . Все последовательности одинаково вероятны, поэтому вероятность равна $x^n$

\frac{x^{n} - n \sum_{y = 1}^{y = x - 1} y^{n - 1}}{x^{n}}

$\frac{x^n - n\sum_{y=1}^{y=x-1}y^{n-1}}{x^n}$

С я делаю вероятность 0.120004212454. $x=100,n=25$

$x,n$

import itertools
import numpy.random as np

def countinlist(x, n):
    count = 0
    total = 0
    for perm in itertools.product(range(1, x+1), repeat=n):
        total += 1
        if perm.count(max(perm)) > 1:
            count += 1

    print "Counting: x", x, "n", n, "total", total, "count", count

def simulate(x,n,N):
    count = 0
    for i in range(N):
        perm = np.randint(x, size=n)
        m = max(perm)
        if sum(perm==m) > 1:
            count += 1
    print "Simulation: x", x, "n", n, "total", N, "count", count, "prob", count/float(N)

x=100
n=25
N = 1000000 # number of trials in simulation

#countinlist(x,n) # only call this for reasonably small x and n!!!!
simulate(x,n,N)
formula = x**n - n*sum([i**(n-1) for i in range(x)])
print "Formula count", formula, "out of", x**n, "probability", float(formula) / x**n

Эта программа выведена

Simulation: x 100 n 25 total 1000000 count 120071 prob 0.120071
Formula count 12000421245360277498241319178764675560017783666750 out of 100000000000000000000000000000000000000000000000000 probability 0.120004212454

TooTone
источник

200000

$200000$

0.11957

$0.11957$

x

$x$

n

$n$

Я смоделировал с помощью Perl и получил очень стабильный 0,005. pastebin.com/gb7JMLt6

agweber

x

$x$

n

$n$

x = 20, n = 5

$x=20,n=5$

15600 / 160000 = 0.0975

$15600/160000=0.0975$

x, n

$x,n$ и вероятность по формуле I. Мне любопытно узнать, что является источником разногласий между нашими кодами.

TooTone

10^{7}

$10^7$

0.119983,

$0.119983,$ n = 10^7; Total[Boole[Equal @@ (#[[Ordering[#, -2]]])] & /@ x = RandomInteger[{1, 100}, {n, 25}]] / n

Я бы подумал, чтобы найти вероятность того, что победитель будет первым

$x$ $\frac{{25\choose1} (x-1)^{24}}{{100}^{25} }$ $y-1$

Победитель может выиграть с его числом, равным от 2 до 100, поэтому общая вероятность

\begin{aligned} \sum_{i = 2}^{100} \frac{25 (i - 1)^{24}}{100^{25}} \\ = & 25 \sum_{i = 1}^{99} \frac{i^{24}}{100^{25}} \\ = & - \frac{1}{4} + 25 \sum_{i = 1}^{100} \frac{i^{24}}{100^{25}} \\ \approx & - \frac{1}{4} + 25 \frac{\frac{1}{24 + 1} 100^{24 + 1} + \frac{1}{2} 100^{24} + \frac{24}{2} \frac{1}{6} 100^{23}}{100^{25}} \\ = & 0.88 \end{aligned}

$\begin{align} &\sum_{i=2}^{100} \frac {25(i-1)^{24}}{{100}^{25}}\\ =& 25\sum_{i=1}^{99} \frac{i^{24}}{{100}^{25}}\\ =& -{1 \over 4}+25\sum_{i=1}^{100} \frac{i^{24}}{{100}^{25}}\\\approx&-{1 \over 4}+25 {{1\over24+1}{100}^{24+1}+{{1\over2}{100}^{24}+{{{24\over2} {1\over6}}{100}^{23} }}\over{100}^{25}}\\ =&0.88 \end{align}$

$100^{23}$

$1-0.88=0.12$

Гэри
источник

-3

Похоже, вопрос очень похож на парадокс дня рождения ( http://en.wikipedia.org/wiki/Birthday_problem ), единственное отличие состоит в том, что в этом случае вы не хотите совпадать ни с одним числом, а только с самым большим числом. На первом этапе расчета рассчитывают вероятность того, что не случайные числа перекрываются ( $p$ ). (см. ссылку выше), а затем вероятность того, что некоторые из 25 чисел перекрываются, $1-p$ где p - это вероятность, которую вы уже рассчитали. В этом случае вероятность того, что 25 чисел не пересекаются с максимумом, определяется как: $p=1*(1-1/100)*(1-1/100)......*(1-1/10)=(1-1/100)^{24}$ тогда вероятность, которую вы ищете $P=1-p=1-(1-1/100)^{24} = 0.214$

Мишель Г
источник

Означает ли это, что вероятность составляет 21,4%? кажется довольно высоким, но опять же, парадокс дня рождения имеет такой же удивительный ответ. Спасибо.

Nzall

-1 В таком виде этот ответ не верный. Правильный ответ предоставлен @TooTone.

COOLSerdash