¿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?

Question

En muchos juegos en línea, cuando los jugadores completan una tarea difícil, a veces se da una recompensa especial que pueden utilizar todos los que la hayan completado. Suele tratarse de una montura (método de transporte) u otro objeto de vanidad (objetos que no mejoran el rendimiento del personaje y se utilizan principalmente para personalizar su aspecto).

Cuando se da una recompensa de este tipo, la forma más habitual de determinar quién la obtiene es mediante números aleatorios. El juego suele tener un comando especial que genera un número aleatorio (probablemente pseudoaleatorio, no aleatorio cripto seguro) entre 1 y 100 (a veces el jugador puede elegir otra tirada, pero 100 es la más común). Cada jugador utiliza este comando, todos los jugadores pueden ver quién ha sacado qué, y el objeto se concede a la persona que saque el número más alto. La mayoría de los juegos tienen incluso un sistema integrado en el que los jugadores sólo tienen que pulsar un botón y, una vez que todos han pulsado el suyo, el juego hace el resto automáticamente.

A veces, algunos jugadores generan el mismo número alto y nadie les gana. Esto se suele resolver regenerando los números de esos jugadores, hasta que haya un único número más alto.

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

Answer 1

Sea

• $x$ ser el extremo superior de su gama, $x=100$ en tu caso.
• $n$ el número total de sorteos, $n=25$ en tu caso.

Para cualquier número $y\le x$ el número de secuencias de $n$ números con cada número de la secuencia $\le y$ es $y^n$ . De esta secuencia, el número que no contiene $y$ s es $(y-1)^n$ y el número que contiene uno $y$ es $n(y-1)^{n-1}$ . Por lo tanto, el número de secuencias con dos o más $y$ s es $$y^n - (y-1)^n - n(y-1)^{n-1}$$ El número total de secuencias de $n$ números con la cifra más alta $y$ que contenga al menos dos $y$ s es \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 $x^n$ . Todas las secuencias son igualmente probables, por lo que la probabilidad es $$ \frac{x^n - n\sum_{y=1}^{y=x-1}y^{n-1}}{x^n}$$

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

He probado esto usando el siguiente programa Python, que cuenta las secuencias que coinciden manualmente (para baja $x,n$ ), simula y calcula utilizando la fórmula anterior.

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 dio como resultado

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

Answer 2

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

Probabilidad de tener un único ganador y su número es $x$ es igual a $\frac{{25\choose1} (x-1)^{24}}{{100}^{25} }$ ya que hay 25 opciones para el ganador, y el resto puede tener un número que va del 1 al $y-1$

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

\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í he utilizado la aproximación hasta $100^{23}$ Como referencia: https://en.wikipedia.org/wiki/Faulhaber 's_formula

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

Answer 3

Parece una cuestión muy similar a la paradoja del Cumpleaños ( http://en.wikipedia.org/wiki/Birthday_problem ), la única diferencia es que en este caso no quieres que coincida cualquier número sino sólo el número más alto. El primer paso del cálculo es calcular la probabilidad de que ninguno de los números aleatorios coincida ( $p$ ). (véase el enlace anterior) y entonces la probabilidad de que algunos de los 25 números se solapen es $1-p$ donde p es la probabilidad que ya has calculado. En este caso la probabilidad de que los 25 números no coincidan 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 buscas es $P=1-p=1-(1-1/100)^{24} = 0.214$