Jakie jest prawdopodobieństwo, że spośród 25 liczb losowych od 1 do 100 najwyższa pojawi się więcej niż jeden raz?

W wielu grach online, gdy gracze wykonują trudne zadanie, czasami przyznawana jest specjalna nagroda, z której mogą skorzystać wszyscy, którzy ukończyli zadanie. jest to zazwyczaj wierzchowiec (metoda transportu) lub inny przedmiot próżności (przedmioty, które nie poprawiają wydajności postaci i służą głównie do dostosowywania wyglądu).

Gdy taka nagroda jest przyznawana, najczęstszym sposobem ustalenia, kto ją otrzymuje, są liczby losowe. Gra zazwyczaj ma specjalne polecenie, które generuje losową (prawdopodobnie pseudolosową, nie krypto-bezpieczną losową) liczbę od 1 do 100 (czasami gracz może wybrać inny spread, ale 100 jest najczęściej). Każdy gracz używa tego polecenia, wszyscy gracze mogą zobaczyć, kto rzucił, a przedmiot jest przyznawany osobie, która rzuciła najwięcej. Większość gier ma nawet wbudowany system, w którym gracze po prostu naciskają przycisk, a gdy wszyscy naciskają przycisk, gra wykonuje resztę automatycznie.

Czasami niektórzy gracze generują tę samą wysoką liczbę i nikt ich nie pokonuje. jest to zazwyczaj rozwiązywane przez tych graczy, którzy regenerują swoje liczby, dopóki nie będzie unikalnej najwyższej liczby.

Moje pytanie jest następujące: Załóżmy, że generator liczb losowych może wygenerować dowolną liczbę od 1 do 100 z takim samym prawdopodobieństwem. Załóżmy, że masz grupę 25 graczy, z których każdy generuje 1 liczbę za pomocą takiego generatora liczb losowych (każdy z własnym nasieniem). Będziesz miał 25 liczb od 1 do 100, bez ograniczeń, ilu graczy rzuca konkretnym numbderem i bez związku między liczbami. Jaka jest szansa, że ​​najwyższa generowana liczba jest generowana przez więcej niż 1 gracza? Innymi słowy, jakie jest prawdopodobieństwo remisu?

Pozwolić

• $x$ będzie górną krawędzią twojego zakresu, w twoim przypadku.$x=100$
• $n$ będzie całkowitą liczbą losowań, w twoim przypadku.$n=25$

Dla dowolnej liczby liczba sekwencji$y\le x$ liczb z każdą liczbą w sekwencji ≤ y wynosi y n . Z tej sekwencji liczba niezawierająca y s wynosi ( y - 1 ) n , a liczba zawierająca jedno y to n ( y - 1 ) n - 1 . Stąd liczba sekwencji z dwoma lub więcej y s wynosi y n - ( y - 1 ) n - $n$$\le y$$y^n$$y$$(y-1)^n$$y$$n(y-1)^{n-1}$$y$ Łączna liczba sekwencji n liczb o najwyższej liczbie y zawierających co najmniej dwa y s wynosi x ∑ y = 1 ( y n - ( y - 1 ) n - n ( y - 1 ) n - 1

$$y^n - (y-1)^n - n(y-1)^{n-1}$$ $n$$y$$y$ $$\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}$$

$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

Ten program wyszedł

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

Zastanowiłbym się, czy najpierw nie uda mi się znaleźć wyjątkowego zwycięzcy

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

Zwycięzca może wygrać, gdy jego liczba wynosi od 2 do 100, więc całkowite prawdopodobieństwo wynosi

$$\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$

$p$$1-p$$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$