An Inversion problem from PiMuEpsilon

Often times in math, a given problem can be solved in multiple ways using algebra, geometry, calculus etc. and we try to find the shortest proof among them. But say if we are interested in Geometry, we would still look for a geometrical proof even if it is more cumbersome. This post is a perfect example of such an instance.

Let's say we a given a semicircle $C_1$ with diameter $AB$ and a circle $C_2$ with center $P$ internally tangent to $C_1$. Let the two (half) chords of $C_1$ tangent to $C_2$ and perpendicular to diameter $AB$ meet $AB$ at $R$ and $S$ respectively. Let the line perpendicular to $AB$ and passing through $P$ meet $AB$ at $Q$. We asked to prove that $PQ$ is the geometric mean of $AR$ and $SB$.

An algebraic proof is easy to find but we attempt to find a geometric one. To do that, we begin by constructing a few circles.

We first construct a circle tangent at and passing through $B$ and also is orthogonal to the blue circle, which can be constructed by drawing a tangent from $B$ to the blue circle and using the distance from $B$ and the tangent point as the radius. This is shown in orange in the next figure.

We construct another circle that is internally tangent to the green circle at $B$ and externally tangent to the blue circle. We also reflect this circle w.r.t line $PQ$. Both these are shown in violet in the following figure.

A little thought shows that the violet circle and the green circle must be inversions of each other under the orange circle.

We finally contruct another circle using the following three points (i) intersection of line $PQ$ and the orange circle and (ii) the points of intersection of the green circle and the mirrored violet circle. This is shown in red in the following figure.

We will now show that the mirrored violet circle and the green circle are inversion of each other under the red circle.

To this effect, we construct an inversion circle with center at the (lower) point of intersection of line $PQ$ and the violet circle, and make the inversion circle orthogonal to the violet circles. The inversion circle is shown in black in the following figure.

The violet circles and line $PQ$ are all invariant under this inversion.

Both the orange and the red circle pass through the center of inversion. Therefore they become straight lines. These lines can be drawn using the points of intersection of the respective circles with the inversion circle. Note that the point of intersection of the lines must lie on line $PQ$.

Line $PQ$ and the orange circle are both orthogonal to the blue circle. Therefore, their inversions will also be so. This shows the point of intersection of the orange line and line $PQ$ is the center of the blue circle's inversion. Using the fact the blue circle is tangent to both the (invariant) violet circles, we can also construct the 'inverted' blue circle.

Because the red line also passes through the point of intersection of the orange line and line $PQ$ (because the red circle passes through the intersection of the orange circle and line $PQ$), we see that the red line is orthogonal to the 'inverted' blue circle. That means, the red circle and the blue circle are actually orthogonal to each other.

As we know that the green circle and the violet circle are inversion of each other under the orange circle, we get to see that the inversion of the green circle must be the reflection of the (invariant) violet circle w.r.t the orange line.

Also, the red circle passes through the point of intersection of the green circle and the mirrored violet circle which must also be the case after inversion. Therefore we see that the 'inverted' green circle and the mirrored violet circle are reflections of each other w.r.t red line.

That clearly means that the green circle and the mirrored violet circle are actually inversions of each other under the red circle.

Because of the said inversion, we see that $FR^2=RA \cdot RA'$

But $FR=PQ$. Also, $RA'=SB$ by symmetry. Therefore, $PQ^2=AR \cdot SB$ as claimed.

Until then
Yours Aye
Me

Expected area of Routh's triangle

Hi everyone! Wish you a very happy New Year! Now onto my first post of the year...

I recently came up a problem in Geometric probability which really had a stunning result that took by surprise. 

Consider a triangle $ABC$. Choose points $D$, $E$ and $F$ uniformly randomly on sides $BC$, $CA$ and $AB$ respectively. The three cevians $AD$, $BE$ and $CF$ form a smaller central triangle, which we call as Routh's triangle, between them as shown in the figure below.

Now what might be the expected value of the ratio of the area of $\triangle PQR$ to that of $\triangle ABC$?

Let the random variable $T$ denote the ratio we are interested in. Then given the positions of $D$, $E$ and $F$, Routh's theorem tells us,

$\displaystyle \frac{\triangle PQR}{\triangle ABC}=\frac{(uvw-(1-u)(1-v)(1-w))^2}{(1-u+uv)(1-v+vw)(1-w+wu)}$

