text:
\section{Proofs of propositions}
\label{Proofs of propositions}

In this appendix, we first present an auxiliary proposition mentioned in the main discussion, and then prove Propositions  \ref{Prop: Upper Bound on MI} and \ref{Prop: MSE Decomposition}.

\subsection{Auxiliary proposition}
\label{Proof of Prop Estimator Stochastic Matrix}

The ensuing proposition shows that the ``empirical stochastic matrix'' $S$ defined in \eqref{Eq: Stochastic Matrix Estimator} (and used in Algorithm \ref{Algorithm: Density Estimation}) is indeed row stochastic with high probability.

\begin{proposition}[Empirical Stochastic Matrix]
\label{Prop: Estimator Stochastic Matrix}
If $n \geq 2$ and $p \geq 16(c_1 + 1) \log(n) / (3 n)$ for any fixed (universal) constant $c_1 > 0$, then we have:
$$ \P\!\left(S \in \S_{n \times n}\right) \geq 1 - \frac{1}{n^{c_1}} \, . $$
\end{proposition}

\begin{proof}
First, define the random variables:
$$ \forall m \in [n], \enspace M_m \triangleq \sum_{r \in [n]\backslash\!\{m\}}{\I\!\left\{\{m,r\} \in \G(n,p)\right\}} $$
which count the numbers of outcomes of games observed for each player. Furthermore, define the event:
$$ A \triangleq \left\{\forall m \in [n], \, M_m \leq 2 (n-1) p \right\} . $$
Then, we can verify that $A \subseteq \{S \in \S_{n \times n}\}$. Indeed, if $A$ occurs, then we have:
\begin{align*}
& \forall m \in [n], \enspace \frac{1}{2 n p} \sum_{r \in [n]\backslash\!\{m\}}{\I\!\left\{\{m,r\} \in \G(n,p)\right\}} \leq \frac{M_m}{2 (n-1) p} \leq 1 \\
\Rightarrow \quad & \forall m \in [n], \enspace \frac{1}{2 n p} \sum_{r \in [n]\backslash\!\{m\}}{Z(m,r)} \leq 1 \\
\Leftrightarrow \quad & \forall m \in [n], \enspace S(m,m) \geq 0 \\
\Leftrightarrow \quad & S \in \S_{n \times n}
\end{align*}
where the second line follows from \eqref{Eq: Observation matrix}, and the third and fourth lines follow from \eqref{Eq: Stochastic Matrix Estimator}. Hence, it suffices to prove that $\P(A^{c}) \leq n^{-c_1}$. To this end, notice that:
\begin{align*}
\P\!\left(A^{c}\right) & = \P\!\left(\exists \, m \in [n], \, M_m > 2 (n-1)p \right) \\
& \leq n \, \P\!\left(\frac{1}{n-1} \sum_{r = 2}^{n}{\I\!\left\{\{1,r\} \in \G(n,p)\right\} - p} \geq p\right) \\
& \leq n \exp\!\left(-\frac{3 (n-1) p}{8}\right) \\
& \leq n \exp\!\left(-\frac{2 (c_1 + 1) (n-1) \log(n)}{n}\right) \\
& \leq \frac{1}{n^{c_1}}
\end{align*}
where the second inequality follows from the union bound and the fact that $\{M_m : m \in [n]\}$ are identically distributed random variables, the third inequality follows from \lemref{Lemma: Bernstein's Inequality} in Appendix \ref{App: Concentration of Measure Inequalities} since each indicator random variable $\I\{\{1,r\} \in \G(n,p)\}$ has mean $p$, variance $p(1-p) \leq p$, and satisfies $\big|\I\{\{1,r\} \in \G(n,p)\} - p\big| \leq 1$, the fourth inequality follows from our assumption that $p \geq 16(c_1 + 1) \log(n) / (3 n)$, and the fifth inequality holds because $n \geq 2$. This completes the proof.
\end{proof}

\subsection{Mutual information, covering numbers, and the proof of \propref{Prop: Upper Bound on MI}}
\label{App: Covering numbers}

The goal of this subsection is to establish the upper bound on $I(\pi;Z)$ in \propref{Prop: Upper Bound on MI}. To this end, we commence by presenting some basic definitions and properties of mutual information from information theory. Recall that for any two probability measures $\mu$ and $\nu$ over the same measurable space $(\Omega,\F)$, the KL divergence (or relative entropy) of $\nu$ from $\mu$ is defined as (cf. \cite[Definition 1.4]{PolyanskiyWu2017Notes}):
\begin{equation}
\label{Eq: KL definition}
D(\mu||\nu) \triangleq
\begin{cases}
\displaystyle{\int_{\Omega}{\log\!\left(\frac{\diff \mu}{\diff \nu}\right) \diff\mu}} \, , & \mu \text{ is absolutely continuous with respect to } \nu \\
+\infty \, , & \text{otherwise}
\end{cases}
\end{equation}
where $\frac{\diff \mu}{\diff \nu}$ is the Radon-Nikodym derivative (or density) of $\mu$ with respect to $\nu$. Using \eqref{Eq: KL definition}, for any pair of jointly distributed random variables $X$ and $Y$, we define the \emph{mutual information} between $X$ and $Y$ as (cf. \cite[Definition 2.3]{PolyanskiyWu2017Notes}):
\begin{equation}
\label{Eq: MI Def}
I(X;Y) \triangleq D(P_{X,Y}||P_X \otimes P_Y)
\end{equation}
where $P_{X,Y}$ denotes the joint probability law of $X$ and $Y$, and $P_X \otimes P_Y$ denotes the product measure of the corresponding marginal probability laws of $X$ and $Y$, respectively. Note that in \eqref{Eq: MI Def}, the random variables $X$ or $Y$ can be compound variables. So, for example, if $Y = (Y_1,Y_2)$, i.e., $Y$ is actually a pair of random variables $Y_1,Y_2$ (where $X,Y_1,Y_2$ are jointly distributed), then we can write $I(X;Y) = I(X;Y_1,Y_2)$. Furthermore, given three jointly distributed random variables $X,Y,W$, where $W \in \mathcal{W}$ is a discrete random variable whose probability distribution $P_W$ has support $\mathcal{W}$, we define the mutual information between $X$ and $Y$ given $W = w$ as:
\begin{equation}
\label{Eq: Cond MI Pre-Def}
\forall w \in \mathcal{W}, \enspace I(X;Y|W = w) \triangleq D(P_{X,Y|W = w}||P_{X|W = w} \otimes P_{Y|W = w})
\end{equation}
where $P_{X,Y|W = w}$ denotes the conditional (joint) probability law of $X$ and $Y$ given $W = w$, and $P_{X|W = w} \otimes P_{Y|W = w}$ denotes the product measure of the conditional (marginal) probability laws of $X$ and $Y$ given $W = w$, respectively. Then, using \eqref{Eq: Cond MI Pre-Def}, the \emph{conditional mutual information} between $X$ and $Y$ given $W$ is defined as (cf. \cite[Definition 2.4]{PolyanskiyWu2017Notes}):
\begin{equation}
\label{Eq: Cond MI Def}
I(X;Y|W) \triangleq \sum_{w \in \mathcal{W}}{P_W(w) I(X;Y|W = w)}
\end{equation}
which the expected value of $I(X;Y|W = w)$ with respect to $P_W$. We will utilize the following well-known properties of mutual information in the sequel.

\begin{lemma}[Properties of Mutual Information {\cite{PolyanskiyWu2017Notes,CoverThomas2006}}]
\label{Lemma: Properties of Mutual Information}
For any three jointly distributed random variables $X,Y,W$, the following results hold:
\begin{enumerate}
\item \emph{(Chain rule} \cite[Theorem 2.5]{PolyanskiyWu2017Notes}, \cite[Theorem 2.5.2]{CoverThomas2006}\emph{)} If $W \in \mathcal{W}$ is a discrete random variable whose probability distribution $P_W$ has support $\mathcal{W}$, then:
$$ I(X;Y,W) = I(X;W) + I(X;Y|W) \, . $$
\item \emph{(Data processing inequality} \cite[Theorem 2.5]{PolyanskiyWu2017Notes}, \cite[Theorem 2.8.1]{CoverThomas2006}\emph{)} If $X \rightarrow Y \rightarrow W$ forms a Markov chain, i.e., $X$ and $W$ are conditionally independent given $Y$, then:
$$ I(X;W) \leq I(Y;W) \, . $$
\end{enumerate}
\end{lemma}

Another set of ideas we will exploit to prove \propref{Prop: Upper Bound on MI} concerns a powerful and general approach to upper bound mutual information (or more generally, Shannon capacity, cf. \cite[Sections 4.4 and 4.5]{PolyanskiyWu2017Notes}, \cite[Chapter 7]{CoverThomas2006}) via covering arguments. While there are several variants of such arguments in the literature, in this paper, we will resort to the classical covering argument of \cite{YangBarron1999}. (We refer readers to \cite[Section 5]{ChenGuntuboyinaZhang2016} for generalizations of such covering arguments for a class of $f$-informativities \cite{Csiszar1972}.)

To present the technique in \cite{YangBarron1999}, let us condition on any fixed realization of the underlying Erd{\H o}s-R\'{e}nyi random graph $\G(n,p) = G$. Then, the partial observations $Z$, defined in \eqref{Eq: Observation matrix}, can be equivalently represented using the (compound) random variable:
\begin{equation}
\label{Eq: Compound rv}
Z_G \triangleq \left\{Z(i,j) : \{i,j\} \in G, \, i < j \right\}
\end{equation}
where the notation $\{i,j\} \in G$ shows that the undirected edge $\{i,j\}$ exists in the graph $G$, and each $Z(i,j) = \frac{1}{k}\sum_{m = 1}^{k}{Z_m(i,j)}$ given $\{i,j\} \in G$ (where the $Z_m(i,j)$'s are defined via \eqref{Eq: BT model}). Moreover, using \eqref{Eq: Compound rv}, we have the relation:
\begin{equation}
\label{Eq: Simplified MI Relation}
I(\alpha_1,\dots,\alpha_n;Z|\G(n,p) = G) = I(\alpha_1,\dots,\alpha_n;Z_G)
\end{equation}
where we use \eqref{Eq: Cond MI Pre-Def}, and the fact that the random variables $\alpha_1,\dots,\alpha_n,Z_G$ are independent of $\G(n,p)$. (Note that if $G$ contains no edges, then $Z_G$ is a deterministic quantity and $I(\alpha_1,\dots,\alpha_n;Z_G) = 0$.) Now consider the $n$-dimensional hypercube $[\delta,1]^n$ in which the skill parameter random variables $(\alpha_1,\dots,\alpha_n)$ take values. For any parameter vector (realization) $\beta = (\beta_1,\dots,\beta_n) \in [\delta,1]^n$, let $P_{Z_G|\beta}$ denote the conditional probability distribution of $Z_G$ given $\alpha_i = \beta_i$ for all $i \in [n]$ (with abuse of notation); see \eqref{Eq: BT model} and \eqref{Eq: Observation matrix}. Then, for any $\varepsilon > 0$, we define an \emph{$\varepsilon$-covering} of $[\delta,1]^n$ with finite cardinality $M \in \N$ to be a subset of parameter vectors $\big\{\beta^{(1)},\dots,\beta^{(M)}\big\} \subset [\delta,1]^n$ that satisfies:
\begin{equation}
\forall \beta \in [\delta,1]^n, \, \exists \, i \in [M], \enspace D\!\left(P_{Z_G|\beta}\big|\big| P_{Z_G|\beta^{(i)}}\right) \leq \varepsilon
\end{equation}
where we use KL divergence as our ``distance'' measure. Furthermore, for every $\varepsilon > 0$, we define the \emph{$\varepsilon$-covering number} as:
\begin{equation}
M^{*}(\varepsilon) \triangleq \min\!\left\{M \in \N : \exists \, \varepsilon\text{-covering of } [\delta,1]^n \text{ with cardinality } M \right\} .
\end{equation}
The next lemma distills the upper bound on mutual information via covering numbers presented in \cite[Equation (2), p.1571]{YangBarron1999}, and specializes it to our setting of \eqref{Eq: Simplified MI Relation}.

\begin{lemma}[Covering Number Bound {\cite[Lemma 16.1]{Wu2019}}]
\label{Lemma: Covering Number Bound}
Let $(\alpha_1,\dots,\alpha_n)$ be i.i.d. with
distribution $\pdf= \unif([\delta,1])$, and recall that the conditional probability distribution of $Z_G$
given $(\alpha_1,\dots,\alpha_n)$ is defined by \eqref{Eq: BT model} and
\eqref{Eq: Observation matrix}. Then, the mutual information between
$(\alpha_1,\dots,\alpha_n)$ and $Z_G$ is upper bounded by:
$$ I(\alpha_1,\dots,\alpha_n;Z_G) \leq \inf_{\varepsilon > 0}{\, \varepsilon + \log(M^{*}(\varepsilon))} \, . $$
\end{lemma}
Using Lemmata \ref{Lemma: Properties of Mutual Information} and \ref{Lemma: Covering Number Bound}, we can finally prove the upper bound on $I(\pi,Z)$ in \propref{Prop: Upper Bound on MI}.
\begin{proof}[Proof of \propref{Prop: Upper Bound on MI}]
First, notice that $\pi \rightarrow (\alpha_1,\dots,\alpha_n) \rightarrow Z$ forms a Markov chain, because $\pi$ is a deterministic function of $(\alpha_1,\dots,\alpha_n)$ (according to \eqref{Eq: Canonically scaled merit parameters}). Hence, by part 2 of \lemref{Lemma: Properties of Mutual Information}, we get:
\begin{equation}
\label{Eq: DPI Consequence 1}
I(\pi;Z) \leq I(\alpha_1,\dots,\alpha_n;Z) \, .
\end{equation}
Furthermore, notice that $Z \rightarrow (Z,\G(n,p)) \rightarrow (\alpha_1,\dots,\alpha_n)$ forms a Markov chain, because $Z$ is a deterministic (projection) function of $(Z,\G(n,p))$. Thus, by part 2 of \lemref{Lemma: Properties of Mutual Information}, we also get:
\begin{align}
I(\alpha_1,\dots,\alpha_n;Z) & \leq I(\alpha_1,\dots,\alpha_n;Z,\G(n,p)) \nonumber \\
& = I(\alpha_1,\dots,\alpha_n;\G(n,p)) + I(\alpha_1,\dots,\alpha_n;Z|\G(n,p)) \nonumber \\
& = I(\alpha_1,\dots,\alpha_n;Z|\G(n,p))
\label{Eq: DPI Consequence 2}
\end{align}
where the second equality utilizes part 1 of \lemref{Lemma: Properties of Mutual Information}, and the third equality holds because $(\alpha_1,\dots,\alpha_n)$ and $\G(n,p)$ are independent, which implies that $I(\alpha_1,\dots,\alpha_n;\G(n,p)) = 0$ (see \eqref{Eq: MI Def}). Combining \eqref{Eq: DPI Consequence 1} and \eqref{Eq: DPI Consequence 2}, we obtain:
\begin{equation}
\label{Eq: Intermediate MI Bound}
I(\pi;Z) \leq I(\alpha_1,\dots,\alpha_n;Z|\G(n,p)) \, .
\end{equation}
So, it suffices to upper bound the conditional mutual information $I(\alpha_1,\dots,\alpha_n;Z|\G(n,p))$.

To this end, we condition on any fixed realization of the underlying Erd{\H o}s-R\'{e}nyi random graph $\G(n,p) = G$ (as in the discussion preceding this proof), and proceed to establishing an upper bound on $I(\alpha_1,\dots,\alpha_n;Z_G)$ by employing \lemref{Lemma: Covering Number Bound}. Specifically, we next evaluate the right hand side of the inequality in \lemref{Lemma: Covering Number Bound} above for a judiciously chosen $\varepsilon$-covering of $[\delta,1]^n$. Fix any $q > 0$ (to be chosen later), and quantize the interval $[\delta,1]$ using the set of values:
$$ \Q \triangleq \left\{\delta + \frac{(1-\delta) m}{n^{q}} : m \in \big[\lfloor n^q \rfloor\big] \right\} $$
which has cardinality $|\Q| = \lfloor n^q \rfloor \leq n^q$, and satisfies the condition:
\begin{equation}
\label{Eq: Quantization}
\forall t \in [\delta,1], \enspace \min_{s \in \Q}{|t - s|} \leq \frac{1-\delta}{n^q}
\end{equation}
where the right hand side can be improved to $(1-\delta)/(2 n^q)$ when $t$ is not located at the edges of the interval $[\delta,1]$, and $\lfloor\cdot \rfloor$ denotes the floor function. The next claim shows that $\Q^n$ is actually an $\varepsilon$-covering of $[\delta,1]^n$ with $\varepsilon = O(n^{2-2q})$ (neglecting the dependence of $\varepsilon$ on $\delta$ and $k$).

\begin{claim}[$\varepsilon$-Covering]
\label{Claim: Covering}
$\Q^n$ is an $\varepsilon$-covering of $[\delta,1]^n$ with cardinality $|\Q^n| = (\lfloor n^q \rfloor)^n \leq n^{qn}$ and:
$$ \varepsilon = \frac{(1-\delta)^2}{4 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \frac{k |G|}{n^{2 q}} $$
where $|G|$ denotes the number of edges in the graph $G$ with abuse of notation. (Since $|G| \leq \frac{n(n-1)}{2}$, $\varepsilon = O(n^{2-2q})$.)
\end{claim}

\begin{proof}
The cardinality of $\Q^n$ follows since it is a product set. So, we focus on verifying the value of $\varepsilon$. Fix any parameter vector $\beta = (\beta_1,\dots,\beta_n) \in [\delta,1]^n$. Due to \eqref{Eq: Quantization}, we have that:
\begin{equation}
\label{Eq: Closeness of Parameters}
\forall i \in [n], \, \exists \gamma_i \in \Q, \enspace |\beta_i - \gamma_i| \leq \frac{1-\delta}{n^q} \, .
\end{equation}
Letting $\gamma = (\gamma_1,\dots,\gamma_n) \in \Q^n$, observe that:
\begin{align}
D\!\left(P_{Z_G|\beta} \big|\big| P_{Z_G|\gamma}\right) & = \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{D\big(P_{Z(i,j)|\beta,G} \big|\big| P_{Z(i,j)|\gamma,G}\big)} \nonumber \\
& = \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{\! \sum_{i = 0}^{k}{ \binom{k}{i} \! \left(\frac{\beta_j}{\beta_i + \beta_j}\right)^{\!\! i} \! \left(\frac{\beta_i}{\beta_i + \beta_j}\right)^{\!\! k-i} \!\log\!\left(\frac{\left(\frac{\beta_j}{\beta_i + \beta_j}\right)^{\! i} \! \left(\frac{\beta_i}{\beta_i + \beta_j}\right)^{\! k-i}}{\left(\frac{\gamma_j}{\gamma_i + \gamma_j}\right)^{\! i} \! \left(\frac{\gamma_i}{\gamma_i + \gamma_j}\right)^{\! k-i}}\right) } } \nonumber \\
& = \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}} \log\!\left(\frac{\left(\frac{\beta_j}{\beta_i + \beta_j}\right)}{\left(\frac{\gamma_j}{\gamma_i + \gamma_j}\right)}\right) \sum_{i = 0}^{k}{i \binom{k}{i} \! \left(\frac{\beta_j}{\beta_i + \beta_j}\right)^{\!\! i} \! \left(\frac{\beta_i}{\beta_i + \beta_j}\right)^{\!\! k-i}} \nonumber \\
& \qquad \qquad \quad \enspace \,\, + \log\!\left(\frac{\left(\frac{\beta_i}{\beta_i + \beta_j}\right)}{\left(\frac{\gamma_i}{\gamma_i + \gamma_j}\right)}\right) \sum_{i = 0}^{k}{(k - i) \binom{k}{i} \! \left(\frac{\beta_j}{\beta_i + \beta_j}\right)^{\!\! i} \! \left(\frac{\beta_i}{\beta_i + \beta_j}\right)^{\!\! k-i}} \nonumber \\
& = k \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{ \left(\frac{\beta_j}{\beta_i + \beta_j}\right) \log\!\left(\frac{\left(\frac{\beta_j}{\beta_i + \beta_j}\right)}{\left(\frac{\gamma_j}{\gamma_i + \gamma_j}\right)}\right) + \left(\frac{\beta_i}{\beta_i + \beta_j}\right) \log\!\left(\frac{\left(\frac{\beta_i}{\beta_i + \beta_j}\right)}{\left(\frac{\gamma_i}{\gamma_i + \gamma_j}\right)}\right)}  \nonumber \\
& = k \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{D\!\left(\frac{\beta_j}{\beta_i + \beta_j} \bigg|\bigg| \frac{\gamma_j}{\gamma_i + \gamma_j}\right)} \label{Eq: Tensorization} \\
& \leq k \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{\left(\frac{\beta_j}{\beta_i + \beta_j} - \frac{\gamma_j}{\gamma_i + \gamma_j}\right)^{\!2} \left( 2 + \frac{\gamma_i}{\gamma_j} + \frac{\gamma_j}{\gamma_i} \right)} \nonumber \\
& \leq k \left( 2 + \delta + \frac{1}{\delta}\right) \! \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{\! \left(\frac{\beta_j}{\beta_i + \beta_j} - \frac{\gamma_j}{\gamma_i + \gamma_j}\right)^{\!2}} \nonumber \\
& \leq k \left( 2 + \delta + \frac{1}{\delta}\right) \!\sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{\!\left(\left|\frac{\beta_j}{\beta_i + \beta_j} - \frac{\beta_j}{\gamma_i + \beta_j}\right| + \left|\frac{\beta_j}{\gamma_i + \beta_j} - \frac{\gamma_j}{\gamma_i + \gamma_j}\right|\right)^{\!2}} \nonumber \\
& \leq \frac{k}{16 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \! \sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{\!\left( \left|\beta_i - \gamma_i\right| + \left|\beta_j - \gamma_j\right|\right)^{2}} \nonumber \\
& \leq \frac{(1-\delta)^2}{4 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \frac{k |G|}{n^{2 q}} \nonumber \\
& = \varepsilon \nonumber
\end{align}
where the first equality uses \eqref{Eq: KL definition}, \eqref{Eq: Compound rv}, and the fact that the $Z(i,j)$'s in \eqref{Eq: Compound rv} are conditionally independent given the skill parameters and the random graph realization $G$, and $P_{Z(i,j)|\beta,G}$ denotes the conditional probability distribution of $Z(i,j)$ given $(\alpha_1,\dots,\alpha_n) = \beta$ and $\G(n,p) = G$, the second equality holds because each $k Z(i,j) = \sum_{m = 1}^{k}{Z_m(i,j)}$ has binomial distribution given $\{i,j\} \in G$ (as indicated earlier, where the $Z_m(i,j)$'s are defined via \eqref{Eq: BT model}), the fourth equality follows from applying the formula for expected values of binomial random variables, the fifth equality uses the binary KL divergence function, which is defined as $(0,1) \ni (a,b) \mapsto D(a||b) \triangleq a \log\!\big(\frac{a}{b}\big) + (1-a) \log\!\big(\frac{1-a}{1-b}\big)$, the sixth inequality follows from a simple upper bound on KL divergence in terms of $\chi^2$-divergence \cite{Su1995} (alternatively see, e.g., \cite[Equation (4), Lemma 3]{MakurZheng2020} and the references therein for a detailed exposition):
$$ \forall a,b \in (0,1), \enspace D(a||b) \leq \underbrace{\frac{(a-b)^2}{b} + \frac{(a-b)^2}{1-b}}_{\text{binary } \chi^2\text{-divergence}} = \frac{(a-b)^2}{b(1-b)} \, , $$
the seventh inequality holds because the function $g : \big[\delta,\frac{1}{\delta}\big] \rightarrow \R$, $g(t) = t + \frac{1}{t}$ is maximized at $g(\delta) = g\big(\frac{1}{\delta}\big) = \delta + \frac{1}{\delta}$ (where $\frac{\gamma_i}{\gamma_j} \in \big[\delta,\frac{1}{\delta}\big]$), the eighth inequality follows from the triangle inequality, the ninth inequality follows from the coordinate-wise Lipschitz continuity shown in \clmref{Claim: Coordinate-wise Lipschitz Continuity} below, and the tenth inequality follows from \eqref{Eq: Closeness of Parameters}. This establishes the claim.
\end{proof}

Before proceeding with the proof of \propref{Prop: Upper Bound on MI}, we quickly prove the coordinate-wise Lipschitz continuity claim used in the proof of \clmref{Claim: Covering} for completeness.

\begin{claim}[Coordinate-wise Lipschitz Continuity]
\label{Claim: Coordinate-wise Lipschitz Continuity}
Consider the map $F : [\delta,\infty)^2 \rightarrow (0,\infty)$:
$$ \forall x,y \geq \delta, \enspace F(x,y) \triangleq \frac{x}{x + y} $$
which is used to define the likelihoods of the BTL model in \eqref{Eq: BT model}. This map is coordinate-wise Lipschitz continuous:
\begin{enumerate}
\item For any fixed $x \in [\delta,\infty)$:
$$ \forall y_1,y_2 \in [\delta,\infty), \enspace \left|F(x,y_1) - F(x,y_2) \right| \leq \frac{1}{4\delta} \left|y_1 - y_2\right| . $$
\item For any fixed $y \in [\delta,\infty)$:
$$ \forall x_1,x_2 \in [\delta,\infty), \enspace \left|F(x_1,y) - F(x_2,y) \right| \leq \frac{1}{4\delta} \left|x_1 - x_2\right| . $$
\end{enumerate}
\end{claim}

\begin{proof}
This is a straightforward exercise in calculus. Indeed, we have for all $x,y \geq \delta$:
$$ \left|\frac{\partial F}{\partial y}(x,y)\right| = \frac{x}{(x + y)^2} \quad \text{and} \quad \left|\frac{\partial F}{\partial x}(x,y)\right| = \frac{y}{(x + y)^2} \, , $$
which implies that:
$$ \max_{x,y \geq \delta}{\left|\frac{\partial F}{\partial y}(x,y)\right|} = \max_{x,y \geq \delta}{\left|\frac{\partial F}{\partial x}(x,y)\right|} = \max_{t \geq \delta}{\frac{t}{(t + \delta)^2}} = \frac{1}{4\delta} \, , $$
where the final equality holds because it is easy to verify that the map $\delta \leq t \mapsto t/(t + \delta)^2$ is globally maximized at $t = \delta$. This establishes the Lipschitz constants in parts 1 and 2 of \clmref{Claim: Coordinate-wise Lipschitz Continuity}.
\end{proof}

Finally, using \lemref{Lemma: Covering Number Bound} and \clmref{Claim: Covering}, we get:
\begin{align*}
I(\alpha_1,\dots,\alpha_n;Z_G) & \leq \varepsilon + \log(M^{*}(\varepsilon)) \\
& \leq \frac{(1-\delta)^2}{4 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \frac{k |G|}{n^{2 q}} + \log(|\Q^n|) \\
& \leq \frac{(1-\delta)^2}{4 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \frac{k |G|}{n^{2 q}} + q n \log(n) \, .
\end{align*}
Then, by taking expectations on both sides of this inequality with respect to the law of $\G(n,p)$, we obtain, using \eqref{Eq: Cond MI Def}, \eqref{Eq: Simplified MI Relation}, and \eqref{Eq: Intermediate MI Bound}, that:
\begin{align*}
I(\pi;Z) & \leq \frac{(1-\delta)^2}{8 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) \frac{k p n(n-1)}{n^{2 q}} + q n \log(n) \\
& \leq q n \log(n) + \frac{(1-\delta)^2}{8 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) k p n^{2 - 2 q} \, .
\end{align*}
Neglecting $\delta$, $k$, and $p$, it is clear that setting $q \geq \frac{1}{2}$ ensures that this upper bound is $O(n \log(n))$. As the proofs of Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} in subsections \ref{Proof of Thm Minimax Relative l^infty-Risk} and \ref{Proof of Thm Minimax l^1-Risk} illustrate, choosing the smallest $q$ satisfying $q \geq \frac{1}{2}$ yields the tightest possible minimax lower bound using this approach. Thus, we set $q = \frac{1}{2}$ in the above bound and get:
$$ I(\pi;Z) \leq \frac{1}{2} n \log(n) + \frac{(1-\delta)^2}{8 \delta^2} \left( 2 + \delta + \frac{1}{\delta}\right) k p n $$
as desired.
\end{proof}

In the literature, various information inequalities are often used to upper bound mutual information terms like $I(\alpha_1,\dots,\alpha_n ; Z_G)$, for any realization $\G(n,p) = G$, in a simpler manner (cf. \cite[Equation (44)]{ChenGuntuboyinaZhang2016}). However, these approaches tend to yield poorer scaling in the upper bound with $n$ compared to the covering number argument we utilize (in \lemref{Lemma: Covering Number Bound}). For example, the convexity of KL divergence immediately yields the bound (cf. \cite[Equation (44)]{ChenGuntuboyinaZhang2016} or \cite[p.1319]{Zhang2006}):
\begin{align}
I(\alpha_1,\dots,\alpha_n ; Z_G) & \leq \frac{1}{(1-\delta)^{2n}} \int_{[\delta,1]^n}{\int_{[\delta,1]^n}{D\!\left(P_{Z_G|\beta} \big|\big| P_{Z_G|\gamma}\right) \diff \gamma} \diff \beta} \nonumber \\
& \leq \sup_{\beta,\gamma \in [\delta,1]^n}{D\!\left(P_{Z_G|\beta} \big|\big| P_{Z_G|\gamma}\right)} \nonumber \\
& = k \sup_{\beta,\gamma \in [\delta,1]^n}{\sum_{\substack{i,j \in [n] : \\ \{i,j\} \in G, \, i < j}}{D\!\left(\frac{\beta_j}{\beta_i + \beta_j} \bigg|\bigg| \frac{\gamma_j}{\gamma_i + \gamma_j}\right)}} \nonumber \\
& \leq k |G| \max_{a,b \in \left[\frac{\delta}{1+\delta},\frac{1}{1 + \delta}\right]}{D(a||b)} \nonumber \\
& = k |G| \, D\!\left(\frac{1}{1 + \delta} \bigg|\bigg| \frac{\delta}{1 + \delta}\right)
\label{Eq: Quadratic Upper Bound}
\end{align}
where the third equality follows from \eqref{Eq: Tensorization} (and we use the notation $\beta = (\beta_1,\dots,\beta_n)$ and $\gamma = (\gamma_1,\dots,\gamma_n)$ as before), the maximization in the fourth inequality is over $a,b \in \big[\frac{\delta}{1+\delta},\frac{1}{1 + \delta}\big]$ because the map $0 < x \mapsto x/(c + x)$ is monotone increasing for every fixed $c > 0$, and the last equality follows from basic properties of binary KL divergence (see, e.g., \cite[p.20]{PolyanskiyWu2017Notes}). As before, by taking expectations on both sides of \eqref{Eq: Quadratic Upper Bound} with respect to the law of $\G(n,p)$, we obtain, using \eqref{Eq: Cond MI Def}, \eqref{Eq: Simplified MI Relation}, and \eqref{Eq: Intermediate MI Bound}, that:
\begin{equation}
\label{Eq: Last Quadratic Upper Bound}
I(\pi;Z) \leq \frac{k p n(n-1)}{2} \, D\!\left(\frac{1}{1 + \delta} \bigg|\bigg| \frac{\delta}{1 + \delta}\right) .
\end{equation}
Neglecting $\delta$, $k$, and $p$, it is clear that $I(\pi ; Z) = O(n^2)$ in \eqref{Eq: Last Quadratic Upper Bound}, but the proof of \propref{Prop: Upper Bound on MI} gives the sharper estimate $I(\pi ; Z) = O(n \log(n))$.

\subsection{Relative $\ell^{\infty}$-norm bound and the proof of \propref{Prop: MSE Decomposition}}
\label{App: MSE decomposition}

In order to prove \propref{Prop: MSE Decomposition}, we require the following known result from the literature \cite{Chenetal2019}, which upper bounds the relative $\ell^{\infty}$-norm loss between $\hat{\pi}_*$ and the canonically scaled skill parameters in \eqref{Eq: Canonically scaled merit parameters}. (As explained later in subsection \ref{App: Intuition}, $\hat{\pi}_*$ is intuitively a good estimator of $\pi$.)

\begin{lemma}[Relative $\ell^{\infty}$-Loss Bound {\cite[Theorem 3.1]{Chenetal2019}}]
\label{Lemma: Relative ell^infty-Loss Bound}
Suppose that $p \geq c_2 \log(n)/(\delta^5 n)$ for some sufficiently large constant $c_2 > 0$. Then, there exist (universal) constants $c_4,c_5 > 0$ such that for all sufficiently large $n \in \N$, we have:
$$ \P\!\left(\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}} \leq \frac{c_4}{\delta}\sqrt{\frac{\log(n)}{n p k}} \, \middle| \, \alpha_1,\dots,\alpha_n\right) \geq 1 - \frac{c_5}{n^{5}} $$
where the probability is computed with respect to the conditional distribution of the observation matrix $Z$ and the random graph $\G(n,p)$ given any realizations of the skill parameters $\alpha_1,\dots,\alpha_n$.
\end{lemma}

We remark that the proof of \lemref{Lemma: Relative ell^infty-Loss Bound} in \cite{Chenetal2019} crucially uses the assumption that $\alpha_1,\dots,\alpha_n \in [\delta,1]$. We also note that the conditioning on $\alpha_1,\dots,\alpha_n$ in \lemref{Lemma: Relative ell^infty-Loss Bound} reflects the fact that the authors of \cite{Chenetal2019} consider a non-Bayesian scenario where $\alpha_1,\dots,\alpha_n$ are deterministic (and unknown). In contrast, this work assumes that $\alpha_1,\dots,\alpha_n$ are drawn i.i.d. from a prior PDF $\pdf$.

We now proceed to establishing \propref{Prop: MSE Decomposition} using \lemref{Lemma: Relative ell^infty-Loss Bound}.

\begin{proof}[Proof of \propref{Prop: MSE Decomposition}]
We commence this proof with the following bound on the MSE between $\ests$ and $\pdf$:
\begin{align}
& \E\!\left[\int_{\R}{\left(\ests(x) - \pdf(x)\right)^2\diff{x}}\right] \nonumber \\
& = \E\!\left[\int_{\R}{\left(\ests(x) - \hat{P}_{\alpha^n}^*(x) + \hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right] \nonumber \\
& \leq 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ 2 \, \E\!\left[\int_{\R}{\left(\ests(x) - \hat{P}_{\alpha^n}^*(x)\right)^2\diff{x}}\right] \nonumber \\
& = 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ 2 \int_{\R}{\E\!\left[\left(\ests(x) - \hat{P}_{\alpha^n}^*(x)\right)^2\right] \diff{x}} \nonumber \\
& = 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ \frac{2}{n^2 h^2} \int_{\R}{\E\!\left[\left(\sum_{i = 1}^{n}{K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)}\right)^{2}\right] \diff{x}} \nonumber \\
& = 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ \frac{2}{n^2 h^2} \int_{-1}^{2}{\E\!\left[\left(\sum_{i = 1}^{n}{K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)}\right)^{ 2}\right] \diff{x}}
\label{Eq: First bound on MSE}
\end{align}
where the second inequality follows from the inequality $(a + b)^2 \leq 2 a^2 + 2 b^2$ for all $a,b \in \R$, the third equality follows from Tonelli's theorem, the fourth equality follows from \eqref{Eq: Robust PR Estimator} and \eqref{Eq: True PR estimator} (where $h$ is general, i.e., not necessarily given by \eqref{Eq: Precise Bandwidth}), and the fifth equality holds because $h \leq 1$, $\alpha_i,\hat{\alpha}_i \in [0,1]$ for all $i \in [n]$ (see \eqref{Eq: Estimates of merit parameters}), and the maps $\R \ni t \mapsto K((\alpha_i - t)/h)$ and $\R \ni t \mapsto K((\hat{\alpha}_i - t)/h)$ have supports contained inside the intervals $[\alpha_i - h,\alpha_i + h]$ and $[\hat{\alpha}_i - h,\hat{\alpha}_i + h]$, respectively, for all $i \in [n]$. We proceed by bounding the second term in \eqref{Eq: First bound on MSE}.

To this end, we fix any $x \in \R$, and define $S_x \subseteq [n]$ to be the set of players $i \in [n]$, whose skill parameters $\alpha_i$, or their estimates $\hat{\alpha}_i$, fall into the small (and diminishing) neighborhood $[x - h,x + h]$:
$$ S_x \triangleq \left\{i \in [n] : \alpha_i \in [x - h,x + h] \enspace \text{or} \enspace \hat{\alpha}_i \in [x - h,x + h] \right\} . $$
Then, we may bound the integrand in the second term of \eqref{Eq: First bound on MSE} as follows:
\begin{align}
\E\!\left[\left(\sum_{i = 1}^{n}{K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)}\right)^{ 2}\right] & = \E\!\left[\left(\sum_{i \in S_x}{K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)}\right)^{ 2}\right] \nonumber \\
& \leq \E\!\left[\left(\sum_{i \in S_x}{\left|K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)\right|}\right)^{ 2}\right] \nonumber \\
& \leq \frac{L_2^2}{h^2} \, \E\!\left[\left(\sum_{i \in S_x}{ \left|\hat{\alpha}_i - \alpha_i\right|}\right)^{ 2}\right] \nonumber \\
& \leq \frac{L_2^2}{h^2} \, \E\!\left[|S_x|^2 \max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right]
\label{Eq: Intermediate Integrand Bound}
\end{align}
where the first equality holds because the map $\R \ni t \mapsto K((t - x)/h)$ has support contained inside the interval $[x - h,x + h]$, the second inequality follows from the triangle inequality, and the third inequality follows from the fact that the kernel $K$ is $L_2$-Lipschitz continuous. To further upper bound \eqref{Eq: Intermediate Integrand Bound}, we now present three claims.

