2
$\begingroup$

The question about throwing darts asked on the MathOverflow page Sacred Geometry of Chance was not well received, apparently because of "[t]oo much noise around the actual math", as stated in a well-received comment on the question. I thought that, nonetheless, the essence of the question concerns a certain nontrivial mathematical fact and therefore deserves a second chance, which I will try to give it here.

Stripped of the fancy dressing, the mentioned question becomes as follows:

Let $\mu$ denote the bivariate standard normal probability distribution. Let $D$ denote the disk of area $3$ centered at the origin. Let $\mathcal P$ denote the set of all partitions $P=(A_1,A_2,A_3)$ of $D$ into Borel-measurable sets such $|A_1|=|A_2|=|A_3|[=1]$, where $|\cdot|$ denotes the area. For each $P=(A_1,A_2,A_3)\in\mathcal P$, consider its "score" \begin{equation*} S(P):=\sum_{i=1}^3\,i\,\mu(A_i). \end{equation*} The problem is to minimize $S(P)$ over all $P\in\mathcal P$.

This question is answered below. Moreover, it should be clear from the answer that it is straightforward to generalize the result to any given natural number (in place of $3$) of the pieces of the partition, and also to general nonnegative densities -- not necessarily the bivariate standard normal one ("restricted" to $D$), and also score functions $\{1,\dots,n\}\ni i\mapsto g(i)$ other than the identity map $i\mapsto i$.

However, I could hardly believe that all this, or something quite like this, has not been already done. So, I would be glad to accept an answer with pointers to relevant existing literature.

$\endgroup$
2
  • $\begingroup$ One would guess that greedy is best: Let the (area $1$) set of highest possible measure (the central disk of that area) be $B_1$ and the (area $1$) set of lowest possible measure (an annulus including the boundary) be $B_3$ putting$B_2$ as the annulus between them. This would seem optimal (up to measure zero) for any decreasing density based on distance from the origin. And indeed, that is the answer below. $\endgroup$ Jul 12, 2018 at 2:06
  • $\begingroup$ @AaronMeyerowitz : Thank you for your comment. I think "greedy" may be the right term in search for possible references for such results. Have you seen the use of the Birkhoff--von Neumann theorem in similar settings? $\endgroup$ Jul 12, 2018 at 3:19

1 Answer 1

3
$\begingroup$