where $DC=u\cdot BC$, $EA=v\cdot CA$ and $FB=w\cdot AB$.

Because $u$, $v$ and $w$ are IID uniform random variables by definition,

$\displaystyle \mathbb{E}(T)=\int_0^1\int_0^1\int_0^1 \frac{\triangle PQR}{\triangle ABC} \,dudvdw$

This integral is very unwieldy despite the symmetry between the variables and I can't see a clear way of solving this triple integral. We can solve this with Wolfram Alpha, but let's see how we can solve this without a CAS.

The trick is to solve this problem is shift our focus on triangles $ARC$, $BPA$ and $CQB$. In fact, over the course of proving Routh's theorem we get as an intermittent result that

$\displaystyle \frac{\triangle{ARC}}{\triangle{ABC}}=\frac{u(1-w)}{1-w+wu}$

and similar results for $\triangle{BPA}$ and $\triangle{CQB}$. Because,

$\triangle{ABC}=\triangle{PQR}+\triangle{ARC}+\triangle{BPA}+\triangle{CQB}$

we can now use the linearity of expectation and idea of symmetry to get

$\displaystyle \mathbb{E}(T)=1-3\int_0^1\int_0^1\frac{u(1-w)}{1-w+wu}\,dudw=1-3\int_0^1\int_0^1\frac{(1-w)(1-u)}{1-wu}\,dudw$

Now using Geometric series and term-by-term integration it is easy

$\displaystyle \int_0^1\int_0^1\frac{1}{1-wu}\,dwdu=\zeta(2)$, $\displaystyle \int_0^1\int_0^1\frac{wu}{1-wu}\,dwdu=\zeta(2)-1$ and

$\displaystyle \int_0^1\int_0^1\frac{u}{1-wu}\,dwdu=\int_0^1\int_0^1\frac{w}{1-wu}\,dwdu=1$

Plugging in all these values, we get the amazing amazing result that $E(T)=10-\pi^2$

Because we've calculated an expected value of a non-negative random variable, we know that this quantity is greater than zero and hence $10>\pi^2$.

Such a beautiful result that is atleast as remarkable as A cute sum of Ramanujan!!

Until then
Yours Aye
Me

Minimum of an Exponential random variable - First arrival times

Let $T$ be an exponential random variable with parameter $\lambda$. In this post, we are going to find the expected value of $\text{min}(T,1)$ with four different method each of which is beautiful in its own way.

Direct integration

We know that the density function of $T$ is $\lambda e^{-\lambda t}$. Therefore,

$\begin{align}\displaystyle\mathbb{E}(\text{min}(T,1)) &= \int_0^\infty \text{min}(t,1)\lambda e^{-\lambda t}\,dt \\ &= \int_0^1 t\cdot\lambda e^{-\lambda t}\,dt+\int_1^\infty 1\cdot\lambda e^{-\lambda t}\,dt \\ &= \frac{1-(1+\lambda)e^{-\lambda}}{\lambda}+e^{-\lambda}\\ &= \frac{1-e^{-\lambda}}{\lambda}\end{align}$

Conditional expectation

Here we condition based on the value of the random variable and use the fact that $\mathbb{P}(T>t)=e^{-\lambda t}$ and $\mathbb{E}(T)=1/\lambda$. By the law of total expectation,

$\begin{align}\displaystyle\mathbb{E}(\text{min}(T,1))&=\mathbb{P}(T<1)\mathbb{E}(\text{min}(T,1)|T<1)+\mathbb{P}(T>1)\mathbb{E}(\text{min}(T,1)|T>1) \\ &=\mathbb{P}(T<1)\mathbb{E}(T|T<1)+\mathbb{P}(T>1) \end{align}$

But we can get the first term by conditioning on $T$. We know that

$\displaystyle \mathbb{E}(T)=\mathbb{P}(T<1)\mathbb{E}(T|T<1)+\mathbb{P}(T>1)\mathbb{E}(T|T>1)$

Using the memoryless property, we know that $\mathbb{E}(T|T>1)=1+\mathbb{E}(T)$. Therefore,

$\begin{align}\mathbb{P}(T<1)\mathbb{E}(T|T<1)&=\mathbb{E}(T)-\mathbb{P}(T>1)\mathbb{E}(T|T>1)\\&=\mathbb{E}(T)-\mathbb{P}(T>1)(1+\mathbb{E}(T))\\&=\mathbb{P}(T<1)\mathbb{E}(T)-\mathbb{P}(T>1)\\ \end{align}$

