Musings on Die rolling problem

I recently came across the problem of Conditional Die Rolls which I thoroughly enjoyed and prompted me make this post. In the interest of keeping things general without losing ourselves in notational complexity, let's consider a unfair 6-sided die with probability $p_k$ for each face.

Let $N$ be the random variable indicating the number of rolls needed to get the first $6$ and $K$ be that of the number of $5$s we get before our first $6$. Then Part-I of the problem in the page above, which asks for the expected number of rolls needed to get a $6$ given we did not see a $5$, is about finding $\mathbb{E}(N|K=0)$.

It is easy to see that $N\sim\text{Geom}(p_6)$ and therefore $\mathbb{E}(N)=1/p_6$.

But we need the conditional expectation to answer the question. Rather than getting into messy calculations, we can reason it as follows: We roll the die until we get a $5$-or-$6$ (which is simply given by the Geometric distribution that counts the number of failures before first success). If the final result is a $5$, we ignore that sequence. Else, we needed that one final roll to complete the process. Thus,

$\displaystyle\mathbb{E}(N|K=0)=\frac{1-p_5-p_6}{p_5+p_6}+1=\frac{1}{p_5+p_6}$

In fact, we get a more general result by noting that by ignoring the neither-$5$-nor-$6$ rolls and normalizing the probability of getting a $5$ and that of $6$, we see that

$\displaystyle K \sim \text{Geom}\left(\frac{p_6}{p_5+p_6}\right)$

where $K$ counts the number of failures (getting a $5$) before the first success (getting a $6$). Then,

$\displaystyle \mathbb{P}(N=n|K=0)=\frac{\mathbb{P}(N=n \land K=0)}{\mathbb{P}(K=0)}=\frac{(1-p_5-p_6)^{n-1}p_6}{p_6/(p_5+p_6)}$

and

$\displaystyle \mathbb{P}(\text{getting the first }5\text{ or }6\text{ in the }n\text{-th roll})=(1-p_5-p_6)^{n-1}(p_5+p_6)$

Therefore, the number of rolls needed to get the first $6$ given that we did not see a $5$ is identical in distribution to the number of rolls needed to get a $5$-or-$6$.

To solve Part-II, which in our notation asks for the expected number of rolls needed to get a $6$ given we saw a $5$ i.e. $\mathbb{E}(N|K\geq1)$, we see that this the same as waiting for the first $5$ before a $6$ and then waiting for a $6$. But by symmetry, waiting for the first $5$ before a $6$ is the same as waiting for the first $6$ before a $5$ which we solved in Part-I. Therfore,

$\displaystyle\mathbb{E}(N|K\geq1)=\frac{1}{p_5+p_6}+\frac{1}{p_6}$

In fact, by a similar argument and taking advantage of the memoryless property of die rolls as before, it is easy to see that

$\displaystyle\mathbb{E}(N|K\geq k)=\frac{k}{p_5+p_6}+\frac{1}{p_6}$ and $\displaystyle\mathbb{E}(N|K=k)=\frac{k}{p_5+p_6}+\frac{1}{p_5+p_6}=\frac{k+1}{p_5+p_6}$

Taking it a step further, it should not hard to see that

$N|K\sim\text{NB}(K+1,p_5+p_6)$

where we are using Formulation-2 of the Negative Binomial distribution.

Similarly, we can also quickly see that

$K|N\sim\text{Bin}(N-1,p_5 / (1 - p_6))$

because once we know that we needed $N$th roll resulted in the first $6$, $K$ is just the number of $5$s among $N-1$ non-$6$ rolls which is obviously binomial.

Then it is easy to see that

$\displaystyle \mathbb{E}(K|N=n)=(n-1)\frac{p_5}{1-p_6}$

In fact,

$\displaystyle \mathbb{E}(K|N\geq n)=(n-1)\frac{p_5}{1-p_6}+\frac{p_5}{p_6}$

because the first gives the number of $5$s in the first $N-1$ non-$6$ rolls (as $N\geq n$) and by the memoryless property of die rolls, the number of $5$s from that point on is just $\mathbb{E}(K|N\geq 1)=\mathbb{E}(K)$.

