3
$\begingroup$

Given a set of numbers 1 through N, how many times do I have to randomly pick a number before all of the numbers have been picked a roughly equivalent (within 5% of each other) amount of times, and each one has at least been picked 100 times?

For example: Given numbers 1-10, how many times do I have to randomly pick one before 1,2,3,4,5,6,7,8,9,10 have all been picked about the same number of times?

I thought I was onto something: Each number will have the same chance of being picked, which is 1/N.

So in X picks, N will have X/N picks. N-1 will have X/N picks. ... N-(N-1) will have X/N picks. N-N will have X/N picks.

So if they all have X/N picks, that means as long as X > N, they will all be picked the same amount? It doesn't make sense, I'm missing something having to do with confidence level I think.

Update 7/7/16: This question shows that the probabibility that a particular number was chosen exactly k times when choosing a number randomly m times is: $p(k)={m\choose k}\frac{(n-1)^{(m-k)}}{n^m}$.
I think I'm getting closer, but not sure what to do with this information.

Update 7/7/16: Not a duplicate of "How many times to roll a die where all have been selected once...".

$\endgroup$
  • $\begingroup$ I think you might need to specify a few more things for this problem to be defined well. I can imagine some solution that identifies the probability that the min and max of a multinomial are within 5%, but I can't think of an approach for 'guaranteeing' these things are roughly equivalent $\endgroup$ – Sullysaurus Jul 1 '16 at 20:52
  • $\begingroup$ OK. I only need a 95% confidence level that the number of times picked for each possibility are within 5% of each other. Basically, I want to be able to say: If I make Y selections, each possibility will probably be picked about the same amount of times. $\endgroup$ – Kestrell Jul 1 '16 at 21:01
  • $\begingroup$ Possible duplicate of How often do you have to roll a 6-sided die to obtain every number at least once? $\endgroup$ – Sycorax Jul 7 '16 at 20:47
  • $\begingroup$ @General The two questions differ substantially: "at least once" and "within 5% of each other" not only are different criteria, they appear to require substantially different methods of analysis and even involve different concepts. $\endgroup$ – whuber Jul 7 '16 at 20:59
  • $\begingroup$ Kestrell, For some guidance consider this. Because the frequencies are random, there will always be some slight chance that they differ by more than 5%. Therefore your question should be framed as "how large should the sample be so there is at least a $1-\alpha$ chance that all $N$ frequencies will be within a range that is no longer than $100\gamma\%$ of the average frequency?" With $N=10$, $\gamma=0.05$, and $\alpha=.05$, elementary approximations suggest the answer is close to 80,000. Except for very small $N$ and large $\alpha$ and $\gamma$, approximations will be essential. $\endgroup$ – whuber Jul 7 '16 at 21:17
3
$\begingroup$

Multinomial problems can be tricky. But when the number of observations grows large, approximations can work very well. This post explains how to use mental arithmetic (or, at worst, the back of a napkin) to obtain a reasonable answer. The beauty of this approach lies in how one can solve challenging statistical problems like this one, using little more than mental arithmetic, by means of a passing familiarity with logarithms and the standard Normal distribution.


Notation

Let there be $d$ (rather than $N$) distinct objects, each with an equal probability of being drawn in a sample, and let $n$ be the number of draws (with replacement). Let $X_1, X_2, \ldots, X_d$ designate the frequencies of these objects, indexed by $1$ through $d$.

Framing the question

Because the frequencies are random, there will always be some chance that they differ by more than $5\%$. Therefore the question should be posed as "how large should the sample be so there is at least a $1−\alpha$ chance that all $d$ frequencies will be within a range that is no greater than $100\gamma\%$ of the average frequency?" With $d=10, \gamma=0.05,$ and $1-\alpha=.95$, elementary approximations suggest the answer is somewhat larger than $70,000$, as we will see.

The univariate distributions

Each $X_i$ has a Binomial$(N, 1/d)$ distribution. When the average frequency $N/d$ is sufficiently large (how large depends on $d$), these distributions are approximately Normal. To work with this approximation we need to recall that the mean and variance of a Binomial distribution are $N/d$ and $N(1/d)(1-1/d)$, respectively. Those are the mean and variance of the approximating Normal distribution.

The bivariate distributions

The $X_i$ are not independent, because they sum to $N$. What effect might this have on our calculations? To find out, let's compute their correlation. That calculation starts with the covariances $\operatorname{Cov}(X_i,X_j)$. Since the $X_i$ are completely interchangeable, all these covariances are equal, say to some number $U = \operatorname{Cov}(X_1,X_2)$. We can obtain this with a simple calculation:

$$\eqalign{ 0=\operatorname{Var}(N)=\operatorname{Var}\left(X_1+\cdots+X_d\right) &= d\operatorname{Var}(X_1) + d(d-1)\operatorname{Cov}(X_1,X_2) \\ &= dN\left(\frac{1}{d}\right)\left(1 - \frac{1}{d}\right) + d(d-1)U. }$$

The solution is

$$\operatorname{Cov}(X_i,X_j) = U = -\frac{N}{d^2}.$$

This corresponds to a mutual correlation

$$\rho = \frac{-N/d^2}{N(1/d)(1-1/d)} = -\frac{1}{d-1}.$$

For small $d$, this is large enough in size to be important: for instance, with $d=2$, $X_1$ and $X_2$ are perfectly negatively correlated (obviously, since $X_1 = N-X_2$). For sufficiently large $d$, though, we can expect that neglecting it might be a good approximation.

Distribution of the range

Let's suppose $d$ is large enough that we may approximate the correlation $-1/d$ by zero. Uncorrelated Normal variables are independent. We may recenter and rescale them to be standard Normal (with zero mean and unit variance), provided we remember to undo this change of units at the end.

