Anirban DasGupta says, “We are continuing with our contest model as in the previous puzzles. Each correct answer receives 3 points, each incorrect answer receives -2 points, and each item left unanswered receives -1 point. The top three scorers will be recognized. You can answer just one of the two problems, 52.1 and 52.2, although it will be a pleasure if you attempt both components. The non-contest problem (52.1) is really simple this time, so send your answer to at least that one!” The deadline is September 15, 2024.

Puzzle 52.1
For $n \geq 2$, let $\sigma $ denote a permutation of $\{1, 2, \cdots , n\}$. Call a pair $(i,j)$ a reversal pair of $\sigma $ if $i < j, \sigma (i) > \sigma (j)$. Denote by $I(\sigma )$ the set of all reversal pairs of $\sigma $, and by $T(\sigma )$ the cardinality of $I(\sigma )$. Find the expected value of $T(\sigma )$ if $\sigma $ is chosen uniformly at random from the set of $n!$ permutations of $\{1, 2, \cdots , n\}$.

Puzzle 52.2: For our contest problem, answer True or False, without the need to provide a proof. But reasoned answers are especially welcome. Here are the items.
(a) If $X \sim N_d(\bf{\mu }, I)$, then the only function $h(X)$ such that $E_{\bf{\mu }}\,(h(X)) = h(\bf{\mu })$ for all $\bf{\mu }$ is $h(X) = X$.

(b) There exist real valued nonconstant random variables $X, Y$ such that $X, Y$ are independent, and $\frac{X}{Y}$ and $XY$ have the same distribution.

(c) Suppose $G$ is a graph on $n$ vertices and $m$ edges. A coloring of $G$ is an assignment of colors to the vertices of $G$ in such a way that no two vertices that share an edge receive the same color. Fix an integer $x$ and denote by $P_G(x)$ the number of ways to color $G$ by using exactly $x$ colors. View $P_G(x)$ as a polynomial in a real variable $x$ (you can). Then the sum of all the roots of $P_G(x)$, counting possible complex roots, does not depend on $n$.

(d) If $X$ is a real valued random variable with (finite) variance $\sigma ^2$ and a median $\xi $ (any median), then $|E(X) – \xi | \leq \sigma $.

(e) Suppose $(X_1, X_2, \cdots , X_{100})$ is distributed uniformly on the boundary of the unit ball in $100$ dimensions. Then the joint distribution of the first $10$ coordinates, $(X_1, X_2, \cdots , X_{10})$ can be approximated by a suitable $10$-dimensional normal distribution with a diagonal covariance matrix.

Solution to Puzzle 51

Well done (again!) to Deborshi Das, ISI Delhi, for his correct solution to the first puzzle. You’ll find a reminder of Puzzles 51.1 and 51.2 (plus the bonus puzzle, which was for independent exploration) here.
Puzzle editor Anirban DasGupta explains:

Puzzle 51.1
The diameter of the inscribed ball is $|r|$, and so the volume is $E[(|r|/2)^d]\,v_d$, where $v_d = \frac{\pi ^{d/2}}{\Gamma(\frac{d}{2}+1)}$ is the volume of the unit ball in $d$ dimensions. This reduces the problem to the simple calculation of $E(|r|^d)$.

Puzzle 51.2
(a) The total variation distance between a binomial distribution with parameters $n = 50$ and $p = 0.01$ and the Poisson distribution with mean $0.5$ is no more than $0.01$.

This can be checked numerically. It is about $0.0046$. You can also show analytically that it is less than $0.005$ by using Le Cam’s lemma, that the variation distance is less than $n\,p^2$.

(b) If $X$ is a Cauchy distributed variable with a location parameter $\mu $, then there is no unbiased estimator $\delta (X)$ of $\mu $.

True. It is a known result in inference. Erich Lehmann’s estimation text is a good reference. If the sample size $n > 2$, then unbiased estimators do exist.

(c) If $T_m$ denotes a symmetric $t$ distributed variables on $m$ degrees of freedom, then one can write $T_1$ as $T_2 + W$ where $W$ is independent of $T_2$.

Consider the characteristic functions $u(t), v(t)$ of $T_1, T_2$. They are, respectively $e^{-|t|}$ and $\sqrt{2}\,|t|\,K_1(\sqrt{2\,|t|})$, where $K_1$ is the usual notation for a Bessel $K$-function. Then you can exhibit $t$ such that $\frac{u(t)}{v(t)} > 1$. So $\frac{u(t)}{v(t)}$ cannot be a characteristic function, which answers the question in the negative.

(d) If $\{S_n\}_{0}^\infty $ with $S_0 = 0$ stands for the simple symmetric random walk on the line, then there exist functions $f(S_n)$ such that $f$ is not one-one, but $\{f(S_n)\}_{0}^\infty $ is a Markov chain.

As a standard example, you can use $f(x) = |x|$. This answers the question in the affirmative.

(e) For $n$ iid observations from a univariate normal distribution with an unknown mean and a known variance of $1$, the $N(\bar{X}, 1)$ density is a minimax estimator of the true density among all normal density estimators under an $\ell_2$ loss.

An exact formula for the square of the $L_2$ risk of a general normal density estimator can be found on calculation. This can be maximized easily over the unknown mean. The maximum will not be attained; be careful. You can now see that the maximum risk is not minimized when the density estimator has variance $1$. These are of paradoxical nature to some extent. Should you estimate a known parameter? Is the answer ‘yes, sometimes’, or is there something wrong with our formulation of the problem as a decision theory problem? Think about it; talk to others around you.

(f) Given iid samples $X_1, \cdots , X_n$ from a $d$-dimensional normal distribution for general $n \geq 2, d \geq 2$, with a general mean vector and a general covariance matrix, the sample variance-covariance matrix can be written as $A_1 + A_2$ where $A_1, A_2$ are nonsingular matrices.

Actually, you can assert something much more general. Take a real matrix $A$ and consider its eigenvalues, including any complex eigenvalues. Then the moduli of the eigenvalues are bounded by some finite real $c$. Now consider a decomposition of the form $\frac{1}{2}\, (A+a\,I) + \frac{1}{2}\, (A-a\,I)$ where the real number $a$ is chosen to be sufficiently large.

Bonus Problem for Independent Exploration
A point in the plane is called a Gaussian position if its Cartesian coordinates $(X, Y)$ are iid standard normals. Consider a triangle $T$ with vertices chosen as independent Gaussian positions. Argue for or against the motion that we should predict that the slope of the Euler line of $T$ is zero.

The slope of the Euler line is going to have a density when $(X, Y)$ are iid standard normal. No formula for the density function of this slope is known, and it does not seem possible. Computing seems to show that the density of the slope has a unique global maximum at zero. So one could take the view that if we have to give a point predictor of the slope, we should say zero.