The first claim is a well-understood auxiliary result that is frequently used in the high-dimensional and non-parametric statistics and theoretical machine learning literature. It says that the intersection of high probability events is itself a high probability event.

\begin{claim}[Intersection of High Probability Events]
\label{claim: Intersection of High Probability Events}
Consider any two events $A_1$ and $A_2$ with probabilities satisfying $\P(A_1) \geq 1 - \varepsilon_1$ and $\P(A_2) \geq 1 - \varepsilon_2$ for any constants $\varepsilon_1,\varepsilon_2 \in [0,1]$. Then, we have:
$$ \P\!\left(A_1 \cap A_2\right) \geq 1 - \varepsilon_1 - \varepsilon_2 \, . $$
\end{claim}

\begin{proof}
This is an immediate corollary of the inclusion-exclusion principle.
\end{proof}

The second claim utilizes \lemref{Lemma: Relative ell^infty-Loss Bound} to show that $\left|\hat{\alpha}_i - \alpha_i\right| = O\big(\!\max\{1/(\delta \sqrt{pk}),1\} \sqrt{\log(n)/n}\big)$ for every $i \in [n]$ with high probability for all sufficiently large $n$.

\begin{claim}[$\ell^{\infty}$-Norm Bound on Skill Parameter Estimation]
\label{Claim: Bound on Merit Parameter Estimation}
There exists a (universal) constant $c_6 > 0$ such that for all sufficiently large $n \in \N$:
$$ \P\!\left(\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|} \leq c_6 \max\!\left\{\frac{1}{\delta \sqrt{p k}},1\right\} \! \sqrt{\frac{\log(n)}{n}}\right) \geq 1 - \frac{c_5 + 1}{n^5} $$
where $c_5 > 0$ is the fixed constant from \lemref{Lemma: Relative ell^infty-Loss Bound}.
\end{claim}