All of the above applies even if we sample with replacement. To make things clear, let's work on the problem of finding the expected number of cards required to get an Ace given we get some Kings from a standard 52-card deck. Let $N$ be the random variable indicating the number of cards to get an Ace and $K$ be the number of Kings we get during the process.

The following results vastly simplifies the foregoing discussion. If we sample without replacement from a population of $P$ samples of which $S$ are marked as 'success', we have,

$\displaystyle\mathbb{E}(\text{failures before first success})=\frac{P-S}{S+1}$ and $\displaystyle\mathbb{E}(\text{draws to get first success})=1+\frac{P-S}{S+1}=\frac{P+1}{S+1}$

For example, we have four Aces from a standard deck of cards. Therefore,

$\displaystyle\mathbb{E}(N)=\frac{52+1}{4+1}=\frac{53}{5}$

What about the number of cards needed to get first Ace given we did not get any Aces during the process? Like before, we draw cards till we get an Ace/King. If we get a King next, we restart discarding everything. Else, we needed one more card i.e. the Ace that ended the process. Therefore,

$\displaystyle \mathbb{E}(N|K=0)=\mathbb{E}(\text{draws before Ace or King})+1=\frac{52-8}{8+1}+1=\frac{53}{9}$

We can continue the same for finding the number of cards to get an Ace given we got atleast one King in the process. Because we have four Aces and four Kings in the deck, it is easy to see that either of them comes first between them is $1/2$. Then, using the law of total expecation, we have,

$\mathbb{E}(N)=\mathbb{P}(K=0)\mathbb{E}(N|K=0)+\mathbb{P}(K\geq 1)\mathbb{E}(N|K\geq 1)$

As $\mathbb{P}(K=0)=\mathbb{P}(K\geq 1)=1/2$, we can solve the above easily for $\mathbb{E}(N|K\geq 1)$. But we can proceed in more story-proof like fashion.

From the above and by symmetry, We know that we need $53/9$ cards to get a King before an Ace. We now have $52-53/9=415/9$ cards of which four Aces and we are waiting for the first Ace. It should be easy see that,

$\displaystyle\mathbb{E}(N|K\geq 1)=\frac{53}{9}+\frac{415/9+1}{4+1}=\frac{689}{45}$

Now, Given we needed $n$ cards to get the first Ace, we want to find the expected number of Kings we drew in the process. This can be computed relatively simple as follows:

$\begin{align}\displaystyle\mathbb{E}(K|N\geq n)&=\mathbb{E}(\text{Kings in first }n-1\text{ non-Ace cards})+\mathbb{E}(\text{Kings in remaining cards until first Ace})\\ \end{align}$

Now, it is easy to see that,

$\displaystyle\mathbb{E}(\text{Kings in first }n-1\text{ non-Ace cards})=(n-1)\frac{4}{48}=\frac{n-1}{12}$

Now we know that $4-(n-1)/12$ Kings and four Aces remaining in the deck. Because we are concerned only about the number of Kings and Aces, we can discard the remaining cards. Now we are counting the number of Kings (failures) until the first Ace (Success).

$\displaystyle\mathbb{E}(\text{Kings in remaining cards until first Ace})=\frac{4-(n-1)/12}{4+1}$

Therefore,

$\displaystyle\mathbb{E}(K|N\geq n)=\frac{n-1}{12}+\frac{4-(n-1)/12}{4+1}=\frac{n+11}{15}$

It should be easy by now to see that the Binomial/Neg.Binomial becomes HyperGeometric/Neg.HyperGeometric in the without replacement case. While we have used a handwavy method to solve these problems, seeing how symmetry brings everything together made me thoroughly enjoy the time spent in this problem.

Hope you enjoyed the discussion.

Until then

Yours Aye

Me

Solving an integral without calculus

I've always been a fan of solving integrals using goemetry or probability even if they are pretty trivial and / or straightforward with calculus. The content of this post is such one such integral which I encountered while studying the Kepler problem.

The subject of this post will be the following integrals.

$\displaystyle \int_b^a\sqrt{(a-r)(r-b)}\,dr$, $\displaystyle \int_b^a\frac{\,dr}{\sqrt{(a-r)(r-b)}}$ and $\displaystyle \int_b^a\frac{r\,dr}{\sqrt{(a-r)(r-b)}}$.