Using this, we get,

$\mathbb{E}(\text{min}(T,1))=\mathbb{P}(T<1)\mathbb{E}(T)=\displaystyle\frac{1-e^{-\lambda}}{\lambda}$

Story proof

Let's say the arrival rate of customers to a store follows a Poisson process with parameter $\lambda$. On a given day, the store owners decides to wait the next customer for maximum one hour and shut shop thereafter.

Using this story, we can see that the waiting time of the store owner is $\text{min}(T,1)$ where $T\sim \text{Exp}(\lambda)$.

If the store owner does not have a time limit of one hour, then he would wait for $\mathbb{E}(T)=1/\lambda$ hours for the first customer.

However, if no customer arrive during the first hour, which happens with probability $e^{-\lambda}$, then he would have to wait, on average, for another $1/\lambda$ units time for the first customer by the memoryless property. Therefore, because of his time limit, he saves, on average, $e^{-\lambda}/\lambda$ units of time.

This shows the average waiting time is $1/\lambda-e^{-\lambda}/\lambda$

Using the Poisson distribution

The approaches so far have used the memoryless property one way or the other. Here we do away without that.

Using the story above, let $X$ denote the number of customers that arrive during the first hour. It should be intuitively obvious that the average time of first arrival is $1/(X+1)$. For example, if three customers arrive, we would expect their arrival times, on average, to be the 15th, 30th and the 45th minute mark.

Obviously $X\sim\text{Poisson}(\lambda)$. Therefore,

$\displaystyle\mathbb{E}\left(\frac{1}{X+1}\right)=\sum_{k=0}^\infty \frac{1}{k+1}\cdot\frac{e^{-\lambda}\lambda^k}{k!}=\frac{1}{\lambda}\sum_{k=1}^\infty \frac{e^{-\lambda}\lambda^k}{k!}=\frac{1-e^{-\lambda}}{\lambda}$

There we have it! Four different proofs for this expectation. I'll detail why this expectation is kinda important in a later post.

Before I forget, please allow me to credit reddit users lukewarmtoasteroven and blungbat for the second and third proofs respectively in my reddit question on the same topic.

Until then
Yours Aye
Me

Asymptotic Probability of not finding a pair

Consider the problem of finding the probability of not finding a pair (not two consecutive cards of the same rank) from a well shuffled pack. We already discussed this problem in this post where I could this stackexchange post that uses Generating function to solve the problem.

I was eventually able to understand the Generating function approach in the SE post. I'll postpone that for a later post as we'll be looking at something equally interesting in this post. We'll be using the usual well known approach that is indispensable in this type of problems.

Using the ideas in the SE post, we see that the probability of not finding a pair in a pack of well shuffled deck is given by the integral,

$\displaystyle \mathbb{P}(\text{No pair})=\frac{1}{52!}\int_0^\infty e^{-z} (z^4-12z^3+36z^2-24z)^{13}\,dz$

Notice that this is not exactly in the form given in the SE post but we'll probe how the two expressions are equivalent in a later post. For now, let's focus just on the integral. Let,

$\displaystyle I_{4,n}=\int_0^\infty e^{-z} (z^4-12z^3+36z^2-24z)^n\,dz$

To apply Lapalce's method, we manipulate the above like as shown below.

$\displaystyle I_{4,n}=\int_0^\infty e^{n(-z/n+\ln(z^4-12z^3+36z^2-24z))}\,dz$

We now need the value of $z=z_0$ where the function $f(z)=-z/n+\ln(z^4-12z^3+36z^2-24z)$ is maximized. Here's where things get a little interesting.

Even though, it seems to be very hard to find the exact value of $z_0$, with some experimentation, it seems $z_0 \approx 4n+3$ for large $n$.

Expanding $f(z)$ at $z=4n+3$ and keeping terms upto $O(n^{-1})$, we see that

$\displaystyle f(z)\approx -4-\frac{3}{n}+\ln f(4n+3)-\frac{(z-4n-3)^2}{8n^2}$

Therefore,

$\displaystyle I_{4,n}\approx e^{-4n-3}(256n^4-288n^2-96n+9)^n \int_{-\infty}^\infty e^{\frac{-(z-4n-3)^2}{8n}}\,dz$

Using the Normal approximation, we then have,

$I_{4,n} \approx e^{-4n-3}(256n^4-288n^2-96n+9)^n\sqrt{2\pi}\sqrt{4n}$

