4

You are among N players that will play a competition. A lottery is used to determine the placement of each player. You have an advantage. Two tickets with your name are put in a hat, while for each of the other players only one ticket with her/his name is put in the hat. The hat is well shaken and tickets are drawn one by one from the hat. The order of names appearing determines the placement of each player. What is the probability that you will get assigned the $n$th placement for $n = 1, 2, . . . , N$?

The probability that my name is drawn at $k$th attempts is $\frac{2}{N}(\frac{N-2}{N})^{k-1}$ (ie to say $k-1$ failures before the first success at $k$). I know that the solution is $\prod_{k=1}^{n-1}\frac{2}{2+N-n}\frac{N-k}{2+N-k}$.

Let $A_i$ be the event that my name compairs shows up at $i$th attempts. So:

  • $\mathbb{P}(A_1)=\frac{2}{N+1}$;

  • $\mathbb{P}(A_2)=\mathbb{P}(\bar{A_1})\mathbb{P}(A_2|\bar{A_1})=(\frac{N-1}{N+1})(\frac{2}{N})$

  • $\mathbb{P}(A_3)=\mathbb{P}(\bar{A_1}\cap \bar{A_2})\mathbb{P}(A_3|\bar{A_1}\cap \bar{A_2})=(\frac{N-1}{N+1})(\frac{N-2}{N})(\frac{2}{N-1})$.

Thus I thought that

$\mathbb{P}(A_n)=(\frac{N-1}{N+1})\cdot (\frac{N-2}{N})\cdot ... \cdot (\frac{N-n-1}{N+1-n})\cdot (\frac{2}{N-n})$

but I can't lead me to the product above. Where am I wrong?

Francesco Totti
  • 537
  • It should be $\frac2{N+1}$ Imagine the tickets are drawn and placed face down in a line. What is the probability that the $k$ ticket has your number on it? See this question – saulspatz Sep 08 '20 at 07:06
  • @saulspatz What does it should be "$\frac{2}{N+1}$"? – Francesco Totti Sep 08 '20 at 07:11
  • How many tickets are there in total? – cosmo5 Sep 08 '20 at 07:53
  • @cosmo5 $N$ for each player including me, plus another always for me. So $N+1$, I presume. – Francesco Totti Sep 08 '20 at 08:05
  • The answer should be $\frac2{N+1}$ – saulspatz Sep 08 '20 at 09:02
  • @saulspatz Please, see my edit. – Francesco Totti Sep 08 '20 at 09:30
  • Your main error is that, since you have 2 tickets, you can be in 4th place and also in 1st place. That's why your product doesn't work out, you can be drawn in 4th place while already having been drawn (once) before. Saulspatz is right in their answer to the problem you stated. But the problem in the given context is non-sensical, because either you are "discovered" when your names comes up the second time, or when there is found to be a remaining ticket in the hat after $N$ draws. So I assume the problem statement is not what the "solution you know" refers to. – Ingix Sep 08 '20 at 12:15
  • I guess the information missing from the problem statement is something like "Once a name has been drawn and placed, any future tickets with that name are ignored". – Ingix Sep 08 '20 at 12:18
  • Are you asking for the probability that your name is first drawn on the nth ticket? – saulspatz Sep 08 '20 at 17:23

3 Answers3

3

I get (almost) the same result as you, under the assumption "Once a name has been drawn and placed, any future tickets with that name are ignored":

$(\color{green}{\text{green part edited}})$ $$\mathbb{P}(A_n)=\left(\frac{N-1}{N+1}\right)\cdot \left(\frac{N-2}{N}\right)\cdot ... \cdot \color{red}{\left(\frac{N-n+1}{N+3-n}\right)}\cdot \left(\frac{2}{N\color{green}{+2}-n}\right),$$

there are $n-1$ terms dealing with the first $n-1$ unsuccessful draws and the last with the successful draw. The denominators decrease by 1 in each factor as the number of tickets to draw from decreases by 1 after each draw. For the first $n-1$ terms (the unsuccessful draws) the enumerator decreases by 1 as well, so the difference between denominator and enumerator will always be $2$ in those terms (representing your 2 tickets).

That result can be written as

$$\frac{2}{N\color{green}{+2}-n}\prod_{k=1}^{n-1}\frac{N-k}{N+2-k}.$$