Consider the two concentric circles as shown above with center $D$ such that $\vert BC \vert=b$ and $\vert AC \vert=a$. The radius of the larger (red) circle is then $(a+b)/2$ and that of the smaller (orange) circle is $(a-b)/2$.

Two concentric circles

Now let $r=\vert BH \vert$. Then with simple geometry it can be seen that $\vert GH \vert=\sqrt{(a-r)(r-b)}$.

Then the $\vert GH \vert\,dr=\sqrt{(a-r)(r-b)}\,dr$ is the area of the thin infinitesimal rectangular strip with of dimensions $\vert GH \vert$ and $dr$. It is now easy to see that the first integral is just half the area of orange circle. That is,

$\displaystyle \int_b^a\sqrt{(a-r)(r-b)}\,dr=\frac{1}{2}\pi\left(\frac{a-b}{2}\right)^2$

Again from simple geometry, we have

$\displaystyle \frac{\vert GH \vert}{\vert DG \vert}=\frac{-d(\vert DH \vert)}{ds}$

where $ds$ is the infinitesimal arclength of the orange circle i.e. $ds=\vert DG \vert d\theta$ where $\theta=\angle BDF$.

Because $\vert DH \vert=\vert DB \vert - r$, we have $-d(\vert DH \vert)=dr$. Using all these and substituting, we have,

$\displaystyle \,d\theta=\frac{\,dr}{\sqrt{(a-r)(r-b)}}$

As $H$ moves from $C$ to $C'$, $r$ goes from $b$ to $a$ and $\theta$ from $0$ to $\pi$. Therfore,

$\displaystyle \int_b^a\frac{\,dr}{\sqrt{(a-r)(r-b)}}=\pi$

Similarly,

$\displaystyle \frac{\vert DH \vert}{\vert DG \vert}=\frac{d(\vert GH \vert)}{ds} \implies \vert DB \vert - r=\frac{d(\vert GH \vert)}{d\theta} \implies \vert DB \vert d\theta - r d\theta=d(\vert GH \vert)$

Summing up the infinitesimal changes of $\vert GH \vert$ as $\theta$ moves from $0$ to $\pi$ results in $0$ as $G$ rises in height from the diametric line $DB$ and comes back to the same line. Substituting for $d\theta$ from above, we have,

$\displaystyle \vert DB \vert \pi-\int_b^a \frac{r\,dr}{\sqrt{(a-r)(r-b)}}=0$ (or) $\displaystyle \int_b^a \frac{r\,dr}{\sqrt{(a-r)(r-b)}}=\pi\left(\frac{a+b}{2}\right)$

Hope you enjoyed the discussion.

Until then

Your Aye

Me

Sphere on a freely spinning turntable (again)..

After my initial post on this topic, I still felt that there is some more to the problem than what we've explored. I kept returning to this problem hoping to find something more and am glad I did.

We start with a following 'force' equation that we saw earlier.

$\mathbf{p}''=\alpha p_0 \mathbf{k}\times\widehat{\mathbf{p}}'$

Taking a dot product on both sides with $\mathbf{p}'$, we have

