text:
\section{Experimental Evaluation}\label{sec:experiments}

In this section, we evaluate the performance of Algorithms~\ref{alg:local-clustering} and~\ref{alg:global-clustering}
in terms of both the quality of solutions and running time.

\paragraph{Dataset}
Table~\ref{tab:instance} lists real-world hypergraphs on which our experiments were conducted.
Except for DBLP~KDD, all hypergraphs were collected from KONECT\footnote{

\url{http://konect.uni-koblenz.de/}
}.
As these are originally unweighted bipartite graphs, we transformed each of them into a hypergraph (with edge weights) as follows:
We take the left-hand-side vertices in a given bipartite graph as the vertices in the corresponding hypergraph,
and then for each right-hand-side vertex, we add a hyperedge (with weight one) consisting of the neighboring vertices in the bipartite graph.

DBLP~KDD is a coauthorship hypergraph, which we compiled from the DBLP dataset\footnote{
\url{https://dblp.uni-trier.de/}
}.
Specifically, the vertices correspond to the authors of the papers in KDD 1995--2019,
while each hyperedge represents a paper, which contains the vertices corresponding to the authors of the paper.

As almost all hypergraphs generated as above were disconnected,

we extracted the largest connected component in each hypergraph.
All information in Table~\ref{tab:instance} is about the resulting hypergraphs.

\begin{table}[t]
\centering
\caption{Real-world hypergraphs used in our experiments.}\label{tab:instance}
\scalebox{0.80}{
\begin{tabular}{lrrrr}
\toprule
Name & $n$   & $m$   &$\sum_{v\in V}d_v/n$ &$\sum_{e\in E}|e|/m$\\
\midrule
Graph products &86  &106  &3.57 &2.04\\

Network theory &330 &299 &3.06 &3.04 \\

DBLP KDD &5,590  &2,719  &1.99  &4.00\\
arXiv cond-mat &13,861  &13,571  &3.87  &3.05\\

DBpedia Writers  &54,909  &18,232  &1.80  &5.29\\
YouTube Group Memberships &88,490  &21,974  &3.24  &12.91\\
DBpedia Record Labels  &158,385  &9,827  &1.40  &22.51\\
DBpedia Genre &253,968  &4,934  &1.80  &92.84\\
\bottomrule
\end{tabular}
}
\end{table}

\paragraph{Parameter setting}
We explain the parameter setting of our algorithms. Throughout the experiments, we set $\epsilon =0.9$.
In our implementation, to make the algorithms more scalable, we try to keep the PageRank vector sparse;
that is, we round every PageRank value less than $10^{-5}$ down to zero in each iteration of the Euler method.
As a preliminary experiment, using the two largest hypergraphs,

we observed the effect of the parameters in the Euler method, $\Delta$ (i.e., time span)  and $T$ (i.e., total time), in terms of the solution quality.
Specifically, we selected 50 initial vertices uniformly at random, and for each of which,
we ran Algorithm~\ref{alg:local-clustering} with $\mu=1/2$ for each pair of parameters $(\Delta, T)\in \{0.5, 1.0, 2.0\}\times \{2, 4,\dots, 30\}$.
The results are depicted in Figure~\ref{fig:pre}.
As can be seen, the effect of $\Delta$ is drastic.
The performance with $\Delta=0.5$ is worse than that with $\Delta=1.0$,
which implies that due to the above-mentioned sparsification of the PageRank vector,
we have to spend some amount of time at once to obtain a non-negligible diffusion.
Moreover, the performance with $\Delta=2.0$ is not stable, meaning that we should not use an unnecessarily large value for $\Delta$.
The effect of $T$ is also significant; when $\Delta=0.5$ or 1.0, the conductance of the output solution becomes smaller as $T$ increases.
From these observations, in the following main experiments, we set $\Delta=1.0$ and $T=30$.

\begin{figure}[t]
\begin{subfloat}[DBpedia Record Labels]{
\includegraphics[width=0.227\textwidth]{./dbpedia-recordlabel_LCC_pre.pdf}
}
\end{subfloat}
\begin{subfloat}[DBpedia Genre]{
\includegraphics[width=0.227\textwidth]{./dbpedia-genre_LCC_pre.pdf}
}
\end{subfloat}
\caption{Effect of parameters $\Delta$ and $T$. Average values over 50 initial vertices are plotted.}\label{fig:pre}
\end{figure}

\begin{figure*}[t]
\begin{subfloat}[Graph products]{
\includegraphics[width=0.237\textwidth]{./graphprod_LCC.pdf}
}
\end{subfloat}

\begin{subfloat}[Network theory]{
\includegraphics[width=0.237\textwidth]{./netscience_LCC.pdf}
}
\end{subfloat}

\begin{subfloat}[DBLP KDD]{
\includegraphics[width=0.237\textwidth]{./dblp_kdd_LCC.pdf}
}
\end{subfloat}
\begin{subfloat}[arXiv cond-mat]{
\includegraphics[width=0.237\textwidth]{./opsahl-collaboration_LCC.pdf}
}
\end{subfloat}\\

\begin{subfloat}[DBpedia Writers]{
\includegraphics[width=0.237\textwidth]{./dbpedia-writer_LCC.pdf}
}
\end{subfloat}
\begin{subfloat}[YouTube Group Memberships]{
\includegraphics[width=0.237\textwidth]{./youtube-groupmemberships_LCC.pdf}
}
\end{subfloat}
\begin{subfloat}[DBpedia Record Labels]{
\includegraphics[width=0.237\textwidth]{./dbpedia-recordlabel_LCC.pdf}
}
\end{subfloat}
\begin{subfloat}[DBpedia Genre]{
\includegraphics[width=0.237\textwidth]{./dbpedia-genre_LCC.pdf}
}
\end{subfloat}
\caption{Comparison of the solution quality of Algorithm~\ref{alg:local-clustering} with those of \textsf{CLIQUE} and \textsf{STAR}.}\label{fig:local}
\end{figure*}

\paragraph{Baseline methods}
In local clustering, we used two baselines called \textsf{CLIQUE} and \textsf{STAR}.

\textsf{CLIQUE} first transforms a given hypergraph into a graph using the clique expansion,
i.e., for each hyperedge $e\in E$ and each $u, v\in e$ with $u\neq v$, it adds an edge $uv$ of weight $w(e)$.
Then \textsf{CLIQUE} computes personalized PageRank with some $\alpha$ using the power method and produces sweep cuts.
Finally, it outputs the best subset among them, in terms of the conductance in the original hypergraph.
\textsf{STAR} is an analogue of \textsf{CLIQUE}, which employs the star expansion alternatively,
i.e., for each hyperedge $e\in E$, it introduces a new vertex $v_e$, and then for each vertex $u\in e$, it adds an edge $uv_e$ of weight $w(e)/|e|$.
As the set of vertices has been changed in \textsf{STAR}, we leave out the additional vertices from the sweep cut.
As for the power method, the initial (PageRank) vector is set to be $(1/n, \dots, 1/n)$
and the stopping condition is set to be $\|x - x_\text{prev} \|_1\leq 10^{-8}$,
where $x$ and $x_\text{prev}$ are vectors obtained in the current and previous iterations, respectively.
Note that if we employ $A_\text{cand}$ as the candidate set of $\alpha$, the power method requires numerous number of iterations.
This is because $A_\text{cand}$ contains a lot of small values,
e.g., $\frac{w_\mathrm{min}}{w_\mathrm{max}\sum_{e\in E}|e|}$.

Hence, we just used $\alpha=0.05,0.10,\dots, 0.95$ in our experiments.

In global clustering, we used the well-known hypergraph clustering package called \textsf{hMETIS}\footnote{
http://glaros.dtc.umn.edu/gkhome/metis/hmetis/overview
}
as well as the global counterparts of \textsf{CLIQUE} and \textsf{STAR}, which can be obtained in the same way as that of our algorithms.
Note that \textsf{hMETIS} has a lot of parameters; among those, the parameters \texttt{UBfactor}, \texttt{Nruns}, \texttt{CType}, \texttt{RType}, and \texttt{Vcycle} may affect the solution quality and running time.
To obtain a high quality solution, we run the algorithm for each of
$(\texttt{UBfactor}, \texttt{Nruns}, \texttt{CType}, \texttt{RType}, \texttt{Vcycle})
\in \{5, 10, \dots, 45\}\times \{10\}\times \{1,2,3,4,5\}\times \{1,2,3\}\times \{0,1,2,3\}$ to obtain vertex sets,
and then return the one with the smallest conductance.
We used \textsf{hMETIS} 1.5.3, the latest stable release.
Finally, we remark that \textsf{hMETIS} is not applicable to local clustering
because we cannot specify the volume of a subset containing the specified vertex.

\subsection{Local clustering}
First, we focus on local clustering and evaluate the performance of Algorithm~\ref{alg:local-clustering}.
To this end, for each hypergraph in Table~\ref{tab:instance}, we selected 50 initial vertices uniformly at random,
and for each of which, we ran Algorithm~\ref{alg:local-clustering}, \textsf{CLIQUE}, and \textsf{STAR}.
To focus on local structure, Algorithm~\ref{alg:local-clustering} employs $\mu=1/10$,
and so do \textsf{CLIQUE} and \textsf{STAR} in themselves.
The code is written in C\#, which was conducted on a machine with 2.8~GHz CPU and 16~GB RAM.

The quality of solutions are illustrated in Figure~\ref{fig:local}.
The results for \textsf{CLIQUE} are missing for the three largest hypergraphs because it could not be performed due to the memory limit.
In those plots, once we fix a value in the vertical axis,
we can see the cumulative number of solutions with the conductance less than or equal to the value fixed;
thus, an algorithm drawing a line with a lower right position has a better performance.
As can be seen, Algorithm~\ref{alg:local-clustering} outperforms \textsf{CLIQUE} and \textsf{STAR}.
In fact, Algorithm~\ref{alg:local-clustering} almost always has a larger cumulative number with a fixed conductance value.
It can be observed that \textsf{CLIQUE} performs better than \textsf{STAR}.

Table~\ref{tab:local_time} presents the running time of the algorithms, where we have the average values over 50 initial vertices.
The best results among the algorithms are written in bold.
As is evident, Algorithm~\ref{alg:local-clustering} is much more scalable than \textsf{CLIQUE} and comparable to \textsf{STAR}.

\begin{table}[t]
\begin{center}
\caption{Running time(s) of local algorithms. }\label{tab:local_time}

\scalebox{0.96}{
\begin{tabular}{lrrrr}
\toprule
Name & Algorithm~\ref{alg:local-clustering}   & \textsf{CLIQUE}   & \textsf{STAR}\\
\midrule
Graph products         &0.02    &\textbf{0.01}    &0.03                   \\

Network theory         &\textbf{0.06}    &0.18    &0.11                   \\

DBLP KDD               &\textbf{1.42}   &1.84       &1.54  \\
arXiv cond-mat              &5.43   &\textbf{4.84}   &5.70                   \\

DBpedia Writers             &\textbf{7.07}   &77.98   &17.50   \\
YouTube Group Memberships   &93.67   &OM   &\textbf{57.64}   \\
DBpedia Record Labels       &\textbf{36.69}   &OM   &44.18   \\
DBpedia Genre               &\textbf{85.86}   &OM   &97.47   \\

\bottomrule
\end{tabular}
}
\end{center}
\end{table}

\begin{table*}[t]
\begin{center}
\caption{Performance of Algorithm~\ref{alg:global-clustering}, \textsf{CLIQUE}, \textsf{STAR}, and \textsf{hMETIS}.}\label{tab:global}

\scalebox{1.0}{
\begin{tabular}{lrrrrrrrrrrrrrrr}
\toprule
&\multicolumn{2}{c}{Algorithm~\ref{alg:global-clustering}}
&&\multicolumn{2}{c}{\textsf{CLIQUE}}
&&\multicolumn{2}{c}{\textsf{STAR}}
&&\multicolumn{2}{c}{\textsf{hMETIS}}
\\
\cline{2-3}
\cline{5-6}
\cline{8-9}
\cline{11-12}
Name&$\phi_H(S)$ &Time(s)
&&$\phi_H(S)$ &Time(s)
&&$\phi_H(S)$ &Time(s)
&&$\phi_H(S)$ &Time(s)\\
\midrule
Graph products              &\textbf{0.0234}     &1.01        &&0.0246    &\textbf{0.70}       &&0.0288   &1.47         &&\textbf{0.0234}      &15.30 \\

Network theory              &0.0064     &\textbf{3.03}        &&0.0062    &8.57       &&0.0074   &5.15         &&\textbf{0.0061}      &24.82  \\

DBLP KDD                    &\textbf{0.0116}     &\textbf{68.91}       &&\textbf{0.0116}    &89.24      &&\textbf{0.0116}   &74.98        &&0.0236      &107.03    \\
arXiv cond-mat              &\textbf{0.0127}     &251.81      &&\textbf{0.0127}    &\textbf{237.31}     &&\textbf{0.0127}   &281.37       &&0.0259      &418.08      \\

DBpedia Writers             &0.0069     &\textbf{353.60}      &&\textbf{0.0043}    &3,812.72   &&0.0048   &856.85       &&0.0010      &721.36       \\
YouTube Group Memberships   &\textbf{0.0003}     &4,735.28    &&---       &OM         &&\textbf{0.0003}   &\textbf{2,779.52}     &&0.0029       &3,696.24\\
DBpedia Record Labels       &\textbf{0.0002}     &\textbf{1,766.34}    &&---       &OM         &&\textbf{0.0002}   &2,151.80     &&0.0052      &1,655.88 \\
DBpedia Genre               &\textbf{0.0001}     &\textbf{4,320.72}    &&---       &OM         &&\textbf{0.0001}   &4,779.95     &&0.0023      &8,670.49    &  \\

\bottomrule
\end{tabular}
}
\end{center}
\end{table*}

\subsection{Global clustering}
Next we focus on global clustering and evaluate the performance of Algorithm~\ref{alg:global-clustering}.
As can be inferred from Table~\ref{tab:local_time}, Algorithm~\ref{alg:global-clustering} itself does not scale for large hypergraphs.
Therefore, we modified the algorithm as follows: we selected 50 initial vertices uniformly at random,
and replace $V$ with the set of selected vertices in Line~\ref{line:global_V} (in Algorithm~\ref{alg:global-clustering}).
We modified the global counterparts of \textsf{CLIQUE} and \textsf{STAR} in the same way.
To compare the performance of the algorithms fairly, we used the same initial vertices for those three algorithms.
The code is again written in C\#, which was conducted on the above-mentioned machine.

The results are summarized in Table~\ref{tab:global}, where the best results are again written in bold.
As for the solution quality, Algorithm~\ref{alg:global-clustering} is one of the best choices,
but unlike the local setting, \textsf{STAR} performs well.

In fact, \textsf{STAR} achieves the same performance as that of Algorithm~\ref{alg:global-clustering} for the three largest hypergraphs.
On the other hand, the performance of \textsf{hMETIS} is unfavorable.
In our experiments, \textsf{hMETIS} was performed with almost all possible parameter settings;

therefore, it is unlikely that we can obtain a comparable solution using \textsf{hMETIS}.
The trend of the results for the running time is similar to that of the local setting;
Algorithm~\ref{alg:local-clustering} is much more scalable than \textsf{CLIQUE} and comparable to \textsf{STAR}.


TITLE: G-principal bundles on formal disc
QUESTION [0 upvotes]: How can I prove that the $G$-fiber principal bundles on $\operatorname{Spec} \mathbb{C}[[t]]$ and $\operatorname{Spec} \mathbb{C}((t))$ are trivial when $G$ is an algebraic linear group on $\mathbb{C}$? There are some characterization or theorem which became trivial or easy in this case? I would be glad of any kind of hints.

REPLY [1 votes]: Let $P \to \operatorname{Spf} \mathbb{C}[[t]]$ be a (Zariski-)locally trivial $G$-torsor for a linear algebraic group $G$ over $\mathbb{C}$.  To show that $P$ is trivial, it suffices to exhibit a section $\operatorname{Spf} \mathbb{C}[[t]] \to P$.  Since $\mathbb{C}$ is algebraically closed, there is a rational point $\operatorname{Spec} \mathbb{C} \to P$.  It remains to extend this section over $\operatorname{Spec} \mathbb{C}$ to an infinitesimal neighborhood $\operatorname{Spf} \mathbb{C}[[t]]$.  A map $\operatorname{Spf} \mathbb{C}[[t]] \to P$ is a compatible system of maps $\operatorname{Spec} \mathbb{C}[t]/t^n \to P$.  Starting with $\operatorname{Spec} \mathbb{C} \to P$, this is the lifting problem posed by formal smoothness, which can be solved since $G$ is smooth.
For $\operatorname{Spf} \mathbb{C}((t))$, I don't think the statement is true: consider the nontrivial $\mu_n$-torsor $\operatorname{Spf} \mathbb{C}((t^{1/n})) \to \operatorname{Spf} \mathbb{C}((t))$ for $n > 1$.


TITLE: Is "ternary metrizability" equivalent to pseudometrizability?
QUESTION [12 upvotes]: Below, $X$ is always a set with at least three elements to avoid triviality.

Say that a ternary metric on a set $X$ is a map $t:X^3\rightarrow\mathbb{R}$ with the following properties:

Non-negativity: $t(x_1,x_2,x_3)\ge 0$ and $t(x_1,x_1,x_2)=0$. (However, we may have $t(x_1,x_2,x_3)=0$ even if the $x_i$s are distinct.)

Symmetry: $t(x_1,x_2,x_3)=t(x_{\sigma(1)},x_{\sigma(2)},x_{\sigma(3)})$ for each permutation $\sigma\in S_3$.

Tetrahedral inequality: for all $x_1,x_2,x_3,y$ we have $$t(x_1,x_2,x_3)\le t(x_1,x_2,y)+t(x_1,x_3,y)+t(x_2,x_3,y).$$

The motivating example is $X=\mathbb{R}^{n\ge 2}$ and $t(x,y,z)=$ the area of the triangle with vertices $x,y,z$. Now say that a topological space $(X,\tau)$ is ternary metrizable iff there is a ternary metric $t$ on $X$ such that $\tau$ is generated by the family of sets $$\{\{y: t(x_1,x_2,y)<\epsilon\}:\epsilon\in\mathbb{R}, x_1,x_2\in X\}.$$For example, in $\mathbb{R}^3$ the "area ternary metric" mentioned above induces the usual topology: the (sub)basic open sets are infinite tubes.
My question is:

What is the relationship between pseudometrizability and ternary metrizability?

The most natural guess is that they coincide exactly, and I do suspect that this is the case. However, I can't prove it (or indeed either of the implications involved) at the moment. It's not even obvious to me that for every metrizable space $(X,\tau)$ there is a ternary metric on $X$ inducing a topology $\sigma\subseteq\tau$.

REPLY [3 votes]: This is a follow-up to Eric Wofsey's answer with a partial resolution of the question of which topologies can be induced by a ternary metric.

Proposition. Every completely regular space $X$ is homeomorphic to a clopen subspace of a ternary metric space.

Proof. Let $C$ be the collection of all continuous functions from $X$ to $[0,1]$. It is a well-known fact that the topology on $X$ is the initial topology on $X$ with regards to the family $C$.
If $X$ is a singleton, then we can obviously do this with a metric space and the ternary metric Eric defined, so assume that $X$ has at least two elements.
Consider the set $Y=X \sqcup C$. Define a symmetric function $t: Y^3 \to \mathbb{R}$ as follows.

$t(x,y,z) = 0$ for $x,y,z \in X$.
$t(x,y,f) = |f(x)-f(y)|$ for $x,y \in X$ and $f \in C$.
$t(x,f,g) = 1$ and $t(x,f,f) = 0$ for $x \in X$ and $f,g \in C$ with $f \neq g$.
$t(f,g,h) = 1$ and $t(f,g,g) = 0$ for $f,g,h \in C$ pairwise distinct.

This clearly satisfies the non-negativity and symmetry properties, so we just need to verify the tetrahedral inequality and the fact that $X$ is a clopen subspace with the original topology on $X$.
For an inequality of the form $t(x,y,z) \leq \dots$, there is nothing to show. Similarly, we may always assume that the three arguments of $t$ are pairwise distinct. This leaves six cases. Let $x,y,z \in X$ and $f,g,h,i \in C$.
Case 1. $t(x,y,f) \leq t(x,y,z) + t(x,z,f) + t(z,y,f)$ follows from the fact that $|f(x)-f(y)| \leq |f(x)-f(z)| + |f(z) - f(y)|$.
Case 2. $t(x,y,f) \leq t(x,y,i) + t(x,i,f) + t(i,y,f)$ follows from the fact that

if $f=i$, then $t(x,y,f) \leq t(x,y,i)$ and
if $f\neq i$, then $|f(x) - f(y)| \leq t(x,i,f) = 1$.

Case 3. $t(x,f,i) \leq t(x,z,y) + t(x,z,i) + t(z,f,i)$ follows from the fact that $t(x,f,i) = t(z,f,i) = 1$.
Case 4. $t(x,f,i) \leq t(x,f,h) + t(x,h,i) + t(h,f,i)$ follows from the fact that

if $f=i$, then $t(x,f,i) = t(x,i,g) = 1$,
if $g=i$, then $t(x,f,g) = t(x,f,i) = 1$, and
$t(x,f,g) = t(i,f,g) = 1$ otherwise.

Case 5. $t(f,g,h) \leq t(f,g,z) + t(f,z,h) + t(z,g,h)$ follows from the fact that $t(f,g,h) = t(f,g,z) = 1$.
Case 6. $t(f,g,h) \leq t(f,g,i) + t(f,i,h) + t(i,g,h)$ follows from the fact that at least one of the right-hand terms is $1$.
To see that $X$ is a clopen subspace of $Y$, let $f \in C$ be a constant function, and pick $x \in X$. We obviously have that $t(a,x,f) = 0$ if $a \in X \cup \{f\}$ and $t(a,x,f) = 1$ if $a \in C \setminus \{f\}$. Therefore $X \cup \{f\}$ is clopen for each constant function $f \in C$. Since there is more than one constant function on $X$, we have that $X$ is the intersection of two clopen sets and is therefore clopen.
The topology on $X$ is generated by functions from $X$ to $[0,1]$ that actually attain $0$ for some $y$. For any such function $f$, $f(x) = |f(x) - f(y)|= t(x,y,f)$, so we have that the topology induced on $X$ by $t$ is finer than the original topology. On the other hand, any function of the form $x\mapsto t(x,a,b)$ for $a,b \in Y$ is in $C$, so the topology induced by $t$ must be coarser than the original topology as well. Hence they are the same. $\square$

This result makes it seem like a precise characterization might be non-local. It's not clear to me, for example, that every compact Hausdorff space is a ternary metric space.


TITLE: Planar and Euler's Formula Question
QUESTION [0 upvotes]: If a connected planar graph has four regions and six vertices, how many edges will the graph have?
(I believe the answer is 8 but I'm not positive)
1) 9
2) 8
3) 6
4) 7
Graph A = ({a,b,c,d,e,f,g}, {(a,d),(a,c),(a,b),(b,c),(e,f),(f,g),(e,g)})
Now consider the claim: A has two-regions.
1) False. Euler's formula is not valid because A is bipartite.
2) False. Euler's formula is not valid because A is not connected.
3) True, since there are 7 verts and 7 edges, the Euler formula yields: 7-7+|R| = 2; so |R|=2.
4) False. Euler's formula is not valid because A is not a planar graph.

