Quelle est la probabilité que sur 25 nombres aléatoires compris entre 1 et 100, le plus élevé apparaisse plus d'une fois?

23

Dans de nombreux jeux en ligne, lorsque les joueurs accomplissent une tâche difficile, une récompense spéciale est parfois donnée que toute personne ayant accompli la tâche peut utiliser. il s'agit généralement d'une monture (méthode de transport) ou d'un autre élément de vanité (objets qui n'améliorent pas les performances du personnage et sont principalement utilisés pour la personnalisation de l'apparence).

Lorsqu'une telle récompense est accordée, la façon la plus courante de déterminer qui obtient la récompense est d'utiliser des nombres aléatoires. Le jeu a généralement une commande spéciale qui génère un nombre aléatoire (vraisemblablement pseudo-aléatoire, et non crypto sécurisé) entre 1 et 100 (parfois le joueur peut choisir une autre propagation, mais 100 est le plus courant). Chaque joueur utilise cette commande, tous les joueurs peuvent voir qui a lancé quoi et l'objet est attribué à la personne qui obtient le plus haut. La plupart des jeux ont même un système intégré où les joueurs n'appuient que sur un bouton et une fois que chacun a appuyé sur son bouton, le jeu fait le reste automatiquement.

Parfois, certains joueurs génèrent le même nombre élevé et personne ne les bat. cela est généralement résolu par les joueurs qui régénèrent leur nombre, jusqu'à ce qu'il y ait un nombre unique plus élevé.

Ma question est la suivante: supposons un générateur de nombres aléatoires qui peut générer n'importe quel nombre entre 1 et 100 avec la même probabilité. Supposons que vous avez un groupe de 25 joueurs qui génèrent chacun 1 numéro avec un tel générateur de nombres aléatoires (chacun avec sa propre graine). Vous aurez 25 numéros entre 1 et 100, sans aucune limitation sur le nombre de joueurs qui lancent un numéro spécifique et sans relation entre les numéros. Quelle est la chance que le nombre généré le plus élevé soit généré par plus d'un joueur? En d'autres termes, quelle est la probabilité d'une égalité?