\begin{proof}
We prove this claim in four steps. Firstly, we establish that for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Close to 1}
\P\!\left(\max_{i \in [n]}{\alpha_i} \geq 1 - \frac{5 \log(n)}{b n}\right) \geq 1 - \frac{1}{n^{5}} \, .
\end{equation}
To establish \eqref{Eq: Close to 1}, note that:
\begin{align*}
\P\!\left(\forall i \in [n], \, \alpha_i < 1 - \frac{5 \log(n)}{b n} \right) & = \P\!\left(\alpha_1 < 1 - \frac{5 \log(n)}{b n} \right)^n \\
& = \left(1 - \int_{1 - 5 \log(n)/(b n)}^{1}{\pdf(t) \diff{t}}\right)^n \\
& \leq \left(1 - \frac{5 \log(n)}{n}\right)^n \\
& = \exp\!\left(n\log\!\left(1 - \frac{5 \log(n)}{n}\right)\right) \\
& \leq \frac{1}{n^{5}}
\end{align*}
where the first equality holds because $\alpha_1,\dots,\alpha_n$ are i.i.d., the third inequality holds because we have assumed that $\epsilon \geq 5 \log(n)/(b n)$ and $\pdf$ satisfies the lower bound $\pdf(t) \geq b$ for all $t \in [1-\epsilon,1]$, and for every large enough $n$, the fifth inequality follows from the well-known bound $\log(1 + x) \leq x$ for all $x > -1$. This produces the desired bound \eqref{Eq: Close to 1}.

