Chebyshev's Inequality to solve amount of stock needed

Question

A mail order company offers their first $1000$ customers a ladies' or mens' watch. Suppose that both sexes are equally attracted by the offer. How many ladies' and mens' watches are needed in order to ensure that --with a probability of at least $98$%, all $1000$ customers receive a matching watch.

I was tipped to use Chebyshev's inequality.

My idea:

Define $X:=$"Number of male watches stocked"

Note that since "both sexes are equally attracted by the offer", I only need to look at $500$ watches.

My problem is that my definition of RV $X$ does not allow for me to obtain $\mathbb E[X]$ let alone $\operatorname{Var}(X)$. I believe that I am using the wrong random variables, but cannot find any other appropriate ones.

Answer 1

Let $X=500+x$ male watches stocked, and the same number of female watches stocked. Note that this is not a random variable. Here the number of men or women is random since any customer can be of any sex equiprobable. Denote by $S_{1000}$ the number of men among first $1000$ customers. As wueb suggests, $S_{1000}=X_1+\ldots+X_{1000}$ where $X_i$ equals to $1$ if $i$-th customer is a men and $X_i=0$ if it is a women. Then $1000-S_{1000}$ is the total number of women.

We need both $S_{1000}\leq 500+x$ and $1000-S_{1000}\leq 500+x$ with probabilility at least $0.98$. These inequalities transform to $$ 500-x\leq S_{1000}\leq 500+x $$ or $$ |S_{1000}-500|\leq x. $$ We need to find $x$ such that $$ \mathbb P\left(|S_{1000}-500|\leq x \right) \geq 0.98. $$ If it is required to use Chebyshev's inequality, use $\textrm{Var}(S_{1000})=1000\cdot \textrm{Var}(X_1)=250$ in r.h.s.

$$ \mathbb P\left(|S_{1000}-500|\leq x \right) = 1- \mathbb P\left(|S_{1000}-500|> x \right)=1- \mathbb P\left(|S_{1000}-500|\geq x-1 \right) $$ $$ \geq 1-\frac{\textrm{Var}(S_{1000})}{(x-1)^2}\geq 0.98. $$ Find minimal integer $x$ satisfying this inequality and $500+x$ will be the answer for number of male watches.

Answer 2

It's worth pointing out that if you want to minimise the number of watches you have to stock, then using Chebyshev's inequality is a very poor way of going about it. From NCh's answer, the estimate is $\ 500 + \sqrt{\frac{250}{0.02}}\approx 611.8\ $, which rounds up to $\ 612\ $.

However, more precise calculations of the sums $\ \sum_{i=500-x}^{500+x} \frac{1000\choose i}{2^{1000}}\ $ for $\ x=36\ $ and $\ x=37\ $ give: $$ \sum_{i=463}^{537} \frac{1000\choose i}{2^{1000}}\approx 0.9823\\ \sum_{i=464}^{536} \frac{1000\choose i}{2^{1000}}\approx 0.9791\ . $$ So you really only need to stock $\ 537\ $ of each kind of watch to achieve the desired $\ 98\%\ $ probability.

A much better way to obtain this value is to use the normal approximation to the binomial distribution to obtain an initial estimate (which turns out to be $\ 536.8\ $), and then check the exact probabilities for a few integer values on either side of this. In this case, the normal approximation is so close that it gives you the right answer immediately.