1956 Miklos Schweitzer Counting - Problem 10

Source: 1956 Miklos Schweitzer Contest (a Hungarian undergraduate open-note math contest) Problem 10

In an urn there are balls of $$N$$ different colours, $$n$$ balls of each colour. Balls are drawn and not replaced until one of the colours turns up twice; denote by $$V_{N,n}$$ the number of the balls drawn and by $$M_{N,n}$$ the expectation of the random variable $$v_{N,n}$$. Find the limit distribution of the random variable $$\frac{V_{N,n}}{M_{N,n}}$$ if $$N \to \infty$$ and $$n$$ is a fixed number.

Attempt (wrong): My thought process is that I'd 1. find the distribution of $$V_{N,n}$$, 2. compute $$\mathbb{E}[V_{N,n}]$$, and 3. apply a change of variables to get the distribution in question $$Y=\frac{V_{N,n}}{\mathbb{E}[V_{N,n}]}$$, and 4. justify the limiting distribution (I assume not too bad if we fix $$n$$).

1. We can justify the density by counting. If we desire $$P(V_{N,n}=k)$$, then this event occurs if we select $$k-1$$ colors from $$N$$ possibilities, $$\binom{N}{k-1}$$, and we select one ball from each of the $$k-1$$ colors for the first $$k-1$$ draws, $$\binom{n}{1}^{k-1}$$, and finally we select the last ball to be one of the $$k-1$$ colors already chosen, $$\binom{k-1}{1}$$. In summary, we have for $$k\in\{2,\dots,N+1\}$$

$$\mathbb{P}\left(V_{N,n}=k\right) = \frac{\binom{N}{k-1}n^{k-1}(k-1)}{\binom{Nn}{k}}.$$

1. From here, I thought oh maybe I'd apply some combinatorial identity like hockey-stick, Pascal's, the binomial theorem, look at generating functions or something similar to compute the expectation: $$\mathbb{E}\left[V_{N,n}\right]=\sum\limits_{k=2}^{N+1} \frac{\binom{N}{k-1}n^{k-1}(k-1)}{\binom{Nn}{k}}\cdot k.$$ However, I have no idea how to deal with the bottom - I assume I could apply Stirling's to get an approximation, but is there something exact here?

2. Even if step 2 failed, I try to continue - by change of variables, we have $$\mathbb{P}\left(Y=y\right)=\mathbb{P}\left(V_{N,n}=\mathbb{E}[V_{N,n}]y\right)\cdot\mathbb{E}[V_{N,n}]=\frac{\binom{N}{\mathbb{E}[V_{N,n}]y-1}n^{\mathbb{E}[V_{N,n}]y-1}(\mathbb{E}[V_{N,n}]y-1)}{\binom{Nn}{\mathbb{E}[V_{N,n}]y}}\cdot \mathbb{E}[V_{N,n}].$$ I can obviously not obtain a closed form without finding the expectation; however, it is evident that $$\mathbb{E}[V_{N,n}]\propto N$$ and $$\mathbb{E}[V_{N,n}]\propto n^{-1}$$. Thus as $$N\rightarrow\infty$$, ... uh never mind, there's nothing I think we could deduce.

Edit 1 (old method): With Raskolnikov's help, I now have, after some manipulation,

$$\mathbb{E}[V_{N,n}]=n(n-1)\sum\limits_{k=2}^N \frac{\binom{N}{k-1}n^{k-2}(k-1)}{\binom{Nn}{k}}+\frac{n^{N-1}(N+1)}{\binom{Nn-1}{N-1}}.$$

This looks a little more interesting - I really wanted to get the sum on the left to look like the derivative of the sum if I differentiate with respect to $$n$$, but the denominator is still troubling me. I thought maybe Vandermonde's would be useful

$$\binom{Nn}{k}=\sum\limits_{k_1+\cdots+k_n=k} \binom{N}{k_1}\cdots\binom{N}{k_n},$$

but that also seems to lead to a dead end I think.

Edit 2 (new method): Okay, with Raskolnikov's new method, I think it suffices to show the distribution of $$V_{N,n}$$ is exponential for some rate $$r\in(0,\infty)$$. With this approach, I tried the following (setting $$n=2$$ WLOG) $$\mathbb{P}(V_{N,n}>k)=\frac{2^{k-1}\binom{N-1}{k-1}}{\binom{2N-1}{k-1}}$$ $$= 2^k\frac{(2N-k)\cdots(N-k+1)}{2N\cdots(N+1)}$$ $$= 2^k\left(1-\frac{k}{2N}\right)\cdots\left(1-\frac{k}{N+1}\right)$$ $$=^*\left(1-\frac{rk}{N}\right)^N\rightarrow e^{-rk}\;\;\text{as}\;\; N\rightarrow\infty$$

