Probability (Odds) That Player Index N Draws Ticket Number N
By Ion Saliu, Founder of Randomness Philosophy, Probability Theory of Life
Here is what one can read in cyber forums that I have been known to frequent. Sometimes, I receive emails directing me to such posts.
"I've also posted this on alt.math.recreational:
I cannot seem to find a general solution to the problem below. It strikes me that it must be the sort of problem that has been tackled elsewhere as it can be stated so simply, but I'm not sure what it would be called and hence not sure how to search for it on Google. If you know the answer or could point me to a link I would be grateful.
Problem:
There are n people, each of whom writes their name on a piece of paper and puts that piece of paper into a hat. Each person takes it in turn to remove a piece of paper from the hat, if the piece of paper they remove has their own name written on it they put it back in the hat and choose again. What is the probability that the last person chooses their own name?
Duncan alt.sci.math.probability"
This problem is strongly correlated to the 911 event. I'll develop it even further. The way it is stated, the probability is exactly 1/n^2 - if the author meant EXACTLY the last player and none other. I can say in advance that I used MDIEditor and Lotto to test the validity of my calculations.
Let's try to make it as clear as possible. Let's say there are 5 persons, each with an ID number from 1 to 5 (instead of names). There are five tickets in the hat, numbered from 1 to 5. If I was designated 'player #5', what are various probabilities that I'll draw ticket #5 if I am the last in line to draw (position #5)?
1) I start with the case mostly resembling the '911 on 9/11' stochastic event. I want to know the probability that ANY player draws a ticket equivalent to his/her player ID. In the '911 on 9/11' case, we saw the probability of any pick-3 draw to match its date (in the US format). In words: Probability that player #1 draws ticket #1, OR player #2 draws ticket #2, player #3 draws ticket #3, player #4 draws ticket #4, player #5 draws ticket #5. We are going to dig to the deepest details. Buckle up!
1.1 – Player #1 is first to draw. The probability to draw ticket #1 is undoubtedly 1/5. No strings attached.
1.2 – Player #2 draws after player #1. The probability to draw ticket #2 must take into account what player #1 does. Player #2 is successful if player #1 did not draw ticket #2: p = 4/5. Why? The first step of player #2's success means that player #1 drew any of the other 4 of 5 tickets. Then, this step must be followed by the probability that player #2 draws one favorable ticket (#2) from the remaining 4 tickets in the hat. The events are simultaneous (none can be missing), therefore the probability is the product of the p's of the 2 events: 4/5 x ¼ = 1/5. The same probability as for player #1!
1.3 – One more laywoman/layman case. Player #3 draws after player #1 and player #2. The probability to draw ticket #3 must take into account what player #1 and player #2 just did. Player #3 is successful if player #1 did not draw ticket #3: p = 4/5. Why? The first step of player #3's success means that player #1 drew any of the other 4 tickets. Plus, the second step of player #3's success means that player #2 drew any of the other 3 of 4 tickets. Then, this step must be followed by the probability that player #3 draws one favorable ticket (#3) from the remaining 3 tickets in the hat. The events are simultaneous (none can be missing), therefore the probability is the product of the p's of the 3 events: 4/5 x ¾ x 1/3= 1/5. The same probability as for players #1 or #2!
We can expand to get a simple formula of any of the N players to draw a ticket equivalent to their draw order (or index):
p = (N-1)/N x (N-2)/(N-1) x (N-3)/(N-2) x…x (N-M-1)/(N-M) x … x (1)/(2) x (1)/( 1) = (N-1)! / N! = 1/N
2) In the '911 on 9/11' event, some stress the following condition: “The probability of a draw 911 EXACTLY on 9/11. I am not interested in any other draw that matches its date.”
In the player-and-ticket case: “The probability that EXACTLY player #5 draws last and draws ticket #5.” Also in this case: The probability that ticket #5 will be left alone, after players #1 through #4 drew their chances.
In the 911 on 9/11 situation, there are 365 dates. Clearly, the probability to get EXACTLY 911 on 9/11 is 1/365 x 1/1000 = 1/ 365,000. Several users of datePick3 noticed that the frequency of '911 on 9/11' matches are far, far less frequent than the probability I posted in the main NY draw 911 message. Indeed, they are right. And so am I. I certainly believe that an event like 911 will never repeat in real life. But a draw like 911 on September 11 will repeat according to the Fundamental Formula of Gambling for p=1/365,000. Once every 365 years is the realistic (and sane) expectation that we (Homo sapiens) will see another 911 pick-3 on September 11 in a country that formats date as month/day/year. If the international date formatting will prevail, then we might never see 911 on 9/11 again. Homo sapiens will FFG probably see 119 on 11/9 every 365 years or thereabouts.
In the player matches ticket number case, we'll see that the probability is 1/(NxN) for the last player to draw last and draw the ticket with the last number.
Let's go again with five players, and player #5 as the pivot. We know that player #5 is in the last position. The other 4 players can be arranged in 4! (4 factorial) positions. Position #5 never changes. The general formula in case #1 covers one and only one case: The ticket #5 is left as the last ticket for player #5 to draw. We have, however, 4 more equivalent situations:
2.1 – player #1 draws ticket #1 in draw #1; p = 1/N;
2.2 – player #2 draws ticket #2 in draw #2; p = 1/N;
2.3 – player #3 draws ticket #3 in draw #3; p = 1/N;
2.4 – player #4 draws ticket #4 in draw #4; p = 1/N.
Overall, we have 5 cases. The probability that ONLY one of them will occur is:
p = (N-1)! / N! / N = 1 / (N * N) = 1 / N2.
If there are 10 players, the probability that player #10 will draw ticket #10 if drawing last (position #10) p = 1/100. I verified. Everybody can verify. The free tools are the closest tools. The closest tools are more often than not the most useful tools. MDIEditor and Lotto WE would be such a long described tool. Click on Lotto, Odds + Random Lotto; select a game of 5 with 1 number per combination. The combination generating is very fast. Stop it quickly. You have to count the occurrences manually using MDI Go to Line command. If number 5 is in a multiple of 5 positions, count it as a success. I did get 5 of 95, 5 of 110, and 5 of 105 successes for a 1 of 5 game. It must be that the formula 2 is correct. At first, I believed the probability was 1 / N (not 1 / (N * N)). Remember, the probability is calculated as EXACTLY #M draws ticket #M. We need count all such occurrences and then average them out.
3) The original problem added one more restriction. “…if the piece of paper they remove has their own name written on it they put it back in the hat and choose again.” I also added one more restriction of my own. The original restriction makes the game possible only for three or more players and is applicable to the last player. If there are only two players, the first player can draw ticket #2 only. Therefore, ticket #2 is never available to player #2 (the last player in such a case).
All possible cases are reduced to: N2 – N + 1.
*** 3 players, player = P, ticket = T:
P1T2; P1T3
P2T1; P2T3
P3T1; P3T2 + P3T3
*** 4 players:
P1T2; P1T3; P1T4
P2T1; P2T3; P2T4
P3T1; P3T2; P1T4
P4T1; P4T2; P4T3 + P4T4
The final probability becomes:
p = 1 / {N2 – N + 1}
For any other situation, for the overwhelming majority of situations, the probability is:
p = 1 / N2.
It covers any case from 1 player, to N players. For one player, the probability would be:
(N-1) / N2 = 0!/1 = 1/1 = 1
We've heard this many times:
“It is a one-horse race. Guess who is winning…”
My supplementary restriction is that if a previous player draws his/her own index ticket, the ticket will be put back in the hat, but NO additional draw is performed. This makes matters a little more complicated, but will do the honor of closing the circle. In the end, the last player will be faced in some situations with more than one ticket to draw (draw from). The number of favorable cases was 1, while the number of total cases was N^2 for case 2. In this supplementary restriction, the total number of cases will be (N2 + N).
Therefore, the probability is p = 1 / (N2 + N) when the previous players return their index ticket to the hat and do not draw again.
I believe that all the bases are covered now.
Resources in Theory of Probability, Mathematics, Statistics, Combinatorics, Software
See a comprehensive directory of the pages and materials on the subject of theory of probability, mathematics, statistics, combinatorics, plus software.
Of great interest: