# Find expected value and variance when selecting n ID cards without replacement

I am really stuck in this probability-related problem which is stated as follows:

You have $n$ people, each one with a different ID card (so a total of $n$ cards) and they put them in a box. Then each one takes an ID card from the box without putting it back (so without replacement) until the box becomes empty. We say that if a person picked his own ID card a success. Let us denote as $X$ the random variable which represents the number of such successes. We have to find the expected value and the variance of $X$.

Up until now, I have reached these conclusions:

• Let us denote: $X_i= \begin{cases} 1, & \text{if$i$person finds his ID card} \\ 0, & \text{if otherwise} \end{cases}$, so we get that $X=\sum_{i=1}^n X_i$ and $E[X]=E[\sum_{i=1}^n X_i]=\sum_{i=1}^n E[X_i]=\sum_{i=1}^nP[X_i=1]$. It all comes down to find $P[X_i=1]$ which I believe is this: $P[X_i=1]=P(\forall j<i,j \text{ person didn't take the$i$ID card})*P(\text{$i$person picked his own ID card})=P*\frac{1}{n-(i-1)}$.
• The above way of finding $P[X_i=1]$ also introduces some concept of ordering in the picking process (the $i$-th person picks after $1,2,...,i-1$ have already picked and while the rest have not) which I don't know if its right or not.
• I saw some connection with the hypergeometric distribution, but couldn't get something substantial out of it, based on the fact that I could find the expected value using the probability mass function: $E[X]=\sum_{i=0}^n xP[X=x]$ . I am pretty sure though that the probability to have $n$ successes is $P[X=n]=\prod_{i=0}^{n-1} 1/(n-i)$.
• I may looking at it the wrong way! Any ideas?
• $P(X_i=1)=\frac1{n}$ for $i=1,\dots,n$. Jan 24, 2017 at 13:04
• Isn't that the simple case when the cards are placed back in the box and the picking is therefore an independent action? I believe that we have dependency upon the picks of others in the problem.
– John
Jan 24, 2017 at 13:33
• In the case you describe we also have that outcome. Nevertheless the dependency does not spoil that. It is evident that the person who picks firstly will have chance $\frac1{n}$ to pick his own ID card. But can you give me a reason why the person who picks secondly will have a bigger or smaller chance to pick his own ID card than the person who picks firstly? The ordering of picking is irrelevant here. They might grab into the box all together and come out with an ID card they found. Jan 24, 2017 at 13:40

The "ordening of picking" is irrelevant.

For a fixed ID card in the box all $n$ persons (among them is the owner of the card) have equal chances to pick it out. So the probability that it is picked out by its owner is $\frac1{n}$. This makes us conclude: $$P(X_i=1)=\frac1{n}$$ where $i$ denotes the owner of the card.

This makes it easy to find $\mathbb EX$. In order to find $\text{Var}X$ we make use of the familiar:$$\text{Var}X=\mathbb EX^2-[\mathbb EX]^2$$

Observe that $\mathbb EX^2=\mathbb\sum_{i=1}^n\sum_{j=1}^n\mathbb EX_iX_j$ and make use of symmetry: if $i\neq j$ then $\mathbb EX_iX_j=\mathbb EX_1X_2$ and also $\mathbb EX_i^2=\mathbb EX_1^2$.

• So, we say that actually $X_i$ are independent here and get $E[X_i X_j]=E[X_i]E[X_j]=1/n*1/n$ ?
– John
Jan 24, 2017 at 14:12
• No, they are not independent. $\mathbb EX_1X_2=P(X_1=1,X_2=1)=P(X_1=1)P(X_2=1\mid X_1=1)=\frac1{n}\times\frac1{n-1}$. Jan 24, 2017 at 16:58
• Ok, so I guess: $E[X_1X_1]=P(X_1=1,X_1=1)=\frac{1}{n}\times\frac{1}{n}$. Can you please verify for me that after some calculations, $E[X]=1$ and that $Var(X)=1/n$?
– John
Jan 24, 2017 at 21:16
• Note that $X_1^2=X_1$(because $X_1$ only takes values in $\{0,1\}$) so that $E[X_1^2]=E[X_1]=\frac1{n}$. Secondly: $E[X]=1$ is correct but a good calculation leads (if $n>1$) to $\text{Var}(X)=1$. Jan 25, 2017 at 9:30
• Ah, yes of course everything is clear now, thanks a lot drhab :)
– John
Jan 25, 2017 at 17:10