but I'm blanking on the choice of $$r$$ to get $$=^*$$ to hold (or if it's even possible).

Question: I would appreciate some help for evaluating the limit in the new edited section. Thanks!

• Oh sorry. I just have seen the numbers and then made the wrong conclusion. So it is a well asked question. Commented Aug 2, 2022 at 18:23

This is almost like the birthday paradox problem, but without replacement. So it is natural to expect that $$M_{N,n}\propto \sqrt{N}$$. For any $$x>0$$, write $$\mathbb{P}(V_{N,n}>x\sqrt{N}) = \frac{nN\cdot n(N-1) \cdots n(N-x\sqrt{N}+1)}{nN(nN-1)\cdots (nN-x\sqrt{N}+1)} \\ = n^{x\sqrt{N}}\frac{N!(nN - x\sqrt{N})!}{(N-x\sqrt{N})!(nN)!}\\ \sim n^{x\sqrt{N}} \frac{\sqrt{2\pi N} \cdot \left(\frac{N}{e}\right)^{N}\cdot \sqrt{2\pi (nN-x\sqrt{N})} \cdot \left(\frac{nN-x\sqrt{N}}{e}\right)^{nN-x\sqrt{N}}}{\sqrt{2\pi (N-x\sqrt{N})} \cdot \left(\frac{N-x\sqrt{N}}{e}\right)^{N-x\sqrt{N}}\sqrt{2\pi n N} \cdot \left(\frac{nN}{e}\right)^{nN}}\\ \sim \frac{\left(1-\frac{x}{n\sqrt{N}}\right)^{nN-x\sqrt{N}}}{\left(1-\frac{x}{\sqrt{N}}\right)^{N-x\sqrt{N}}}, \quad N\to\infty.$$ Now $$\log \frac{\left(1-\frac{x}{n\sqrt{N}}\right)^{nN-x\sqrt{N}}}{\left(1-\frac{x}{\sqrt{N}}\right)^{N-x\sqrt{N}}}\\ = (nN-x\sqrt{N})\cdot \log \left(1-\frac{x}{n\sqrt{N}}\right) - (N-x\sqrt{N})\cdot \log \left(1-\frac{x}{\sqrt{N}}\right)\\ = -(nN-x\sqrt{N})\cdot \left(\frac{x}{n\sqrt{N}} + \frac{x^2}{2nN} + o(N^{-1})\right)\\ + (N-x\sqrt{N})\cdot \left(\frac{x}{\sqrt{N}}-\frac{x^2}{2N} + o(N^{-1})\right)\\ = -\frac{x^2}{2}\cdot \left(1-\frac1n\right) + o(1),\quad N\to\infty.$$ As a result, $$\mathbb{P}(V_{N,n}>x\sqrt{N}) \to \exp\left\{-\frac{x^2}{2}\cdot \left(1-\frac1n\right) \right\},\quad N\to\infty.$$ Consequently, $$V_{N,n}/\sqrt{N}$$ converges weakly to the Rayleigh distribution with scale parameter $$\sigma_n=(1-n^{-1})^{-1/2}$$.