REPLY [1 votes]: Euler's formula states that a finite, connected, planar graph, when drawn in the plane with no intersecting edges, satisfies:
$$v-e+f=2$$
where $v$ is the number of vertices, $e$ the number of edges, and $f$ the numbers of faces/regions.

substitute into the formula. That's all.
Draw that graph on paper. The definition has nothing to do with bipartiteness, so that rules out 1). Is it planar and connected? If not, the answer is 2) or 4). Otherwise, the answer is 3).


TITLE: Can Bose–Einstein condensate (BEC) take up no space?
QUESTION [0 upvotes]: If multiple bosons can occupy the same state, does that mean you can put an infinite number of them in a fixed container at zero temperature without pressure.

REPLY [1 votes]: Being in the same state does not mean being at the same position.
For example, the ground state of a square well of side length $L$ goes as $\Psi \propto \sin(x/L)$. As you make $L\rightarrow \infty$, this becomes a flat distribution of infinite extent. So, indeed, they do not take zero space.
As far as pressure is concerned, the pressure $P$ of a weakly interacting Bose-Condensed gas with interaction strength $g$ is (at $T=0$):
$$ P = \frac{1}{2}gn^2.$$
So a non-interacting BEC ($g=0$) will have zero pressure (at $T=0$).  An attractively interacting system in unstable as it will collapse ($P<0$), whereas a repuslively interacting system has a positive pressure so it costs energy to "stuff" particles in a box. NB at $T \neq 0$ there is always thermal pressure in interacting and non-interacting systems alike.

