Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

In many online games, when players complete a difficult task, sometimes a special reward is given which everyone who completed the task can use. this is usually a mount (method of transportation) or another vanity item (items which don't improve the performance of the character and are mainly used for appearance customization).

When such a reward is given, the most common way of determining who gets the reward is through random numbers. The game usually has a special command which generates a random (likely pseudorandom, not crypto secure random) number between 1 and 100 (sometimes the player can choose another spread, but 100 is the most common). Each player uses this command, all the players can see who rolled what, and the item is awarded to the person who rolls highest. Most games even have a a built-in system where players just press a button and once everyone pressed their button, the game does the rest automatically.

Sometimes, some players generate the same high number and noone beats them. this is usually resolved by those players regenerating their numbers, until there is a unique highest number.

My question is the following: Assume a random number generator which can generate any number between 1 and 100 with the same probability. Assume that you have a group of 25 players who each generate 1 number with such a random number generator (each with their own seed). You'll have 25 numbers between 1 and 100, with no limitations on how many players roll a specific numbder and no relation between the numbers. What is the chance that the highest generated number is generated by more than 1 player? In other words, what is the likelihood of a tie?

share|improve this question
5  
World of Warcraft eh? –  Behacad Mar 14 at 12:06
    
yes, it's uniform random, as stated in the question (any number between 1 and 100 inclusinve has the same probability. –  Nate Kerkhofs Mar 14 at 12:30
    
Good question, but this strikes me as a bad way to choose a winner. Just list the players in some way (you could say, "names alphabetically" or shuffle it and show everyone the list, or sort some other way), and pick a random number between 1 and 25. The number corresponding to the player wins. –  Tim S. Mar 14 at 13:58
2  
Noobs, use DKP! –  Davor Mar 14 at 21:44
1  
Suggestion: given a random sample $X_1,\dots,X_{25}$ from $\textrm{U}\{1,\dots,100\}$, we need to compute $P(X_{(24)}<X_{(25)})$ using what we know from the theory of order statistics. –  Zen Mar 15 at 2:35
show 1 more comment

2 Answers 2

up vote 19 down vote accepted

Let

  • $x$ be the top end of your range, $x=100$ in your case.
  • $n$ be the total number of draws, $n=25$ in your case.

For any number $y\le x$, the number of sequences of $n$ numbers with each number in the sequence $\le y$ is $y^n$. Of these sequence, the number containing no $y$s is $(y-1)^n$, and the number containing one $y$ is $n(y-1)^{n-1}$. Hence the number of sequences with two or more $y$s is $$y^n - (y-1)^n - n(y-1)^{n-1}$$ The total number of sequences of $n$ numbers with highest number $y$ containing at least two $y$s is \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}^n(y-1)^n - \sum_{y=1}^nn(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}

The total number of sequences is simply $x^n$. All sequences are equally likely and so the probability is $$ \frac{x^n - n\sum_{y=1}^{y=x-1}y^{n-1}}{x^n}$$

With $x=100,n=25$ I make the probability 0.120004212454.

I've tested this using the following Python program, which counts the sequences that match manually (for low $x,n$), simulates and calculates using the above formula.

import itertools
import numpy.random as np

def countinlist(x, n):
    lst = list(itertools.product(range(1,x+1), repeat=n))

    count = 0
    for perm in lst:
        if perm.count(max(perm)) > 1:
            count += 1

    print "Counting: x", x, "n", n, "total", len(lst), "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

This program outputted

Simulation: x 100 n 25 total 1000000 count 120071 prob 0.120071
Formula count 12000421245360277498241319178764675560017783666750 out of 100000000000000000000000000000000000000000000000000 probability 0.120004212454
share|improve this answer
1  
+1 A short simulation in R is compatible with this result. After $200000$ simulations, I got an estimate of $0.11957$. –  COOLSerdash Mar 14 at 13:32
    
@COOLSerdash That's great thankyou. I tested my formula by listing out all permutations before posting (I'm going to list the python program in a minute), on small values of $x$ and $n$, but I hadn't thought to simulate the actual question asked. –  TooTone Mar 14 at 13:34
    
I simulated using perl and got a very consistent 0.005. pastebin.com/gb7JMLt6 –  agweber Mar 14 at 16:32
    
@agweber Thanks for writing and running your simulation. I'm not a Perl programmer so I can't comment on the details of your program altho at a high level it looks sound. Did you test your simulation code with known probabilities, which are easy to generate simply by counting for low $x$ and $n$? E.g. $x=20,n=5$, the exact probability is $15600/160000=0.0975$. I've also augmented my Python program with simulation code, which agrees with exact probabilities for low $x,n$, and the probability from the formula I derived. I'm curious to know what the source of the disagreement between our code is. –  TooTone Mar 14 at 17:07
4  
A Mathematica simulation with $10^7$ iterations produced $0.119983,$ which is likely to be correct through the first four digits. The code is n = 10^7; Total[Boole[Equal @@ (#[[Ordering[#, -2]]])] & /@ x = RandomInteger[{1, 100}, {n, 25}]] / n –  whuber Mar 14 at 18:29
show 5 more comments

It seems a very similar question to the Birthday paradox (http://en.wikipedia.org/wiki/Birthday_problem), the only difference is that in this case you don't want to match any number but only the highest number. The first step in the calculation calculate the probability that non of the random numbers overlap ($p$). (see the link above) and then the probability that some of the 25 numbers overlap is $1-p$ where p is the probability you already calculated. In this case the probability the the 25 numbers don't overlap with the maximum is given by: $p=1*(1-1/100)*(1-1/100)......*(1-1/10)=(1-1/100)^{24}$ then the probability you are looking for is $P=1-p=1-(1-1/100)^{24} = 0.214$

share|improve this answer
    
does this mean that the probability is 21.4%? seems pretty high, but then again, the birthday paradox has a similar surprising answer. thanks. –  Nate Kerkhofs Mar 14 at 13:30
6  
-1 As it stands, this answer is not correct. The correct answer was provided by @TooTone. –  COOLSerdash Mar 14 at 13:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.