# Probability of selecting same numbers by players (not a pigeon hole problem)

There are $n$ players who play a game of selecting numbers from a range $k$ over a period of time and the rules of the game are as follows :

• The game is played for 1 minute and the players are only allowed to select a random number from the range $k$ after the passage of every 1 second.
• After selecting a number, a player is not allowed to select another number until the selected number decreases to 0. It means that after selecting a number, the number decreases by $1$ after every second. As an example, if a player $\mathcal A$ selects a the number $5$, then $\mathcal A$ has to wait for $5$ seconds before the number becomes $0$ and only then $\mathcal A$ can select another number.

I want to find following probabilities :

• Case 1: When a particular player $\mathcal A$ selects a number from a range $k$, what is the probability that other players also selects the same number from the given range $k$

• Case 2: Consider a player $\mathcal A$, who selects 5. Then after 1 second, what is the probability that other players select a number which is equal to the (selected number by $\mathcal A$ (minus $1$) i.e. $5 - 1 = 4$). Similarly after $2$ seconds, what is the probability that any other player selects a number which is equal to the (selected number by $\mathcal A$ (minus $2$) i.e. $5 - 2 = 3$). And so on until the number selected by $\mathcal A$ becomes $0$.

In short I want to find the combined probability of selecting a number, which is similar to the number selected by $\mathcal A$ (both in Case 1, and while the number is being decremented in Case 2), by other players for 1 minute.

I am bad at probabilities , so a stepwise approach would be very helpful.

• What have you tried ? And does "other players select " mean at least one other player ? – true blue anil Jun 26 '15 at 8:51
• I tried to apply that pigeon hole formula but that does apply here. I am bad at probabilities, so I am stuck without help. Yes, "other players select" means at least one other player. – tina maholand Jun 26 '15 at 9:10

## 2 Answers

To start you off,

Case 1 :

$\mathscr P$(a player selects a different # than $\mathcal A$) = $\frac{k-1}{k}$

$\mathscr P$(n-1 players select a different # than $\mathcal A$) = $[\frac{k-1}{k}]^{(n-1)}$ = X (say)

$\mathscr P$(at least one player selects the same # as $\mathcal A$) = 1 - X

Case 2 :

Those who chose 2 or more (category P) can't select after 1 second.

Even if they chose 1, (category Q) they get eliminated if they choose any # other than $\mathcal A$-1

There could be varying #s in "P" and Q" so case 2 becomes quite complicated, more so with time ....

I wonder... has this question been given to you ?

• No, this question has been created by me. Actually, I have designed a new protocol, and it needs some formulation so that i can put some rigor into my protocol design. since, probability is not my thing, i am stuck. – tina maholand Jun 26 '15 at 15:24
• Case 2 seems quite messy to me to tackle analytically. Simulation may be a simpler approach with good enough results, but I am sorry I can not help you there ! – true blue anil Jun 26 '15 at 16:34
• thank you anil, actually i already have the results through simulation. i appreciate your help :) – tina maholand Jun 26 '15 at 22:41

Does this make the scenario simpler?

Scenario: A person “X” selects at random a number from range “r”. If X selects a number “n”, then “X” makes “n” more attempts to select numbers from the same range “r”. As an example, If “X” first selects “3” from range [0 - 5] then “X” makes 3 more attempts to select random numbers from [0 - 5].

So,

1: Given “y” number of players who select random numbers from the same range simultaneously, then what is the probability that any other player selects the same number as selected by “X”.

2: Considering that "X" has selected "3". Then "X" makes 3 more attempts in picking numbers from the same range. So, what is the probability that in the next attempt, “X” selects a number which is equal to the (selected number by “X” (minus 1) i.e. 3−1=2). Similarly in subsequent attempt, what is the probability that “X” selects a number which is equal to the (selected number by “X” (minus 2) i.e. 3−2=1). And in the final attempt, what is the probability that “X” selects a number which is equal to the (selected number by “X” (minus 3) i.e. 3−3=0).

So, what is the combined probability (that another player selects the same number as selected by “X” in the first attempt”) plus the probability (for “X” to select the number as specified in case 2 in the subsequent attempts).