Gaps between cards after a random shuffle

This post is more of a continuation of Probability on a standard deck of cards. I was randomly thinking about some probability problems when I came across The probability of cards meeting after a shuffle. The author of this paper discusses about two problems both of which is solved by simulation. This post aims at giving explicit closed form solutions to both of the said problems.

The first problem deals with the probability of finding cards with the same rank adjacent to other after a random shuffle.

Before I could even give it a thought, I just remembered the connection between this problem and AMBALLS problem in CodeChef. The following Mathematica code based on the tutorial immediately confirms the author's simulation results.

Clear["Global`*"];

(* https://discuss.codechef.com/t/amballs-editorial/1953 *)

n = 13; m = 4;

vals[x_, y_] := 0;

vals[0, 0] = 1;

Do[

    Do[

        Do[

            If[vals[x - 1, y] > 0,

                Do[

                    i = ij - j;

                    z = 1 + 4 (x - 1) - y;

                    vals[x, y - j + m - ij] += vals[x - 1, y] Binomial[y, j] Binomial[z, i] Binomial[m - 1, ij - 1];

                , {j, 0, Min[ij, y]}

                ];

            ];

        , {y, 0, 1 + 4 (x - 1)}

        ];

    , {ij, 0, m}

    ];

, {x, n}

];

vals[n, 0] * Power[Factorial[m], 13] / Factorial[m n]

N[%]

1 - %

I searched for a few other answers for a same question when I found this stack exchange post. The generating function result in the SE post took me by surprise.

Based on the post, we can see that when we have $c_j$ balls of color $j$ encoded in array $\mathbf{c}=(c_1,c_2,c_3,\cdots)$, then the number of ways $W(\mathbf{c})$ of arranging the balls linearly such that no two balls same of the same color are adjacent to each other is given by

$\displaystyle W(\mathbf{c})=\sum_{k_1=1}^{c_1} \sum_{k_2=1}^{c_2}\cdots (-1)^{c-k}\binom{k}{\mathbf{k}}\prod_i \binom{c_i-1}{k_i-1}$

where $\mathbf{k}=(k_1,k_2,k_3,\cdots)$, $k = k_1+k_2+\cdots$, $c=c_1+c_2+\cdots$ and $\binom{k}{\mathbf{k}}$ is the multinomial coefficient.

This gives us a closed form solution. I don't understand the reasoning behind the Generating function approach yet and that will be a subject of a post later. In any case, all these approaches confirm that the probability is about $94.45\%$.

We now come to the second problem of finding the probability that the Kings and Queens are separated by more than one card after a random shuffle. The author (possibly via simulations) suspects that the complementary probability is above 70% without giving a final result.

This question seemed very interesting to me and I couldn't find a clear idea with a casual Google search. Anyway, stripping the problem of labels, this questions boils down to counting the number of words with alphabets $\{a,b,c\}$ such that the $a$'s and $b$'s are atleast two $c$'s apart.

After trying multiple approaches, I realized that the best way to solve this problem is to first solve the following sub-problem: Find the number of words that can be formed with $a$ and $b$ such that we have $k$ change of 'runs'.

For example $aabbb$ has one change of run whereas both $baba$ and $aaabbbbaabbb$ both has three change of runs.

Fortunately, this can be easily solved with Generating functions. Let $\mathcal{G}$ be the language of such words. Then, it is easy to see that

$\displaystyle \mathcal{G}=\mathcal{W}_{a,b}+\mathcal{W}_{b,a}$

where $\displaystyle \mathcal{W}_{a,b}=\mathrm{SEQ}_{\geq 1}(a)\cdot \mathrm{SEQ}(t\mathrm{SEQ}_{\geq 1}(b)t\mathrm{SEQ}_{\geq 1}(a))\cdot(1+t\mathrm{SEQ}_{\geq 1}(b))$

Therefore, the generating function is given by

$\displaystyle G(a,b)=\frac{a+b+2ab-2abt}{1-a-b+ab-abt^2}$

Now $g(m,n,k)=[a^mb^nt^k]G(a,b)$ gives the number of words having $m$ a's, $n$ b's and $k$ change of runs. Note that the special case of $m=n$ is given in A152659.

But the approach above is not easily generalizable. A better way is to use the idea of Smirnov words which counts the number of words in which no adjacent letters are the same. The generating function of Smirnov words is given by

$\displaystyle S(v_1,v_2,v_3,\cdots)=\left(1- \sum_i \frac{v_i}{1+v_i}\right)^{-1}$

If we take a non-empty Smirnov word and use the substitution $v_i \mapsto t v_i/(1-v_i)$, we get the generating function we need with one extra $t$ (which counts the zeroth run). Therefore, we have

$\displaystyle G(v_1,v_2,v_3,\cdots,t)=\sum_i \frac{v_i}{1-v_i+tv_i}\cdot\left(1-t\sum_i \frac{v_i}{1-v_i+tv_i}\right)^{-1}$

We can use the above to solve our problem in greater generality. Let's $g_p(m,n,r)$ be the number of words with $m$ a's, $n$ b's and $r$ c's such that there are atleast $p$ c's between the a's and b's. Then,

$\displaystyle g_p(m,n,r)=\sum_{k=1}^{m+n-1}g(m,n,k)\binom{r-pk+m+n+1-1}{m+n+1-1}=\sum_{k=1}^{m+n-1}g(m,n,k)\binom{r-pk+m+n}{m+n}$

That is, we first arrange the a's and b's such that there are $k$ change of runs. In each of these $k$ changes, we insert $p$ c's. We then have '$r-pk$' c's which we insert in the available $m+n+1$ spaces between the a's and b's.

Therefore,

$\displaystyle \mathbb{P}(\text{Ks and Qs separated by atleast two cards})=\frac{g_2(4,4,44)4!4!44!}{52!}\approx 26.4\%$

This approach also answer's our question from the previous post. We have,

$\displaystyle \mathbb{P}(\text{No Ks and Qs adjacent})=\frac{g_1(4,4,44)4!4!44!}{52!}\approx 51.37\%$

The following Mathematica code was used to calculate the above values.

Clear["Global`*"];

f[a_, b_] := a / (1 - a) (1 + t b / (1 - b)) / (1 - t b / (1 - b) * t a / (1 - a));

g = f[a, b] + f[b, a];

k = 4; q = 4; c = 44;

(* SeriesCoefficient[g, {a, 0, k}, {b, 0, q}, {t, 0, c}] *)

Ways[m0_, n0_, t0_] := Ways[m0, n0, t0] = Module[{m = m0, n = n0, t = t0},

    If[t <= 0, Return[Boole[Xor[m <= 0, n <= 0]]];];

    If[t <= 1, Return[2 Boole[And[m > 0, n > 0]]];];

    If[Or[m <= 0, n <= 0], Return[0];];

    Ways[m - 1, n, t] + Ways[m, n - 1, t] - Ways[m - 1, n - 1, t] + Ways[m - 1, n - 1, t - 2]

];

Sum[Ways[k, q, j] Binomial[c - 2 * j + k + q, k + q], {j, k + q - 1}]

% * Factorial[4] * Factorial[4] * Factorial[44] / Factorial[52]

N[%]

1 - %

Sum[Binomial[44 + 1, m] Binomial[4 - 1, m - 1] Binomial[4 + 44 - m, 4], {m, 4}]

% * Factorial[4] * Factorial[4] * Factorial[44] / Factorial[52]

N[%]

1 - %

Clear["Global`*"];

Factor[(a / (1 - a + a t) + b / (1 - b + b t)) / (1 - t (a / (1 - a + a t) + b / (1 - b + b t)))]

Finally, a more direct generating function would be the following.

$\displaystyle G^*(v_1,v_2,\cdots,c)=\frac{1}{1-c}\cdot G\left(\frac{v_1}{1-c},\frac{v_2}{1-c},\cdots,c^p\right)$

Clear["Global`*"];

f = a / (1 - c - a + a c c) + b / (1 - c - b + b c c);

f = f / (1 - c c f) / (1 - c);

SeriesCoefficient[f, {a, 0, 4}, {b, 0, 4}, {c, 0, 44}]

Until then
Yours Aye
Me

Tangent-Asymptote triangle of a Hyperbola, Part 1

While exploring a different area of math, I came across the fact that a tangential segment of a hyperbola between the asymptotes is bisected at the tangent point.

Several attempts and internet searches later, I realised that this was already known to Apollonius of Perga. Reading the Conics, it became clear Apollonius proves this through a series of propositions.

While it was a great read, I was a little disappointed at the length of the proof and wanted to find a shorter one. The content of this post consequently is the proof that I found in this regard.

Consider the hyperbola $y^2-x^2=1$. Take any point $B$ on the upper branch and draw a tangent at that point. Draw a line parallel to the tangent such that it cuts upper branch of the hyperbola at two points as shown in the following figure. We show that the midpoint of $DE$ coincides with that of $FG$.

Figure 1

The idea of the proof is to use the third dimension as well. We know that the hyperbola is the intersection curve of a cone and a perpendicular plane. 

Figure 2

If we now consider the line through $EF$ as a plane in the above figure cutting the cone, giving an ellipse as shown in the following figure. Note that this ellipse also cuts the hyperbola.

Figure 3

Looking from the $x$-axis, this arrangement would look like the following figure.

Figure 4

Looking through the line perpendicular to the plane containing the ellipse, it is clear that the tangent segment caught between the asymptotes is the major of the ellipse and the segment caught between the hyperbola is a chord parallel to the major axis of the ellipse. It is clear then that the midpoints of both the segments will lie on the minor axis.

Figure 5

But looking through the line perpendicular to the plane containing the hyperbola, the minor axis is just a point proving that the midpoint of both the segments coincide.

Moving back to 2D, this property is true for all the line cutting the hyperbola. In the limiting case of a tangent line to the hyperbola, the segment caught between the hyperbola collapses to a point which is its own midpoint and therefore the midpoint of the tangential segment caught between the asymptotes.

This is very nice as we can use it give a geometric proof of $x^{-1}$ which I wasn't able to find even after an extensive internet search.

Note that Apollonius showed something more. He also proved for a given tangent, the midpoints of all the chords parallel to the tangent lie on a straight line passing through the center of the hyperbola and too for all the conics. Truly spectacular!

Until then
Yours Aye
Me

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