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

A classic Pursuit problem

One the most famous and classic pursuit problem goes like this: A pursuer, initially at point $(0, b)$, is trying to catch a pursuee, initially at point $(a,0)$ and running along the $x$-axis in the positive direction, by always running directly towards him. If they both run at constant speed and the ratio of pursuer's speed to that of the pursuee is $1:k$ (with $k<1$), how far do the pursuer runs in the pursuit?

This problem is discussed in The American Mathematical Monthly (P3573, Vol. 40, No. 7, (Aug. - Sep., 1933)) and Pi Mu Epsilon Journal (Vol. 6, No. 9, Fall 1978, Pg. 545) among others (for example Pursuit Curve and Pursuit).

In both AMA and PME, the solution is obtained (albeit for a special case where the pursuee starts at the origin) by solving a 'challenging' differential equation which gives the exact equation of the path traversed by the pursuer.

However, if the distance traversed by the pursuer is all we want, do we still have to go through the trouble of solving such a complicated differential equation?

A pursuit curve with $k=4/5$ (Note that Geogebra is unable to render the full curve).

One of the key points to note in this problem is that the respective distance travelled by the participants in given interval of time is directly proportional to the ratio of the speeds.

We make an assumption that the pursuer ends up catching the pursuee (say at $C$ as shown above). While this may be obvious from the full solution, for our purposes, this will remain an assumption.

Consider the infinitesimal distance $\,ds$, say between $F$ and $H$ as shown below, covered by the pursuer in time $\,dt$. Drawing tangents at these points, we know that the pursuee was at position $J$ and $K$ respectively.

As the distance covered by them are in proportion to their speeds, we know that $|JK|=k\cdot|FH|=k\,ds$.

Let $l$ denote the relative distance between the pursuer and pursuee. Then, $\,dl=|FJ|-|HK|$. To calculate this, we complete the right $\triangle FMH$ and draw a line passing through $J$ and perpendicular to $FJ$ such that it intersects line $HK$ at $L$.

We now rotate line $FJ$ about $H$ such that $F$ moves to $F'$ (not shown in image) in line $HK$. Also, because the rotation is infinitesimally small, $J$ moves to $L$ in line $HK$.

Then, $|FJ|\approx |F'L|=|FH|+|HK|-|LK|$. That is, $|FH|=|FJ|-|HK|+|LK| \implies \,ds=\,dl+|LK|$

Because both $\angle FJL$ and $\angle HLJ$ are approximately right angled, $\angle HFM = \angle LJK$. Therefore, by the similarity of $\triangle FMH$ and $\triangle JLK$ and the fact that $|JK|=k\,ds$, we have,

$|LK|=k|HM|=k\,dx$

where $\,dx$ is the infinitesimal movement of pursuer along the $x$-direction.

Combining everything we have so far, we see that $\,ds=\,dl+k\,dx$.

We have now shown that $\,d(s-l-kx)=0$ (or) $s - l - kx = \text{const.}$

We can choose $s$ to be the distance to be travelled by the pursuer to reach $C$ and $x$ to be the distance along the $x$-axis between the pursuer and $C$.

We know that at point $C$, $s=l=x=0$ which means that the constant in the equation above is $0$ giving us the relation that $s=l+kx$.

Before we celebrate our success, we notice a glaring inconvenience in the above relation. While we will know that $l=l_0$ is the relative distance between the two parties at the start of the pursuit and $s=s_0$ is the distance we are trying to find, we do not know $x_0$. However, this is simple to resolve.

Let $x_0=h_0+p_0$ where $h_0$ is the horizontal distance between the pursuer and the pursuee at the start (which should be known for the problem to be defined) and $p_0$ is the distance between the pursuee and $C$.

By our definition of point $C$, we know that the pursuer travels distance $s_0$ in the time the pursuee travels distance $p_0$. Therefore, $p_0=k\cdot s_0$. Using this and solving for $s_0$, we get (after dropping subscripts),

$\displaystyle s=\frac{l+k\cdot h}{1-k^2}$

which solves the problem of finding the distance traversed by the pursuer in a more general setting where the they are not necessarily in the same vertical.

Hope you enjoyed this post.

Until then

Yours Aye

Me

Arclength of the Cycloid(s) from velocity vectors

Cycloid, the curve traced by a point on the rim of a circle rolling on a straight line, probably needs no introduction. Amongst its other distinctions, it remains one of the first few curves to be rectified. In this post we attempt to rectify the cycloid(s) with kinematics.

The cycloid's trajectory is a combination of simple motions - rolling and translation. Because the circle rolls without slipping on the straight line, its translational velocity is equal to its rotational velocity.

In fact, at the point at which the circle touches the base, the velocities are exactly equal in magnitude and opposite in direction making this point the instantaneous center of rotation.

The green vectors in the image below shows the translational and rotational velocities, and the velocity of the tracing point is represented by the red vector. Further, the rotational velocity vector is further resolved along the perpendicular components $PG$ and $PO'$.

From the geometry of the configuration, we can easily see that $|PF|=2\cdot |HE|$.

Because $PE$ represents the circle's infinitesimal arclength (in time $dt$) and $HE$ is the component of that arclength along $PG$, we also know that $|HE|=d(|PG|)$. Therefore, the infinitesimal arclength $ds$ of the cycloid traversed by the tracing point $P$ in time $dt$ is,

$ds=|PF|=2\cdot |HE|=2\cdot d(|PG|)$

As the change in arclength is equal to twice the change in $PG$ in any given time interval, the total arclength of the semiarch of the cycloid is equal to twice the diameter of the circle.

We can use the almost same reasoning for hypocycloids which are curves traced by a point on a rolling  circle of radius (say) $b$ inside within a larger circle of radius (say) $a$. For integer $q=a/b$, we get nice closed hypocycloids. The case for $q=5$ is shown below.

A pentoid ($q=5$)

Note that because the circle rolls without slipping, the angular velocity of rotation of the rolling circle is $q$ times its angular velocity of its revolution. Consequently, the movement of the tracing point is a composition of (i) rotation of vector of length $a-b$ by angle $t$ in the counter-clockwise direction about the origin and (ii) rotation of a vector of length $b$ by an angle $(q-1)t$ in the clockwise direction about the origin.

The above in turn means that the velocity vectors of both the rotations noted above are the same and are proportional to $(a-b)$ times $\,dt$ (or equivalently $b$ times $(q-1)\,dt$) denoted by green vectors below.

Here again, from the geometry of the configuration, it is immediately clear that the infinitesimal arclength traversed by the tracing point in time $dt$ is $ds=|PF|=2|HE|$.

But, because the smaller circle rotates $q$ times faster, the magnitude of the velocity vector of any point on its circumference will be proportional to $b\cdot q\,dt=a\,dt$ which is represented by the cyan vector in the image above.

Therefore, $\displaystyle \frac{|HE|}{|H'E'|}=\frac{a-b}{a} \implies |HE|=\frac{a-b}{a}|H'E'|=\frac{a-b}{a}\,d(|PG|)$

We then finally have $\displaystyle ds=2\frac{a-b}{a}d(|PG|)$

Then, the arclength to be traversed by the tracing point to reach the top of the arch is $2(a-b)/a$ times its distance to the topmost point of the rolling circle.

While the demonstration given for the cycloid in Wikipedia is even nicer method to determine the arclength, it is always fun to arrive at the same results with different methods. As shown below, its is not very difficult to extend the demonstration quoted above to hypocycloids as well.

Hope you enjoyed this post.

Until then

Yours Aye

Me