Your "known solution" is giving the empty product for $n=1$, so that would mean probability 1, which is obviously not correct. So please check if you copied it correctly.

Ingix
  • 14,494
  • Sorry, I edited. The correct solution is $\prod_{k=1}^{n-1}\frac{2}{2+N-n}\frac{N-k}{2+N-k}$. – Francesco Totti Sep 08 '20 at 13:28
  • I made an error, now corrected. The only difference now is that in your formula the constant term $\frac{2}{(2+N-n)}$ is inside the product, which is wrong. Not sure where the error is in your source or how you copied it here. – Ingix Sep 08 '20 at 14:24
2

Your solution simplifies extensively. For some reason, \cancel doesn't work, so I've tried to indicate what I mean by showing the terms that cancel in the same color. I can only show the first few terms this way, unfortunately.

$$\frac{\color{red}{N-1}}{N+1}\frac{\color{blue}{N-2}}{N} \frac{\color{green}{N-3}}{\color{red}{N-1}} \frac{\color{orange}{N-4}}{\color{blue}{N-2}}\dots $$

Here's a better way to do it.

Let $1\leq n\leq N$ be given.
Let $A$ be the event that your name is on the $n$th ticket. Let $B$ be the event that you name is not on any of tickets $1,2,\dots,n-1$. We seek $\Pr(A\cap B)$.

$$\Pr(A\cap B) = \Pr(A)\Pr(B|A) = \boxed{\frac2{N+1}\frac{N+1-n}{N}}$$

The first term is obvious. For the second, there are $N$ places where the other ticket with your name can be, and $N+1-n$ of them come after the $n$th ticket.

If you carry out the simplification described above, you will come to this simple answer.

saulspatz
  • 53,131
0

Maybe I'm not understanding how this probability experiment is being conducted, but I'm getting a different answer than everyone else. Maybe someone can point out why my reasoning is improper, if any of it is?

Let's assume once a player's name has been chosen, any future tickets with that name are ignored.

The number of ways tickets can be drawn so that your name shows up in the $n^{th}$ slot is ${2 \choose 1} \cdot {{N-1} \choose {N-1}} \cdot (N-1)!$

The number of ways tickets can be drawn in total is ${2 \choose 1}\cdot {{N-1} \choose {N-1}} \cdot N!$

Dividing these two gives the coveted likelihood of $$\frac{ 2 \cdot {{N-1} \choose {N-1}} \cdot (N-1)! }{ 2 \cdot {{N-1} \choose {N-1}} \cdot N! }=\frac{1}{N}$$

To see this we can look at a specific example. Suppose you're person #1 playing in a lottery with $N-1=2$ other people and $ \{1,1^*\} $ represents your two contributing tickets out of the $N+1=4$ tickets in the hat. We will denote the collection of all the tickets in the hat by $\{1,1^*,2,3\}$. We can list all ${2 \choose 1}\cdot {{3-1} \choose {3-1}} \cdot 3!=12$ possible orderings of the names explicitly: $$\{1,2,3\}, \{ 1,3,2\}, \{ 2,1,3\}, \{ 3,1,2\}, \{2,3,1 \},\{3,2,1 \}$$ $$\{1^*,2,3\}, \{ 1^*,3,2\}, \{ 2,1^*,3\}, \{ 3,1^*,2\}, \{2,3,1^* \},\{3,2,1^*\}$$ The probability that you're assigned to the $n^{th}$ placement is $ \frac{1}{N}=\frac{1}{3}$ for $n=1,2,3$ which makes total sense to me.

Matthew H.
  • 9,191
  • The problem is that by not showing the actual order tickets are drawn, inlcuding both $1$ and $1^$, those orders you consider do not have the same probability. For example, ${3,2,1}$ can only happen if $1^$ is the last remaining ticket in the hat. But for ${1,2,3}$, $1^*$ could be on positions 2,3 or 4. So ${3,2,1}$ is happening only one third of the time that ${1,2,3}$ happens. – Ingix Sep 08 '20 at 20:58
  • @Ingix Could you please tell me what you think about saulspatz's answer? – Francesco Totti Sep 09 '20 at 06:39
  • Very good and correct (I upvoted). I was just blind not to see the simplification and the answer has an alternative way to arive at the formula. – Ingix Sep 09 '20 at 09:02