REPLY [0 votes]: Yes. An infinite number of Bosons can occupy the same state. But this does not mean that they will occupy the same location. The constraint that you applied (zero temperature and pressure) incorrectly assumes that there will cease to be any motion, so that all the particles are localised, and will not escape the container. This is incorrect, as even in zero temperature (and pressure) there will still be motion, due to quantum vacuum fluctuations. These fluctuations are a manifestation of the Uncertainty relation $\Delta E\Delta t \geqslant \frac{1}{2} \hbar$.


TITLE: Pedal length/curvature differential relation
QUESTION [0 upvotes]: By constructing differential triangles in polar coordinates in the plane show that
$$ \dfrac{dp}{ds}= \dfrac{t}{R} = t \,\kappa$$
[ pedal length $p$ , tangent projection $t$, instant radius $R$ , curvature $\kappa$, arc  $s$].
EDIT 1:
In place of $(12), (13)$ I obtained by scalar arc differentiation the RHS as  $ (t \kappa, 1- \kappa \,p )$ respectively in which sign of  $\kappa $ is the opposite.
I reasoned for the new latter Equation (13) taking the example of an involute of a circle.... since the magnitude of normal is constant (= radius of circle from which a taut string is unwound), it should vanish, so that
$$ \kappa p = +1,\, p = +R $$
But Robert Lewis and by implication and also Ted Shifrin put the sign as
$$ \kappa p = -1,\, p = -R $$
which should be reconciled.

REPLY [3 votes]: I haven't worked out an "infinitesimal" argument, but I can give a very elementary argument, which also clarifies the sign issue on $t$. By the definition of the support line and $p$, we have the equation
$$p = \boldsymbol\alpha \cdot (\cos\theta,\sin\theta).$$
Differentiating with respect to arclength, we get
$$p'(s) = \boldsymbol\alpha'(s)\cdot (\cos\theta,\sin\theta) + \boldsymbol\alpha(s)\cdot (-\sin\theta,\cos\theta)\theta'(s).$$
The first term is $0$ because $(\cos\theta,\sin\theta)$ is normal to the support line (which is the tangent line). $\theta'(s)=\kappa(s)$ (almost by definition for a plane curve), and $t=\boldsymbol\alpha\cdot (-\sin\theta,\cos\theta)$.
Comment: I think in your original question, you should think of the relevance of $R = 1/\kappa$ in terms of using $ds = R\,d\theta$ for one side of your infinitesimal triangle.


TITLE: How is $S_{n-1} = n^2 +2$?
QUESTION [6 upvotes]: I'm learning Arithmetic Progression. There's an example given in my book which I'm not able to understand from yesterday. The example is:

If the sum to $n$ terms of a sequence is given by $S_n =n^2+2n+3$, find $t_n$ and hence find $t_1$ and $t_2$.
Solution:
$S_n =(n^2+2n+3)$ and $S_{n-1} = (n-1)^2 + 2(n-1)+3 = n^2+2$.
Therefore, $t_n = (S_n - S_{n-1}) = (n^2 +2n + 3) - (n^2 + 2) = (2n+1)$.
Consequently, $t_1 = 3$ and $t_2 =5$.

I'm not getting the first line of the solution. To be honest, I'm not able to understand the question. Please help. Sorry if I asked something foolish (as I'm quite week in mathematics) and also for my bad English.
Thanks in advance!

REPLY [0 votes]: What is missed out by the book solution is that the sum does not work.
In order to fix that, we need the first term - whether it is (as implied) $t_1$ or potentially $t_0$ - to be different from the formula which we can use for the other terms.
For the first term, there is no $S_{n-1}$, and we must have that $t_n$=$S_n$ (for the first term only).
So, assuming that $t_1$ is the first term and there is no $t_0$, we get that $t_1 = 1^2 + 2\times 1 +3 = 6$.
Or if we have an extra $t_0$ that is the first term,  then $t_0=S_0=3$


TITLE: Comparing two integrals
QUESTION [2 upvotes]: I am trying to solve the following problem:

Let $f:[0,1] \rightarrow [1,\infty)$ be Lebesgue measurable. Which quantity is greater:

$\int_0^1 \! f(x)\log f(x) \, \mathrm{d}x$
or
$\int_0^1 \! f(y) \, \mathrm{d}y \int_0^1 \! \log f(z) \, \mathrm{d}z.  $

I was thinking of using Fubini-Tonelli in some way, but I am not getting anywhere. I would be very grateful for some help. Thanks!

REPLY [0 votes]: Did originally posted this answer, with a small omission, but changed to another. I think it is worth having this answer, so I will repeat it.
The function $u(x)=x\log(x)$ is convex on $(0,\infty)$: $u''(x)=\frac1x\gt0$.
By Jensen's Inequality, we have
$$
\int_0^1f(x)\,\mathrm{d}x\cdot\log\left(\int_0^1f(x)\,\mathrm{d}x\right) \le\int_0^1f(x)\log(f(x))\,\mathrm{d}x\tag{1}
$$
Furthermore, since $\log(x)$ is concave on $(0,\infty)$ we have
$$
\int_0^1\log(f(x))\,\mathrm{d}x\le\log\left(\int_0^1f(x)\,\mathrm{d}x\right)\tag{2}
$$
Since $\int_0^1f(x)\,\mathrm{d}x\ge0$, $(1)$ and $(2)$ imply that
$$
\int_0^1f(x)\,\mathrm{d}x\cdot\int_0^1\log(f(x))\,\mathrm{d}x
\le\int_0^1f(x)\log(f(x))\,\mathrm{d}x\tag{3}
$$


text:
\section{Minimax lower bounds via generalized Fano's method}
\label{App: Minimax lower bound via generalized Fano's method}

In this appendix, we establish the minimax bounds in Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk}. In order to simplify the exposition, we first present the generalized Fano's method in subsection \ref{Generalized Fano's method}, derive three useful auxiliary lemmata in subsection \ref{Auxiliary lemmata 2}, and then present 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}, respectively.

\subsection{Generalized Fano's method}
\label{Generalized Fano's method}

A canonical approach to obtaining minimax lower bounds in non-parametric estimation problems is the so called \emph{Fano's method}, which was introduced in \cite{Khasminskii1979,IbragimovKhasminskii1977} (also see, e.g., \cite{Yu1997} and \cite[Section 2.7.1]{Tsybakov2009} for modern treatments). Fano's method proceeds by first lower bounding minimax risk by a Bayes risk, where all the prior probability mass is placed over a suitably chosen (and large) finite set of parameters in the (non-parametric or infinite-dimensional) parameter space, then lower bounding this Bayes risk using the probability of error of a multiple hypothesis testing problem, and finally, lower bounding this probability of error using the well-known \emph{Fano's inequality} from information theory (cf. \cite[Theorem 2.10.1]{CoverThomas2006}). In the problem of estimating \eqref{Eq: Canonically scaled merit parameters} based on $Z$, the parameter space of the minimax risks in Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} is the infinite-dimensional family of PDFs $\pdfs$. For simplicity and analytical tractability, instead of directly applying Fano's method to this large parameter space $\pdfs$, which would involve constructing a prior distribution over some judiciously chosen finite subset of $\pdfs$, we first obtain lower bounds on the minimax risks in Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} in terms of Bayes risks. In particular, as discussed earlier, we set $\pdf = \unif([\delta,1]) \in \pdfs$ throughout subsections \ref{Auxiliary lemmata 2}, \ref{Proof of Thm Minimax Relative l^infty-Risk}, and \ref{Proof of Thm Minimax l^1-Risk}, so that $\alpha_1,\dots,\alpha_n$ are i.i.d. $\pdf = \unif([\delta,1])$. Hence, $\P(\cdot)$ denotes the joint probability law of $\alpha_1,\dots,\alpha_n$, $\{Z_m(i,j) : i,j \in [n], \, i < j, \, m \in  [k]\}$, and $\G(n,p)$ with $\pdf = \unif([\delta,1])$ in the sequel, and $\E[\cdot]$ denotes the corresponding expectation operator. This yields the following lower bound on the minimax relative $\ell^{q}$-norm risk for any $q \in [1,+\infty]$:
\begin{equation}
\label{Eq: Bayes Risk Lower Bound}
\inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{q}}{\left\|\pi\right\|_{q}}\right]}} \geq
\inf_{\hat{\pi}}{\E\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{q}}{\left\|\pi\right\|_{q}}\right]}
\end{equation}
where the infima are over all (measurable) randomized estimators $\hat{\pi} \in \S_n$ of the canonically scaled skill parameters $\pi$ based on the observation matrix $Z$, and $\E_{P_{\alpha}}[\cdot]$ denotes the expectation operator with respect to general (not necessarily uniform) $\pdf$. Clearly, letting $q = +\infty$ and $q = 1$ yield the minimax problems in Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk}, respectively. Therefore, we can focus on the simpler problem of lower bounding the Bayes risks on the right hand side of \eqref{Eq: Bayes Risk Lower Bound} for $q \in \{1,+\infty\}$.

Unfortunately, while Fano's method is very effective at lower bounding non-parametric minimax risks, it cannot lower bound Bayes risks where the parameter space is not a discrete and finite set, because the classical Fano's inequality only holds for discrete and finite parameter sets, cf. \cite[Theorem 2.10.1]{CoverThomas2006}. To remedy this dearth of Fano-based techniques to lower bound Bayes risks where the parameter space is a continuum, the so called \emph{generalized Fano's method} has been developed in the recent literature \cite{Zhang2006,ChenGuntuboyinaZhang2016,XuRaginsky2017}. One of the first results in this line of work was a generalization of Fano's inequality to the \textit{continuum Fano inequality} in \cite[Proposition 2]{DuchiWainwright2013}, which had useful consequences for minimax estimation with a specific zero-one valued loss function \cite[Section 3]{DuchiWainwright2013}. The techniques of \cite{DuchiWainwright2013} have been vastly generalized in \cite{ChenGuntuboyinaZhang2016} and \cite{XuRaginsky2017} to obtain lower bounds on Bayes risks in terms of \emph{$f$-informativity}, cf. \cite{Csiszar1972}, and conditional mutual information (with auxiliary random variables), respectively. In this paper, we will utilize the key result in \cite[Theorem 1, Equation (6)]{XuRaginsky2017}. The lemma below presents the result in \cite[Theorem 1, Equation (6)]{XuRaginsky2017} specialized to our relative $\ell^{q}$-loss setting.

\begin{lemma}[Generalized Fano's Method {\cite[Theorem 1]{XuRaginsky2017}}]
\label{Lemma: Generalized Fano's Method}
For any $q \in [1,+\infty]$, the Bayes risk on the right hand side of \eqref{Eq: Bayes Risk Lower Bound} is lower bounded by:
$$ \inf_{\hat{\pi}}{\E\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{q}}{\left\|\pi\right\|_{q}}\right]} \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{I(\pi ; Z) + \log(2)}{\log(1/\L_q(t))}\right)} $$
where we define the \emph{small ball probability} $\L_q(\cdot)$ as (cf. \cite[Equation (2)]{XuRaginsky2017}):
\begin{equation}
\label{Eq: Small Ball Prob Def}
\forall t > 0, \enspace \L_q(t) \triangleq \sup_{\nu \in \S_n}{\P\!\left(\frac{\left\|\pi - \nu\right\|_q}{\left\|\pi\right\|_q} \leq t\right)} \, ,
\end{equation}
and $I(\pi ; Z)$ denotes the mutual information (defined in \eqref{Eq: MI Def}) between the canonically scaled skill parameters $\pi$ (defined in \eqref{Eq: Canonically scaled merit parameters}) and the observation matrix $Z$ (defined in \eqref{Eq: Observation matrix}).
\end{lemma}

We remark that several variants of \lemref{Lemma: Generalized Fano's Method} exist in the literature, such as \cite[Theorem 6.1]{Zhang2006} and \cite[Remark 10, Corollary 12(i)]{ChenGuntuboyinaZhang2016}. As expounded in \cite{ChenGuntuboyinaZhang2016}, in order to compute lower bounds such as that in \lemref{Lemma: Generalized Fano's Method}, we need to establish two things:
\begin{enumerate}
\item Tight upper bounds on the mutual information $I(\pi ; Z)$.
\item Tight upper bounds on the small ball probability $\L_q(t)$.
\end{enumerate}
We have already derived an upper bound on $I(\pi ; Z)$ in \propref{Prop: Upper Bound on MI} using the covering number argument presented in subsection \ref{App: Covering numbers}. Next,
we prove upper bounds on the small ball probability $\L_q(t)$ for $q \in \{1,+\infty\}$.

\subsection{Upper bounds on small ball probability}
\label{Auxiliary lemmata 2}