I believe that with a little bit of extra work (basically, through $$M_{N,n} = \int_{0}^\infty \mathbb{P}(V_{N,n}>t)dt$$; I'm too lazy to do it) one can show that $$M_{N,n}\sim \sigma_n\sqrt{\pi N/2}, N\to\infty$$. As a result, $$V_{N,n}/M_{N,n}$$ converges in distribution to the Rayleigh distribution with parameter $$\sqrt{2/\pi}$$ (and mean $$1$$).

Here is another, less formal and perhaps more intuitive, derivation (we look at $$V_{N,n}/\sqrt{N}$$, so work in this scale): given that $$V_{N,n}>x\sqrt{N}$$, the conditional probability that a repetition will happen in the next $$\Delta x \sqrt{N}$$ draws, is approximately $$\mathbb P(V_{N,n}< (x+\Delta x) \sqrt{N}\mid V_{N,n}>x\sqrt{N})\approx 1 - \Big(\frac{nN-nx\sqrt{N}}{nN - x\sqrt{N}}\Big)^{\Delta x\sqrt{N}} \\ = 1 - \Big(1 - \frac{(n-1) x}{n\sqrt{N} - x}\Big)^{\Delta x\sqrt{N}} \approx \Big(1 - \frac{1}{n}\Big)x \cdot \Delta x.$$ This equation somehow confirms the intuition that the hazard rate is proportional to the number of balls already drawn. Hence, denoting by $$\overline F_n$$ the limiting complementary cdf of $$V_{N,n}/\sqrt{N}$$, we get $$\frac{\overline F_n(x) -\overline F_n(x+\Delta x)}{\overline F_n(x)}\approx \Big(1 - \frac{1}{n}\Big)x \cdot \Delta x,$$ so $$\overline F_n'(x) = -\Big(1 - \frac{1}{n}\Big)x\cdot \overline F_n(x),$$ whence, taking into account that $$\overline F_n(0) = 1$$, we get $$\overline F_n(x)= \exp\left\{-\frac{x^2}{2}\cdot \left(1-\frac1n\right) \right\}.$$

• @Raskolnikov actually, it is also quite intuitive that the limit is not exponentially distributed. This is because the latter is memoryless, while the distribution in question obviously has increasing hazard rate: the longer we wait the more likely color repetition is to appear. Commented Aug 15, 2022 at 19:39
• To be honest, that is not so obvious to me, especially in the limit of large $N$. Commented Aug 15, 2022 at 19:59
• @Raskolnikov, I've given an alternative derivation, which might be a little bit more intuitive. Commented Aug 16, 2022 at 6:58
• It's indeed neat, but I think what I really missed was two points: 1/ scaling with $\sqrt{N}$ (should have seen that coming though, because it's so common in statistics), 2/ the fact that we scale the mean. If indeed we just started the game with an infinite amount of colours, the game would be memoryless. But that's not what happens, we start with a finite amount and scale it up, thereby scaling up the mean as well, which "maintains the memory". Anyway, things are always obvious in hindsight. Commented Aug 16, 2022 at 7:43
• @Raskolnikov, the rate $\sqrt{N}$ is quite intuitive too: around $a$ draws, $V_{N,n}$ behaves like (in fact, is dominated by) a geometric random variable with success probability $a/N$, so it should be $N/a$ on average. Equating $a \approx N/a$ yields the right scale. Commented Aug 16, 2022 at 8:18

EDIT: Some update to the problem and a suggestion for a new approach. This is still not a full answer, but I think it is more promising than the initially suggested approach.

First of all, let's go back on the calculation of the probabilities $$\mathbb{P}\left(V_{N,n}=k\right)$$. To make my original approach more explicit, I worked with a probability tree, working out step by step what happens.

In the first step, we just draw one ball, which one is irrelevant, but the situation after drawing is the following:

$$\{ n-1 , \overbrace{n , \ldots , n}^{N-1} \}$$