Let $\mathbb{P}_{j,n}(\text{No Pair})$ be the probability of getting no pair in a pack of $nj$ cards where each card has an integer from $1$ to $n$ and each integer has $j$ cards. Then,

$\displaystyle\mathbb{P}_{j,n}(\text{No Pair})=\frac{I_{j,n}}{(nj)!}$

Using Stirling's approximation, we know that

$n!~\approx \sqrt{2\pi n}e^{-n}n^n$

Therefore,

$\displaystyle \mathbb{P}_{4,n}(\text{No Pair})\approx \frac{e^{-4n-3}(256n^4-288n^2-96n+9)^n\sqrt{2\pi}\sqrt{4n}}{\sqrt{2\pi}\sqrt{4n}e^{-4n}(4n)^{4n}}$

Simplifying further, we get

$\displaystyle \mathbb{P}_{4,n}(\text{No Pair})\approx e^{-3}\left(1-\frac{288n^2+96n-9}{256n^4}\right)^n\approx e^{-3}\left(1-\frac{9}{8n}\right)$

Doing this for different $j$, I was able to see that, in general,

$\displaystyle \mathbb{P}_{j,n}(\text{No Pair})\approx e^{1-j}\left(1-\frac{(j-1)^2}{2nj}\right)$

For example, this approximation gives $\mathbb{P}_{4,13}(\text{No Pair})\approx 0.0454785$ versus the exact value of $\mathbb{P}_{4,13}(\text{No Pair})=0.0454763$ which is extremely good.

Unfortunately, its not the case always. For example, the approximation above gives $\mathbb{P}_{13,4}(\text{No Pair})\approx 0.00000441615$ versus an actual value, given in the SE post quoted at the beginning of the post, of $0.00000118175$ which is understandable as $n$ in this case is very small.

But using the approximations $e^x\approx 1+x$ and $\ln (1-x)^{-1}\approx x+x^2/2$, we get refine our approximation to give,

$\displaystyle \mathbb{P}_{j,n}(\text{No Pair})\approx e^{-(j-1)}e^{\frac{-(j-1)^2}{2nj}}\approx \text{exp}\left(-nj \ln\left(\frac{1-j^{-1}}{n}\right)^{-1}\right)=\left(1-\frac{1-j^{-1}}{n}\right)^{nj}$

Now this 'hand-wavy' approximation gives

$\mathbb{P}_{4,13}(\text{No Pair})\approx 0.045501$ and $\mathbb{P}_{13,4}(\text{No Pair})\approx 0.00000118835$

which is much better in both the cases and gives us some us some reason to take the 'hand-waviness' seriously.

Until then
Yours Aye
Me

Sunrise Problem - With Replacement

The famous Laplace Sunrise problem asks for the probability of the sun rising tomorrow given that it has risen for the past $n$ days. In this post, we generalize this problem to a setup where the population size is finite and how it changes the required probability.

Mathematically, we are looking for the posterior distribution of the unknown parameter $p$ such that

$X|p \sim \text{Bin}(n,p)$ and $p \sim \text{Beta}(\alpha,\beta)$

It is then well known that the posterior distribution is

$p|X \sim \text{Beta}(\alpha + X, \beta + n - X)$

Therefore, if we start with a uniform prior for $p$ so that $p \sim \text{Beta}(1,1)$ and given that $X=n$, then $p|X=n \sim \text{Beta}(1+n,1)$. Then

$\displaystyle \mathbb{E}(p|X)=\frac{n+1}{n+2}$

We now consider the following problem: Let's say we have an Urn containing $N$ balls such that some are white and rest are black. Let's say we draw $n_1$ balls from the Urn without replacement and observe the number of white balls. We then take $n_2$ balls from the Urn. Now, what is the probability distribution of the number of white balls in the second sample?

Casting the given information in mathematical terms, we have

$X_1|K \sim \text{HG}(N,K,n_1)$

$X_2|K-X_1 \sim \text{HG}(N-n_1,K-X_1,n_2)$ and

$K \sim \text{Beta-Bin}(N,\alpha,\beta)$

where the Beta-Binomial distribution is the discrete analog of the Beta distribution and has the discrete uniform distribution as the special case when $\alpha=\beta=1$. Note that we are looking for $X_2|X_1$.

It is then well known (this beta-binomail as conjugate to hypergeometric and Some Relationships and Properties of the Hypergeometric Distribution) that 