As noted in both \cite{ChenGuntuboyinaZhang2016} and \cite{XuRaginsky2017}, there is no general recipe for obtaining upper bounds on $\L_q(t)$. So, we develop our bounds via direct computation. To this end, the ensuing lemma presents an upper bound on the mode of the joint PDF of $\pi$, or more precisely, the joint PDF of:
\begin{equation}
\label{Eq: Projected pi}
\tilde{\pi} \triangleq (\pi(1),\dots,\pi(n-1))
\end{equation}
with respect to the Lebesgue measure on $\R^{n-1}$, which excludes $\pi(n)$, because $\pi(n) = 1 - \pi(1) - \cdots - \pi(n-1)$.

\begin{lemma}[Bound on Mode of Joint PDF of $\tilde{\pi}$]
\label{Lemma: Bound on Mode of Joint PDF of pi}
Let the joint PDF of $\tilde{\pi}$ with respect to the Lebesgue measure on $\R^{n-1}$ be denoted $P_{\tilde{\pi}}$. The mode of $P_{\tilde{\pi}}$ is upper bounded by:
$$ \esssup_{\tau \in \R^{n-1}}{\, P_{\tilde{\pi}}(\tau)} \leq \frac{n^{n-1}}{(1-\delta)^n} $$
where $\esssup$ denotes the essential supremum.
\end{lemma}

\begin{proof}
First, consider the map $h : [\delta,1]^n \rightarrow \image(h)$:
$$ \forall \beta = (\beta_1,\dots,\beta_n) \in [\delta,1]^n, \enspace h(\beta) \triangleq \left(\frac{\beta_1}{\sum_{i = 1}^{n}{\beta_i}},\dots,\frac{\beta_{n-1}}{\sum_{i = 1}^{n}{\beta_i}},\sum_{i = 1}^{n}{\beta_i}\right) $$
where $\image(h) \triangleq \big\{(\tau_1,\dots,\tau_{n-1},\sigma) \in
\big[\frac{\delta}{n - 1 + \delta}, \frac{1}{1 + \delta(n-1)}\big]^{n-1} \times [n\delta,n] : \exists \, \beta_1,\dots,\beta_n \in [\delta,1], \, \sigma = \sum_{j = 1}^{n}{\beta_j}\text{ and }\forall i \allowbreak \in [n-1], \, \tau_i = \beta_i/\sigma\big\}$ denotes the range (or image) of $h$. Clearly, we have $h(\alpha_1,\dots,\alpha_n) = (\tilde{\pi},\alpha_1 + \cdots + \alpha_n)$ using \eqref{Eq: Canonically scaled merit parameters} and \eqref{Eq: Projected pi}. Furthermore, $h$ is a bijection with inverse function $h^{-1} : \image(h) \rightarrow [\delta,1]^n$:
$$ \forall (\tau_1,\dots,\tau_{n-1},\sigma) \in \image(h) , \enspace h^{-1}(\tau_1,\dots,\tau_{n-1},\sigma) = \left(\sigma \tau_1,\dots,\sigma \tau_{n-1},\sigma\!\left(1 - \sum_{i = 1}^{n-1}{\tau_i}\right)\right) . $$
By direct evaluation, the \emph{Jacobian matrix} of $h^{-1}$, denoted $\nabla h^{-1} : \image(h) \rightarrow \R^{n \times n}$, is:
$$ \forall (\tau_1,\dots,\tau_{n-1},\sigma) \in \image(h) , \enspace \left[\nabla h^{-1}\right]_{i,j} =
\begin{cases}
\sigma \I\{i = j\} \, , & i,j \in [n-1] \\
-\sigma \, , & i = n, \, j \in [n-1] \\
\tau_i \, , & i \in [n-1], \, j = n \\
\displaystyle{1 - \sum_{i = 1}^{n-1}{\tau_i}} \, , & i = j = n
\end{cases}
$$
where $[\nabla h^{-1}]_{i,j}$ denotes the $(i,j)$th entry of the matrix $\nabla h^{-1}$ for $i,j \in [n]$. (Note that $\nabla h^{-1}$ is also well-defined on the boundary of $\image(h)$, because there exists an open set containing $\image(h)$ such that the first partial derivatives of $h^{-1}$ exist on this open set.) Now define the successive sub-matrices:
$$ \forall r \in \{0,1,\dots,n-2\}, \enspace M_{n-r} \triangleq \left[
\begin{array}{ccccc}
1 & 0 & \cdots & 0 & \tau_{r+1} \\
0 & 1 & \cdots & 0 & \tau_{r+2} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & \tau_{n-1} \\
-1 & -1 & \cdots & -1 & 1 - \sum_{i = 1}^{n-1}{\tau_i}
\end{array}
\right] \in \R^{(n-r)\times(n-r)} $$
where $M_n$ is closely related to $\nabla h^{-1}$ (as shown below in \eqref{Eq: Multilinear}), and let the transpose of the \emph{Frobenius companion matrix} of the monic polynomial $q_n(t) = 1 + t + t^2 + \cdots + t^n$ be (cf. \cite[Definition 3.3.13]{HornJohnson2013}):
$$ C_n \triangleq \left[
\begin{array}{cccccc}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1 \\
-1 & -1 & -1 & \cdots & -1
\end{array}
\right] \in \R^{n \times n} \, .
$$
Then, the corresponding \emph{Jacobian determinant} satisfies the recurrence relation:
\begin{align}
\forall (\tau_1,\dots,\tau_{n-1},\sigma) \in \image(h) , \enspace \det\!\left(\nabla h^{-1}\right) & = \det\!\left(\left[
\begin{array}{ccccc}
\sigma & 0 & \cdots & 0 & \tau_1 \\
0 & \sigma & \cdots & 0 & \tau_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & \sigma & \tau_{n-1} \\
-\sigma & -\sigma & \cdots & -\sigma & 1 - \sum_{i = 1}^{n-1}{\tau_i}
\end{array}
\right]\right) \nonumber \\
& = \sigma^{n-1} \det(M_n) \label{Eq: Multilinear} \\
& = \sigma^{n-1} \left(\det(M_{n-1}) + (-1)^{n+1} \tau_1 \det(C_{n-1}) \right) \label{Eq: Laplace}
\end{align}
where $\det(\cdot)$ denotes the determinant operator, \eqref{Eq: Multilinear} follows from the multilinearity of the determinant, and \eqref{Eq: Laplace} uses the \emph{Laplace (cofactor) expansion} of determinants by minors along the first row (see, e.g., \cite[Section 0.3.1]{HornJohnson2013}). We next compute this Jacobian determinant.

It is easy to calculate $\det(C_{n-1})$ in \eqref{Eq: Laplace}, because $q_{n-1}(t)$ is also the characteristic polynomial of its (adjoint) companion matrix $C_{n-1}$, cf. \cite[Theorem 3.3.14]{HornJohnson2013}. The $n-1$ distinct roots of $q_{n-1}(t)$ are the following $n$th roots of unity:
$$ \forall r \in [n-1], \enspace q_{n-1}\big(\omega^r\big) = 0 $$
where $\omega = \exp\!\big(\frac{2 \pib \iotab}{n}\big)$. (Note that unlike the rest of this paper, in the definition of $\omega$, we use $\iotab$ and $\pib$ to represent the imaginary unit $\iotab = \sqrt{-1}$ and the mathematical constant $\pib = 3.14159\dots$, respectively.) Hence, $\big\{\omega^r : r \in [n-1]\big\}$ are the eigenvalues of $C_{n-1}$, and we have:
$$ \det(C_{n-1}) = \prod_{r = 1}^{n-1}{\omega^r} = \omega^{n(n-1)/2} = (-1)^{n-1}$$
since the determinant is the product of the eigenvalues (see, e.g., \cite[Section 1.2]{HornJohnson2013}). Combining this with \eqref{Eq: Laplace}, we get:
\begin{align}
\forall (\tau_1,\dots,\tau_{n-1},\sigma) \in \image(h) , \enspace \det\!\left(\nabla h^{-1}\right) & = \sigma^{n-1} \left(\det(M_{n-1}) + (-1)^{n+1} \tau_1 (-1)^{n-1} \right) \nonumber \\
& = \sigma^{n-1} \underbrace{\left(\det(M_{n-1}) + \tau_1 \right)}_{= \, \det(M_n)} \nonumber \\
& = \sigma^{n-1} \left(\det(M_{2}) + \sum_{j = 1}^{n-2}{\tau_j}\right) \nonumber \\
& = \sigma^{n-1} \left(1 - \sum_{j = 1}^{n-1}{\tau_j} + \tau_{n-1} + \sum_{j = 1}^{n-2}{\tau_j}\right) \nonumber \\
& = \sigma^{n-1}
\label{Eq: Jacobian det}
\end{align}
where the third equality follows from unwinding the recursion in the second line.

Now observe that the joint PDF of $(\alpha_1,\dots,\alpha_n)$ (with respect to the Lebesgue measure on $\R^{n}$) is given by:
$$ \forall \beta \in \R^n, \enspace P_{\alpha_1,\dots,\alpha_n}(\beta) = \frac{1}{(1-\delta)^n} \, \I\!\left\{\beta \in [\delta,1]^n\right\} $$
since $\alpha_1,\dots,\alpha_n$ are i.i.d. $\pdf = \unif([\delta,1])$. As a consequence, the joint PDF of $h(\alpha_1,\dots,\alpha_n) = (\tilde{\pi},\alpha_1+\cdots+\alpha_n)$ (with respect to the Lebesgue measure on $\R^{n}$) is given by the \emph{change-of-variables formula}:
\begin{align}
P_{\tilde{\pi},\alpha_1+\cdots+\alpha_n}(\tau_1,\dots,\tau_{n-1},\sigma) & = P_{\alpha_1,\dots,\alpha_n}(h^{-1}(\tau_1,\dots,\tau_{n-1},\sigma)) \left|\det\!\left(\nabla h^{-1}\right)\right| \nonumber \\
& = \frac{\sigma^{n-1}}{(1-\delta)^n} \, \I\!\left\{(\tau_1,\dots,\tau_{n-1},\sigma) \in \image(h)\right\}
\label{Eq: Joint PDF Calculation}
\end{align}
for all $(\tau_1,\dots,\tau_{n-1},\sigma) \in \R^n$, where we utilize our earlier computation of the Jacobian determinant in \eqref{Eq: Jacobian det}. Although we only seek to bound the joint PDF of $\tilde{\pi}$, the joint PDF in \eqref{Eq: Joint PDF Calculation} includes an additional random variable $\alpha_1+\cdots+\alpha_n$ as an artifact of our calculation approach (which requires an invertible map $h$ with a well-defined and invertible Jacobian matrix $\nabla h$).

So, in the final step of this proof, we marginalize the joint PDF in \eqref{Eq: Joint PDF Calculation} and then bound the desired joint PDF of $\tilde{\pi}$ (with respect to the Lebesgue measure on $\R^{n-1}$):
\begin{align*}
\forall \tau \in \R^{n-1}, \enspace P_{\tilde{\pi}}(\tau) & = \I\!\big\{\tau \in \tilde{\S}_n\big\} \int_{[n\delta,n]}{P_{\tilde{\pi},\alpha_1+\cdots+\alpha_n}(\tau,\sigma) \, \diff \sigma} \\
& = \frac{\I\!\big\{\tau \in \tilde{\S}_n\big\}}{(1-\delta)^n} \int_{[n\delta,n]}{\sigma^{n-1} \, \I\!\left\{(\tau,\sigma) \in \image(h)\right\} \diff \sigma} \\
& \leq \frac{\I\!\big\{\tau \in \tilde{\S}_n\big\}}{(1-\delta)^n} \int_{[n\delta,n]}{\sigma^{n-1} \, \diff \sigma} \\
& = \frac{n^{n-1} (1 - \delta^n)}{(1-\delta)^n} \, \I\!\big\{\tau \in \tilde{\S}_n\big\} \\
& \leq \frac{n^{n-1}}{(1-\delta)^n} \, \I\!\big\{\tau \in \tilde{\S}_n\big\}
\end{align*}
where $\tilde{\S}_n \triangleq \big\{(\tau_1,\dots,\tau_{n-1}) \in \big[\frac{\delta}{n - 1 + \delta},\frac{1}{1 + \delta(n-1)}\big]^{n-1} : \exists \, \beta_1,\dots,\beta_n \in [\delta,1], \, \forall i \allowbreak \in [n-1], \, \tau_i = \beta_i/\big(\sum_{j = 1}^{n}{\beta_j}\big)\big\}$. Taking the (essential) supremum over all $\tau \in \R^{n-1}$ in the above bound completes the proof.
\end{proof}

We now use \lemref{Lemma: Bound on Mode of Joint PDF of pi} to upper bound the small ball probabilities $\L_q(t)$ for $q \in \{1,+\infty\}$ in the lemmata below.