Secondly, we define the normalized skill parameter random variables:
$$ \forall i \in [n] , \enspace \tilde{\alpha}_i \triangleq \frac{\alpha_i}{\max_{j \in [n]}{\alpha_j}} = \frac{\pi(i)}{\left\|\pi\right\|_{\infty}} $$
where $\pi$ denotes the probability vector of canonically scaled skill parameters in \eqref{Eq: Canonically scaled merit parameters}. It turns out that for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Good approximation of normalized params}
\P\!\left(\forall i \in [n], \, 0 \leq \tilde{\alpha}_i - \alpha_i \leq \frac{10}{c_3} \sqrt{\frac{\log(n)}{n}} \right) \geq 1 - \frac{1}{n^{5}}
\end{equation}
i.e., the normalized skill parameters are close to the true skill parameters with high probability. To derive \eqref{Eq: Good approximation of normalized params}, suppose that the event in \eqref{Eq: Close to 1} occurs. Then, we have:
$$ 1 - \frac{5 \log(n)}{b n} \leq \max_{i \in [n]}{\alpha_i} \leq 1 $$
which implies that for every $i \in [n]$:
$$ \alpha_i \leq \tilde{\alpha}_i \leq \alpha_i \left(1 - \frac{5 \log(n)}{b n} \right)^{\! -1} \leq \alpha_i \left(1 - \frac{5}{c_3} \sqrt{\frac{\log(n)}{n}} \right)^{\! -1} \leq \alpha_i \left(1 + \frac{10}{c_3} \sqrt{\frac{\log(n)}{n}} \right) $$
where the third inequality follows from the lower bound we have assumed on $b$ in the proposition statement, and the fourth inequality holds for all sufficiently large $n \in \N$, because the bound $(1 - x)^{-1} = 1 + x + x^2(1 - x)^{-1} \leq 1 + x + 2 x^2 \leq 1 + 2x$ holds for any $x \in \big(0,\frac{1}{2}\big]$. Thus, since $\alpha_i \leq 1$ for all $i \in [n]$, we get \eqref{Eq: Good approximation of normalized params}.

