Question

In the generalized match problem, there are n individuals of whom n_i wear hat size $i,\sum _{i=1}^r n_i=n$. There are also n hats, of which h_i are of size$i,\sum _{i=1}^r h_i=n$. If each individual randomly chooses a hat (without replacement), find the expected number who choose a hat that is their size

Short answer

The expected number that chooses a hat that is their size is will be$E\left[X\right]=\frac{1}{n}\sum _{i=1}^r h_i{n}_i$.

Step-by-step solution

Given information

The available information is. There are n individuals, n_i of them wear a hat of size i. Also, there are n hats, of which h_i are of size i.

Solution

We need to find the new variable,

$X_{i,j}=\left\{\begin{array}{l}1\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if the}j\text{th individual choose hat size of}i\\ 0\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if not}\end{array}\right\}$

The number of individuals that choose a hat of there is given by,

$X=\sum _{i=1}^r \sum _{j=1}^{n_i} X_{i,j}$

The probability of choosing a hat of size $h_i$is $\frac{h_i}{n}$

Thus the expected value of X will be,

$E\left[X\right]=E\left[\sum _{i=1}^r \sum _{j=1}^{n_j} X_{i,j}\right]$

$=\sum _{i=1}^r \sum _{j=1}^{n_j} E\left[X_{i,j}\right]$

$=\sum _{i=1}^r \sum _{j=1}^{n_i} \frac{h_i}{n}$

$=\frac{1}{n}\sum _{i=1}^r h_i\times n_i$

$=\frac{1}{n}\sum _{i=1}^r h_i{n}_i$

Final answer

The expected number that chooses a hat that is their size is will be$E\left[X\right]=\frac{1}{n}\sum _{i=1}^r h_i{n}_i$