Student Puzzle editor Anirban DasGupta returns with three problems, over diverse topics. He says, “You can send a solution to just one, but we would be delighted if you send more! We hope you will enjoy thinking about the different things in these problems.”

The deadline for solutions is November 1, 2025: email bulletin@imstat.org with the subject “Student Puzzle Corner”.

Puzzle 58.1
Let $\bf{Y}$ be a two dimensional multivariate normal with the mean vector equal to $(0, 0)$ and covariance matrix given by \[ \sigma_{ij} = (2-|i-j|)^2. \]
(a) Find explicitly the set of all constants $a, b$ such that $aY_1^2+bY_2^2$ has a chi-square distribution.

(b) Find explicitly the set of all constants $a, b$ such that $aY_1^2+bY_2^2$ and $Y_1^2+Y_2^2$ are independent.

Puzzle 58.2
A fair coin is tossed $n$ times. Suppose $X$ heads are obtained. Given $X = x$, let $Y$ be generated according to the Poisson distribution with mean $x$. Find the unconditional variance of $Y$, and then find the limit of the probability
$P(|Y-\frac{n}{2}| > n^{\frac{3}{4}})$, as $n \rightarrow \infty $.

Puzzle 58.3
Consider an Erdős–Rényi random graph $G(n, p)$ with parameters $n$ and $p$. For every given $n$, let $p = \frac{c}{n}$, where $c > 0$ is a fixed constant.

(a) Find the limit as $n \to \infty $ of the expected number of triangles in $G(n,p)$.

(b) Find the limit as $n \to \infty $ of the variance of the number of triangles in $G(n,p)$.

(c) Does the number of triangles in $G(n,p)$ have a nondegenerate limiting distribution? If it does, identify that limiting distribution.

Solution to Puzzle 57

Guest puzzle-setters Stanislav Volkov and Magnus Wiktorsson explain their puzzle:

An easy calculation shows that
$$
E_{n,p} = \sum_{j = 0}^{n-1} \mathbb{P}(\text{Player 1 wins with Player 2 at } j) \cdot (n – j)
– \sum_{i = 0}^{n-1} \mathbb{P} (\text{Player 2 wins with Player 1 at } i) \cdot (n – i)
$$
To reach $n$ wins for one player before the other, the game must last $n + k – 1$ rounds, and the winner must win the last round. The probability that the winning player whose probability of winning is $\theta$ reaches $n$ wins while the other Player 2 has exactly $k$ wins is:
$$
h(\theta,k) = \binom{n + k – 1}{k} \cdot \theta^n \cdot (1 – \theta)^k,
$$
where $\theta=p,1-p$. Then the expected net profit is:
\begin{align*}
E_{n,p} &= \sum_{k=0}^{n-1}(n – k)h(p,k)
– \sum_{k=0}^{n-1}(n – k)h(q,k)
= \sum_{k=0}^{n-1} \binom{n + k – 1}{k} \left( p^n q^k-q^n p^k \right)(n – k)
\\ &=
\sum_{k=0}^{n-1} \binom{n + k – 1}{k} (pq)^{k}\left( p^{n-k}-q^{n-k} \right)(n – k)
=
(p-q)\sum_{k=0}^{n-1} \binom{n + k – 1}{k} (n – k)(pq)^{n}A_{n-k}
\end{align*}
where $A_m=\frac{p^m-q^m}{p-q}$. Then for $m=1,2,\dots$, noting that $p+q=1$,
$$
A_m=\sum_{i=0}^{\lfloor\frac{m-1}2\rfloor}\binom{m-1-i}{i}(-z)^i,\quad z=pq
$$
(this can be shown by induction as $A_{m+2}=A_{m+1}-zA_m$, and $A_1=A_2=1$).
Hence, with $z=pq$,
\begin{align*}
\frac{E_{n,p}}{p-q}
&=\sum_{k=0}^{n-1} \binom{n+k-1}{k} (n – k)z^k
\sum_{i=0}^{\lfloor\frac{n-k-1}2\rfloor}\binom{n-k-1-i}{i}(-z)^i
\\ &=
\sum_{k=0}^{n-1} \binom{n-1+k}k(n- k)
\sum_{j=k}^{\lfloor\frac{n+k-1}2\rfloor}z^j\binom{n-1-j}{j-k}(-1)^{j-k}
\\ &=
\sum_{j=0}^{n-1} (-1)^j z^j
\sum_{k=0}^{j}\binom{n-1+k}k \binom{n-1-j}{j-k}(-1)^{k}
(n – k)
\end{align*}
using the change of order of summation.
Now,
\begin{align}\label{main}
\sum_{k=0}^{j}\binom{n-1+k}k \binom{n-1-j}{j-k}(-1)^{k}
(n-k)=\frac{(-1)^j\ n}{j+1}\binom{2j}{j}=(-1)^j\ n\ C_j
\end{align}
where $C_j$ are Catalan numbers with the generator function
$$
c(z)=\sum_{j=0}^\infty C_j z^j=\frac{1-\sqrt{1-4z}}{2z}
=1+z+2z^2+5z^3+14z^4+42z^5+132z^6+\dots
$$
Hence
$$
E_{n,p}=n(p-q)\,\sum_{j=0}^{n-1} C_j z^j
\qquad\text{where }z=pq.
$$