Thirdly, we approximate the normalized skill parameters $\tilde{\alpha}_i$ using the estimates $\hat{\alpha}_i$. Recall from \lemref{Lemma: Relative ell^infty-Loss Bound} that for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Chen event}
\P\!\left(\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}} \leq \frac{c_4}{\delta}\sqrt{\frac{\log(n)}{n p k}}\right) \geq  1 - \frac{c_5}{n^5}
\end{equation}
where we take expectations with respect to the law of $\alpha_1,\dots,\alpha_n$. Suppose that the event in \eqref{Eq: Chen event} happens. Then, for any $i \in [n]$, notice that for all sufficiently large $n \in \N$:
\begin{align*}
\hat{\alpha}_i & = \frac{\hat{\pi}_*(i)}{\left\|\hat{\pi}_*\right\|_{\infty}} \\
& = \frac{\pi(i) + (\hat{\pi}_*(i) - \pi(i))}{\left\|\pi\right\|_{\infty} + (\left\|\hat{\pi}_*\right\|_{\infty} - \left\|\pi\right\|_{\infty})} \\
& \leq \frac{\pi(i) + \left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty} - \left|\left\|\hat{\pi}_*\right\|_{\infty} - \left\|\pi\right\|_{\infty}\right|} \\
& \leq \frac{\pi(i) + \left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty} - \left\|\hat{\pi}_* - \pi\right\|_{\infty}} \\
& = \left(\tilde{\alpha}_i + \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \! \left(1 - \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right)^{\! -1} \\
& \leq \left(\tilde{\alpha}_i + \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \! \left(1 + 2 \, \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \\
& \leq \tilde{\alpha}_i + 4 \, \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}
\end{align*}
where the first equality follows from \eqref{Eq: Estimates of merit parameters}, the fourth inequality follows from the (reverse) Minkowski inequality, the sixth inequality holds for all sufficiently large $n \in \N$ because: 1) the event in \eqref{Eq: Chen event} occurs, 2) we have assumed that $\lim_{n \rightarrow \infty}{\delta^{-1} (n p k)^{-1/2} \log(n)^{1/2}} = 0$ in the proposition statement, and 3) we use the bound $(1 - x)^{-1} \leq 1 + 2x$ for $x \in \big(0,\frac{1}{2}\big]$, and the seventh inequality holds because $\tilde{\alpha}_i \leq 1$ for all $i \in [n]$. Likewise, using analogous reasoning, observe that for all sufficiently large $n \in \N$:
\begin{align*}
\hat{\alpha}_i & \geq \frac{\pi(i) - \left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty} + \left\|\hat{\pi}_* - \pi\right\|_{\infty}} \\
& = \left(\tilde{\alpha}_i - \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \! \left(1 + \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right)^{\! -1} \\
& \geq \left(\tilde{\alpha}_i - \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \! \left(1 - \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right) \\
& \geq \tilde{\alpha}_i - 2 \, \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}} \, .
\end{align*}
Therefore, using \lemref{Lemma: Relative ell^infty-Loss Bound}, we obtain that for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Good approximation of normalized params 2}
\P\!\left(\max_{i \in [n]}{\left|\hat{\alpha}_i - \tilde{\alpha}_i\right|} \leq 4 \, \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}} \right) \geq 1 - \frac{c_5}{n^5} \, .
\end{equation}

