¿Cuál es la probabilidad de que de 25 números aleatorios entre 1 y 100, el más alto aparezca más de una vez?

En muchos juegos en línea, cuando los jugadores completan una tarea difícil, a veces se otorga una recompensa especial que todos los que completaron la tarea pueden usar. Esto suele ser una montura (método de transporte) u otro elemento de tocador (elementos que no mejoran el rendimiento del personaje y se utilizan principalmente para la personalización de la apariencia).

Cuando se otorga dicha recompensa, la forma más común de determinar quién obtiene la recompensa es a través de números aleatorios. El juego generalmente tiene un comando especial que genera un número aleatorio (probablemente pseudoaleatorio, no aleatorio seguro criptográfico) entre 1 y 100 (a veces el jugador puede elegir otro spread, pero 100 es el más común). Cada jugador usa este comando, todos los jugadores pueden ver quién lanzó qué y el objeto se otorga a la persona que obtiene el mayor puntaje. La mayoría de los juegos incluso tienen un sistema incorporado en el que los jugadores simplemente presionan un botón y una vez que todos presionan su botón, el juego hace el resto automáticamente.

A veces, algunos jugadores generan el mismo número alto y nadie los supera. esto generalmente es resuelto por aquellos jugadores que regeneran sus números, hasta que haya un número más alto único.

Mi pregunta es la siguiente: suponga un generador de números aleatorios que puede generar cualquier número entre 1 y 100 con la misma probabilidad. Suponga que tiene un grupo de 25 jugadores que cada uno genera 1 número con un generador de números aleatorio (cada uno con su propia semilla). Tendrás 25 números entre 1 y 100, sin limitaciones sobre cuántos jugadores tiran un número específico y sin relación entre los números. ¿Cuál es la posibilidad de que el número más alto generado sea generado por más de 1 jugador? En otras palabras, ¿cuál es la probabilidad de un empate?

probability random-generation Nzall
fuente

World of Warcraft eh?

Behacad

Sí, es uniforme al azar, como se indica en la pregunta (cualquier número entre 1 y 100 inclusive tiene la misma probabilidad.

Nzall

Buena pregunta, pero esto me parece una mala forma de elegir un ganador. Simplemente haga una lista de los jugadores de alguna manera (podría decir "nombres alfabéticamente" o baraje y muestre a todos la lista, u ordene de alguna otra manera), y elija un número aleatorio entre 1 y 25. El número correspondiente al jugador gana.

Tim S.

Noobs, usa DKP!

Davor

Sugerencia: dada una muestra aleatoria

, necesitamos calcular

usando lo que sabemos de la teoría de las estadísticas de orden.

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)})$

Zen

Respuestas:

Dejar

sea el extremo superior de su rango, en su caso. $x$ $x=100$
sea el número total de sorteos, en su caso. $n$ $n=25$

Para cualquier número , el número de secuencias de números con cada número en la secuencia es . De estas secuencias, el número que no contiene s es , y el número que contiene un es . Por lo tanto, el número de secuencias con dos o más s es $y\le x$ $n$ $\le y$ $y^n$ $y$ $(y-1)^n$ $y$ $n(y-1)^{n-1}$ $y$ El número total de secuencias de números con el número más alto contiene al menos dos s es

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

El número total de secuencias es simplemente . Todas las secuencias son igualmente probables, por lo que la probabilidad es $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}$

Con hago la probabilidad 0.120004212454. $x=100,n=25$

He probado esto usando el siguiente programa Python, que cuenta las secuencias que coinciden manualmente (para ), simula y calcula usando la fórmula anterior. $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

Este programa salió

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

TooTone
fuente

200000

$200000$

0.11957

$0.11957$

x

$x$

n

$n$

Simulé usando perl y obtuve un 0.005 muy consistente. pastebin.com/gb7JMLt6

agosto

x

$x$

n

$n$

x = 20, n = 5

$x=20,n=5$

15600 / 160000 = 0.0975

$15600/160000=0.0975$

x, n

$x,n$ , y la probabilidad de la fórmula que deriva. Tengo curiosidad por saber cuál es la fuente del desacuerdo entre nuestro código.

TooTone

10^{7}

$10^7$

0.119983,

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

Consideraría encontrar primero la probabilidad de tener un ganador único

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

El ganador puede ganar con su número igual a 2 a 100, por lo que la probabilidad total es

\begin{aligned} \sum_{yo = 2}^{100} \frac{25 (yo - 1)^{24}}{100^{25}} \\ = & 25 \sum_{yo = 1}^{99} \frac{{yo}^{24}}{100^{25}} \\ = & - \frac{1}{4 4} + 25 \sum_{yo = 1}^{100} \frac{{yo}^{24}}{100^{25}} \\ \approx & - \frac{1}{4 4} + 25 \frac{\frac{1}{24 + 1} 100^{24 + 1} + \frac{1}{2} 100^{24} + \frac{24}{2} \frac{1}{6 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}$

Aquí usé la aproximación hasta $100^{23}$ Para referencia: https://en.wikipedia.org/wiki/Faulhaber 's_formula

Por lo tanto, la probabilidad de tener un empate es $1-0.88=0.12$

Gary
fuente

-3

Parece una pregunta muy similar a la paradoja del cumpleaños ( http://en.wikipedia.org/wiki/Birthday_problem ), la única diferencia es que en este caso no desea hacer coincidir ningún número, sino solo el número más alto. El primer paso en el cálculo calcula la probabilidad de que ninguno de los números aleatorios se superponga ( $p$ ) (ver el enlace de arriba) y luego la probabilidad de que algunos de los 25 números se superpongan es $1-p$ donde p es la probabilidad que ya calculó. En este caso, la probabilidad de que los 25 números no se superpongan con el máximo viene dada por: $p=1*(1-1/100)*(1-1/100)......*(1-1/10)=(1-1/100)^{24}$ entonces la probabilidad que estás buscando es $P=1-p=1-(1-1/100)^{24} = 0.214$

Michel G
fuente

¿Significa esto que la probabilidad es del 21.4%? parece bastante alto, pero de nuevo, la paradoja del cumpleaños tiene una respuesta sorprendente similar. Gracias.

Nzall

-1 Tal como está, esta respuesta no es correcta. La respuesta correcta fue proporcionada por @TooTone.

COOLSerdash