From which we can deduce that the probability of drawing the same colour on our next draw is $$(n-1)/(nN-1)$$ and the complement is $$n(N-1)/(nN-1)$$. If the second draw is unsuccessful (i.e. we don't draw the same colour), we are left with the situation:

$$\{ n-1 , n-1 , \overbrace{n , \ldots , n}^{N-2} \}$$

Which means that the probability of success on the next draw is now $$2(n-1)/(nN-2)$$ and the complement $$n(N-2)/(nN-2)$$.

We can keep repeating this. Finding the probability of success for after k draws is then only a matter of multiplying out those conditional probabilities. I want to however bring the attention to the complementary probabilities. When we multiply these out, we get the probabilities of succeeding taking more than $$k$$ turns, i.e.

$$\mathbb{P}\left(V_{N,n}>k\right) = \frac{n^{k-1}\binom{N-1}{k-1}}{\binom{Nn-1}{k-1}}$$

Note that this formula is a bit neater than the other ones and works for $$k \in \{1,\ldots,N+1\}$$. Also,

$$\mathbb{P}\left(V_{N,n}=k\right) = \mathbb{P}\left(V_{N,n}>k-1\right) - \mathbb{P}\left(V_{N,n}>k\right) \; .$$

Here comes the second step. I figured out that it would be more clever to guess what the solution of the problem is before continuing. What could the limiting distribution be? Considering this is an open-note contest problem, my guess is that the limiting distribution would be one of the basic ones you encounter (Normal, Exponential, Poisson, etc...). Obviously, the range of values for $$V_{N,n}/M_{N,n}$$ will be continuous and unbounded. There's no reason why with infinite colours, the game could not go on indefinitely with ever decreasing probability. And there's no reason why the mean value would be entire. That rules out discrete distributions and distributions on a bounded support. Note also, that the problem suggest there is only one relevant parameter: the mean. If the limiting distribution was Normal, surely an extra variance parameter would be required. But this is not the case. Hence, my guess: the limiting distribution will be the exponential distribution. If you think about it conceptually, it makes sense because $$V_{N,n}/M_{N,n}$$ behaves a bit like a waiting time.

Now, for an exponential distribution, the moment generating function is

$$\mathbb{E}\left(e^{tX}\right)=\frac{\lambda}{\lambda-t}, \text{ for } t<\lambda$$

In our case $$X=V_{N,n}/M_{N,n}$$ and thus $$\mathbb{E}(X)=1$$. So, we expect that $$\lambda=1$$. Hence, the moments of the limiting $$X$$ need to satisfy

$$\mathbb{E}(X^a)=1 ,$$

which can be deduced by performing a Taylor expansion of the moment generating function. Hence, we are left to prove that

$$\lim_{N\to\infty}\frac{\mathbb{E}\left(V_{N,n}^a\right)}{M_{N,n}^a}=1 , \text{ for } a \in \mathbb{N}\setminus\{0,1\}$$

The moment is

$$\mathbb{E}\left(V_{N,n}^a\right) = \sum_{k=2}^{N+1} k^a \mathbb{P}\left(V_{N,n}=k\right)$$

which with a bit of algebra and my results from the first step can be recast into

$$\mathbb{E}\left(V_{N,n}^a\right) = 2^a + \sum_{k=2}^{N} ((k+1)^a-k^a) \mathbb{P}\left(V_{N,n}>k\right)$$

Which results in the following limit

$$\lim_{N\to\infty}\frac{\mathbb{E}\left(V_{N,n}^a\right)}{M_{N,n}^a} = \lim_{N\to\infty}\frac{2^a + \sum_{k=2}^{N} ((k+1)^a-k^a) \mathbb{P}\left(V_{N,n}>k\right)}{\left[2 + \sum_{k=2}^{N} \mathbb{P}\left(V_{N,n}>k\right)\right]^a}$$

or more explicitly

$$\lim_{N\to\infty}\frac{\mathbb{E}\left(V_{N,n}^a\right)}{M_{N,n}^a} = \lim_{N\to\infty}\frac{2^a + \sum_{k=2}^{N} ((k+1)^a-k^a) \frac{n^{k-1}\binom{N-1}{k-1}}{\binom{Nn-1}{k-1}}}{\left[2 + \sum_{k=2}^{N} \frac{n^{k-1}\binom{N-1}{k-1}}{\binom{Nn-1}{k-1}}\right]^a}$$

I claim that this limit is indeed one. However, I was not able to make a completely clean calculation, I approximated the binomial coefficients using the Stirling formula and then tried to work my way out to see that things canceled out, but I feel the computation is not clean enough to present here. So, that should still be the point to work on. But, I thought this result was worth writing down nonetheless.

This is not a full response yet, but will address part 1 of the question.

If we look at what your proposed formula predicts for $$k=2$$, we have

$$\mathbb{P}\left(V_{N,n}=2\right) = \frac{\binom{N}{1}n^{1}(1)}{\binom{Nn}{2}} = \frac{2}{nN-1}.$$

This can't be right. Think about it this way: at the start, you pick one ball of any colour. So you have now $$n-1$$ balls left over of that specific colour and $$nN-1$$ balls in total left. So on your second picking, your chance of picking the same colour is $$(n-1)/(nN-1)$$ which is not what your formula predicts.

I claim that the correct formula for $$2\leq k \leq N$$ is

$$\mathbb{P}\left(V_{N,n}=k\right) = \frac{\binom{N}{k-1}(n-1)n^{k-2}(k-1)}{N\binom{Nn-1}{k-1}},$$

and for $$k=N+1$$

$$\mathbb{P}\left(V_{N,n}=N+1\right) = \frac{n^{N-1}}{\binom{Nn-1}{N-1}}.$$

This might not be the most elegant way to state the probability though. Any comment welcome.

• Thanks - I counted wrong. From here, it may be more elegant to rewrite the density as $$\mathbb{P}(V_{N,n}=k)=\frac{\binom{N}{k-1}n^{k-1}(n-1)(k-1)}{\binom{Nn}{k}}$$ for $k\in\{2,\dots,N\}$
– user672552
Commented Aug 4, 2022 at 16:44
• Shouldn't there be an additional factor $k$ somewhere in your reworked version? Commented Aug 4, 2022 at 18:07
• Yes - I couldn't edit the comment earlier
– user672552
Commented Aug 5, 2022 at 3:18
• Again - really awesome effort! So you have shifted the problem statement to showing that for $a\in\mathbb{N}\setminus\{1\}$, we have $$M_{N,n}^a=\mathbb{E}[V_{N,n}^a]$$ as $N\rightarrow\infty$ by guessing that this is exponential when thinking about this in relation to waiting times
– user672552
Commented Aug 11, 2022 at 15:33
• Basically, what we need to do now is derive a good asymptotic formula for the $\mathbb{P}\left(V_{N,n}>k\right)$. At least good to some order in $1/N$. Obviously, since they are probabilities, they are $O(1)$ and if you fill that in, you get 1 as a limit. However, that is too crude an estimate to be believable. Commented Aug 11, 2022 at 15:49