Finally, we combine \eqref{Eq: Good approximation of normalized params} and \eqref{Eq: Good approximation of normalized params 2} together. Suppose that the events in both \eqref{Eq: Good approximation of normalized params} and \eqref{Eq: Chen event} occur. Then, we get:
\begin{align*}
\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|} & \leq \max_{i \in [n]}{\left|\hat{\alpha}_i - \tilde{\alpha}_i\right|} + \max_{i \in [n]}{\left|\tilde{\alpha}_i - \alpha_i\right|} \\
& \leq 4 \, \frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}} + \frac{10}{c_3} \sqrt{\frac{\log(n)}{n}} \\
& \leq \frac{4 c_4}{\delta} \sqrt{\frac{\log(n)}{n p k}} + \frac{10}{c_3} \sqrt{\frac{\log(n)}{n}} \\
& = O\!\left(\!\max\!\left\{\frac{1}{\delta \sqrt{p k}},1\right\} \! \sqrt{\frac{\log(n)}{n}}\right)
\end{align*}
where the first inequality follows from the triangle inequality, the second inequality follows from \eqref{Eq: Good approximation of normalized params} and \eqref{Eq: Good approximation of normalized params 2}, and the third inequality follows from \eqref{Eq: Chen event} (or \lemref{Lemma: Relative ell^infty-Loss Bound}). Using \clmref{claim: Intersection of High Probability Events}, this produces the desired bound:
$$ \P\!\left(\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|} =  O\!\left(\max\!\left\{\frac{1}{\delta \sqrt{p k}},1\right\} \! \sqrt{\frac{\log(n)}{n}}\right)\right) \geq 1 - \frac{c_5 + 1}{n^5} $$
for all sufficiently large $n$.
\end{proof}