$\newcommand{\al}{\alpha} \newcommand{\be}{\beta} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\ep}{\varepsilon} \newcommand{\ga}{\gamma} \newcommand{\Ga}{\Gamma} \newcommand{\la}{\lambda} \newcommand{\si}{\sigma} \newcommand{\Si}{\Sigma} \newcommand{\thh}{\theta} \newcommand{\om}{\omega} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\F}{\mathcal{F}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\Var}{\operatorname{\mathsf Var}} \renewcommand{\P}{\operatorname{\mathsf P}} \newcommand{\ii}[1]{\operatorname{\mathsf I}\{#1\}} \newcommand{\eD}{\overset{\text{D}}\to} \newcommand{\D}{\overset{\text{D}}=} \newcommand{\ave}{\operatorname{\mathsf{ave}}}$

An optimal partition $Q=(B_1,B_2,B_3)$ is as follows: $B_j=\big(\sqrt\frac j3\,D\big)\setminus\big(\sqrt\frac{j-1}3\, D\big)$ for $j=1,2,3$. Moreover, the optimal partition is unique, up to sets of zero Lebesgue measure.

To begin proving these statements, note that the $B_j$'s are the annuli of area $1$ each centered at the origin, with the following property:

whenever $1\le j_1<j_2\le 3$ and $E_1$ and $E_2$ are Borel sets of nonzero Lebesgue measure such that $E_1\subseteq B_{j_1}$ and $E_2\subseteq B_{j_2}$, we have \begin{equation*} \ave_{E_1}f\ge\ave_{E_2}f, \tag{0} \end{equation*} where $f$ is the density of the bivariate standard normal probability distribution $\mu$ with respect to the Lebesgue measure and \begin{equation*} \ave_E f:=\frac{\mu(E)}{|E|}=\frac1{|E|}\int_E f(x)dx, \end{equation*} the average value of density $f$ over the set $E$.

Property (0) holds because $\inf_{B_{j_1}}f\ge \sup_{B_{j_2}} f$ if $1\le j_1<j_2\le 3$.

Take now any partition $P=(A_1,A_2,A_3)\in\mathcal P$ and let $C_{i,j}:=A_i\cap B_j$. The crucial observation is that the matrix $(|C_{i,j}|)_{i,j=1}^3$ is double stochastic, and so, by the Birkhoff--von Neumann theorem, \begin{equation*} |C_{i,j}|=\sum_{\pi\in\Pi}w_\pi \ii{j=\pi(i)} \end{equation*} for all $i,j$, where $\Pi$ is the set of all permutations of the set $\{1,2,3\}$, $\ii{\cdot}$ is the indicator function, and the $w_\pi$'s are some nonnegative real numbers such that $\sum_{\pi\in\Pi}w_\pi=1$. Therefore and because the Lebesgue measure has no atoms, for each triple $(i,j,\pi)$ there is a Borel set $C_{\pi;i,j}$ such that \begin{equation*} |C_{\pi;i,j}|=w_\pi \ii{j=\pi(i)} \tag{1} \end{equation*} and $(C_{\pi;i,j})_{\pi\in\Pi}$ is a partition of $C_{i,j}$ for each $(i,j)$.

Let now \begin{equation*} r_{\pi;i,j}:=\frac{\mu(C_{\pi;i,j})}{|C_{\pi;i,j}|}=\ave_{C_{\pi;i,j}} f \end{equation*} if $|C_{\pi;i,j}|\ne0$; otherwise, define $r_{\pi;i,j}$ arbitrarily, but so that one have \begin{equation} r_{\pi;i_1,j_1}\ge r_{\pi;i_2,j_2} \tag{2} \end{equation} whenever $1\le j_1<j_2\le 3$, for any $\pi,i_1,i_2$; this is possible to do because of the property highlighted above; for instance, one may let $r_{\pi;i,j}:=\sup_{B_j}f$ for all $\pi,i,j$ such that $|C_{\pi;i,j}|=0$.

Then
\begin{multline} S(P)=\sum_{i=1}^3\,i\,\mu(A_i) =\sum_{i,j=1}^3\,i\,\mu(C_{i,j}) =\sum_\pi\sum_{i,j}\,i\,\mu(C_{\pi;i,j}) =\sum_\pi\sum_{i,j}\,i\,r_{\pi;i,j}|C_{\pi;i,j}| \\ =\sum_\pi w_\pi\sum_i\,i\,r_{\pi;i,\pi(i)} =\sum_\pi w_\pi\sum_j\,\pi^{-1}(j)\,a_{\pi;j} \tag{3} \end{multline} by (1), where \begin{equation*} a_{\pi;j}:=r_{\pi;\pi^{-1}(j),j}. \tag{4} \end{equation*} Similarly, with $Q=(B_1,B_2,B_3)$ as before,
\begin{multline} S(Q)=\sum_{i=1}^3\,j\,\mu(B_j) =\sum_{i,j=1}^3\,j\,\mu(C_{i,j}) =\sum_\pi\sum_{i,j}\,j\,\mu(C_{\pi;i,j}) =\sum_\pi\sum_{i,j}\,j\,r_{\pi;i,j}|C_{\pi;i,j}| \\ =\sum_\pi w_\pi\sum_j\,j\,r_{\pi;\pi^{-1}(j),j} =\sum_\pi w_\pi\sum_j\,j\,a_{\pi;j}. \tag{5} \end{multline}

Fix now any $\pi\in\Pi$ and let $\si:=\pi^{-1}$, $a_j:=a_{\pi;j}$, and $h_i:=a_i-a_{i+1}$ (with $a_4:=0$). By (4) and (2), $h_i\ge0$ for all $i=1,2,3$. So, \begin{multline} \sum_j\,\pi^{-1}(j)\,a_{\pi;j}=\sum_j\,\si(j)\,a_j=\sum_{j=1}^3\,\si(j)\,\sum_{i=j}^3 h_i =\sum_{i=1}^3\,h_i\sum_{j=1}^i\si(j) \\ \ge\sum_{i=1}^3\,h_i\sum_{j=1}^i j =\sum_{j=1}^3\,j\,\sum_{i=j}^3 h_i =\sum_j\,j\,a_j=\sum_j\,j\,a_{\pi;j}. \end{multline}

So, by (3) and (5), $S(P)\ge S(Q)$, for any $P\in\mathcal P$. That is, the partition $Q$ is optimal. Following the lines of the above proof, we can see that the optimal partition is unique, up to sets of zero Lebesgue measure. This concludes the entire proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.