\begin{lemma}[Upper Bound on Small Ball Probability for $q=\infty$]
\label{Lemma: Upper Bound on Small Ball Probability}
For every $t > 0$, we have:
$$ \L_{\infty}(t) \leq \left(\frac{2}{\delta (1-\delta)}\right)^{\! n} t^{n-1} \, . $$
\end{lemma}

\begin{proof}
Starting with \eqref{Eq: Small Ball Prob Def}, observe that:
\begin{align*}
\forall t > 0, \enspace \L_{\infty}(t) & = \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\P\!\left(\left\|\pi - \nu\right\|_{\infty} \leq t \left\|\pi\right\|_{\infty}\right)} \\
& \leq \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\P\!\left(\left\|\pi - \nu\right\|_{\infty} \leq \frac{t}{\delta n}\right)} \\
& \leq \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\P\!\left(\left\|\tilde{\pi} - (\nu_1,\dots,\nu_{n-1})\right\|_{\infty} \leq \frac{t}{\delta n}\right)} \\
& = \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\int_{\R^{n-1}}{P_{\tilde{\pi}}(\tau) \, \I\!\left\{\left\|\tau - (\nu_1,\dots,\nu_{n-1})\right\|_{\infty} \leq \frac{t}{\delta n}\right\} \diff \tau}} \\
& \leq \frac{n^{n-1}}{(1-\delta)^n} \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\underbrace{\int_{\R^{n-1}}{\I\!\left\{\left\|\tau - (\nu_1,\dots,\nu_{n-1})\right\|_{\infty} \leq \frac{t}{\delta n}\right\} \diff \tau}}_{\text{volume of } \ell^{\infty}\text{-ball with radius } t/(\delta n)}} \\
& = \frac{n^{n-1}}{(1-\delta)^n} \left(\frac{2 t}{\delta n}\right)^{\! n-1} \\
& \leq \left(\frac{2}{\delta (1-\delta)}\right)^{\! n} t^{n-1}
\end{align*}
where the second inequality uses the bound:
$$ \left\|\pi\right\|_{\infty} = \frac{\max_{i \in [n]}{\alpha_i}}{\sum_{i = 1}^{n}{\alpha_i}} \leq \frac{1}{\delta n} $$
which follows from \eqref{Eq: Canonically scaled merit parameters} and the fact that $\alpha_1,\dots,\alpha_n \in [\delta,1]$, the third inequality uses \eqref{Eq: Projected pi} and the fact that $\|\tilde{\pi} - (\nu_1,\dots,\nu_{n-1})\|_{\infty} \leq \|\pi - \nu\|_{\infty}$, the fifth inequality follows from \lemref{Lemma: Bound on Mode of Joint PDF of pi}, the sixth equality uses the well-known volume of the $\ell^{\infty}$-ball (or hypercube) with radius $t/(\delta n)$, and the seventh inequality follows from the fact that $2/\delta \geq 1$. This completes the proof.
\end{proof}

\begin{lemma}[Upper Bound on Small Ball Probability for $q=1$]
\label{Lemma: Upper Bound on Small Ball Probability 2}
For every $t > 0$, we have:
$$ \L_1(t) \leq \frac{1}{5 \sqrt{n}} \left(\frac{2 e}{1-\delta}\right)^{\! n} t^{n-1} \, . $$
\end{lemma}

\begin{proof}
As before, starting with \eqref{Eq: Small Ball Prob Def} and the fact that $\|\pi\|_1 = 1$, observe that:
\begin{align*}
\forall t > 0, \enspace \L_1(t) & = \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\P\!\left(\left\|\pi - \nu\right\|_1 \leq t\right)} \\
& \leq \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\P\!\left(\left\|\tilde{\pi} - (\nu_1,\dots,\nu_{n-1})\right\|_1 \leq t\right)} \\
& = \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\int_{\R^{n-1}}{P_{\tilde{\pi}}(\tau) \, \I\!\left\{\left\|\tau - (\nu_1,\dots,\nu_{n-1})\right\|_1 \leq t\right\} \diff \tau}} \\
& \leq \frac{n^{n-1}}{(1-\delta)^n} \sup_{\nu = (\nu_1,\dots,\nu_n) \in \S_n}{\underbrace{\int_{\R^{n-1}}{\I\!\left\{\left\|\tau - (\nu_1,\dots,\nu_{n-1})\right\|_1 \leq t\right\} \diff \tau}}_{\text{volume of } \ell^{1}\text{-ball with radius } t}} \\
& = \frac{n^{n-1} 2^{n-1}}{(1-\delta)^n (n-1)!} \, t^{n-1} \\
& \leq \frac{1}{5 \sqrt{n}} \left(\frac{2 e}{1-\delta}\right)^{\! n} t^{n-1}
\end{align*}
where the second inequality uses \eqref{Eq: Projected pi} and the fact that $\|\tilde{\pi} - (\nu_1,\dots,\nu_{n-1})\|_1 \leq \|\pi - \nu\|_1$ (and this bound is not too loose because $\|\pi - \nu\|_1 \leq 2 \, \|\tilde{\pi} - (\nu_1,\dots,\nu_{n-1})\|_1$ via the triangle inequality), the fourth inequality follows from \lemref{Lemma: Bound on Mode of Joint PDF of pi}, the fifth equality uses the well-known volume of the $\ell^1$-ball (or cross-polytope) with radius $t$, and the sixth inequality follows from the Stirling's formula bound (see, e.g., \cite[Chapter II, Section 9, Equation (9.15)]{Feller1968}):
$$ n! \geq \frac{5}{2} \sqrt{n} \left(\frac{n}{e}\right)^{\! n} . $$

This completes the proof.
\end{proof}

Next, we provide proofs of Theorems \ref{Thm: Minimax Relative l^infty-Risk} and \ref{Thm: Minimax l^1-Risk} using \propref{Prop: Upper Bound on MI}, Lemmata \ref{Lemma: Relative ell^infty-Loss Bound}, \ref{Lemma: Generalized Fano's Method}, \ref{Lemma: Upper Bound on Small Ball Probability}, and \ref{Lemma: Upper Bound on Small Ball Probability 2}, and the result in \cite[Theorem 5.2]{Chenetal2019}.

\subsection{Proof of \thmref{Thm: Minimax Relative l^infty-Risk}}
\label{Proof of Thm Minimax Relative l^infty-Risk}

\begin{proof}
We first prove the minimax upper bound. The inequality:
$$ \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]}} \leq \sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]} $$
holds trivially, because $\hat{\pi}_* \in \S_n$ in \eqref{Eq: Empirical Stat Dist} is an estimator for $\pi$ based on $Z$. To prove an upper bound on the extremal Bayes risk on the right hand side of this inequality, we define the event in \lemref{Lemma: Relative ell^infty-Loss Bound} as:
$$ A \triangleq \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\} $$
where $c_4 > 0$ is the universal constant from \lemref{Lemma: Relative ell^infty-Loss Bound}. Then, \eqref{Eq: Chen event} states that for any PDF $\pdf \in \pdfs$ and for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Lemma Restatement}
\P_{\pdf}\!\left(A\right) \geq 1 - \frac{c_5}{n^5}
\end{equation}
where $c_5 > 0$ is another universal constant from \lemref{Lemma: Relative ell^infty-Loss Bound}, and $\P_{\pdf}(\cdot)$ denotes the probability measure with respect to general (not necessarily uniform) $\pdf$. Hence, for every PDF $\pdf \in \pdfs$ and for all sufficiently large $n$, we have:
\begin{align}
\E_{\pdf}\!\left[\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right] & = \E_{\pdf}\!\left[\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\middle|A\right] \P_{\pdf}(A) + \E_{\pdf}\!\left[\frac{\left\|\hat{\pi}_* - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\middle|A^{c}\right] \P_{\pdf}(A^{c}) \nonumber \\
& \leq \frac{c_4}{\delta} \sqrt{\frac{\log(n)}{n p k}} + \frac{c_5}{n^4} \nonumber \\
& \leq \frac{2c_4}{\delta} \sqrt{\frac{\log(n)}{n p k}}
\label{Eq: Intermediate Extremal Risk Bound}
\end{align}
where the first equality uses the law of total expectation, the second inequality follows from \eqref{Eq: Lemma Restatement} and the facts that $\|\pi\|_{\infty} \geq 1/n$ and $\|\hat{\pi}_{*} - \pi\|_{\infty} \leq 1$, and the third inequality \eqref{Eq: Intermediate Extremal Risk Bound} holds for all sufficiently large $n$ because $k = \Theta(1)$. Letting $c_{15} = 2 c_4/(\delta \sqrt{p k})$ and substituting it into \eqref{Eq: Intermediate Extremal Risk Bound}, and then taking the supremum in \eqref{Eq: Intermediate Extremal Risk Bound} over all PDFs $\pdf \in \pdfs$ yields the desired upper bound in the theorem statement.

We next prove the information theoretic lower bound. Fix any $\varepsilon > 0$, and consider any sufficiently large $n \geq 2$ such that:
\begin{equation}
\label{Eq: Pre Lower Bound Condition Large n 1}
n \geq \max\!\left\{2 + \frac{1}{\varepsilon}, \left(\frac{2 }{\delta(1-\delta)}\right)^{\! 4/\varepsilon} \! , \, \exp\!\left(\frac{(1-\delta)^2 \!\left( 2 + \delta + \frac{1}{\delta}\right) k p + 4 \log(2)\delta^2}{\delta^2 \varepsilon}\right)\right\} .
\end{equation}
Then, observe that:
\begin{align}
\inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]}} & \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{I(\pi ; Z) + \log(2)}{\log(1/\L_{\infty}(t))}\right)} \nonumber \\
& \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{\frac{1}{2} n \log(n) + c(\delta,p,k) n + \log(2)}{\log(1/\L_{\infty}(t))}\right)} \nonumber \\
& \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{\frac{1}{2} n \log(n) + c(\delta,p,k) n + \log(2)}{(n-1)\log(1/t) - \log(2 / (\delta (1-\delta))) n}\right)} \nonumber \\
& = \sup_{t > 0}{ \, t \!\left(1 - \frac{1 + \frac{2 c(\delta,p,k)}{\log(n)} + \frac{\log(4)}{n \log(n)}}{\frac{2 (n-1)\log(1/t)}{n \log(n)} - \frac{2 \log(2 / (\delta (1-\delta)))}{\log(n)}}\right)} \nonumber \\
& \geq \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(1 - \frac{1 + \frac{2 c(\delta,p,k)}{\log(n)} + \frac{\log(4)}{n \log(n)}}{(1 + 2 \varepsilon) \! \left(1 - \frac{1}{n}\right) - \frac{2 \log(2 / (\delta (1-\delta)))}{\log(n)}}\right) \nonumber \\
& \geq \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(1 - \frac{1 + \frac{\varepsilon}{4}}{1 + \frac{\varepsilon}{2}}\right) \nonumber \\
& = \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(\frac{\varepsilon}{4 + 2 \varepsilon}\right)
\label{Eq: Pre Lower Bound 1}
\end{align}
where the first inequality follows from \eqref{Eq: Bayes Risk Lower Bound} and \lemref{Lemma: Generalized Fano's Method}, the second inequality follows from \propref{Prop: Upper Bound on MI} and we let:
\begin{equation}
\label{Eq: Constant in the MI Prop}
c(\delta,p,k) = \frac{(1-\delta)^2}{8 \delta^2} \left(2 + \delta + \frac{1}{\delta}\right) k p
\end{equation}
for clarity, the third inequality holds due to \lemref{Lemma: Upper Bound on Small Ball Probability}, the fifth inequality follows from setting $t = n^{-(1/2) - \varepsilon}$, and the sixth inequality follows from \eqref{Eq: Pre Lower Bound Condition Large n 1}, which implies the following bounds:
\begin{align}
\label{Eq: Detailed Large n condition 1}
n \geq \exp\!\left(\frac{(1-\delta)^2 \!\left( 2 + \delta + \frac{1}{\delta}\right) k p + 4 \log(2)\delta^2}{\delta^2 \varepsilon}\right) \quad & \Rightarrow \quad \frac{2 c(\delta,p,k)}{\log(n)} + \frac{\log(4)}{n \log(n)} \leq \frac{\varepsilon}{4} \, , \\
\label{Eq: Detailed Large n condition 2}
n \geq 2 + \frac{1}{\varepsilon} \quad & \Leftrightarrow \quad 1 - \frac{1}{n} \geq \frac{1 + \varepsilon}{1 + 2\varepsilon} \, ,  \\
n \geq \left(\frac{2}{\delta(1-\delta)}\right)^{\! 4/\varepsilon} \quad & \Leftrightarrow \quad \frac{2 \log\!\left(\frac{2 }{\delta (1-\delta)}\right)}{\log(n)} \leq \frac{\varepsilon}{2} \, . \nonumber
\end{align}

Now, let us define the constant:
$$ c_{16} = \max\!\left\{4 \log\!\left(\frac{2}{\delta(1 - \delta)}\right),\frac{(1-\delta)^2 \!\left( 2 + \delta + \frac{1}{\delta}\right) k p + 4 \log(2)\delta^2}{\delta^2}\right\} $$
and set $\varepsilon = c_{16}/\!\log(n)$. It is straightforward to verify that \eqref{Eq: Pre Lower Bound Condition Large n 1} is satisfied for this choice of $\varepsilon$ for all sufficiently large $n$. Moreover, since $\varepsilon \leq 1$ for all sufficiently large $n$, we see that \eqref{Eq: Pre Lower Bound 1} can be recast as:
$$ \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{P_{\alpha}}\!\left[\frac{\left\|\hat{\pi} - \pi\right\|_{\infty}}{\left\|\pi\right\|_{\infty}}\right]}} \geq \frac{c_{16}}{6 \log(n) \, n^{\frac{1}{2} + \frac{c_{16}}{\log(n)}}} = \left(\frac{c_{16}}{6 \exp(c_{16})}\right) \frac{1}{\log(n) \sqrt{n}} $$
for all sufficiently large $n$. Finally, letting $c_{14} = c_{16}/(6 \exp(c_{16}))$ yields the minimax lower bound in the theorem statement. This completes the proof.
\end{proof}