Finally, our third claim uses \clmref{Claim: Bound on Merit Parameter Estimation} to argue that with high probability, the cardinality of $S_x$ is \emph{not} too large.

\begin{claim}[Cardinality Bound for $S_x$]
\label{Claim: Cardinality Bound}
There exists a sufficiently large (universal) constant $c_7 > 0$ such that for every sufficiently large $n \in \N$, we have:
$$ \P\!\left(|S_x| \leq c_7 B h n \right) \geq 1 - \frac{c_5 + 2}{n^{5}} \, . $$
\end{claim}

\begin{proof}
First, for any constant $\tau > 1$ (to be chosen later), we define $N_h \in [n]\cup\!\{0\}$ to be the discrete random variable representing the number of players $i \in [n]$ for whom $\alpha_i$ belongs to the interval $[x - \tau h,x + \tau h]$:
$$ N_h \triangleq \sum_{i = 1}^{n}{\I\!\left\{\alpha_i \in [x - \tau h,x + \tau h]\right\}} \, . $$
Then, fix any $\varepsilon \geq 0$, and observe using \lemref{Lemma: Hoeffding's Inequality} in Appendix \ref{App: Concentration of Measure Inequalities} that:
$$ \P\!\left(\frac{1}{n} N_h - \P\!\left(\alpha_1 \in [x - \tau h,x + \tau h]\right) > \varepsilon\right) \leq \exp\!\left(- 2 n \varepsilon^2\right) $$
which uses the fact that $\big\{\I\{\alpha_i \in [x - \tau h,x + \tau h]\} : i \in [n]\big\}$ are i.i.d. Bernoulli random variables with mean $\P(\alpha_1 \in [x - \tau h,x + \tau h])$, since $\alpha_1,\dots,\alpha_n$ are drawn i.i.d. from $\pdf$. At this point, letting $\varepsilon = \sqrt{5 \log(n) / (2 n)}$ yields:
\begin{equation}
\label{Eq: Intermediate Hoeffding Bound}
\P\!\left(\frac{1}{n} N_h - \P\!\left(\alpha_1 \in [x - \tau h,x + \tau h]\right) > \sqrt{\frac{5 \log(n)}{2 n}} \right) \leq \exp\!\left(-\frac{5 n \log(n)}{n} \right) = \frac{1}{n^{5}} \, .
\end{equation}
Next, recall that $\pdf \in \pdfs$ is uniformly bounded (almost everywhere) by $B > 0$, i.e., $\pdf(t) \leq B$ for all $t \in \R$.

Using this bound, we obtain:
\begin{equation}
\label{Eq: Upper Bound on Expectation}
\P\!\left(\alpha_1 \in [x - \tau h,x + \tau h]\right) = \int_{x - \tau h}^{x + \tau h}{\pdf(t) \diff{t}} \leq 2 B \tau h \, .
\end{equation}
Hence, combining \eqref{Eq: Intermediate Hoeffding Bound} and \eqref{Eq: Upper Bound on Expectation}, we have that with probability at least $1 - n^{-5}$:
\begin{align*}
\frac{1}{n} N_h & \leq \P\!\left(\alpha_1 \in [x - \tau h,x + \tau h]\right) + \sqrt{\frac{5 \log(n)}{2 n}} \\
& \leq 2 B \tau h + \sqrt{\frac{5 \log(n)}{2 n}} \, .
\end{align*}
Equivalently, we have derived the following bound:
\begin{equation}
\label{Eq: Proportion of Players in Small Neighborhood}
\P\!\left(N_h \leq 2 B \tau h n + \sqrt{\frac{5}{2}\, n \log(n)} \right) \geq 1 - \frac{1}{n^{5}} \, .
\end{equation}

Now, recall from the proposition statement that $h = \Omega\big(\!\max\{1/(\delta \sqrt{pk}),1\} \sqrt{\log(n)/n}\big)$. Hence, we may choose $\tau > 1$ large enough so that for all sufficiently large $n$, we have:
\begin{equation}
\label{Eq: Domination of h}
(\tau - 1) h \geq c_6 \max\!\left\{\frac{1}{\delta \sqrt{pk}},1\right\} \! \sqrt{\frac{\log(n)}{n}}
\end{equation}
where $c_6 > 0$ is the constant from \clmref{Claim: Bound on Merit Parameter Estimation}. Assume that both the events in \eqref{Eq: Proportion of Players in Small Neighborhood} and \clmref{Claim: Bound on Merit Parameter Estimation} occur. Then, for any $i \in [n]$, if $\alpha_i \in [x - h,x + h]$, then we trivially have $\alpha_i \in [x - \tau h,x + \tau h]$ since $\tau > 1$. On the other hand, if $\hat{\alpha}_i \in [x - h,x + h]$, then we have $\alpha_i \in [x - \tau h,x + \tau h]$, because $|\hat{\alpha}_i - \alpha_i| \leq c_6 \max\{1/(\delta \sqrt{pk}),1\} \sqrt{\log(n)/n} \leq (\tau - 1) h$ by \clmref{Claim: Bound on Merit Parameter Estimation} and \eqref{Eq: Domination of h}. Thus, we get:
$$ |S_x| \leq N_{h} $$
with $\tau$ chosen according to \eqref{Eq: Domination of h}. Applying \clmref{claim: Intersection of High Probability Events}, \clmref{Claim: Bound on Merit Parameter Estimation}, and \eqref{Eq: Proportion of Players in Small Neighborhood} together yields:
$$ \P\!\left(|S_x| \leq 2 B \tau h n + \sqrt{\frac{5}{2}\, n \log(n)} \right) \geq 1 - \frac{c_5 + 2}{n^{5}} $$
for every sufficiently large $n$. Lastly, let $c_7 > 2 \tau$ be a sufficiently large constant so that for all sufficiently large $n$:
$$ (c_7 - 2 \tau) B h \geq \sqrt{\frac{5 \log(n)}{2 n}} $$
which is consistent with our assumption that $h = \Omega\big(\!\max\{1/(\delta \sqrt{pk}),1\} \sqrt{\log(n)/n}\big)$. Therefore, we may write:
$$ \P\!\left(|S_x| \leq c_7 B h n \right) \geq 1 - \frac{c_5 + 2}{n^{5}} $$
for every sufficiently large $n$, which completes the proof.
\end{proof}

Having developed \clmref{Claim: Cardinality Bound}, we are now in a position to upper bound \eqref{Eq: Intermediate Integrand Bound}. For any sufficiently large $n$, define the event in \clmref{Claim: Cardinality Bound} as:
$$ A_n \triangleq \left\{|S_x| \leq c_7 B h n\right\} . $$
Then, observe that:
\begin{align}
& \E\!\left[|S_x|^2 \max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] \nonumber \\
& \qquad = \E\!\left[|S_x|^2 \max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\middle|A_n\right] \P(A_n)

+ \E\!\left[|S_x|^2 \max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\middle|A_n^c\right] \P(A_n^c) \nonumber \\
 & \qquad \leq c_7^2 B^2 h^2 n^2 \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\middle|A_n\right] \P(A_n) + \frac{c_5 + 2}{n^3} \nonumber \\