Let the distribution function of a standard Normal variable be $F$ with density function $f$. The density function of the range $R = \max(X_i) - \min(X_i)$ is a little hard to work with, but it can be useful, so here it is for $r \ge 0$:

$$f_R(r) = n(n-1)\int_{-\infty}^\infty f(x)\left(F(x+r)-F(x)\right)^{n-2}f(x+r) \text{d}x.\tag{1}$$

This can be numerically integrated with a computer. In the meantime, notice that the symmetry of the standard Normal distribution around $0$ implies the distribution of the maximum is the same as the distribution of the negative of the minimum. The distribution function of the maximum is just $F^n$. Intuitively, the max and min must be positively correlated: when the maximum is large, that means all the values are a little larger than they might be predicted to be, which suggests even the minimum is a little larger than its average. But for even modest values of $d$, that correlation is not great. (For $d=10$ it's around $0.077$.) Therefore, we might consider approximating the range as the difference between two independent variables, one distributed like the maximum and the other like the minimum.

Once again we may resort to a (crude) approximation. Although the distribution of the maximum is not Normal--it has some positive skew--it's not that far off. We could estimate its mean and variance, then replace the range by a variable with twice that mean and twice that variance (which means its standard deviation will be $\sqrt{2}$ times as great).

That's still too hard to calculate exactly, but we can approximate the mean as the median and the standard deviation as half the distance between the 84th and 16th percentiles (which holds perfectly for a Normal distribution and is still pretty good for sort-of-Normal distributions).

Now we have something that's easy to work with. Consider the median (50th percentile) of the maximum. This is the value $z$ for which

$$F(z)^{10} = F_{\max}(z) = 0.50.$$

Equivalently, taking roots, it is the $z$ for which

$$F(z) = 0.50^{1/10}.$$

Since $\log(0.50) = -\log(2)\approx -0.7$, $\log(0.50^{1/10}) = (1/10)\log(0.50) \approx - 0.07$, implying $0.50^(1/10) \approx \exp(-0.07) \approx 1-0.07 = 0.93$. A basic familiarity with the Normal distribution indicates $z$ will lie between $1.28$ and $1.64$, perhaps around $1.5$ (interpolating). Therefore the expected value of the range is around $2\times 1.5=3.0$. (Numerical integration of $(1)$ gives $3.077$.)

Using similar back-of-the-napkin calculations we may solve the equations

$$F(z)^{10} = F_{\max}(z) = 0.84;\quad F(z)^{10} = F_{\max}(z) = 0.16$$

by approximating $\log(0.84) \approx 1-0.84 = -0.16$ and $\log(0.16) \approx \log(1/(2\times 3)) = -\log(2) - \log(3) \approx -0.7 - 1.05 = -1.75$. These yield

$$F^{-1}_{\max}(0.84) \approx F^{-1}(1 - 0.016) \approx 2.2$$

and

$$F^{-1}_{\max}(0.16) \approx F^{-1}(1 - 0.175) \approx 1.0.$$

Therefore the standard deviation of the maximum is approximately $(2.2-1)/2 = 0.6$ and the SD of the range will be estimated as $$0.6\times \sqrt{2} \approx 0.8.$$ (The correct value is $0.8125\ldots$.)

From these numbers--a mean range of $3.0$ and standard deviation of $0.8$--we may find upper limits for the range. For instance, because $95\%$ of the standard Normal distribution is less than $1.65$, the range should have around a $95\%$ chance of being less than $3.0 + 1.65(0.8) \approx 4.3.$ (A more accurate answer, also taking into account the correlation between maximum and minimum, is $4.47$.)

Application of the results

We have seen that in a sample of size $n$, by making many approximations and neglecting various correlations, the range of the $X_i$ has around a $95\%$ chance of being less than $4.3$ times the common standard deviation of the $X_i$, which is $\sqrt{n(1/d)(1-1/d)} = \sqrt{n(10-1)}/10$. The average of the $X_i$ obviously is $n/d$. We ask, then, how large must $n$ be in order that this limiting range not exceed $5\%$ of the average? In symbols, the inequality is

$$4.3 \frac{\sqrt{n(10-1)}}{10} \le \frac{5}{100} \frac{n}{10}$$

with the easy solution

$$70000\approx \left(\frac{4.3}{5/100}\right)^2(10-1) \le n.$$

By neglecting the negative correlations among the $X_i$, we have surely underestimated this sample size.

Checking via simulation

This gives us the starting value for a quick R simulation. In a few seconds, we can perform the experiment (of drawing ten numbers 70,000 times) over and over again 5,000 times:

n.sim <- 5e3
d <- 10
n <- 7e4
sim <- replicate(n.sim, diff(range(tabulate(sample.int(d, n, replace=TRUE), nbins=d))))
(quantile(sim*d/n, .95))

The output is around $0.0535$, showing that all $d=10$ counts were within $5.3\%$ of each other in $95\%$ of samples from $n=70,000$ draws. We're in the right ballpark and we were correct in supposing that slightly more draws would be needed.

Note that these recommended values of $n$ are so large, many of the Normal approximations used to derive it are amply justified.


Summary

The methods described here work for large $d$, $\alpha$ not too small, and $\gamma$ not too large. How to check? We will run into trouble if $\alpha$ is much smaller than $1\%$. When $nd$ is large--hundreds or more--you're probably ok using these approximations.

$\endgroup$
  • $\begingroup$ Thanks Whuber, I'll study this in depth and get back to it. $\endgroup$ – Kestrell Jul 8 '16 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.