Nzall
la source
7
World of Warcraft hein?
Behacad
1
oui, c'est aléatoire uniforme, comme indiqué dans la question (tout nombre compris entre 1 et 100 inclusinve a la même probabilité.
Nzall
Bonne question, mais cela me semble une mauvaise façon de choisir un gagnant. Énumérez simplement les joueurs d'une manière ou d'une autre (vous pouvez dire "noms par ordre alphabétique" ou mélangez-les et montrez la liste à tout le monde, ou triez d'une autre manière), et choisissez un nombre aléatoire entre 1 et 25. Le nombre correspondant au joueur gagne.
Tim S.
2
Noobs, utilisez DKP!
Davor
2
Suggestion: étant donné un échantillon aléatoire de , nous devons calculer utilisant ce que nous savons de la théorie des statistiques d'ordre. U { 1 , , 100 } P ( X ( 24 ) < X ( 25 ) )X1,,X25U{1,,100}P(X(24)<X(25))
Zen

Réponses:

25

Laisser

  • x = 100X soit le haut de gamme, dans votre cas.X=100
  • n = 25n soit le nombre total de tirages, dans votre cas.n=25

Pour tout nombre , le nombre de séquences de nombres avec chaque nombre dans la séquence est . De ces séquences, le nombre ne contenant aucun est , et le nombre contenant un est . Par conséquent, le nombre de séquences avec deux ou plusieurs s est Le nombre total de séquences de nombres avec le plus grand nombre contenant à moins deux de les est -n y y n y ( y - 1 ) n y n ( y - 1 ) n - 1 y y n - ( y - 1 ) nyXnyyny(y-1)nyn(y-1)n-1y n y y x y = 1 ( y n - ( y - 1

yn-(y-1)n-n(y-1)n-1
nyy
y=1X(yn-(y-1)n-n(y-1)n-1)=y=1Xyn-y=1X(y-1)n-y=1Xn(y-1)n-1=Xn-ny=1X(y-1)n-1=Xn-ny=1X-1yn-1

Le nombre total de séquences est simplement . Toutes les séquences sont également probables et donc la probabilité est x n - nXn

Xn-ny=1y=X-1yn-1Xn

Avec je fais la probabilité 0,120004212454.X=100,n=25

J'ai testé cela en utilisant le programme Python suivant, qui compte les séquences qui correspondent manuellement (pour les faibles ), simule et calcule en utilisant la formule ci-dessus.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

Ce programme a généré

Simulation: x 100 n 25 total 1000000 count 120071 prob 0.120071
Formula count 12000421245360277498241319178764675560017783666750 out of 100000000000000000000000000000000000000000000000000 probability 0.120004212454
TooTone
la source
2
+1 Une courte simulation en R est compatible avec ce résultat. Après simulations, j'ai obtenu une estimation de . 0.119572000000.11957
COOLSerdash
@COOLSerdash C'est super merci. J'ai testé ma formule en listant toutes les permutations avant de poster (je vais lister le programme python dans une minute), sur de petites valeurs de et , mais je n'avais pas pensé à simuler la vraie question posée. nXn
TooTone
J'ai simulé en utilisant perl et j'ai obtenu un 0.005 très cohérent. pastebin.com/gb7JMLt6
agweber
@agweber Merci d'avoir écrit et exécuté votre simulation. Je ne suis pas un programmeur Perl, je ne peux donc pas commenter les détails de votre programme à un niveau élevé, il semble solide. Avez-vous testé votre code de simulation avec des probabilités connues, faciles à générer simplement en comptant les et faibles ? Par exemple, , la probabilité exacte est de . J'ai également augmenté mon programme Python avec du code de simulation, qui est d'accord avec les probabilités exactes pour les faibles et la probabilité de la formule que j'ai dérivée. Je suis curieux de savoir quelle est la source du désaccord entre notre code. n x = 20 , n = 5 15600 / 160000 = 0,0975XnX=20,n=515600/160000=0,0975X,n
TooTone
4
Une simulation Mathematica avec itérations a produit ce qui est probablement correct sur les quatre premiers chiffres. Le code est 0,119983 ,dix70,119983,n = 10^7; Total[Boole[Equal @@ (#[[Ordering[#, -2]]])] & /@ x = RandomInteger[{1, 100}, {n, 25}]] / n
whuber
3

J'envisagerais de trouver la probabilité d'avoir un gagnant unique en premier

La probabilité d'avoir un gagnant unique et son nombre est est égal à car il y a 25 choix pour le gagnant, et le le reste peut avoir un nombre compris entre 1 etX(251)(X-1)2410025y-1

Le gagnant peut gagner avec son nombre égal à 2 à 100, donc la probabilité totale est

je=210025(je-1)2410025=25je=199je2410025=-14+25je=1100je2410025-14+25124+110024+1+1210024+242161002310025=0,88

Ici, j'ai utilisé l'approximation jusqu'à Pour référence: https://en.wikipedia.org/wiki/Faulhaber 's_formula10023

Par conséquent, la probabilité d'avoir une égalité est de1-0,88=0,12

gary
la source
-3

Cela semble être une question très similaire au paradoxe de l'anniversaire ( http://en.wikipedia.org/wiki/Birthday_problem ), la seule différence est que dans ce cas, vous ne voulez pas correspondre à un nombre mais uniquement au plus grand nombre. La première étape du calcul calcule la probabilité qu'aucun des nombres aléatoires ne se chevauche ( ). (voir le lien ci-dessus), puis la probabilité que certains des 25 chiffres se chevauchent est où p est la probabilité que vous avez déjà calculée. Dans ce cas, la probabilité que les 25 nombres ne se chevauchent pas avec le maximum est donnée par: alors la probabilité que vous recherchez estp1-pp=1(1-1/100)(1-1/100)......(1-1/dix)=(1-1/100)24P=1-p=1-(1-1/100)24=0,214

Michel G
la source
cela signifie-t-il que la probabilité est de 21,4%? semble assez élevé, mais là encore, le paradoxe d'anniversaire a une réponse surprenante similaire. Merci.
Nzall
6
-1 En l'état, cette réponse n'est pas correcte. La réponse correcte a été fournie par @TooTone.
COOLSerdash