& \qquad\leq c_7^2 B^2 h^2 n^2 \bigg(\E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\middle|A_n\right] \P(A_n)

+ \underbrace{\E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\middle|A_n^c\right] \P(A_n^c)}_{\geq \, 0}\bigg) + \frac{c_5 + 2}{n^3}\nonumber \\
&\qquad = c_7^2 B^2 h^2 n^2 \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{c_5 + 2}{n^3}
\label{Eq: Intermediate Integrand Bound 2}
\end{align}
where the first and fourth equalities follow from the tower property, and the second inequality uses \clmref{Claim: Cardinality Bound} and the facts that $|S_x| \leq n$ and $|\hat{\alpha}_i - \alpha_i| \leq 1$ for all $i \in [n]$ (see \eqref{Eq: Estimates of merit parameters}). Plugging \eqref{Eq: Intermediate Integrand Bound 2} into \eqref{Eq: Intermediate Integrand Bound} produces:
$$ \E\!\left[\left(\sum_{i = 1}^{n}{K\!\left(\frac{\hat{\alpha}_i - x}{h}\right) - K\!\left(\frac{\alpha_i - x}{h}\right)}\right)^{ 2}\right] \leq \frac{L_2^2}{h^2} \left(c_7^2 B^2 h^2 n^2 \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{c_5 + 2}{n^3}\right) . $$
We can then substitute this bound into \eqref{Eq: First bound on MSE} to obtain:
\begin{align*}
& \E\!\left[\int_{\R}{\left(\ests(x) - \pdf(x)\right)^2\diff{x}}\right]  \\
& \quad \leq 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ \frac{2 L_2^2}{n^2 h^4} \int_{-1}^{2}{c_7^2 B^2 h^2 n^2 \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{c_5 + 2}{n^3} \, \diff{x}} \\
& \quad = 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ \frac{6 L_2^2}{n^2 h^4} \left(c_7^2 B^2 h^2 n^2 \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{c_5 + 2}{n^3} \right)  \\
& \quad = 2 \, \E\!\left[\int_{\R}{\left(\hat{P}_{\alpha^n}^*(x) - \pdf(x)\right)^2\diff{x}}\right]

+ \frac{6 c_7^2 B^2 L_2^2}{h^2} \, \E\!\left[\max_{i \in [n]}{\left|\hat{\alpha}_i - \alpha_i\right|^{2}}\right] + \frac{6 (c_5 + 2) L_2^2}{n^5 h^4}
\end{align*}
for all sufficiently large $n$. This completes the proof after letting $c_8 = 6  c_7^2$ and $c_9 = 6 (c_5 + 2)$.
\end{proof}


TITLE: Mutual Inductance and the Dot Convention
QUESTION [2 upvotes]: Can anyone please explain me, the dot convention in coil systems (Mutual and self inductance) with some related images to understand..?

REPLY [3 votes]: I think you'll find this article (with pictures) helpful for dot convention and this one for mutual inductance.  Let me know if this doesn't clear it up.


TITLE: Notation for set of all closed sets
QUESTION [4 upvotes]: Is there a common notation for the set of all closed sets of a topological space?
I have been using $(X,\tau)$ to denote a topological space with $\tau$ being the topology, set of all open sets. I was wondering if there is something like that this is used widely but for all the closed sets.

REPLY [10 votes]: There is no such standard notation. The safest approach is to let $\langle X,\tau\rangle$ (or $\langle X,\mathscr{T}\rangle$, etc.) be a topological space and then explicitly to name the collection of closed sets, e.g., by letting $\mathscr{F}=\{X\setminus U:U\in\tau\}$.
Since $F$ (from French fermé) is one of the letters that I conventionally use for closed sets, I’m likely to use $\mathscr{F}$ or $\mathscr{C}$ (for closed) for the collection of closed sets unless those letters have been pre-empted.


TITLE: Find the maximum area of the regular pentagon
QUESTION [6 upvotes]: Find the maximum area of the regular pentagon that inscribed a unit square.

REPLY [2 votes]: It is easier to start with a regular pentagon with vertices on the unit circle, one of them at $(1,0)$, and finding the smallest square containing it. Consider supporting lines $x \cos\phi +y \sin\phi =f(\phi)$. Then $f$ periodic with period ${2\pi\over 5}$, and  one has
$$f(\phi)=\cos\phi\qquad\left(-{\pi\over5}\leq\phi\leq{\pi\over5}\right)\ .$$
We  want to know
$$s:=\min_{0\leq\phi\leq 2\pi}\biggl\{\max\bigl\{f(\phi)+f(\phi+\pi), \ f(\phi+{\textstyle{\pi\over2}}) +f(\phi-{\textstyle{\pi\over2}})\bigr\}\biggr\}\ .$$
Because of symmetry reasons it is enough to consider the $\phi$-interval $\bigl[0,{\pi\over10}\bigr]$, in which each of the $f$-expressions on the right has a unique form.
When this $s$ has been determined it is easy to compute the area ratio between the pentagon and the resulting square.


TITLE: Tuple definition
QUESTION [1 upvotes]: Is it correct?
$S=\{\langle t,h\rangle:t\in\{0,\Delta t,2\Delta t,\cdots,24\},h\in\{0,\Delta h,2\Delta h,\cdots,H\}\}$
I would like to say that $S$ is a 2-tuple. The first tuple can vary from $0$ to $24$, with $\Delta T$ step, and the second one can vary from $0$ to $H$, with $\Delta H$ step.

REPLY [2 votes]: $S$ is not a tuple, it's a set of $2$-tuples.
I think what you want to say is that $S$ is a set of ordered pairs ($2$-tuples), each of which has a first entry that can vary from $0$ to $24$ in steps of length $\Delta t$; and second entry that can vary from $0$ to $H$ in steps of length $\Delta h$. As written, it would only make sense if $24$ is evenly divisible by $\Delta t$ and $H$ by $\Delta h$; that is, if and only if there exist integers $k$ and $\ell$ such that $24 = k\Delta t$ and $H=\ell\Delta h$.
If the latter is not the case, then I would say that the first entry will take the values $k\Delta t$ with $k=0,1,2,\ldots,\lfloor\frac{24}{\Delta t}\rfloor$, and the second entry will take the values $\ell\Delta h$ with $\ell=0,1,2,\ldots,\lfloor\frac{H}{\Delta h}\rfloor$.
Note, however, that $S$ is a set of tuples (not a tuple), and it is the first/second entry of the elements of $S$ that we are describing, not a "first tuple" and "second tuple": the elements of $S$ are themselves not ordered, so it doesn't make sense to talk about a "first tuple" and a "second tuple", when $S$ is a set.