\subsection{Proof of \thmref{Thm: Minimax l^1-Risk}}
\label{Proof of Thm Minimax l^1-Risk}

Although the upper bound in \thmref{Thm: Minimax l^1-Risk} can be established using \lemref{Lemma: Relative ell^infty-Loss Bound}, we can remove an extra $\sqrt{\log(n)}$ factor by utilizing \cite[Theorem 5.2]{Chenetal2019} (also see \cite[Theorem 2]{NegahbanOhShah2017}). So, we present this result in the lemma below.

\begin{lemma}[Relative $\ell^{2}$-Loss Bound {\cite[Theorem 5.2]{Chenetal2019}}]
\label{Lemma: Relative ell^2-Loss Bound}
Suppose that $\delta = \Theta(1)$ and $p \geq c_{19} \log(n)/n$ for some sufficiently large constant $c_{19} > 0$ (which may depend on $\delta$). Then, there exists a constant $c_{20} > 0$ (which may depend on $\delta$) and a (universal) constant $c_{21} > 0$ such that for all sufficiently large $n \in \N$, we have:
$$ \P\!\left(\frac{\left\|\hat{\pi}_* - \pi\right\|_{2}}{\left\|\pi\right\|_{2}} \leq \frac{c_{20}}{\sqrt{n p k}} \, \middle| \, \alpha_1,\dots,\alpha_n\right) \geq 1 - \frac{c_{21}}{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$, and the estimator $\hat{\pi}_* \in \S_n$ is defined in \eqref{Eq: Empirical Stat Dist}.
\end{lemma}

This lemma is an analog of \lemref{Lemma: Relative ell^infty-Loss Bound}, but for $\ell^2$-norm
instead of $\ell^\infty$-norm. As remarked after \lemref{Lemma: Relative ell^infty-Loss Bound}, in contrast to this work, the conditioning on $\alpha_1,\dots,\alpha_n$ in \lemref{Lemma: Relative ell^2-Loss Bound} reflects the non-Bayesian scenario considered in \cite{Chenetal2019}
(where $\alpha_1,\dots,\alpha_n$ are deterministic). We next derive \thmref{Thm: Minimax l^1-Risk}.

\begin{proof}[Proof of \thmref{Thm: Minimax l^1-Risk}]
The proof strategy is identical to the proof of \thmref{Thm: Minimax Relative l^infty-Risk}, but we present the details again for completeness. We first prove the minimax upper bound. As before, the inequality:
$$ \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\left\|\hat{\pi} - \pi\right\|_{1}\right]}} \leq \sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\left\|\hat{\pi}_* - \pi\right\|_{1}\right]} $$
holds trivially. To prove an upper bound on the extremal Bayes risk on the right hand side of this inequality, we define the event in \lemref{Lemma: Relative ell^2-Loss Bound} as:
$$ A \triangleq \left\{\frac{\left\|\hat{\pi}_* - \pi\right\|_{2}}{\left\|\pi\right\|_{2}} \leq \frac{c_{20}}{\sqrt{n p k}} \right\} . $$
Then, after taking expectations in \lemref{Lemma: Relative ell^2-Loss Bound} with respect to the law of $\alpha_1,\dots,\alpha_n$, we get that for any PDF $\pdf \in \pdfs$ and for all sufficiently large $n \in \N$:
\begin{equation}
\label{Eq: Lemma Restatement 2}
\P_{P_{\alpha}}\!\left(A\right) \geq 1 - \frac{c_{21}}{n^5} \, .
\end{equation}
Hence, for every PDF $\pdf \in \pdfs$ and for all sufficiently large $n$, we have:
\begin{align}
\E_{\pdf}\!\left[\left\|\hat{\pi}_* - \pi\right\|_{1}\right] & = \E_{\pdf}\!\left[\left\|\hat{\pi}_* - \pi\right\|_{1}\middle|A\right] \P_{\pdf}(A) + \E_{\pdf}\!\left[\left\|\hat{\pi}_* - \pi\right\|_{1}\middle|A^{c}\right] \P_{\pdf}(A^{c}) \nonumber \\
& \leq \frac{c_{20}}{\delta \sqrt{n p k}} + \frac{2 c_{21}}{n^5} \nonumber \\
& \leq \frac{2 c_{20}}{\delta \sqrt{n p k}}
\label{Eq: Intermediate Extremal Risk Bound 2}
\end{align}
where the first equality uses the law of total expectation, the second inequality follows from \eqref{Eq: Lemma Restatement 2} and the facts that $\|\hat{\pi}_{*} - \pi\|_{1} \leq \|\hat{\pi}_{*}\|_{1} + \|\pi\|_{1} = 2$ (via the triangle inequality), and conditioned on $A$, we get:
$$ \left\|\hat{\pi}_{*} - \pi\right\|_{1} \leq \sqrt{n} \left\|\hat{\pi}_{*} - \pi\right\|_{2} \leq \frac{c_{20}}{\sqrt{p k}} \left\|\pi\right\|_2 \leq \frac{c_{20}}{\delta \sqrt{n p k}}  $$
which, in turn, uses the equivalence of $\ell^1$ and $\ell^2$-norms (via the Cauchy-Schwarz-Bunyakovsky inequality) and the simple bound $\|\pi\|_2 \leq 1/(\delta \sqrt{n})$ (due to \eqref{Eq: Canonically scaled merit parameters} and $\alpha_1,\dots,\alpha_n \in [\delta,1]$), and the third inequality \eqref{Eq: Intermediate Extremal Risk Bound 2} holds for all sufficiently large $n$ because $k = \Theta(1)$. Letting $c_{18} = 2 c_{20}/(\delta \sqrt{p k})$ and substituting it into \eqref{Eq: Intermediate Extremal Risk Bound 2}, and then taking the supremum in \eqref{Eq: Intermediate Extremal Risk Bound 2} over all PDFs $\pdf \in \pdfs$ yields the desired upper bound in the theorem statement.