$\mathbf{p}'\cdot\mathbf{p}''=\alpha p_0 \mathbf{p}'\cdot(\mathbf{k}\times\widehat{\mathbf{p}}')$

Permuting the RHS and integrating the above, we see that

$\displaystyle \frac{1}{2}\left\vert{\mathbf{p}'}\right\vert^2+\alpha p_0 \int\mathbf{k}\cdot(\mathbf{p}'\times\widehat{\mathbf{p}}')\,dt=\text{const.}$

For any vector $\mathbf{q}$, with straightforward differentiation, we can show that

$\displaystyle \mathbf{q}'\times\widehat{\mathbf{q}}'=\frac{\mathbf{q}\cdot\mathbf{q}'}{\left\vert\mathbf{q}\right\vert^3}(\mathbf{q}\times\mathbf{q}')$

Using this result, the constant vector $\mathbf{m}$ from our earlier post and the fact that $\mathbf{p}\cdot\mathbf{k}=\sqrt{\delta/\alpha}$, we see that

$\displaystyle \mathbf{k}\cdot(\mathbf{p}'\times\widehat{\mathbf{p}}')=\frac{\mathbf{p}\cdot\mathbf{p}'}{p^3}\left(\mathbf{k}\cdot\mathbf{m}-\frac{\delta p_0}{p}\right)$

where $p=\left\vert\mathbf{p}\right\vert$.

Let $u=1/p$. It is easy to see that $u'=-(\mathbf{p}\cdot\mathbf{p}')/p^3$. This makes it almost trivial to integrate the above expression.

With the above, our 'energy' equation becomes

$\displaystyle E=\frac{1}{2}\left\vert{\mathbf{p}'}\right\vert^2-\alpha (\mathbf{k}\cdot\mathbf{m}) \frac{p_0}{p}+\frac{\delta\alpha}{2}\frac{p_0^2}{p^2}$

Now comes the interesting part. If we interpret the first term of the RHS as a measure of kinetic energy, the remaining terms gives us the 'effective potential' energy of the system. That is,

$\displaystyle V_{\text{eff}}(p)=-\alpha (\mathbf{k}\cdot\mathbf{m}) \frac{p_0}{p}+\frac{\delta\alpha}{2}\frac{p_0^2}{p^2}$

But that is exactly in the same form as that of the effective potential of the radial equation of an inverse square central force (Central forces). Therefore, the problem of a sphere on a freely spinning turntable is a Kepler problem in disguise which helps us in utilizing many known results.

For example, it known that the orbital period of a kepler problem can be written in terms of the 'energy' and the coefficient of the '$1/r$' term in the effective potential. Using the same, we can see that the orbital period $T$ for our problem is given by

$$\displaystyle T=\frac{2\pi\text{ }\alpha\text{ }p_0\text{ }(\mathbf{k}\cdot\mathbf{m})}{\left\vert2E\right\vert^{3/2}}$$

UPDATE (4-Aug-2026):

From (13) of Wessecker's paper, we can easily infer that

$L=\alpha p_0 p + \mathbf{k}\cdot(\mathbf{p}\times\mathbf{c})$

where $L$ is the reduced angular momentum about the $z$-axis which is shown to be a constant and $\mathbf{c}$ is the constant of integration in (10).

Now we define a vectorized form of $L$ such that,

$\mathbf{L}=\alpha p_0 p \mathbf{k}+\mathbf{p}\times\mathbf{c}$

We now show that $\mathbf{L}$ is a constant of motion by showing its components perpendicular and parallel to $\mathbf{k}$ are constants.

It's easy to see that $\mathbf{L}\cdot\mathbf{k}=L$ is a constant. Now,

$\mathbf{L}_{\perp}=\mathbf{k}\times(\mathbf{L}\times\mathbf{k})$

Using the fact that $\mathbf{c}\cdot\mathbf{k}=0$, we have

$\mathbf{k}\times(\mathbf{p}\times\mathbf{c})=(\mathbf{p}\cdot\mathbf{k})\mathbf{c}$

which is clearly a constant. Thus we see that $\mathbf{L}_{\perp}$, and hence, $\mathbf{L}$ is a constant.

We now start with the velocity equation which is (10) of Wessecker's paper expressed in terms of $\mathbf{p}$.

$\displaystyle\mathbf{p}'=\alpha p_0 \text{ }\mathbf{k}\times\hat{\mathbf{p}}+\mathbf{c}=\frac{\alpha p_0}{p} \text{ }\mathbf{k}\times\mathbf{p}+\mathbf{c}$.

Crossing the velocity equation with $\mathbf{p}$, with simple manipulations its easy to see in fact that $\mathbf{L}=\mathbf{m}$.

Dotting the velocity equation with itself and simplifying, we have,

$\displaystyle\vert \mathbf{p}'\vert^2=\vert\mathbf{c}\vert^2-\alpha^2 p_0^2+\frac{2\alpha p_0 L}{p}-\alpha\delta\frac{p_0^2}{p^2}$

Comparing with our energy equation, we see that

$\displaystyle E=\frac{1}{2}(\vert\mathbf{c}\vert^2-\alpha^2 p_0^2)=\frac{1}{2}\vert \mathbf{p}'\vert^2-\frac{\alpha p_0 L}{p}+\frac{\alpha\delta p_0^2}{2p^2}$

Hope you enjoyed the discussion. See ya later.

Until then

Yours Aye

Me

A Trigonometric Interpretation of an Infinite Product for the Lemniscate Constant

It is well known that Viete's infinite product formula for $\pi$ has a lemniscatic analog as showed by Levin in A Geometric Interpretation of an Infinite Product for the Lemniscate Constant.

$\displaystyle \frac{2}{\pi} = \sqrt{\frac{1}{2}} \cdot \sqrt{\frac{1}{2} + \frac{1}{2}\sqrt{\frac{1}{2}}} \cdot \sqrt{\frac{1}{2} + \frac{1}{2}\sqrt{\frac{1}{2} + \frac{1}{2}\sqrt{\frac{1}{2}}}} \cdots$

$\displaystyle \frac{2}{\varpi} = \sqrt{\frac{1}{2}} \cdot \sqrt{\frac{1}{2} + \frac{\frac{1}{2}}{\sqrt{\frac{1}{2}}}} \cdot \sqrt{\frac{1}{2} + \frac{\frac{1}{2}}{\sqrt{\frac{1}{2} + \frac{\frac{1}{2}}{\sqrt{\frac{1}{2}}}}}} \cdots ,$

Unfortunately, Levin's proof of this formula gets into Weierstrass with complex arguments to arrive at the result. This post is attempt to give a simpler proof with just trigonometric identities. We'll use the lemniscate sine and cosine functions but will reparametrize them in such a way that the proof remains simple.

The lemniscate elliptic functions, $\text{sl}(s)$ and $\text{cl}(s)$ are close analogues of the classical sine and cosine functions as can be seen in the figures in Relation to geometric shapes. The lemniscate curve was made immortal when Fagnano first found that they obey a doubling identity. That is,

$\displaystyle \text{sl}(2s)^2=\frac{4\text{sl}(s)^2(1-\text{sl}(s)^4)}{(1+\text{sl}(s)^4)^2}$

It can also easily seen that $\text{sl}'(s)^2=1-\text{sl}(s)^4$ where prime denotes differential w.r.t. $s$.

Surprisingly, this is all we need for our proof from the lemniscate. To begin, let's parametrise the lemniscate sine function with a parameter $t$ such that

$\text{sl}(s/2)=\sqrt{\tan(t)}$

Then using Fagnano's formula and double angle formulas of sine and cosine using tangents, we can quickly see that

$\text{sl}(s)=\sqrt{\sin(4t)}$

From here, it is straightforward that $\text{sl}'(s)=\cos(4t)$ and $\text{sl}'(s/2)=\sqrt{1-\tan^2(t)}$

Now with simple trigonometric identities, we have

$\displaystyle \frac{1}{\text{sl}'(s/2)}=\frac{\cos(t)}{\sqrt{\cos(2t)}}=\sqrt{\frac{1+\cos(2t)}{2\cos(2t)}}=\sqrt{\frac{1+\sec{2t}}{2}}$

But we know that $\text{sl}'(s)=\cos(4t)$ and therefore,

$\displaystyle \cos(2t)=\sqrt{\frac{1+\cos(4t)}{2}}=\sqrt{\frac{1+\text{sl}'(s)}{2}}$

Using this expression, we have

$\displaystyle\frac{1}{\text{sl}'(s/2)}=\sqrt{\frac{1+\left(\sqrt{\frac{1+\text{sl}'(s)}{2}}\right)^{-1}}{2}}$

To avoid this nested square roots, we introduce a new function such that $\hat{\text{sl}}(s)=\cos(2t)$. We then have,

$\displaystyle\text{sl}'(s/2)^{-1}=\sqrt{\frac{1+\hat{\text{sl}}(s)^{-1}}{2}}$ and $\displaystyle\hat{\text{sl}}(s)=\sqrt{\frac{1+\text{sl}'(s)}{2}}$