$K-X_1|X_1 \sim \text{Beta-Bin}(N-n_1,\alpha+X_1,\beta+n_1-X_1)$

We now take a detour into a slightly different problem.

Let $Y|X \sim \text{HG}(N,K,n)$ and $K \sim \text{Bin}(N,p)$. What would be the unconditional distribution of $Y$?

We can get into an algebraic mess of expression to solve this but let's do it with a story proof. Let's say we have $N$ marbles each of which is painted either green (with probability $p$) or red and put into a bag. If we now draw $n$ marbles from the bag without replacement, what is the probability distribution of the green marbles?

With some thinking, it should be easy to easy that this is exactly what we have interms of $X$ (number of marbles painted green) and $Y$ (number of green marbles drawn) above. I posted this on reddit of which one particular reasoning was way better than mine which I give here.

If we don't know $X$, it is as good as saying that the colored marbles are wrapped in an opaque cover before being put in the bag. Therefore, the drawn marbles are no different from each other and unwrapping them after being drawn, we would find a marble to be green with probability $p$ and red otherwise. Therefore,

$Y \sim \text{Bin}(n,p)$

Notice that $N$ disappears and contributes nothing to the unconditional distribution. This result holds even if we replace the $\text{Bin}$ distribution with a $\text{Beta-Bin}$ distribution.

We now get back to our original problem. Knowing $X_2|K-X_1$ and $K-X_1|X_1$, we can immediately see that $X_2|X_1$ is Beta-binomially distributed. Therefore,

$X_2|X_1 \sim \text{Beta-Bin}(n_2,\alpha+X_1,\beta+n_1-X_1)$

If, for example, we started with an Urn of $N$ balls (in which some are white and some are black) and drew $n$ balls without replacement and found all of them to be white, then

$X_2|X_1=n \sim \text{Beta-Bin}(n_2,1+n,1)$

If the size of the second sample is 1, then this clearly shows that

$\displaystyle \mathbb{E}(X_2|X_1)=\frac{n+1}{n+2}$

Very surprisingly, this is exactly the same answer we would get even if we had made the draws with replacement (which is exactly the Sunrise problem)!!

We have so far generalized the Birthday problem, the Coupon collector problem and the problem of points in our blog and in every case, the 'finiteness' of the population alters the final result in one way or the other. Even in this case, at the onset, I doubt that very few would feel that the probability would remain unchanged in the finite case.

Until then
Yours Aye
Me

Expected number of cards drawing two Aces in a row

Let's say we shuffle a standard 52-card deck and draw cards one by one looking for.consecutive cards that form a pair (two cards with the same rank).

I was interested in this question after seeing this StackExchange post. Though the post does not offer an exact solution, the approximate solution given there was really interesting. When I solved the question finding the exact solution, I was really surprised by how good the approximation is.

In this post, we will solving a similar question both exactly and approximately. We are interested in the expected number of draws without replacement before drawing two Aces in a row.

Just to be clear, there may be cases we exhaust all the cards without finding two Aces in a row. In these cases, the number of cards drawn will obviously be 52.

Let $N$ be the random variable indicating the number of draws and we want $\mathbb{E}(N)$.

To solve this in exact form, we first need the probability of drawing $j$ Aces when drawing $k$ cards from the deck such that the Aces are not together. Let's denote this event by $T_{j,k}$. Then it is easy to see that,

$\displaystyle\mathbb{P}(T_{j,k})=\mathbb{P}(j\text{ Aces in }k\text{ draws})\mathbb{P}(\text{Aces are not consecutive})$

The first term is textbook Hypergeometric. For the second term, we lay the $k-j$ non-Ace cards giving us $k-j+1$ spaces between them. We simply have to $j$ spaces out of these for the Aces. Therefore,

$\displaystyle\mathbb{P}(T_{j,k})=\frac{\binom{4}{j}\binom{48}{k-j}}{\binom{52}{k}}\cdot \frac{\binom{k-j+1}{j}}{\binom{k}{j}}$

Therefore, the probability that $N>k$ i.e. we have no consecutive Aces from a set of $k$ cards drawn from the deck is

$\displaystyle\mathbb{P}(N>k)=\sum_{j=0}^4\mathbb{P}(T_{j,k})$

Note that $N$ can only take values between $0$ and $52$ (both inclusive). Therefore,