We next prove the information theoretic lower bound. As before, fix any $\varepsilon > 0$, and consider any sufficiently large $n \geq 2$ such that:
\begin{equation}
\label{Eq: Pre Lower Bound Condition Large n}
n \geq \max\!\left\{2 + \frac{1}{\varepsilon}, \left(\frac{2 e}{1-\delta}\right)^{\! 4/\varepsilon} \! , \, \exp\!\left(\frac{(1-\delta)^2 \!\left( 2 + \delta + \frac{1}{\delta}\right) k p + 4 \log(2)\delta^2}{\delta^2 \varepsilon}\right)\right\} .
\end{equation}
Then, observe that:
\begin{align}
\inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{P_{\alpha}}\!\left[\left\|\hat{\pi} - \pi\right\|_{1}\right]}} & \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{I(\pi ; Z) + \log(2)}{\log(1/\L_{1}(t))}\right)} \nonumber \\
& \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{\frac{1}{2} n \log(n) + c(\delta,p,k) n + \log(2)}{\log(1/\L_{1}(t))}\right)} \nonumber \\
& \geq \sup_{t > 0}{ \, t \!\left(1 - \frac{\frac{1}{2} n \log(n) + c(\delta,p,k) n + \log(2)}{(n-1)\log(1/t) - \log(2 e / (1-\delta)) n}\right)} \nonumber \\
& = \sup_{t > 0}{ \, t \!\left(1 - \frac{1 + \frac{2 c(\delta,p,k)}{\log(n)} + \frac{\log(4)}{n \log(n)}}{\frac{2 (n-1)\log(1/t)}{n \log(n)} - \frac{2 \log(2 e / (1-\delta))}{\log(n)}}\right)} \nonumber \\
& \geq \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(1 - \frac{1 + \frac{2 c(\delta,p,k)}{\log(n)} + \frac{\log(4)}{n \log(n)}}{(1 + 2 \varepsilon) \! \left(1 - \frac{1}{n}\right) - \frac{2 \log(2 e / (1-\delta))}{\log(n)}}\right) \nonumber \\
& \geq \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(1 - \frac{1 + \frac{\varepsilon}{4}}{1 + \frac{\varepsilon}{2}}\right) \nonumber \\
& = \frac{1}{n^{\frac{1}{2} + \varepsilon}} \!\left(\frac{\varepsilon}{4 + 2 \varepsilon}\right)
\label{Eq: Pre Lower Bound}
\end{align}
where the first inequality follows from \eqref{Eq: Bayes Risk Lower Bound}, \lemref{Lemma: Generalized Fano's Method}, and the fact that $\|\pi\|_1 = 1$, the second inequality follows from \propref{Prop: Upper Bound on MI} with $c(\delta,p,k)$ as defined in \eqref{Eq: Constant in the MI Prop}, the third inequality holds due to the following consequence of \lemref{Lemma: Upper Bound on Small Ball Probability 2}:

$$ \forall t > 0, \enspace \L_{1}(t) \leq \left(\frac{2 e}{1-\delta}\right)^{\! n} t^{n-1} \, , $$
the fifth inequality follows from setting $t = n^{-(1/2) - \varepsilon}$, and the sixth inequality follows from \eqref{Eq: Pre Lower Bound Condition Large n}, which implies the bounds \eqref{Eq: Detailed Large n condition 1}, \eqref{Eq: Detailed Large n condition 2}, and:
$$ n \geq \left(\frac{2 e}{1-\delta}\right)^{\! 4/\varepsilon} \quad \Leftrightarrow \quad \frac{2 \log\!\left(\frac{2 e}{1-\delta}\right)}{\log(n)} \leq \frac{\varepsilon}{2} \, . $$

Now, let us define the constant:
$$ c_{22} = \max\!\left\{4 \log\!\left(\frac{2 e}{1 - \delta}\right),\frac{(1-\delta)^2 \!\left( 2 + \delta + \frac{1}{\delta}\right) k p + 4 \log(2)\delta^2}{\delta^2}\right\} $$
and set $\varepsilon = c_{22}/\!\log(n)$. As mentioned earlier, it is straightforward to verify that \eqref{Eq: Pre Lower Bound Condition Large n} is satisfied for this choice of $\varepsilon$ for all sufficiently large $n$. Finally, as before, we can rewrite \eqref{Eq: Pre Lower Bound} as:
$$ \inf_{\hat{\pi}}{\sup_{\pdf \in \pdfs}{\E_{\pdf}\!\left[\left\|\hat{\pi} - \pi\right\|_{1}\right]}} \geq \left(\frac{c_{22}}{6 \exp(c_{22})}\right) \frac{1}{\log(n) \sqrt{n}} $$
for all sufficiently large $n$. Letting $c_{17} = c_{22}/(6 \exp(c_{22}))$ yields the minimax lower bound in the theorem statement. This proves the theorem.
\end{proof}

config: arxiv


TITLE: Are the ring of power series and the ring of germs of holomorphic functions catenary?
QUESTION [3 upvotes]: I am wondering if the following rings are catenary:

If $k$ is a field, is the ring of formal power series $k[[X_1,\dots,X_n]]$ catenary?
Is the ring of complex power series with a non-zero radius of convergence  $\Bbb C\{X_1,\dots,X_n\}$ (id est the ring of germs of holomorphic functions at zero) a catenary ring?

REPLY [10 votes]: Yes, they are regular (the maximal ideal is generated by a number of elements equal to its dimension) and therefore Cohen-Macaulay (Matsumura, Theorem 17.8). And a Cohen Macaulay ring is catenary (Matsumura, Theorem 17.4).
Matsumura, Commutative Ring Theory, CUP, 1986


TITLE: Proof Verification: C closed, convex, symmetric in Banach space X and $\cup_{n \in N \setminus 0} n.C= X$ then $B_\epsilon(0) \in C $.
QUESTION [0 upvotes]: I have an outline of the proof of this which I've expanded (correctly or otherwise) below, I'd appreciate feedback on it. (I think that C has to be closed in order to assert that $\cup_{n \in N \setminus 0} n.C= X $, but I'm not sure about that)
$\cup_{n \in N \setminus 0} n.C= X $, and from the Baire category theorem, X is not the countable union of nowhere dense sets, so that at least one of the n.C must contain some open set.
Since open sets are preserved under scaling, then C too must contain an open set, and therefore within it some open ball $B_\epsilon(x) \in C $.
Any vector $z \in B_\epsilon(-x) \subset X$ satisfies $||z – (-x)||  = ||-z - x|| < \epsilon$. So $-z \in B_\epsilon(x) \subset C$.
Since C is symmetric then $z = -(-z) \in C$ and therefore $B_\epsilon(-x) \subset C$.
If $w \in B_\epsilon(0)$  then $||w|| < \epsilon $
Let $z_1 = w + x$, so that $z_1 - x = w$, then $||z_1 – x|| < \epsilon$ and so $z_1 \in  B_\epsilon(x)$. Similarly, $z_2 \in  B_\epsilon(-x)$
But $w = z_1 + (z_2 – z_1)/2$ and so by the convexity of $C$, $w \in C$ and therefore $B_\epsilon(0) \subset C$.

REPLY [1 votes]: In order to invoke Baire you have to assume the closedness of $C$. Otherwise your proof is fine.


TITLE: If $f(x)$ is continuous and bounded on $(0,1)$, is it uniformly continuous on $(0,1)$?
QUESTION [4 upvotes]: I have a question which is:

If $f(x)$ is continuous and bounded on $(0,1)$ is it uniformly continuous on $(0,1)$?
  And how does this change if $f(x)$ is also monotonic?

I have been told the that unless it's monotonic then the it is not uniformly continuous. But I don't see why...
Can someone please help me understand this? Thanks :)

REPLY [8 votes]: Let me add a little to Arturo's answer.
First: how do you approach to problem?
You may have already known that a continuous function on any compact space is necessarily uniformly continuous. You may also know that a closed interval is a compact space. (Or you may just know that a continuous function on a closed interval is necessarily uniformly continuous.)
Therefore, if your continuous function $f:(0,1)\to\mathbb{R}$ admits limits
$$ f_0 = \lim_{x\to 0} f(x) \qquad f_1 = \lim_{x\to 1} f(x) $$
then defining the function
$$ \tilde{f} :[0,1] \to\mathbb{R} $$
by $\tilde{f}(0) = f_0$, $\tilde{f}(1) = f_1$ and $\tilde{f}(x) = f(x)$ otherwise you get a continuous function on $[0,1]$, and so $\tilde{f}$ must be uniformly continuous. And so $f$, being the restriction of $\tilde{f}$, must also be uniformly continuous.
This tells us that if you want to look for possible problems, you must consider the case where one of the limits, say $\lim_{x\to 0}f(x)$, fail to exist.
How can the limit fail to exist? There are basically two ways: either the $\limsup$ or the $\liminf$ do not exist (in which case the function is unbounded, and which you ruled out by assumption), or the $\limsup$ and $\liminf$ both exist but do not equal one another. Using the definition of the $\limsup$ and $\liminf$ you then "immediately see" that the oscillation that Arturo mentioned can cause problems to uniform continuity.
Note that this also explains the remark someone else made to you about monotonic functions: if you assume that $f$ is monotonic near $0$ and $1$, then you can use the fact that for bounded monotonic functions, the $\lim$ must exist, to conclude that $f$ extends to a continuous function on $[0,1]$ (like above) and therefore must be uniformly continuous.


TITLE: Cardinality of the set of points on a circle whose coordinates are constructable is $\aleph_0$
QUESTION [0 upvotes]: Let $C=${$(x,y)\in\mathbb R^{2}|(x-a)^{2}+(y-b)^{2}=r^{2}$} be a circle of radius $r>1$ and centre $(a,b)$ where $a,b,r$ are all constructible. We want to show that the cardinality of the set of points on $C$ whose coordinates are constructible is $\aleph_0$
I do not have a good idea on how to approach this question. Is it enough that I show any coordinate with constructable numbers on the 2d plane is $\aleph_0$? Or should I show a bijection between the natural numbers and the set of points on C who's coordinates are constructable? If so, what bijection should I use? And I also do not know what is the use of the information that $a,b,r$ are constructable and $r<1$

REPLY [1 votes]: I would follow the first approach, to show that the set of constructible points is $\aleph_0$.  At any stage in a construction, there are only finitely many points that can be constructed.  The number of stages of a construction is also finite.  The set of constructible points is then a countable union of finite sets.


TITLE: Find all $(a , b , c)$ such that $\frac{(a - b)(b - c)(c - a) + 4}{2}$ is power of $2016$.
QUESTION [1 upvotes]: Find all $(a , b , c)$ such that $\frac{(a - b)(b - c)(c - a) + 4}{2}$ is power of $2016$. (Power of $2016$ means the number can be written in the form $2016^n$ for some non-negative $n$.
I don’t know what to do. Should I factorize $2016$ and consider by mod $32$ , mod $9$ and mod $7$?
Can anyone give me some hint please. Thank you!

REPLY [3 votes]: Hints: First, let $x = b-a$ and $y = c-b$. Then, $(a-b)(b-c)(c-a) = xy(x+y)$.
We want $\dfrac{xy(x+y)+4}{2} = 2016^n$, i.e. $xy(x+y) = 2\cdot 2016^n-4$ for some integer $n \ge 0$.
If $n \ge 1$, then we need $xy(x+y) \equiv 5 \pmod{9}$. Is this possible? You have quite a few cases to check, but remember that none of $x$, $y$, and $x+y$ can be $0 \pmod{3}$.
If $n = 0$, then we need $xy(x+y) = -2$. This should be easy enough to solve.


TITLE: Prove that Normal $\implies$ Regular $\implies T_2 \implies T_1 \implies T_0$
QUESTION [1 upvotes]: Prove that Normal $\implies$ Regular $\implies T_2 \implies T_1 \implies T_0$

Proof: Let $\mathscr{X}$ be a topological space such that, for each $x \in \mathscr{X}$, the set $\{x\}$ is closed. We will show that if $\mathscr{X}$ is a normal space this implies $\mathscr{X}$ is a regular space. Suppose $\mathscr{X}$ is a normal space. By Definition 3.24 this means for every pair of disjoint closed sets $C, D \subseteq \mathscr{X}$, there are disjoint open sets $U$ and $V$ such that $C \subseteq U$ and $D \subseteq V$. Then let $C \subseteq \mathscr{X}$ and $D \subseteq \mathscr{X}$ be a pair of disjoint closed sets and let $U$ and $V$ be disjoint open sets such that $C \subseteq U$ and $D\subseteq V$. Since $C$ and $D$ are disjoint closed sets, we know that there exists some $x\in \mathscr{X}$ such that $x\in C$ but $x \notin D$. Let $y\in C$ such that the set $\{y\}$ is closed. Since $C$ and $D$ are disjoint closed sets we know that $y\in C$ implies that $y\notin D$. This implies that $y\in U$ but $y\notin V$. But by Definition 3.24 we have that $D\subseteq V$. Therefore, we have shown that $\mathscr{X}$ is a regular space because $y\in U$ and $D\subseteq V$, while for the closed set $D\subseteq \mathscr{X}, y\notin D$.
We will show that Regular$\,\Rightarrow T_{2}$. Suppose $\mathscr{X}$ is a regular space. Let $E\subseteq \mathscr{X}$ be a closed set such that for every point $z\notin E$, there are disjoint open sets $Q$ and $R$ such that $z\in Q$ and $E\subseteq R$. Let $b,c \in \mathscr{X}$ be a pair of disjoint points such that $b\in E$ and $c\notin E$. Let $Q$ and $R$ be disjoint open sets such that $c\in Q$ and $E\subseteq R$. Since $b\in E$, this implies $b\in R$. But since $Q$ and $R$ are disjoint open sets we know $b\notin Q$. But we have that $c\in Q$. Therefore, we have that $b\in R$ and $c\in Q$ by Definition 3.22 means that $\mathscr{X}$ is $T_{2}$, or a Hausdorff space.
We will show $T_{2}\,\Rightarrow T_{1}$. Suppose $\mathscr{X}$ is a $T_{2}$ space. Let $x,y \in \mathscr{X}$ be disjoint points such that, for disjoint open sets $U$ and $V$, $x\in U$ and $y\in V$. Since $U$ and $V$ are disjoint we know $x\in U$ implies $x\notin V$ and $y\in V$ implies $y\notin U$. By Definition 3.21, this means $\mathscr{X}$ is $T_{1}$.
We will show that $T_{1}\,\Rightarrow T_{0}$. Suppose $\mathscr{X}$ is $T_{1}$. Let $x,y\in \mathscr{X}$ be a pair of disjoint points such that $x\in U$ but $y\notin U$, and $y\in V$ but $x\notin V$. By Definition 3.20, we have $\mathscr{X}$ is $T_{0}$.
I believe the problem in this proof is where I show a regular space implies the space is $T_{2}$. I am looking for proof verification.
Definitions used for proof

REPLY [3 votes]: It's quite verbose for normal/regular/Hausdorff. Also the structure is wrong:
E.g.: Let $X$ be a normal space. To see it's regular note that in a normal space all sets $\{x\}$ are closed (and this is part of the requirements for regular as well). Let $x$ be a point not in the closed set $C$. Then $\{x\}$ and $C$ are disjoint closed sets in the normal space $X$, so they can be separated by disjoint open sets. So $X$ is regular.
It's really simple: normal implies regular because points are closed (in your definition), and so separating two disjoint closed sets implies separating a point disjoint from a closed sets, which implies separating two points ($T_2$) as well, it's all a matter of choosing $\{x\}$ as closed sets in the regular or normal definition. Your proofs of $T_2$ implies $T_1$ implies $T_0$ are OK.


TITLE: Confusion concerning a theorem *about* propositional logic
QUESTION [1 upvotes]: The first theorem is called a “derived rule” (of inference) because it involves a hypothesis, $T$, which can be any axiom or previous theorem. Such a derived rule of inference is a theorem about rather than in the implicational calculus, but it provides a recipe to shorten subsequent proofs. Specifically, theorem 1.12 shows a derivation of $S\implies T$ from $T$ and axiom $P1$...
1.12 Theorem (derived rule): For each well-formed formula $S$ and for each theorem $T$, the implication $S\implies T$ is a theorem: $P1,\,T\vdash S\implies T$.
proof:
\begin{align*}
&\vdash T\text{ hypothesis}\\
&\vdash T\implies(S\implies T)\text{ axiom P1}\\
&\vdash S\implies T\text{ detachment}
\end{align*}

i am not sure I understand how this is a theorem about the implicational calculus, and what that would mean exactly. aren't theorems things that we derive using the implicational calculus itself (so how can they be about it)?
as per my understanding, a rule of inference tells us that when we have theorems of a specific form we can infer another theorem, which we would call a conclusion. comparing this derived rule of inference to usual ones, it seems to me that the difference is that we now have a well formed formula that we don't suppose is a theorem in the equation.
would this be the reason why the stated theorem is about, not in, the implicational calculus? if yes, why would this make the theorem about the calculus? especially since, as i said bove, we are using an axiom and a rule of inference of the calculus to prove it.

REPLY [1 votes]: "as per my understanding, a rule of inference tells us that when we have theorems of a specific form we can infer another theorem, which we would call a conclusion. comparing this derived rule of inference to usual ones, it seems to me that the difference is that we now have a well formed formula that we don't suppose is a theorem in the equation."
The hypothesis and the sequent (right hand side of the $\vdash$) both get used to refer to well-formed formulas which are not supposed as theorems, usually at least.  Note, I don't think 'S⟹T' is a well-formed formula of your calculus, I would guess it's '(S⟹T)', though it could also be '(S)⟹(T)' similar to the pattern in Kleene (Introduction to Metamathematics) or Stoll's book (Set Theory and Logic).
However, if something is true for well-formed formulas which may not be theorems, then it is also true for theorems.  Falsity implies truth, and truth implies true.  So, the meta-theorem does tell you something about theorems in the calculus, insofar it can be said to 'tell' anything.  Here it implies that for any theorem T in the calculus, (S⟹T) is also true, no matter whether S is a theorem or not.
To perhaps try to put that into your notation scheme, it might look something like this:
{ P1 , ($\vdash$T) } ⊢ [ S ⟹ ($\vdash$T) ].
Also, if anyone were to ask us "how many theorems are there in propositional calculus?"  We could easily and conclusively respond that there is no possible limit that we can write.  Even if infinity isn't a valid concept, anytime someone presented us with a theorem, we could respond that well 'S' could be a theorem too. But, 'S' is completely arbitrary and not fixed by any of the premises.  So, there's always a way to produce more theorems even if infinity does not exist... unless we run out of physical material to do so.
I can't say this answers all of your questions, but perhaps it's at least something.


TITLE: Proving a piece-wise function is continuous at a point
QUESTION [0 upvotes]: I have the function:
$$f(x) = \begin{cases}  \ \ x \quad \text{if} \ x\not\in\Bbb{Q} \\ 0 \quad \text{if} \ x\in\Bbb{Q}\end{cases}$$
How do i prove this function is continous at $x=0$. I cannot apply the definition is seems since $f(x)-f(c)$ has two "forms" that depend whether $x$ is rational or not. Any hints greatly appriciated

REPLY [0 votes]: Hint:
By the defintion of $f$, $|f(x)-f(0)|\le|x-0|$ and the $\delta-\epsilon$ proof will work with $\delta=\epsilon$.


TITLE: Simple Probability Formula and Convergence
QUESTION [1 upvotes]: I have the probability of an event A defined as $P(A) = \frac{N_{a}}{N}$.
In order to understand precisely this concept, i hypothesized that the meaning of this formula is :
,

as i repeat the observation of the event A in practically the same
  conditions, i get that, as $i$ grows, $\frac{\sum N_{a_{i}}}{\sum N_{i}}\Rightarrow  \frac{N_{a}}{N}$, where $N_{a_{i}}$ is a specific occurrence of event
  A.

Is it correct ?

REPLY [2 votes]: You mention a limiting process. My guess is you are looking at the
so-called 'frequentist' formulation of probability.
This formulation of probability requires a repeatable experiment.
Suppose you are tossing a fair coin and are interested in the probability
of getting a Head. For simplicity we denote Heads as $1$'s and Tails as $0$'s
At the $n$th toss of the coin we get a number $T_i$ which is $0$ of $1.$
After each toss, we look at the number $A_n$
of $1$'s up through the $n$th roll and the ratio $R_n = A_n/n$
which is the proportion of $1$'s up through
the $n$th roll.
If I simulate 4000 tosses of such a coin using a computer, then I might get
a data table with the first 10 rows looking like this:
   n t a         r
   1 1 1 1.0000000
   2 1 2 1.0000000
   3 0 2 0.6666667
   4 0 2 0.5000000
   5 0 2 0.4000000
   6 1 3 0.5000000
   7 0 3 0.4285714
   8 0 3 0.3750000
   9 1 4 0.4444444
  10 1 5 0.5000000

I happened to get Heads ($1$'s) on tosses 1, 2, 6, 9, and 10.
Up to the 5th roll I had two $1$s for a ratio $R_5 = 0.4$ and
up to the 10th roll I had five $1$s for a ratio $R_{10} = 0.5.$
At the beginning, the ratios $R_n$ fluctuate greatly.
However, if we look at the last ten entries in the data table,
here is what I see:
     n t   a         r
  3991 0 2019 0.5058882
  3992 0 2019 0.5057615
  3993 0 2019 0.5056349
  3994 1 2020 0.5057586
  3995 1 2021 0.5058824
  3996 1 2022 0.5060060
  3997 1 2023 0.5061296
  3998 0 2023 0.5060030
  3999 1 2024 0.5061265
  4000 1 2025 0.5062500

The values of $R_n$ have stabilized very near to $1/2$, the probability of
getting Heads. A plot of the ratio $R_n$ against $n$ is shown below.

Because coin tossing is a random process, there is no guarantee what
value $R_{4000}$ will take. A theorem you will likely see a little later
in your course, called the Law of Large Numbers, says $R_n$ tends to
get ever closer to $1/2$ as $n$ increases. Usually, by about $n = 4000$
we get $R_n$ in the range $0.5 \pm 0.016.$
(Somewhere around $n = 300$
we happened to get a lot of Tails, but eventually those 'extra'
Tails
were balanced by the large patches of results where Heads and Tails
happened to be nearly equal. The blue line will often behave
'badly', with a lot of variability, near the left of the graph where $n$ is small. Certainly, the coin is not consciously
keeping track to compensate for patches of strange behavior early on.
It's called the law of large numbers because random anomalies early
on get 'swamped out' by huge numbers of tosses later on.)
However, this is not a
deterministic limiting process.  For the sequence $D_n = \frac{n+5}{2n-7}$
we know exactly what $D_n$ will be for each value of $n$ and we can write
$\lim_{n \rightarrow \infty} D_n = 1/2,$ without mentioning anything about
probability.
For the coin-tossing limit, we sometimes write
$\text{plim}_{n \rightarrow \infty} R_n = 1/2$ and say "$R_n$
converges in probability to $1/2.$" But that expression
needs a careful definition before we can prove theorems about it.


TITLE: Does all function's domain stay the same\expands as we derivate them?
QUESTION [2 upvotes]: Lets define a funciton $f(x)$ with a domain of, lets say $a>x>b$. If I derivate this function, it's domain will always stay the same or expand? Or it can be "reduced"? Is that mean that $f'(x)$ must be defined in the following domain?:
$$g>x>t$$ $$g \leq a$$  $$t \geq b$$

REPLY [4 votes]: Consider, for example, the function $f(x)=\sqrt[3]x$ on $\Bbb R$ for an example in which the derivative's domain is not the same as the original function's domain.
Recall that the definition of the derivative is $$f'(x):=\lim_{h\to 0}\frac{f(x+h)-f(x)}h,$$ if this limit exists. In order for $f'(x)$ to make any sense, $f(x)$ has to make sense first, i.e.: $x$ must be in the domain of $f.$


TITLE: Area under the curve
QUESTION [2 upvotes]: suppose we have graph of $\sin(x)$ and a ellipse say $\frac{x^2}{10}+\frac{y^2}{2}=1$ it comes like following

now when we intregrate $\int_{0}^{2\pi}\sin(x)dx$ it comes out to be zero , because area above $x$-axis is equal to area below $x$-axis so therefore when we compute area of ellipse it should also be equal to zero ? why is't it taken to be zero?

REPLY [2 votes]: As The Chaz said, computing the integral gives a signed integral; so, since your ellipse is centered, the result is zero. If you move the center of the same ellipse up or down, you will get a different result.


TITLE: Referencing "unpublished" works
QUESTION [1 upvotes]: On arXiv I found this paper, the subject of which I am interested in. It was submitted to arXiv on 24 Dec 1998, so some years ago. However, I cannot find this publication in any journal from this date onwards. So, what is the credibility of this paper? I realise I could work through it properly and form my own opinion, but who cares about my opinion, especially if I were to reference it. Is it okay to reference a paper on arXiv even when it has not been published in a journal?

REPLY [0 votes]: I was not aware until just now, but this is a pretty good discussion on Math Overflow.


TITLE: Question about the definition of the composition of relations
QUESTION [0 upvotes]: I am slightly confused about following definition:

Suppose R is a relation from A to B and S is a relation from B to C.
  Then the composition of S and R is the relation S ◦ R from A to C
  defined as follows:
  $$S \circ R = \{(a,c) \in A \times C \mid \exists b \in B((a,b) \in R
\text{ and } (b,c) \in S\}$$

I struggle to explain my question in words, hence I will give you an example to show where I'm confused.
Case 1
Suppose
$A = \{a_1,a_2,a_3\}$, $B = \{b_1,b_2,b_3\}$, $C = \{c_1,c_2,c_3\}$
$R$ is a relation from $A$ to $B$, and $D$ is a relation from $B$ to $C$
$R = \{(a_1,b_1)\}$ and $D = \{(b_1,c_3)\}$
I'm pretty sure that in this case, $R \circ D = \{(a_1,c_3)\}$
But now consider slightly different example:
Case 2
$A = \{a_1,a_2,a_3\}$, $B = \{b_1,b_2,b_3\}$, $C = \{c_1,c_2,c_3\}$
$R$ is a relation from $A$ to $B$, and $D$ is a relation from $B$ to $C$
$R = \{(a_1,b_2)\}$ and $D = \{(b_1,c_3)\}$ (Note that each subsets of $R$ and $D$ now have $b$'s with different indices)
In this case, is $R \circ D = \{(a_1,c_3)\}$ or $R \circ D = \emptyset$ ?

REPLY [0 votes]: You are correct.
The composite relation is not always non-empty.
You have to have the range of $D$ to be a subset of the domain of $ R$ in order for  $RoD$ to be non-empty.


TITLE: Expected number of flips for $THT$ sequence
QUESTION [0 upvotes]: A Coin with Probability of heads $p$ is continously flipped till the sequence $THT$ occurs.Find the Expected number of coin flips.
My Try: if $X$ is number of coin flips till  $THT$ occurs, $X$ can take values of $3$, $4$,$5$,$\cdots$
$$P(X=3)=(1-p)^2p$$
For $X=4$ the Sample space is $HTHT$ or $TTHT$
$$P(X=4)=(1-p)^2p$$
For $X=5$ the Sample space is $HHTHT$ or $HTTHT$ or $TTTHT$
$$P(X=5)=(p^2-p+1)(1-p)^2p$$ But i feel the process becomes tedious as $X$ increases. Please suggest me any hint...

REPLY [2 votes]: Consider the set of prefixes of the word $tht$, that is, the set $\{o,t,th,tht\}$ where $o$ denotes the empty prefix. For every prefix $w$ let $m_w$ denote the mean number of draws needed to produce the word $tht$ starting from a sequence of draws which ends by $w$ but not by any longer prefix.
Thus, $m_{tht}=0$ and the question is to compute $m_o$. Let $q=1-p$.
The usual one-step decomposition yields the identities $$
m_o=1+pm_o+qm_t,\quad m_t=1+pm_{th}+qm_t,\quad m_{th}=1+pm_o,
$$
and solving this affine system yields
$$
m_o=\frac1q+\frac1{pq^2}.
$$
An approach to compute the mean time necessary to produce any word $w$ in terms of the structure of its prefixes (and an explanation of the formula above) is in the book DNA, Words And Models by Robin, Rodolphe, and Schbath. The authors explain why this mean time is the sum of the inverses of the probabilities of each prefix of $w$ which is also a suffix of $w$. When $w=tht$, these prefixes-suffixes are $tht$ and $t$, whose probabilities are $pq^2$ and $q$ respectively, hence the formula above.


TITLE: Bound of expectation of product
QUESTION [0 upvotes]: We know the Cauchy–Schwarz inequality,
\begin{align}
(E(XY))^2\le E(X^2)E(Y^2).
\end{align}
I am wodering whether the following holds for positive random variables $X$ and $Y$
\begin{align}
(E(X^mY^n))^2\le E(X^{m+n})E(Y^{m+n}).
\end{align}
This is just my guess, and the Cauchy–Schwarz inequality is special case of above with $m=n=1$.

REPLY [3 votes]: Taking $X=c$ and $Y$ following a standard lognormal distribution, it yields
$$c^{2m}\exp(m^2)=c^{2m}(\mathbb{E}[Y^n])^2\leq c^{m+n}\mathbb{E}[Y^{m+n}]=c^{m+n}\exp\bigl((m+n)^2/2\bigr).$$
That is,
$$c^{m-n}\leq\exp(n^{2}/2+mn-m^{2}/2)$$
should hold with any $c$. Note that RHS is fixed for any $m,n$, however, for any $m> n$, LHS can go to infinity as $c\to\infty$; and for any $m<n$, LHS can go to infinity as $c\to0$.
Therefore, it must be $m=n$. But in that case $$(\mathbb{E}[X^{n}Y^{n}])^{2}\leq \mathbb{E}[X^{2n}]\mathbb{E}[Y^{2n}]$$ is just a Cauchy–Schwarz inequality for $X^{n}$ and $Y^{n}$.

As pointed out by stochasticboy321, the issue of this inequality is
a lack of homogeneity when $m\neq n$: even if the relationship holds for $X,Y$, it cannot hold for $cX,Y$ either as $c\to0$ or as $c\to\infty$.