What is the probability of drawing a number which is equal to the number of the draw?

Question

I am dealing with a problem right now. It sounds like this: assume that there are N papers with numbers throughout 1 to N in a box. Whenever one of them is drawn it is not put back in the box. What is the probability of drawing AT LEAST one paper which has the same number as the number of the draw?

What I tried: I tried visualising the problem and came to the conclusion that the first draw has the chance of 1/N. Although the second draw, if the first one failed, is equal to 1/(N-2). Things get complicated afterwards for me.

I would be grateful if you could provide me with a solution and an explanation, I'm new to this topic. Thanks!

Answer 1

The drawing on its own can be looked at as drawing an element out of the set of permutations on $\{1,\dots,n\}$ in such a way that all $n!$ permutations are equiprobable, and to be found is then the probability of drawing a permutation $\sigma$ such that $\sigma(i)=i$ for at least one $i\in\{1,\dots,n\}$.

This probability equals $1$ minus the probability of drawing a permutation $\sigma$ that satisfies $\sigma(i)\neq i$ for every $i\in\{1,\dots,n\}$ which is by definition a so-called derangement.

The total number of derangements here is: $$!n:=n!\sum_{i=0}^n\frac{(-1)^i}{i!}$$

So the probability that a derangement is drawn is: $$\sum_{i=0}^n\frac{(-1)^i}{i!}$$Then the probability that you are looking for is:$$1-\sum_{i=0}^n\frac{(-1)^i}{i!}=\sum_{i=1}^n\frac{(-1)^{i-1}}{i!}$$

Answer 2

Question : What is the probability of drawing paper $x$ on draw $x$ ? (drawing without replacement)

The probability of choosing the wrong paper on the first $x-1$ draws is

$${(N-1) \over N }.{ (N-2) \over (N-1)} . {(N-3) \over (N-2)} .... {(N-x+1) \over (N-x)} = {(N-x+1) \over N} $$

Given that we are on draw $x$ and paper $x$ still exists in the remaining stack the probability of choosing paper $x$ is then ${1 \over (N-x+1)}$.

Therefore, the probability of choosing paper $x$ on draw $x$ is $${(N-x+1) \over N} .{ 1 \over (N-x+1)} ={ 1 \over N}$$

Answer 3

Let $P(x)$ denote the probability of drawing paper $x$ on draw $x$. We've shown $P(x)=(1/n)$. Let $P(x^{∗})$ denote the probability paper $x$ is drawn on draw $x$ AND no smaller paper is drawn on its number. $$ P(x^{∗}) = P(x)\cdot\prod_{y\lt x}(1-P(y))=(1/n)\cdot(1-(1/n))^{x-1} $$ where the product is taken over $y \lt x$.

The probability that at least one paper is drawn on its number is then the $\sum\limits_{x=1}^n P(x^{*})$ which yields $1-((n-1)/n)^n$.

Answer 4

drhab's answer is correct. In this answer, I simply use Inclusion-Exclusion to count the number of non-derangements.

Without changing the trials, assume the papers are stacked randomly in the box and we draw the top paper from the box.

We will use Inclusion-Exclusion to compute the probability that at least one paper is at its proper position in the stack.

Let $S(k)$ be the event that paper $k$ is at its proper position; that is, paper $k$ is at position $k$ in the stack.

Because each paper has probability $\frac1n$ to be in a given position, $S(k)$ has probability $\frac1n$ for each $k$. There are $\binom{n}{1}$ choices for $k$, so the sum of singleton probabilities is $$ \binom{n}{1}\frac1n=1\tag1 $$ Similarly, $S(j)\cap S(k)=\frac1n\frac1{n-1}$; that is, the probability that paper $k$ is in the proper position is $\frac1n$, and then the probability that paper $j$ is in its proper position is $\frac1{n-1}$. There are $\binom{n}{2}$ choices for $j$ and $k$, so the sum of the pair probabilities is $$ \binom{n}{2}\frac1n\frac1{n-1}=\frac1{2!}\tag2 $$ For the intersection of $m$ of the $S(k)$, we have a probability of $\frac1n\frac1{n-1}\cdots\frac1{n-m+1}=\frac{(n-m)!}{n!}$ and there are $\binom{n}{m}$ choices for the $S(k)$, so the sum of the m-tuple probabilities is $$ \binom{n}{m}\frac{(n-m)!}{n!}=\frac1{m!}\tag3 $$ Inclusion-Exclusion gives the probability of at least one paper being in the proper position to be $$ \sum_{m=1}^n\frac{(-1)^{m-1}}{m!}\tag4 $$