$\displaystyle\mathbb{E}(N)=\sum_{k=0}^{51}\mathbb{P}(N>k)=\sum_{k=0}^{51}\sum_{j=0}^4\mathbb{P}(T_{j,k})$

Solving this with Wolfram Alpha instantly gives us

$\displaystyle\mathbb{E}(N)=\frac{257026}{5525}\approx 46.5205$

The simplified fraction kind of hints that there may be a more direct way of solving this. I'll update if I find something on this.

To solve this approximately, note that $\mathbb{P}(N>0)=\mathbb{P}(N>1)=1$. Also,

$\displaystyle \mathbb{P}(N>2)=\mathbb{P}(\text{first two cards are not consecutive Aces})=1-\mathbb{P}(\text{first two cards are Aces})=1-\frac{4}{52}\frac{3}{51}=\frac{220}{221}$

Now comes the approximation. On each subsequent draws, we assume that the probability that the current and the previous draw does not form two consecutive Aces is still $220/221$ and that each of these draws are independent. Therefore,

$\displaystyle \mathbb{P}(N>k)\approx\left(\frac{220}{221}\right)^{k-1}$ for $k>0$

This gives

$\displaystyle\mathbb{E}(N)=\mathbb{P}(N>0)+\sum_{k=1}^{51}\mathbb{P}(N>k)\approx 1+\sum_{k=1}^{51}\left(\frac{220}{221}\right)^{k-1}\approx 46.6350$

That's already a great approximation deviating from the correct value by less than quarter of a percentage.

If we further use a exponential approximation (which can also be obtained directly using a Poisson approximation), we have

$\displaystyle \mathbb{E}(N)\approx 1+51\frac{1-e^{-51\cdot 1/221}}{51\cdot 1/221}\approx 46.5431$

That's an insane level of accuracy!!

The following Mathematica code is used for this post.

Clear["Global`*"];

ProbG[k_] := Sum[Binomial[k - j + 1, j] / Binomial[k, j] * Binomial[4, j] Binomial[48, k - j] / Binomial[52, k], {j, 0, Min[4, k]}];

res = Sum[ProbG[k], {k, 0, 51}];

N[res, 15]

lam = 51 * Binomial[4, 2] / Binomial[52, 2];

approx = 1 + 51 * (1 - Exp[-lam]) / lam;

N[approx, 15]

p = Binomial[4, 2] / Binomial[52, 2];

approx = 1 + (1 - Power[1 - p, 51]) / p;

N[approx, 15]

The following code is the simulation for the problem.

Clear["Global`*"];

n = 10000000;

res = 0;

Do[

    test = Split[Mod[RandomSample[Range[0, 51]], 13]];

    Do[

        If[Length[k] <= 1,

            res += 1;,

            If[First[k] > 0, res += Length[k];, res += 2; Break[];];

        ];

    ,{k, test}

    ];

, {j, n}

];

res / n

N[%]

Until then
Yours Aye
Me

Factorial moments of the Binomial and related distributions

Factorial moments are defined as the expected value of the falling factorial of a random variable. In this post, we are going to try to compute the (scaled) Factorial moments of certain distributions without a direct computation.

The Factorial moment of a random variable $X$ is given by

$$\mathbb{E}[(X)_r]=\mathbb{E}[X(X-1)(X-2)\cdots (X-r+1)]$$

For our purposes, we focussing on the following definition which differs from the above only by a constant factor.

$$\displaystyle\mathbb{E}\left[\binom{X}{r}\right]=\mathbb{E}\left[\frac{(X)_r}{r!}\right]$$

Let's start with the famous Binomial distribution. The Binomial random variable $X$, with parameters $n$ and $p$, is the number of successes in a sequence of $n$ independent draws (with replacement), each with a success probability $p$.

Taking a cue from Problem of 7 of Strategic Practice 8 of Stat 110, $\binom{X}{k}$ denotes the set of draws where all the draws in the set result in a success. Creating an Indicator random variable for each set and using the linearity of expectations, we have

$$\displaystyle\mathbb{E}\left[\binom{X}{k}\right]=\binom{n}{k}\cdot p^k$$

We now move on to the Hypergeometric distribution (which is exactly the Stat 110 problem quoted above). Let $X$ denote the number of white balls from an Urn containing $N$ balls of which $K$ are white in a sample of $n$ draws. This is exactly the same problem given in Stat 110 quoted above.

$$\displaystyle\mathbb{E}\left[\binom{X}{k}\right]=\binom{n}{k}\cdot \frac{\binom{K}{k}}{\binom{N}{k}}$$