Now comes the interesting part. From our definitions of the lemniscate functions in terms of $t$,

$\displaystyle \frac{\text{sl}(s)}{2\text{sl}(s/2)}=\frac{\sqrt{\sin(4t)}}{2\sqrt{\tan(t)}}=\cos(t)\sqrt{\cos(2t)}$

Also,

$\displaystyle\frac{\hat{\text{sl}}(s)}{\text{sl}'(s/2)}=\frac{\cos(2t)}{\sqrt{1-\tan^2(t)}}=\cos(t)\sqrt{\cos(2t)}$

Therefore, we see that

$\displaystyle \frac{\text{sl}(s)}{2\text{sl}(s/2)}=\frac{\hat{\text{sl}}(s)}{\text{sl}'(s/2)}$

Repeated application of this relation $n$ times,

$\displaystyle \frac{\text{sl}(s)}{2^n\text{sl}(s/2^n)}=\frac{\hat{\text{sl}}(s)}{\text{sl}'(s/2)}\frac{\hat{\text{sl}}(s/2)}{\text{sl}'(s/4)}\cdots\frac{\hat{\text{sl}}(s/2^{n-1})}{\text{sl}'(s/2^n)}$

As $n \to \infty$ and noting that $\lim_{n \to \infty}2^n\text{sl}(s/2^n)=s$, we have

$\displaystyle \frac{\text{sl}(s)}{s}=\hat{\text{sl}}(s)\cdot\text{sl}'(s/2)^{-1}\cdot\hat{\text{sl}}(s/2)\cdot\text{sl}'(s/4)^{-1}\cdot\hat{\text{sl}}(s/4)\cdot\text{sl}'(s/8)^{-1}\cdots$

Based on the relations we saw before, if $a$ and $b$ are two consecutive terms on the RHS above, we see that

$\displaystyle b=\sqrt{\frac{1+a^{-1}}{2}}$

We have $\text{sl}(\varpi/2)=1$, $\text{sl}'(\varpi/2)=0$ and $\hat{\text{sl}}(\varpi/2)=1/\sqrt{2}$. Using these values in the infinite product above, we get the lemniscatic analogue of Viete's formula.

Hope you enjoyed this. See ya later.

Until then

Yours Aye

Me

Blending the Birthday Problem and the Coupon Collector Problem

The Birthday Problem and Coupon Collector problem are well known problems in probability that are like duals of each other. While the former deals with 'first collision', the latter deals with the 'complete collection'. I believe they are too famous even warrant further introduction here.

In this post, we attempt to solve a blend of these two problems. We start with the following question: If we are collecting coupons from among $n$ different types of coupons, what is the expected numbers of coupons that are needed to complete the collection given that the first collision occurred at the $c$'th coupon.

Let $K$ be the random variable indicating the number of coupons required to complete the collection and $C$ be the random variable indicated the number of coupons for the first collision. Then, we are looking for $\mathbb{E}(K|C=c)$.

This is not very hard. First, we already have collected $c$ coupons and because the first collision occurred at the $c$'th coupon, we have '$c-1$' distinct coupons. From here, we could proceed just like in the case of the original coupon collector problem. Therefore, we have,

$\begin{align}\mathbb{E}(K|C=c)&=c+\frac{n}{n-(c-1)}+\frac{n}{n-(c-2)}+\cdots+\frac{n}{1}\\&=c+n\text{ }H_{n-c+1} \\\end{align}$

where $H_n$ is the $n$'th Harmonic number. Note that the formula is valid for $1<c\leq n$.

We now deal with the (more challenging) 'reverse' question. That is, given we have completed the collection in $K=k$ coupons, how many cards were average would the first collision have occurred. That is, we look for $\mathbb{E}(C|K=k)$.

After trying out different approaches, I settled on the following approach. Let's first count the number of valid sequences. Let $N(n,j)$ be the number of sequences which collects $n$ different coupons exactly on the $j$'th draw. Obviously, $N(n,j)=0$ for $j<n$ and $N(n,n)=n!$.

With some thought, we could see that

$N(n,j)=n\text{ }N(n-1,j-1)+(n-1)\text{ }N(n,j-1)$

This works because, to collect $n$ exactly at the $j$'th draw, we could've (1) collected $n-1$ exactly at the $j-1$'th draw and the final coupon (for which we have $n$ choices) becomes the new coupon to complete the set (or) taken a sequence which completed the set of $n$ coupons in $j-1$ draws, choose any of the $n-1$ coupons except the last and insert it the penultimate position.

The $N$ function also has 'direct' formula via Stirling numbers of the second kind but we prefer this recurrence. We'll see why in a moment. Now, the expected value we are after can be written as,

$\displaystyle\mathbb{E}(C|K=k)=\frac{T(n,k)}{N(n,k)}$

where $T(n,j)$ is the sum of the first-collision-index of all the valid $N(n,j)$ sequences.

We don't have to look further to solve $T(n,j)$. Note that the neither of the two operations we described above for deriving the recurrence of $N(n,j)$ affects the first-collision-index of that sequence because the last coupon cannot be part of first collision (by definition, it has to be a new coupon to complete the set). Therefore, the same recurrence works for $T(n,j)$ as well!

The only tricky part is the boundary. Consider $T(n,n)$ which is the sum of all first collision indices where the set of $n$ coupons is collected in exactly $n$ draws. But those sequences must contain all distinct elements and therefore cannot have first collision. However, staying true to the process, we attribute a first collision index of $n$ to these sequences as we have collected $n$ coupons and the process have concluded. Therefore, we define, $T(n,n)=n \cdot n!$.

For example, using these recurrences, I get $\displaystyle\mathbb{E}(C|K=8,n=5)=612/175\approx 3.497$.

Now that we are on this subject, we can also check for $N(n,c,k)$, the number of sequences of coupons (from $n$ different coupons) that is 'complete' in the $k$'th draw and has its first collision on the $c$'th draw.

To compute $N(n,c,k)$, we must (1) choose '$c-1$' numbers in order (2) choose one among the '$c-1$' numbers for the $c$'th draw (3) choose one of the remaining '$n-c+1$' numbers to the last that completes the collection which means by now $c$ are already present in the sequence (4) choose $i$ of the remaining '$k-c-1$' positions for the '$n-c$' unseen numbers (5) partition the '$n-c$' numbers in $i$ non-empty subsets (6) use the '$c-1$' numbers at the start in the remaining positions without any constraint. Then,

$\displaystyle N(n,c,k)=\frac{n!}{(n-c+1)!}\cdot (c-1)\cdot(n-c+1)\cdot\sum_{i=0}^{k-c-1}\binom{k-c-1}{i}\cdot (n-c)!\left\{ \begin{matrix} i \\ n-c \end{matrix} \right\} \cdot (c-1)^{k-c-1-i}$

This can be simplified to finally give,

$\displaystyle N(n,c,k)=n!\cdot (c-1)\cdot\sum_{i=0}^{k-c-1}\binom{k-c-1}{i}\cdot \left\{ \begin{matrix} i \\ n-c \end{matrix} \right\} \cdot (c-1)^{k-c-1-i}$

I tried hard to find a recurrence or a generating function but failed miserably. I then delegated to CoPilot, Gemini and ChatGPT, and had a great time pointing one's error to the other. Finally, CoPilot (though I used it more than the others) figured out

$\displaystyle \sum_{n \geq 0,c > 0,k > c}N(n,c,k)\frac{x^n}{n!}\frac{y^{k-c-1}}{(k-c-1)!}z^{n-c}=\frac{x^2}{(1-xe^y)^2}\exp(y+xz(e^y-1))$

Gemini gave me the following python code that can be used to check the validity of the formula.

(code starts here..)

import itertools

def count_sequences(n, c, k):

    """

    n: total number of distinct digits available

    c: position of the first repetition (1-indexed)

    k: total length of the sequence

    """

    digits = list(range(n))

    valid_count = 0

    

    # Brute force through all n^k possibilities

    for seq in itertools.product(digits, repeat=k):

        # 1. Find the first repetition

        first_repeat_pos = 0

        seen = set()

        for i, val in enumerate(seq):

            if val in seen:

                first_repeat_pos = i + 1

                break

            seen.add(val)

        

        if first_repeat_pos != c:

            continue

            

        # 2. Check if the k-th digit is the one that completes the n-set

        if len(set(seq)) == n and len(set(seq[:-1])) == n - 1:

            valid_count += 1

            

    return valid_count

# Specific Example

n, c, k = 6, 4, 9

result = count_sequences(n, c, k)

print(f"count_sequences(n={n}, c={c}, k={k}) = {result}")

(... and ends here.)

Hope you enjoyed the discussion.

Until then

Yours Aye

Me