That is, we've considered an Indicator random variable for each $k$-set of draws and used the Linearity of Expectation. Note that $X$ is the number of successes where a 'success' is viewed as draw that gives a white ball.

Alternately, we can view a 'success' as a white ball that gets drawn. This way, we can solve the problem by considering an Indicator random variable for each $k$-set of white balls. Then,

$$\displaystyle\mathbb{E}\left[\binom{X}{k}\right]=\binom{K}{k}\cdot \frac{\binom{k}{k}\binom{N-k}{n-k}}{\binom{N}{n}}$$

Again, using the Linearity of Expectation, we restrict our attention to only a particular $k$-set of white balls. The probability that we are interested is that this particular set gets drawn when drawing $n$ balls. This is again a Hypergeometric distribution where only this particular set constitute 'successes' and rest are considered failures.

We now get to the Negative Binomial distribution with parameter $p$ and $j$ where $X$ denotes the number of failures we encounter before the $r$'th success. It can be verified with direct calculation that

$$\displaystyle\mathbb{E}\left[\binom{X}{k}\right]=\binom{k+r-1}{k}\left(\frac{q}{p}\right)^k$$

While the calculation is itself is not hard, I could not get a nice 'story' proof for the above. Rather we come back to this problem after the next case.

We now move to the Negative Hypergeometric distribution which will be most interesting aspect of this post. Here, again in the context of Urn and balls, $X$ denotes the number of black balls (failures) we get before the $r$'th white ball (success) from a population of $N$ balls in which $K$ are white.

Here again, $\binom{X}{k}$ denotes the $k$-set of draws that are black balls (failures) that gets drawn before the $r$'th white ball (success). Let $I_j,j \in \{1,2,\cdots,N-K\}$ be $1$ if the $j$th black ball (failure) gets drawn before the $r$'th white ball (success) and $0$ otherwise. Let the indicator random variable $I_S$ be the product of all the indicator random variable in the set $S$. Then,

$\displaystyle\mathbb{E}\left[\binom{X}{k}\right] =\sum_{S_k \subset \{1,2,\cdots,N-K\}}\mathbb{E}(I_{S_k})=\binom{N-K}{k}\mathbb{E}(I_1I_2\cdots I_k)=\binom{N-K}{k}\mathbb{P}(E)$

where $S_k$ denotes a $k$-element subset and $E$ denotes the event that failures $1$ to $k$ occur before the $r$'th success.

In other words, the probability that we want is the probability that we draw (without replacement) $k$ specific black balls from a bag containing $K$ white balls and $N-K$ black balls before the $r$'th white ball. This is a nice question by itself.

The key is to realise that we are concerned only about the $k$ specific black balls. This means we can completely ignore the remaining $N-K-k$ black balls and focus only on the $K$ white balls and the specific $k$ black balls.

The probability that we want is then the probability of getting $k$ black balls before the $r$'th white ball from an Urn containing $K+k$ balls of which $K$ are white. But that is exactly Negative Hypergeometric. Therefore,

$\displaystyle \mathbb{E}\left[\binom{X}{k}\right]=\binom{N-K}{k}\binom{k+r-1}{k}\frac{\binom{K+k-k-r}{K-r}}{\binom{K+k}{K}}=\binom{k+r-1}{k}\frac{\binom{N-K}{k}}{\binom{K+k}{k}}$

Alternately, the required probability can be seen as the probability of drawing $k$ black balls and $j-1$ white balls from an Urn containing $K+k$ balls of which $K$ are white. Then,

$\displaystyle \mathbb{E}\left[\binom{X}{k}\right]=\binom{N-K}{k}\frac{\binom{k}{k}\binom{K}{r-1}}{\binom{k+K}{k+r-1}}=\binom{N-K}{k}\frac{\binom{K}{r-1}}{\binom{k+K}{k+r-1}}$

Now we get back to the Negative Binomial case. Though I can't get a nice story proof for it, we can note that the first expression of the Negative Hypergeometric can be alternatively written as

$\displaystyle \mathbb{E}\left[\binom{X}{k}\right]=\binom{k+r-1}{k}\frac{\binom{N}{K+k}}{\binom{N}{K}}$

Using the asymptotic expression we derived in an earlier post, we can see that it matches with the result that we got from a direct calculation.

Hope you enjoyed the discussion. See ya in the next post.

Until then
Yours Aye
Me