text:
\begin{document}

\title{$\F$-Saturation Games}

\author[J. D. Lee]{Jonathan D. Lee}
\address{Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3\thinspace0WB, UK}
\email{j.d.lee@dpmms.cam.ac.uk}

\author[A. Riet]{Ago-Erik Riet}
\address{Institute of Mathematics, University of Tartu, Juhan Liivi 2, 50409 Tartu, Estonia}
\email{ago-erik.riet@ut.ee}
\thanks{The research was partially supported by institutional research funding IUT20-57 of the Estonian Ministry of Education and Research.}

\date{\today}
\subjclass[2010]{Primary 60K35; Secondary 60C05}

\begin{abstract}
We study \emph{$\F$-saturation games}, first introduced by F\"uredi, Reimer and Seress~\cite{FuReSe} in 1991, and named as such by West~\cite{We}. The main question is to determine the length of the game whilst avoiding various classes of graph, playing on a large complete graph. We show lower bounds on the length of path-avoiding games, and more precise results for short paths. We show sharp results for the tree avoiding game and the star avoiding game.
\end{abstract}

\maketitle

\section{Introduction}

For $\F$ a family of graphs, we say a graph $G$ is \emph{$\F$-free} if $G$ contains no member of $\F$ as a subgraph. We say $G\subset H$ is a \emph{$\F$-saturated} subgraph of $H$ if $G$ is a maximal $\F$-free subgraph of $H$. For a discussion of saturated graphs see for example Bollob\'as~\cite{Bo}. Take $H$ a graph, $|H| = n$, and let $\F$ be a family of graphs. Following the definition of the triangle free game of F\"uredi, Reimer and Seress~\cite{FuReSe}, and building on the notation of West\cite{We}, we define the \emph{$\F$-saturation game} as follows.

We have two players, \emph{Prolonger} and \emph{Shortener}, who we take to be male and female respectively. We define a graph process $\G_i$. We initially set $\G_0 = E_n$, the empty graph on $n$ vertices. The process ends at time $t^*$ if $G_{t^*}$ is a $\F$-saturated subgraph of $H$. Otherwise, at time $2t$ , Prolonger chooses an edge $uv \in H \backslash \G_{2t}$ and $\G_{2t}\cup uv$ is $\F$-free, and $\G_{2t+1} = G_{2t} \cup uv$. Similarly, at time $2t+1$ Shortener chooses an edge from $H\backslash \G_{2t+1}$ to add, such that the process remains $\F$-free. Prolonger's goal is to maximise $t^*$, whilst Shortener wishes to minimise $t^*$. Our results will not depend on which of the two players moves first, and so we refer to this game as $\G(H;\F)$. We say the value of $t^*$ under optimal play by both Prolonger and Shortener is the \emph{score} or \emph{game saturation number} of $\G(H;\F)$, denoted by $\textbf{Sat}(\G)$ or simply $\G$ provided there can be no confusion. When only one graph is excluded, we write $\G(H;F) := \G(H;\{F\})$.

F\"uredi, Reimer and Seress~\cite{FuReSe} concentrate on the game $\G(K_n,K_3)$. They exhibit
a strategy for Prolonger which demonstrates that $\G(K_n,K_3) \geq (\frac{1}{2} + o(1))n \log_2 n$. They attribute to Erd\H os a lost proof that Shortener has a strategy showing $\G(K_n,K_3) \leq \frac{n^2}{5}$. Bir\'o, Horn and Wildstrom~\cite{BiHoWi} show that $\G(K_n,K_3) \leq \frac{9n^2}{50}$, by showing that Shortener is able to cover almost all vertices with disjoint cycles of length 5, and that the number of edges between two such cycles is bounded by 18.

Motivated by these results, we study the case where $\F = \{P_k\}$, $\F$ is the class of all trees on $k$ vertices or $\F = \{K_{1,k}\}$.

\section{Our results}

As is standard, for any $k \in \mathbb{N}$ we denote a path on $k$ vertices by $P_k$. To illustrate the difficulties encountered by Prolonger, we first study a variant where on his turn, he is permitted to decline to pick any edge, and set $\G_{2t+1} = \G_{2t}$. Since Shortener is still required to add edges, this process will still become $\F$-saturated and thus have a score as defined for the $\F$-saturation game. We will refer to this game as $\G_{-P}$. Since we have given Prolonger additional options, it is clear that any strategy he might use in $\G$ is valid in $\G_{-P}$, and so we have that $\G_{-P}(H;\F) \geq \G(H;\F)$

\begin{theorem}\label{G_P-}
For all $n \geq k$, we have $\frac{1}{4}n(k - 2) \leq \G_{-P}(K_n; P_k) \leq \frac{1}{2}n(k-1)$.
\end{theorem}

Returning to $\G(K_n, P_k)$, we have results only for small values of $k$. Whilst these results are quite precise, they are predicated on a complete categorisation of the connected $P_k$-saturated graphs. Obtaining results of this precision for larger $k$ thus seems challenging. Recently Carraher, Kinnersley, Reiniger and West \cite{Ca} made us aware of another proof, only in the $P_4$ case, which gives a slight improvement on the additive constants.
\begin{theorem}\label{P4-bound}
For all $n > 0$, we have $\frac{4}{5}n-\frac{8}{5} \leq \G(K_n, P_4) \leq \frac{4}{5}n + 1$.
\end{theorem}
\begin{theorem}\label{P5-bound}
For all $n > 0$, we have $n-1 \leq \G(K_n,P_5) \leq n+2$.
\end{theorem}

For larger classes of graphs, we have substantially precise bounds for all $k$. We define $\T_k$ to be the family of all trees on $k$ vertices.
\begin{theorem}\label{Tree-bound}
For all $n$, $k$, we have:
\[\begin{array}{lll} \\
\G(K_n, \mathcal{T}_k) &
  \begin{array}{l}
  = \lfloor\frac{n}{k-1}\rfloor {\binom{k-1}{2}} + {\binom{n-(k-1)\lfloor\frac{n}{k-1}\rfloor}{2}}
  \end{array}
& n \not\equiv 1 \mod (k-1)\\
\G(K_n, \mathcal{T}_k) &
  \begin{array}{l}
  \leq \frac{n}{k-1} {\binom{k-1}{2}} \\
  \geq \frac{n}{k-1} {\binom{k-1}{2}} - (k-3)
  \end{array}
& n \equiv 1 \mod (k-1),\; k \geq 3.\\
\end{array}\]
\end{theorem}

Carraher, Kinnersley, Reiniger and West \cite{Ca} consider the case $n=k$ of the preceding Theorem and determine the precise score. In fact, the primary constraint of $\T_k$ saturation is to exclude a $K_{1,k-1}$. If only this graph is excluded, we have a precise bound:
\begin{theorem}\label{Star-bound}
For $n \geq (3k+1)(k-2)$, we have the following bounds:
\[
\frac{1}{2}kn \geq \G(K_n, K_{1,k+1}) \geq \frac{1}{2}\left(kn-2(k-1)\right).
\]
\end{theorem}

\section{Avoiding \texorpdfstring{$P_k$}{P\_k} in \texorpdfstring{$\G_{-P}$}{\G\_-P}}

\begin{proof}[Proof of Theorem \ref{G_P-}]
The upper bound is the saturation result of Erd\H{o}s and Gallai from \cite{ErGa}. To obtain the lower bound, we exhibit a strategy for Prolonger that guarantees the required length of game. We say a graph is \emph{everywhere traceable} if for every vertex $v$ in the graph there is a Hamiltonian path starting at $v$. Hence if a graph is Hamiltonian it is everywhere traceable. We will show that the following strategy for Prolonger guarantees that the score will be large enough:
\begin{enumerate}[i)]
\item If there is a component $C$ which is not everywhere traceable, he finds a Hamiltonian path $P$ in $C$ and adds the edge which augments $P$ to a Hamiltonian cycle;
\item Otherwise he does not add an edge on his turn.
\end{enumerate}

To prove this, we first show the following auxiliary claim.
\begin{claim}
After his move, every connected component is everywhere traceable.
\end{claim}
\begin{proof}
Induct on the number of edges in the graph. Hence we may assume that after his previous move, all the components were everywhere traceable. As the base case, note that the empty graph and an isolated edge are everywhere traceable, so regardless of who moves first, Prolonger will choose to add no edges and leave the graph satisfying the claim.

After Shortener's move, Prolonger is faced with a graph $G$. If her move did not alter the component structure of the process, then every component is still everywhere traceable and he will add no edges, satisfying the claim. Her move altered at most 2 components by connecting them, which produces a single component $C$ which is not everywhere traceable. Since $C$ was formed by joining two everywhere traceable components by an edge, we know that $C$ contains a Hamiltonian path $P$. Since after her move the graph is $P_k$-free, we know that $|P| = |C| < k$.

Since by assumption $C$ is not everywhere traceable, we have that $|C| > 2$ and that the endpoints $u, v$ of $P$ are not adjacent as $C$ is not Hamiltonian. Since $|C| < k$, any path using the edge $uv$ in $G \cup uv$ is contained in $V(C)$, and so has length less than $k$. So $G \cup uv$ is $P_k$-free, and Prolonger may add this edge. The component $C \cup uv$ is Hamiltonian and thus everywhere traceable. Hence after his move, Prolonger leaves every connected component everywhere traceable.
\end{proof}

Hence in $\G_{t^*}$ , the total number of vertices in any two components is $\geq k$, as otherwise these two components could be joined by an edge. Since all components are Hamiltonian, every component is of size less than $k$ and so will be complete. Hence the sum of degrees of any two disconnected vertices is at least $k - 2$. Hence taking $\delta$ the minimum degree of $\G_{t^*}$, we have:
\[2\G \geq \max(k - 2 - \delta, \delta)(n - \delta - 1) + \delta(\delta + 1) = \max(k - 2 - 2\delta, 0)(n - \delta - 1) + \delta n\]
which is minimised by taking $\delta = \lfloor\frac{k - 2}{2}\rfloor$. Checking $k$ even or odd, and recalling that $k < n$ yields $\G \geq\frac{1}{4}n(k-2)$ as required.
\end{proof}

In fact, the notion of ensuring that all components remain everywhere traceable almost allows for an effective strategy for Prolonger in $\G(K_n; P_k)$. The only point at which Prolonger could not guarantee to leave every component everywhere traceable is when when the graph consists of a disjoint union of cliques. In this case, his move necessarily leaves a component which is not everywhere traceable. This could be exploited by Shortener to produce a large induced star with each vertex attached to a long path, and any path between vertices of the star passing through the central vertex. This permits disconnected vertices to have degrees summing to less than $k-1$, and thus in principle to push $\G$ below $\frac{1}{4}n(k-2)$.

\section{The game \texorpdfstring{$\G(K_n, P_4)$}{G(K\_n, P\_4)}}

We now turn to a detailed examination of the game $\G(K_n, P_4)$ and Theorem~\ref{P4-bound}. Let us begin with the following characterisation of $P_4$-saturated graphs, which is easily seen by inspection:

\begin{lemma}\label{P4_saturated}
A $P_4$ saturated graph is either a vertex-disjoint union of triangles and stars with at least two vertices or a vertex-disjoint union of triangles and an isolated vertex (cf. Figure \ref{P4-cmpts}).
\end{lemma}
\begin{proof}
\end{proof}

\begin{figure}[h]
\scalebox{.8}{
  \begin{tikzpicture}
    \tikzstyle{every node}=[draw,circle,fill=blue,minimum size=0.2cm,
                            inner sep=0pt]
    \node (p1) at ( 0, 0.5) {};
    \node (p2) at ( 2, 0) {};
    \node (p3) at ( 1.5,2) {};
    \node (q1) at ( 6,0) {};
    \node (q2) at ( 4.5,1.7) {};
    \node (q3) at ( 5.5, 2.2) {};
    \node (q4) at ( 6.5,2.2) {};
    \node (q5) at ( 7.5,1.7) {};
    \begin{scope}[every path/.style={-}]
       \draw (p1) -- (p2);
       \draw (p2) -- (p3);
       \draw (p3) -- (p1);
       \draw (q1) -- (q2);
       \draw (q1) -- (q3);
       \draw (q1) -- (q4);
       \draw (q1) -- (q5);
       \draw[dashed] (q4) -- (q5);

    \end{scope}
  \end{tikzpicture}
}
\captionof{figure}{Maximal components of a $P_4$ saturated graph}
\label{P4-cmpts}
\end{figure}

This straightforward lemma leads to reasonably good bounds on the score, as we can exactly track which components could form.

\begin{proof}[Proof of Theorem \ref{P4-bound}]
The upper bound is demonstrated by considering the following strategy for Shortener. She will:

\begin{enumerate}[i)]
\item extend a $K_{1,2}$ to a $K_{1,3}$ if possible, otherwise
\item draw an isolated edge if possible, otherwise
\item extend a star by attaching the central vertex to an isolated vertex if possible, otherwise
\item extend a $K_{1,2}$ to a $K_3$.
\end{enumerate}

\begin{claim}\label{P4-structure}
After Prolonger's move, there is at most one $K_{1,2}$ component.
Shortener will not complete the $K_{1,2}$ to a $K_3$, unless this makes the graph
$P_4$ saturated. After Shortener's move, there is at most one $K_{1,2}$ component.
If there is a $K_{1,2}$ component after Shortener's move, Prolonger will extend it to a $K_3$ and make the
graph $P_4$ saturated.\end{claim}
\begin{proof}
We proceed by induction.
\begin{enumerate}[1.]
\item Suppose that $G_i$ has a $K_{1,2}$ component after Prolonger's move..
\begin{enumerate}[1)]
\item If there is an isolated vertex in $G_i$, Shortener will extend the $K_{1,2}$ to a
$K_{1,3}$. Hence there is no $K_{1,2}$ component in $G_{i+1}$, and there can be at
most one after Prolonger's next move to $G_{i+2}$.
\item If there is no isolated vertex in $G_i$, Shortener will extend the $K_{1,2}$ to a
$K_3$. Two components of size $> 1$ cannot be joined without creating a
$P_4$. Hence no further components can be joined or extended, and the
graph is $P_4$ saturated.
\end{enumerate}
\item Suppose that $G_i$ has no $K_{1,2}$ component after Prolonger's move.
\begin{enumerate}[1)]
\item If Shortener creates a $K_{1,2}$ component, then $G_i$ contained exactly one
isolated vertex. Hence all components are now of size > 1, so
Prolonger can only complete the $K_{1,2}$ to a $K_3$.
\item Otherwise there are no $K_{1,2}$ components in $G_{i+1}$, and Prolonger can
produce at most one in $G_{i+2}$.
\end{enumerate}
\end{enumerate}
This finishes the proof.
\end{proof}
By Claim \ref{P4-structure}, until $t^*$, Shortener has ensured that the graph is a vertex disjoint union of stars. Let there be $\lambda$ components in $G_{t^*}$. Since there is at most 1 triangle, the score is bounded above by $n + 1 - \lambda$, with $n - \lambda$ moves producing non-trivial components (i.e. creating isolated edges) or extending stars. To prevent her from making a new non-trivial component by case (ii) of her strategy, Prolonger must make a $K_{1,2}$, which occurs at most once for each component of $\G_{t^*}$. Hence at most $\lambda$ of Shortener's moves fail to make a non-trivial component. Hence there are at least $\frac{1}{2} (n - \lambda) - \lambda$ components. So $\lambda\geq \frac{1}{5}n$, and the score is at most $\frac{4}{5}n + 1$.

The lower bound is demonstrated by considering the following strategy
for Prolonger. He will:
\begin{enumerate}[i)]
\item complete a triangle component if possible, otherwise
\item complete a $K_{1,2}$ component if possible, otherwise
\item extend a star component if possible, otherwise
\item draw an isolated edge.
\end{enumerate}
Note that Prolonger is forced to play an isolated edge only as the first move or after Shortener completes a triangle.  We say that a move \emph{uses $k$ new vertices} if the number of isolated vertices is reduced by $k$ as a result of that move.

We first claim that if Prolonger creates a $K_{1,2}$ component in $\G_i$, at most 2 isolated vertices are used between $\G_i$ and $\G_{i+2}$. If Shortener plays elsewhere, Prolonger will extend the $K_{1,2}$ to a $K_3$. If Shortener extends the $K_{1,2}$ to a $K_3$, Prolonger can make an arbitrary move. If Shortener extends the $K_{1,2}$ to a $K_{1,3}$ then Prolonger can extend that to a $K_{1,4}$. In all cases at most two new vertices are used.

Note that if Prolonger can create a $K_{1,2}$ component when creating $\G_i$ but does not, then he must extend a $K_{1,2}$ into a $K_3$. Hence at most 2 new vertices are used between $\G_{i-2}$ and $\G_i$.

If Prolonger cannot create a $K_3$ or $K_{1,2}$ component then either there are no isolated edges in $\G_{i-1}$, or there are no isolated vertices in $\G_{i-1}$. Hence Shortener uses at most one isolated vertex from $\G_{i-2}$ or $\G_{i-1}$ is $P_4$ saturated. Prolonger uses 2 new vertices only if he adds an isolated edge to form $\G_i$, which requires that Shortener completed a triangle into $\G_{i-1}$ and used no new vertices. Hence either 1 new vertex is used to end the game or at most 2 new vertices are used between $\G_{i-2}$ and $\G_i$.

Note that with this strategy of Prolonger when $\G_i$ is created from $\G_{i-2}$ we never use 4 new vertices. Furthermore, we use 3 new vertices only if in $\G_{i-2}$ there was no $K_{1,2}$ component and in $\G_i$ there is. As a consequence, no two consecutive pairs of moves by Shortener and then Prolonger both use 3 new vertices. If Prolonger moves first, then his first move consumes two new vertices. If Shortener makes the last move last then her move may consume two new vertices. If there are an odd number of pairs of moves by Shortener and then Prolonger we may have 1 more pair using 3 new vertices than 2. In the worst case, all of these occur, the score would be $2(2k+1)+2$ with $n = 5k + 3 + 2 + 2 = 5k + 7$, and so the score would be $\frac{4}{5}(n-2)$. This completes the proof of the lower bound.
\end{proof}

\section{The game \texorpdfstring{$\G(K_n, P_5)$}{G(K\_n, P\_5)}}

We now turn to a detailed examination of the game $\G(K_n, P_5)$ and Theorem~\ref{P5-bound}. Denote a double star with $k$ pendant edges at one end of the central edge and $l$ at the other by $D_{k,l}$. Denote a triangle with $k$ pendant edges at one vertex by $T_k$ (cf. Figure~\ref{dt}).
\begin{figure}[h]
\scalebox{.8}{
  \begin{tikzpicture}
    \tikzstyle{vertex}=[draw,circle,fill=blue,minimum size=0.2cm,inner sep=0pt]

    \node[vertex] (r1) at ( 11,0) {};
    \node[vertex] (r2) at ( 9.3,-1.5) {};
    \node[vertex] (r3) at ( 8.8, -0.5) {};
    \node[vertex] (r4) at ( 8.8,0.5) {};
    \node[vertex] (r5) at ( 9.3,1.5) {};
    \node[vertex] (r6) at ( 13, 1.2) {};
    \node[vertex] (r7) at ( 13, -1.2) {};

    \begin{scope}[every path/.style={-}]
       \draw (r1) -- (r2);
       \draw (r1) -- (r3);
       \draw (r1) -- (r4);
       \draw (r1) -- (r5);
       \draw[dashed] (r4) -- (r5);
       \draw (r6) -- (r7);
       \draw (r7) -- (r1);
       \draw (r1) -- (r6);
     \end{scope}
\draw [decorate,decoration={brace,amplitude=10pt}] (8.6,-1.8) -- (8.6,1.8) node [midway,xshift=-0.6cm] {\footnotesize $k$};
\node at (11,-2.5) { $T_k$};

    \node[vertex] (q1) at ( 17,0) {};
    \node[vertex] (q2) at ( 15.3,-1.5) {};
    \node[vertex] (q3) at ( 14.8,-0.5) {};
    \node[vertex] (q4) at ( 14.8, 0.5) {};
    \node[vertex] (q5) at ( 15.3, 1.5) {};
    \node[vertex] (p1) at ( 19,0) {};
    \node[vertex] (p2) at ( 20.7,-1.5) {};
    \node[vertex] (p3) at ( 21.2,-0.5) {};
    \node[vertex] (p4) at ( 21.2,0 .5) {};
    \node[vertex] (p5) at ( 20.7, 1.5) {};

    \begin{scope}[every path/.style={-}]
       \draw (q1) -- (q2);
       \draw (q1) -- (q3);
       \draw (q1) -- (q4);
       \draw (q1) -- (q5);
       \draw[dashed] (q4) -- (q5);
       \draw (p1) -- (p2);
       \draw (p1) -- (p3);
       \draw (p1) -- (p4);
       \draw (p1) -- (p5);
       \draw[dashed] (p4) -- (p5);
       \draw (q1) -- (p1);
     \end{scope}

\draw [decorate,decoration={brace,amplitude=10pt}] (14.6,-1.8) -- (14.6,1.8) node [midway, xshift = -0.6cm] {\footnotesize $k$};
\draw [decorate,decoration={brace,amplitude=10pt}] (21.4,1.8) -- (21.4,-1.8) node [midway, xshift=0.6cm]  {\footnotesize $l$};
\node at (18,-2.5) { $D_{k,l}$};
  \end{tikzpicture}
}

\captionof{figure}{$T_k$ and $D_{k,l}$}
\label{dt}

\end{figure}

 As in the case of the $P_4$-saturation game, we start by characterising the $P_5$-saturated graphs, which is easily shown by inspection:
\begin{lemma}\label{P5-saturated}
A $P_5$ saturated graph is \emph{either} a vertex-disjoint union of copies of $K_4$, $T_{\geq 0}$, $D_{k, l}$ where $\max(k,l)>0$ and at most one isolated edge \emph{or} a vertex-disjoint union of one isolated vertex and copies of $K_4$.\end{lemma}

\begin{proof}[Proof of Theorem \ref{P5-bound}]
The upper bound is demonstrated by considering the following strategy for Shortener. She will:
\begin{enumerate}[i)]
\item if there are no isolated vertices in $\G_i$ then join two isolated edges to form a $P_4$ if possible, otherwise
\item \label{form5}extend a $P_4 = D_{1,1}$ to a $D_{1,2}$ or extend a $K_{1,3} = D_{0,2}$ to a $D_{1,2}$ or extend a $T_1$ to a $T_2$ if possible, otherwise
\item \label{formK}extend an isolated edge to a $K_{1,2} = D_{0,1}$ if possible, otherwise
\item \label{ext5}extend a component of 5 or more vertices by attaching to it an isolated vertex if possible, otherwise
\item \label{edge}draw an isolated edge if possible, otherwise
\item join two $K_{1,2}$ components into a $D_{2,2}$ if possible, otherwise
\item play arbitrarily.
\end{enumerate}

\begin{claim}\label{P5-structure}
Given this strategy by Shortener, in any graph $\G_t$, there is either at most one component of size four and at most one isolated edge or, there are no components of size four and at most two isolated edges.
\end{claim}

\begin{proof}
We proceed inductively; clearly the condition holds after Prolonger's first move. Suppose it holds after Prolonger moves to $\G_i$. We split into cases according to the existence of isolated vertices.

Suppose first that there are no isolated vertices in $\G_i$. Then the only way to create a 4-vertex component is to join two isolated edges from $\G_i$. But inductively if $\G_i$ already contains a 4-vertex component then there is at most one isolated edge, so a second 4-vertex component cannot be made. Otherwise there are $\leq 2$ isolated edges, so at most one 4-vertex component can be produced. Hence the lemma is satisfied.

Suppose alternatively there is an isolated vertex in $\G_i$. Then we make the stronger claim that \emph{either} there is at most one $P_4$, $K_{1,3}$ or $T_1$ and at most one isolated edge, \emph{or} there are no components of size 4 and at most 2 isolated edges during any time of the game, \emph{or} we are forming the last component of size 4 in the game. Clearly this holds after Prolonger's first move; we proceed inductively.

If there is a $P_4$, $K_{1,3}$ or $T_1$ in $\G_i$ then Shortener will extend it to a $\geq$ 5-vertex component (Step \ref{form5}). Otherwise, if there is an isolated edge in $\G_i$ then Shortener will extend it to a $K_{1,2}$ (Step \ref{formK}). Note from Lemma \ref{P5-saturated} that an isolated vertex can be attached to any $\geq$ 5-vertex component, so otherwise Shortener will attach a vertex to a $\geq 5$-vertex component(Step \ref{ext5}).

Hence $\G_{i+1}$ contains no component of size 4 and at most one isolated edge. So in $\G_{i+2}$ Prolonger can create at most one new 4-vertex component, which must be a copy of $P_4$, $K_{1,3}$ or $T_1$, or at most one isolated edge. Hence our stronger claim remains true for $\G_{i+2}$.
\end{proof}

By Claim~\ref{P5-structure}, there is at most one $K_4$. By Lemma~\ref{P5-saturated} the number of edges does not exceed the number of vertices in any other component. Hence the game score is at most $n + 2$, showing the claimed upper bound.

Before outlining the argument for the lower bound, we define some additional notions. Let us call a component \emph{trivial} if it consists of an isolated vertex. Let us call a non-trivial component \emph{standalone} if it can not be connected to another non-trivial component without completing a $P_5$, otherwise call it non-standalone. Note that for a component to be non-standalone it has to have a vertex which is not the endpoint of a $P_3$. The only $P_5$ free components which have a vertex which is not the endpoint of a $P_3$ are stars (indeed, the second neighbourhood of such a vertex is empty and the first neighbourhood is an independent set). Hence any other component may only be joined to an isolated vertex, as otherwise a $P_5$ will neccessarily appear.

The lower bound is demonstrated by considering the following strategy for Prolonger. He will:

\begin{enumerate}[(i)]
\item {complete a triangle in a $D_{1,2}$ component to make it a $T_2$ or in a $K_{1,3}$ component to make it a $T_1$, or, if not possible}
\item {complete a triangle in a component without a triangle, or, if not possible}
\item {connect two isolated edges to form a $P_4$, or, if not possible}
\item {complete a $K_{1,2}$ component, or, if not possible}
\item {draw an isolated edge, or, if not possible}
\item play arbitrarily.
\end{enumerate}

\begin{claim}\label{standalone}
Given this strategy for Prolonger, the set of star components after his move may be:
empty; or one isolated edge; or one $K_{1,2}$. After Shortener's move, the set of
non-standalone components may be: empty, $K_{1,2}$, $K_{1,3}$, $K_{1,2}$ and an isolated
edge, two isolated edges, or one isolated edge. After Shortener's move, at most a single one of $D_{1,2}$, $K_{1,2}$ or $K_{1,3}$ components exists; if a $D_{1,2}$ exists then at most one isolated edge does.
\end{claim}

\begin{proof}
We induct on the number of moves. The result holds trivially for $G_0$ and $G_{1}$. If the condition holds after Prolonger's move, it can easily be
checked that Shortener's move can only produce sets of stars as stated in the lemma. After Shortener's move, Prolonger will:
\begin{enumerate}[(i)]
\item complete a $K_3$ from a $K_{1,2}$ component, or produce a $T_1$ in the $K_{1,3}$ component, both of which are standalone;
\item if not possible, he will complete a $P_4$ from two isolated edges, which is standalone;
\item if not possible, he will complete a $K_{1,2}$ component from one isolated edge;
\item if not possible, he will draw an isolated edge;
\item otherwise, there will be at most one isolated edge and no isolated vertices, and he will play arbitrarily but his move will not extend a star into a larger star (otherwise he could have completed a triangle in it), so his edge will be a part of a standalone component.
\end{enumerate}
In all cases the set of non-standalone components after Prolonger's move is as described in the claim.
\end{proof}

\begin{claim}\label{triangle}
Given this strategy for Prolonger, in $\G_{t^*}$ all standalone components will contain a triangle. The set of non-standalone components will consist of an isolated vertex or an isolated edge.
\end{claim}

\begin{proof}
We claim by induction that after Prolonger's move, there will be at most one component
of size greater than one without a triangle which will be either an isolated edge, a $K_{1,2}$ or a $P_4$. Clearly this holds for $\G_0$, $\G_{1}$ and for this strategy of Prolonger for $\G_2$.
Suppose it holds for after Prolonger's move to $\G_i$. By Claim~\ref{standalone} there is at
most one star component in $\G_i$, so if Shortener connects two components
one of them is an isolated vertex. So in $\G_{i+1}$ the set of non-trivial
components without a triangle will be empty, a $K_2$, a $K_{1,2}$ or $P_4$ or be one
of the preceding and an isolated edge or be a $K_{1,3}$ or a $D_{1,2}$. In each case,
to form $\G_{i+2}$ Prolonger will:

\begin{enumerate}[(i)]
\item complete a triangle in them to create a $T_2$ component or a $T_1$ component or a $K_3$ component or
\item connect two isolated edges to form a $P_4$ component or
\item connect an isolated edge to an isolated vertex to form a $K_{1,2}$ component or
\item create an isolated edge or
\item else there is at most one non-trivial component without a triangle which can only be an isolated edge and he can play arbitrarily
\end{enumerate}
so the set of non-trivial components without a triangle in $\G_{i+2}$ consists of an isolated edge, a $K_{1,2}$ or a $P_4$.

Hence Shortener cannot create $D_{k,l}$ components with both $k,l\geq 2$. By Claim~\ref{standalone} there is at most one star component in $\G_i$, so the component would have to be formed via a $D_{1,2}$ or a $K_{1,3}$ component, which are immediately completed into a $T_2$ or $T_1$ component by Prolonger. Hence at the end of the game the non-trivial components without a triangle will be an isolated vertex or an isolated edge, since the other components cannot be a $D_{k,l}$ with $k, l \geq 2$ in $\G_i$ and thus contain a triangle by Claim~\ref{P5-structure}.
\end{proof}

So by Claim~\ref{triangle} all components in $\G_{t^*}$ will contain a triangle except for
at most one isolated edge or isolated vertex. Hence the number of edges in
these components is greater or equal to the number of vertices. Hence
$\G(K_n, P_5) \geq n - 1$.

\end{proof}

\section{Game of avoiding all trees on \texorpdfstring{$k$}{k} vertices}

Recall that $\T_k$ is defined to be the family of all trees on $k$ vertices. Consider the game $\G(K_n,\T_k)$. Clearly, the condition that $G$ is $\T_k$-free  is equivalent to requiring that all connected components of $G$ have less than $k$ vertices. Hence being $\T_k$-saturated implies that all components will be cliques of size at most $k - 1$ with any two components having total size at least $k$.

\begin{proof}[Proof of Theorem \ref{Tree-bound}]
Suppose $G$ is $\mathcal{T}_k$-saturated. Then $e(G)$ is a convex quadratic
function of the clique sizes, and so is maximised when all but one clique is
of size $k - 1$. The upper bounds follow immediately.

To demonstrate the lower bounds, suppose that Prolonger chooses two components with the
greatest total number of vertices such that this number is at most $k-1$ and
connects them by an edge.
\begin{claim}
After Prolonger's move, yielding $\G_i$, either (1) there exists at
most one connected component $C_i \subseteq \G_i$ with $1 < |C_i| < k - 1$, or (2) there is an
isolated edge, a connected component of size $k - 2$ and connected
components of size $k - 1$.\end{claim}

\begin{proof}
The conditions of (1) hold in $\G_0 = E_n$ and $\G_1 = K_2 \sqcup (n - 2)K_1$. We proceed inductively, and split the analysis of Shortener's move into two cases:

\begin{enumerate}[a)]
\item Shortener connects two isolated vertices to make an isolated edge.
\item Shortener does not form an isolated edge, so either no components are
changed in size or $C_i$ is joined to an isolated vertex $u$.
\end{enumerate}

If Shortener has formed an isolated edge $uv$, then if $|C_i| \leq k - 3$, Prolonger joins it to $uv$ to satisfy the conditions of (1), with $C_{i+2} = C_i \cup \{u,v\}$. If instead there is an isolated vertex $v$ and $|C_i| = k - 2$, then Prolonger joins it to $v$ to satisfy the conditions of (1). Otherwise no component can be extended and the conditions of (2) are satisfied for the rest of the game.

Suppose Shortener has not formed an isolated edge. Then she must have extended $C_i$ or left the component structure unchanged. If there was a set $C_i$, we say $C_{i+1} = C_i$ if she did not extend the component to $u$, and $C_{i+1} = C_i \cup u$ otherwise. If there are no
isolated vertices then no component can be extended and the conditions of (1) are satisfied for the rest of the game. If there is an isolated vertex $v$ and $C_{i+1}$ exists, with $|C_{i+1}| \leq k-2$, Prolonger joins $C_{i+1}$ to $v$ satisfying the conditions of (1). If there is no set $C_i$ or $|C_{i+1}| = k-1$, then if there are two isolated vertices Prolonger joins them to form $C_{i+2}$ satisfying the conditions of (1). If not, then no component can be extended and the conditions of (1) are satisfied for the rest of the game.
\end{proof}

Hence if $n \not\equiv 1 \mod (k - 1)$ the conditions of (2) cannot hold, and since
$G$ is $\mathcal{T}_k$-saturated at the end of the game there cannot be a component of
size $\leq k - 2$ and an isolated vertex. Hence there are $\lfloor\frac{n}{k-1}\rfloor$ $K_{k-1}$'s and one
further clique, which saturates the upper bound.

If $n \equiv 1 \mod (k - 1)$ and $k \geq 3$, then the conditions of (2) could hold, in
which case precisely $k - 2$ edges are lost from removing a vertex from a
$K_{k-1}$ and 1 is gained from an isolated edge. Hence the bound is $k - 3$
below the upper bound.\end{proof}

\section{Forbidding the graph \texorpdfstring{$K_{1,k+1}$}{K\_\{1,k+1\}}}
In lieu of forbidding the family of all trees $T_{k+2}$, we may merely forbid the graph $K_{1, k+1}$. Trivially this corresponds to requiring that in the process, $\Delta(\G_t) \leq k$. From this, we immediately see that in a $K_{1,k+1}$-saturated graph $G$ we have that $\{v \in G : d(v) < k\}$ must form a clique in $G$, as otherwise we could add an edge without producing a $K_{1,k+1}$. Hence, by minimizing the respective quadratic function, we have that the score $\G(K_n, K_{1,k+1}) \geq \frac{1}{2}nk - \frac12 \left(\frac{k+1}{2}\right)^2 $. This lower bound can be improved somewhat.

\begin{proof}[Proof of Theorem \ref{Star-bound}]
The upper bound follows trivially from the fact that $\Delta(G) \leq k$ in any $K_{1,k+1}$-saturated graph $G$. Let Prolonger have the following strategy: Given a graph $\G_i$ by Shortener, she adds the least edge in $\bar{\G_i}$, where the edges $uv$ of $\bar{\G_i}$ are ordered lexicographically by the minimum degree of $u$ and $v$ and then by the maximal degree. Note first that he will attempt to add edges between vertices of degree $\delta(\G_i)$. If Prolonger is unable to find such an edge, then the vertices of degree $\delta(\G_i)$ must form a clique, and hence there are at most $\delta(\G_i) + 1 \leq k+1$ of them. These final $\leq k+1$ vertices may require their degrees to be increased by adding edges to vertices of degree greater than $\delta(\G_i)$.

Consider the graph process given that Prolonger follows this strategy. Let $t_i$ be least such that $\delta(\G_{t_i}) \geq i$ and Shortener has just played. Let $g_i = \sum_v \max(d_{\G_{t_i}}(v) - i, 0)$, if $t_i$ exists, and $g_i = 0$ otherwise. Suppose that $t_i$ exists and that in $\G_{t_i}$ there are $\lambda_i$ vertices of degree $> i$. Then after at most $\left\lceil \frac{1}{2}(n - i - 1 - \lambda_i)\right\rceil$ moves by Prolonger there are $\leq i+1$ vertices of degree $i$, and after at most another $i+1$ moves by Prolonger there are no vertices of degree $i$, unless the game has ended.  Furthermore, note that by parity considerations if the ceiling in phase one increases the bound then the second phase has only $i$ moves.

For the game to end whilst $\delta(\G_t) = i$ requires that there exist $n-i-1$ vertices with degree $k$. Consider the total degree of these vertices between $t_i$ and the hypothesised game end. Note that over Prolonger's $\leq \frac{1}{2}(n - i - 1 - \lambda_i) + i+1$ moves he adds one edge to every vertex of degree $i$, and at most a further $k+1$ to the total degree. We may assume that Shortener only adds edges amongst the $n-i-1$ vertices.

Note that in the first phase of Prolonger's play, his added edges will increase the degree of a subset of the $n-i-1$ vertices, each of degree $i$, by exactly one. So considering just these moves and the initial degree, the sum of degrees over the $n-i-1$ vertices is $(i+1)(n-i-1) + g_i - \lambda_i$, as the first two terms double count the $i+1^{\textrm{th}}$ edge incident on any vertex of degree $> i$ in $\G_{t_i}$. In Shortener's moves, she adds at most $(n-i-1-\lambda_i)$ to this degree sum. In the second phase of Prolonger's play, every pair of moves by Prolonger and Shortener adds at most 3 edges to these vertices. So for the game to last until Prolonger increases $\delta(G_t)$ to $i+1$, it \emph{suffices} to have:
\[
k(n-i-1) \geq  (i+1)(n-i-1) + (g_i - \lambda_i) + (n - i - 1 - \lambda_i) + 3(i+1)
\]
and by the same degree counting we have:
\[g_{i+1} \leq (g_i - \lambda_i) + (n - i - 1 - \lambda_i) + 3(i+1).\]
Note that $\lambda_i \geq g_i/(k - i)$, as any vertex contributes at most $k-i$ to $g_i$ and $\lambda_i$ counts the number of non-zero contributions to $g_i$. Define:
\[f_0 = 0,\quad f_{i+1} = f_i + (n + 2k + 2) - 2f_i / (k - i).\]
For all $i \leq k-2$, $f_{i+1}$ is increasing in $f_i$. Note that $g_0 = 0$, and hence:
\[g_{i+1} \leq g_i + (n + 2i + 2) - 2\lambda_i \leq g_i + (n + 2k + 2) - \frac{2g_i}{k - i} \leq f_{i+1}\]
for all $i \leq k-2$, with the last inequality following by induction on $i$. Note also that $t_{i+1}$ exists if $(k-i-1)(n-i-1) \geq f_{i+1}$, as we have $f_{i+1} \geq (g_i - \lambda_i) + (n - i - 1 - \lambda_i) + 3(i+1)$ from this inequality. Additionally, we have $f_i = i(n + 2k + 2)\frac{k-i}{k-1}$ by induction. Hence to show that $t_i$ exists for all $i \leq k-2$ it suffices that:
\[i(n + 2k + 2)\frac{k-i}{k-1} \leq (k-i)(n-i) \Leftrightarrow i \leq \frac{n(k-1)}{n+3k+1}\]
holds for all $i \leq k-2$. Hence for

So for $n \geq (3k+1)(k-2)$, we have that $t_i$ exists for all $i \leq k-2$, and so the minimum degree of the saturated graph is at least $k-2$. Hence $\G(K_n, K_{1,k+1}) \geq \frac{1}{2}\left(kn-2(k-1)\right)$ as required.
\end{proof}

\section{Concluding Remarks}
There remain many interesting open problems, chiefly the resolution of the triangle saturation game. Given a graph $G$ which is not a tree, providing effective bounds on the $\mathcal{G}(K_n, G)$ would be highly desirable. In our results, we show that a careful analysis of the maximal components is of substantive use, and that the supply of low degree vertices controls the ability of both players to enforce conditions on the game. However, our results are strongly predicated on finding explicit strategies; for example, the component structure of $P_6$-saturated graphs is not hard to determine but finding an explicit strategy in this case seems hard.

config: arxiv


text:
\begin{document}

\maketitle

\begin{abstract}
The development of prior distributions for Bayesian regression has traditionally been driven by the goal of achieving sensible model selection and parameter estimation.  The formalization of properties that characterize good performance has led to the development and popularization of thick tailed mixtures of $g$ priors such as the Zellner--Siow and hyper-$g$ priors.  The properties of a particular prior are typically illuminated under limits on the likelihood or the prior.  In this paper we introduce a new, \emph{conditional information asymptotic} that is motivated by the common data analysis setting where at least one regression coefficient is much larger than others.  We analyze existing mixtures of $g$ priors under this limit and reveal two new behaviors, \emph{Essentially Least Squares (ELS)} estimation and the \emph{Conditional Lindley's Paradox (CLP)}, and argue that these behaviors are, in general, undesirable.  As the driver behind both of these behaviors is the use of a single, latent scale parameter that is common to all coefficients, we propose a block hyper-$g$ prior, defined by first partitioning the covariates into groups and then placing independent hyper-$g$ priors on the corresponding blocks of coefficients.  We provide conditions under which {\em ELS} and the {\em CLP} are avoided by the new class of priors, and provide consistency results under traditional sample size asymptotics.
\end{abstract}

\noindent
\textbf{Keywords}: Bayesian linear model; consistency; Information Paradox; Lindley's Paradox; mixture of normals; model selection; shrinkage estimator.

\section{Introduction}

Bayesian methods for regression address the central questions of model selection and parameter estimation. Conjugate forms have played an important role due to ease of specification and ease of update from prior to posterior.  Zellner's well-known $g$ prior \citep{zellner1986assessing} is fully conjugate for a normal theory regression model.  The conjugate form leads to quick calculation of the posterior distribution and of the marginal likelihood.  The first of these features allows one to compute estimates and make predictions for a given model while the second allows one to compare models via the Bayes factor and, with the addition of a set of prior model probabilities, to engage in model averaging.

The $g$ prior has many close cousins.  One popular formulation imposes conditionally (on an analog of $g$) independent prior distributions for the regression coefficients as in ridge regression \citep{hoerl1970ridge}.  Other formulations have been designed to handle the two main problems of estimation/prediction and model/variable selection.  For estimation/prediction, consistent estimators are desirable, and concern about prior-data conflict suggests nonlinear shrinkage.  Nonlinear shrinkage is produced by placing a scale mixture of normals \citep{west1987scale} on $g$ or on the variance of the regression coefficients.  The Bayesian lasso prior \citep{park2008bayesian,hans2009bayesian}, the orthant normal prior \citep{hans2011elastic}, the generalized double Pareto prior \citep{armagan2013generalized}, the Horseshoe prior \citep{carvalho2010horseshoe}, the normal-exponential-gamma/normal-gamma prior \citep{griffin2005alternative, griffin2010inference, griffin2011bayesian, griffin2012structuring}, and the priors of \cite{polson2010shrink} conform to a mixture representation of this form.

The $g$ prior and the independence prior have been extended for use in model selection  by placing a prior distribution over the discrete space of regression models.  Each model consists of a subset of the covariates, with the other covariates implicitly having zero (or occasionally near-zero) regression coefficients.  The prior specific to each model is a $g$ (or independence) prior, often with a hyper-prior placing a distribution over $g$.  \cite{mitchell1988bayesian} provided a forerunner of these priors, the ``spike and slab'' prior.  Additional priors along these lines have been investigated in \cite{george1993variable}, \cite{george1997approaches}, \cite{foster1994risk}, \cite{kass1995reference}, \cite{george2000calibration}, \cite{fernandez2001benchmark}, \cite{johnstone2004needles} and  \cite{ishwaran2005spike}.  The computational cost of model selection is substantial, and the models are often fit with stochastic search algorithms.  Various algorithms having distinctive features include \cite{george1993variable}, \cite{berger2005posterior}, \cite{hans2007shotgun}, \cite{scott2008feature}, \cite{bott:10} and \cite{clyde2011bayesian}.

In this work, we address model-specific estimation and prediction, model selection, and estimation and prediction under model averaging.  As such, \cite{liang2008mixtures}'s development of the hyper-$g$ prior is particularly relevant.  The hyper-$g$ prior, one of the most commonly used mixture of $g$ priors, has been designed to retain the computational efficiency of the $g$ prior while performing well for both estimation and model selection.  We revisit this performance by studying the limiting behavior of the model under a new, \emph{conditional information asymptotic}.  This type of limit is important in practice, as it provides insight into the behavior of estimation and model selection when one regression coefficient is substantially larger than other non-zero regression coefficients.  As part of the analysis, we describe \emph{Essentially Least Squares (ELS)} estimation wherein inference under a Bayesian model collapses to least squares estimation, and we identify a \emph{conditional version of Lindley's paradox (CLP)} which leads to inconsistent model selection. We show that many commonly used mixtures of $g$ priors, including the hyper-$g$ prior, suffer from both \emph{ELS} and the \emph{CLP}.

In order to overcome the deficiencies of the scale mixture of $g$ priors, we introduce the block hyper-$g$ prior, a collection of ordinary mixture of $g$ priors applied to groups of predictors separately.  The theoretical properties of the new prior are investigated in detail under the analytically tractable blockwise orthogonal design setup, and the new prior is shown to perform well.  The new prior is suitable for situations where one can subjectively (or in an automated fashion) group predictors into blocks. The use of multiple prior variance parameters has been explored in \cite{maruyama2011fully}, \cite{rouder2012default} and \cite{min2012objective}.

In Section~\ref{sec:prelim}, we introduce notation that is used throughout the paper and describe the basic regression setup.  Section~\ref{sec:paradoxes} describes \emph{ELS} and \emph{CLP} behaviors, and contains theoretical results showing that several popular priors perform poorly on these criteria.  Section~\ref{sec:newprior} formulates the block hyper-$g$ prior and provides theoretical properties of the new prior under block orthogonal designs.  Section~\ref{sec:consistency} is dedicated to examining the consistency properties of the block hyper-$g$ prior.  We conclude the article with a brief discussion in Section~\ref{sec:disc}.  Proofs of the main results are in Appendix~\ref{app:proofs}, while proofs of other results are in Appendix \ref{appB} in the Supplementary Material.

\section{Notation and Preliminaries}\label{sec:prelim}

The basic regression problem can be described as explaining the behavior of the response vector $\bfy=(y_1, y_2, $ $ \ldots, y_n)^T$ using a known set of $p$ predictor variables $\bfx_1, \bfx_2, \ldots, \bfx_p$.  We consider the traditional setting where $n > p$.  Let $\bfgambig \in \Gamma=\{0,1\}^p$ denote the index set of the subsets of the predictor variables to be included/excluded in a model so that under a particular model $\mathcal{M}_{\bfgam}$, the $i^{th}$ element of the vector $\bfgambig$ signifies inclusion of predictor $i$ (in model $\mathcal{M}_{\bfgam}$) if $\gamma_i=1$ and exclusion if $\gamma_i=0$. Thus, $\Gamma$ describes the collection of all $2^p$ possible models and each element $\bfgambig$ represents a unique model in $\Gamma$. Let $X_{\bfgam}$ denote the $n \times p_{\gamma}$ design matrix and $\bfb_{\bfgam}$ denote the $p_{\gamma}$ length vector of regression coefficients corresponding to model $\Mgam$. The linear model $\Mgam$ can be represented as:
\[ \bfy = \bone \alpha + X_{\bfgam} \bfb_{\bfgam} + \bfep
\]
where $\bone$ is a $n \times 1$ vector of 1's and $\alpha$ denotes the intercept which appears in every model in $\Gamma$. The vector of observed errors $\bfep=(\epsilon_1,\ldots,\epsilon_n)^\top$ is a Gaussian random vector, $\bfep \sim N(0,\sigma^2 I_n)$. The Bayesian approach places a prior on the vector of the unknown parameters $(\alpha,\bfb_{\bfgam},\sigma^2)=\bftheta_{\bfgam} \in \Theta_{\bfgam}$ corresponding to each model $\Mgam$ along with an additional prior on the model space $\Gamma$. To retain the same meaning for $\alpha$ across all models, we center the columns of $X_{\bfgam}$ so that $\bone^T X_{\bfgam}=0$ and all the covariates are orthogonal to the intercept. Traditionally, this transformation justifies specification of a common prior for $\alpha$ \citep{jeff:61,berger1998bayes}.  Recently \cite{bayarri2012criteria} provided alternative arguments for a common, flat prior on $\alpha$ based on a predictive matching criterion for the prior distribution. Without loss of generality, the  response vector $\bfy$ is also assumed to be centered at zero in our setup, i.e., $\bone^T\bfy=0$.

\subsection{Zellner's $\bfg$ prior}\label{sec:gprior}

Zellner's $g$ prior \citep{zellner1986assessing} is specified as
\begin{eqnarray}
 \pi (\alpha, \sigma^2 \mid \Mgam) &\propto& \frac{1}{\sigma^2} \nonumber  \\
 \bfb_{\bfgam} \mid g, \alpha, \sigma^2, \Mgam &\sim&  N \left( \textbf{0}, g\sigma^2 (X^T_{\bfgam} X_{\bfgam})^{-1} \right)
 	\label{eq:zgprior}
\end{eqnarray}
which results in simple closed form expressions for the marginal likelihoods and Bayes factors. The Bayes factor for any model $\Mgam$ compared to the null model $\Mo$ is
\begin{eqnarray}\label{eq:gBF}
BF(\Mgam : \Mo)= \frac{p(\bfy \mid \Mgam)}{p(\bfy \mid \Mo)} = \frac{(1+g)^{(n-p_{\gamma}-1)/2}}{[1+g(1-R_{\bld{\gamma}}^2)]^{(n-1)/2}}
\end{eqnarray}
where $R^2_{\bfgam}$ is the coefficient of determination for the model $\Mgam$.  Under sum of squared error loss, the Bayes estimator of $\bfbeta_{\bfgam}$ is
\begin{eqnarray}
\label{eq:BayesEstimateg}
\widehat{\bfbeta}_{\bfgam} & = & \frac{g}{1+g} \widehat{\bfbeta}_{\bfgam,LS},
\end{eqnarray}
where $\widehat{\bfbeta}_{\bfgam,LS}$ is the least squares estimator of $\bfbeta_{\bfgam}$.

The $g$ prior requires a value for $g$.  A variety of choices have been suggested based on different considerations.  Well-known (fixed) $g$ priors include the \emph{unit information prior} \citep{kass1995reference}, the \emph{risk inflation criterion prior} \citep{foster1994risk}, the \emph{benchmark prior} \citep{fernandez2001benchmark}, the \emph{local empirical Bayes prior} \citep{hansen2001model} and the \emph{global empirical Bayes prior} \citep{george2000calibration}.  \cite{liang2008mixtures} review the fixed $g$ priors and summarize the justifications behind these specific values of $g$.

\subsection{Mixtures of $\bfg$ priors}\label{sec:mixtures}
There are a variety of motivations for considering a ``fully Bayes'' approach where $g$ is modeled with a prior distribution, leading to a marginal prior for $\bfb_{\bfgam}$ which can be represented as a ``mixture of $g$ priors''
\[
	\pi(\bfb_{\bfgam} \mid \alpha, \sigma^2, \Mgam) = \int_0^\infty N \left( \bfb_{\bfgam} \mid \textbf{0}, g\sigma^2 (X^T_{\bfgam} X_{\bfgam})^{-1} \right)  \pi(g) dg.
\]
Careful choice of the mixing distribution can result in thick-tailed priors for $\bfb_{\bfgam}$ after marginalization of $g$.  An early example is the Zellner--Siow prior \citep{zellner1980posterior}, which can be expressed as a mixture of $g$ priors with an Inverse Gamma ($\frac{1}{2},\frac{n}{2}$) mixing density for $g$.  Mixing over $g$ also endows the Bayes estimator of $\bfb_{\bfgam}$ with data-adaptive shrinkage of the least squares estimator:
\begin{equation}
	\widehat{\bfb}_{\bfgam} =  E(\bfb \mid \bfy, \Mgam) = E\left( \frac{g}{1+g} \mid \bfy, \Mgam \right)  \widehat{\bfb}_{\bfgam,LS}.
	\label{eq:shrink}
\end{equation}
The quantity $E(\frac{g}{1+g} \mid \bfy, \Mgam)$ is often called the \textit{shrinkage factor}.

A variety of prior distributions for $g$ have been considered in the literature. \cite{zellner1980posterior}, \cite{west2003bayesian}, \cite{maruyama2010robust}, \cite{maruyama2011fully} and \cite{bayarri2012criteria} are notable examples.  In this work, we focus primarily on the ``hyper-$g$'' prior of \cite{liang2008mixtures}.

\subsubsection{Hyper-$\bfg$ Priors}\label{sec:hyper}
The ``hyper-$g$'' prior proposed by \cite{liang2008mixtures} places a prior distribution on $g$ with density
\[
\pi(g) = \frac{a-2}{2} (1+g)^{-a/2} \;,\; \; g>0.
\]
The prior is proper if $a > 2$ and the authors suggest using $a \in (2, 4]$, with $a=3$ being the default choice.
The Bayes factor under the hyper-$g$ prior can be expressed as
\begin{eqnarray*}
BF(\Mgam : \Mo) &=& \int_0^{\infty} (1+g)^{(n-p_{\gamma}-1)/2}[1+g(1-R_{\bld{\gamma}}^2)]^{-(n-1)/2} \pi(g)dg \\
&=& \frac{a-2}{p_{\gamma}+a-2}  \; _2F_1 \left(\frac{n-1}{2},1;\frac{a+p_{\gamma}}{2};R_{\bld{\gamma}}^2\right)
\end{eqnarray*}
where $_2F_1(\cdot)$ is the Gaussian hypergeometric function.

\section{Asymptotic Evaluations: Paradoxes, Old and New}\label{sec:paradoxes}

While the $g$ priors described in Section~\ref{sec:gprior} offer many conveniences, they are known to have several undesirable
properties commonly referred to as ``paradoxes.'' In purest form, the paradoxes associated with $g$ priors are revealed when taking a limit.  \cite{liang2008mixtures} describe two such paradoxes which arise from different limits.  The first, Lindley's Paradox, relies on a limit which weakens the prior distribution.  The second, the Information Paradox, relies on a limit where the signal in the data becomes stronger.  Both limits hold the design $X$ (and hence sample size) fixed.  These two ``old'' paradoxes can be summarized as follows.

\emph{Bartlett's Paradox/Lindley's Paradox} : Lindley's Paradox is an anomaly associated with a fixed $g$ prior when the scale factor $g$ is intentionally chosen to be large in an attempt to make the prior weakly informative.  Holding the data $(X_{\bfgam}, \bfy)$ fixed, the Bayes factor \eqref{eq:gBF} comparing any arbitrary non-null model $\Mgam$ to the null model $\Mo$ approaches zero in the limit when $g \rightarrow \infty$, irrespective of the data. The full description of the paradox contrasts this undesirable behavior with the results of a classical hypothesis test \citep{lind:57, bart:57, jeff:61, liang2008mixtures}.

\emph{Information Paradox} : The Information Paradox is associated with a strong signal in the data, as manifested by a high value of  $R_{\bfgam}^2$.  Holding $(X_{\bfgam}, \bfep)$ fixed, let $||\bfb_{\bfgam}|| \rightarrow \infty$, so that $||\widehat{\bfb}_{\bfgam,LS}|| \rightarrow \infty$ and $R_{\bfgam}^2 \rightarrow 1$.  It follows from \eqref{eq:gBF} that $BF(\Mgam:\Mo) \rightarrow (1+g)^{(n-p_{\bldsm{\gamma}}-1)/2}$, a finite constant.  Thus the Bayes factor for $\Mgam$ relative to $\Mo$ is bounded even though the likelihood evidence in favor of $\Mgam$ grows without bound \citep{zellner1986assessing, berger2001objective, liang2008mixtures}.

These undesirable properties can be avoided by using mixtures of $g$ priors with a careful choice of mixing distribution.
\cite{liang2008mixtures} provide sufficient conditions under which a prior $\pi(g)$ resolves the Information Paradox, and prove
that the hyper-$g$ prior avoids both of the above paradoxes \citep[as does the robust prior of][]{bayarri2012criteria}.
While these ``old'' paradoxes have been studied extensively, the limits taken to produce them have further, less well known implications.  The first is initially seen with the limit in Lindley's Paradox.  The second, a new paradox, follows from a modification to \cite{liang2008mixtures}'s limit.  Qualitative descriptions of these behaviors are as follows, with formal results provided in
Section~\ref{sec:clp}.

\emph{Essentially Least Squares Estimation (ELS)} : It is well-known that under the $g$ prior, the Bayes estimator of $\bfbeta_{\bfgam}$ in \eqref{eq:BayesEstimateg} tends to $\widehat{\bfbeta}_{\bfgam,LS}$ as $g \rightarrow \infty$.  Formally, we identify \emph{ELS} behavior as $||\widehat{\bfbeta}_{\bfgam} - \widehat{\bfbeta}_{\bfgam,LS}|| / ||\widehat{\bfbeta}_{\bfgam,LS}|| \rightarrow 0$ under some appropriate limit.  In Sections~\ref{sec:asymp} and \ref{sec:clp}, we consider limits which are driven by changes to the data rather than changes to the prior and show that several common mixtures of $g$ priors exhibit {\em ELS} behavior.

\emph{Conditional Lindley's Paradox (CLP)} : The Conditional Lindley's Paradox arises when comparing two models $\mathcal{M}_{\bfgam_1}$ and $\mathcal{M}_{\bfgam_2}$ with $\mathcal{M}_{\bfgam_1} \subset \mathcal{M}_{\bfgam_2}$, where $\mathcal{M}_{\bfgam_2}$ is the ``correct'' model.  Specific asymptotics for the data (described explicitly in Section~\ref{sec:asymp}) yield $BF(\mathcal{M}_{\bfgam_2}: \mathcal{M}_{\bfgam_1}) \rightarrow 0$, compelling one to accept the smaller (incorrect) model.

Before connecting these behaviors to existing mixtures of $g$ priors, we describe the limits driving the phenomena.

\subsection{A Conditional Information Asymptotic}\label{sec:asymp}
We consider an asymptotic analysis of a sequence of problems, where each element in the
sequence is related to the linear regression model $\bfy=\alpha \bone +X \bfb + \bfep$.  The design matrix $X$
is an $n \times p$ matrix with full column rank, and the columns of $X$ and the response $\bfy$
are centered.  Specifically, we write the linear model as
$\bfy = \alpha \bone + X_1 \bfb_1 + X_2 \bfb_2 + \bfep$, where $X = (X_1, X_2)$, $X_1$ is an $n\times p_1$
matrix, $X_2$ is an $n \times p_2$ matrix and $\bfb = (\bfb_1^T, \bfb_2^T)^T$.  We construct a sequence
$\{ \Psi_N \}_{N=1}^{\infty}$ where each element $\Psi_N$
represents the linear model with
\begin{eqnarray}\label{eq:psiseq}
\Psi_N &=& (X_{1(N)},X_{2(N)},\alpha_N,\bfb_{1(N)}, \bfb_{2(N)},\bfep_N) \nonumber \\
&=& (X_1,X_2,\alpha,\bfb_{1(N)},\bfb_{2},\bfep),
\end{eqnarray}
and $||\bfb_{1(N)}|| \rightarrow \infty$ as
$N  \rightarrow \infty$ while $X_1, X_2, \alpha,\bfb_{2}$ and $\bfep$ are held fixed.  This is a fixed-$n$, fixed-$p_\gamma$
asymptotic, and represents a strengthening of the likelihood that is driven by one particular set of predictor variables.

We refer to this as a \textit{conditional information asymptotic}, as it can be viewed as the limit that drives
the Information Paradox of \cite{liang2008mixtures} (i.e., $|| \bfb|| \rightarrow \infty$) with the additional condition that a portion
of $\bfb$ remains
fixed in the analysis.  The consequences of the information limit considered in \cite{liang2008mixtures} were driven by
$R^2 \rightarrow 1$.  The following lemma notes that the conditional information asymptotic produces the same
behavior.

\begin{lem}\label{lem3.1}
Let $R^2 (N)$ denote the coefficient of determination for element $N$ in the sequence $\{ \Psi_N \}$ as defined in \eqref{eq:psiseq}. Then $R^2 (N) \rightarrow 1$ as $N \rightarrow \infty$.
\end{lem}

The lemma follows immediately by noting that the error vector $\bfep$ is fixed, and hence $\widehat{\sigma}^2 = \frac{||\bld{y}- \widehat{\alpha}_{LS} \bld{1} - X \widehat{\bld{\beta}}_{LS}||^2}{n-p-1}$ also remains unchanged.  $R^2(N) = ||X\widehat{\bfb}_{LS}||^2/[ ||X\widehat{\bfb}_{LS}||^2 + (n-p-1)\widehat{\sigma}^2]$ which tends to one as $||\bfb_1|| \rightarrow \infty$.

\subsection{A Conditional Lindley's Paradox}\label{sec:clp}
In this section we investigate the behavior of several mixtures of $g$ priors under the conditional information asymptotic defined
by \eqref{eq:psiseq}. To streamline notation, we drop the subscript $\bfgambig$ from $\Mgam$ and refer to $R^2 (N)$ simply as $R^2$.  The following results apply to an arbitrary model $\Mgam$ unless otherwise mentioned.
The first theorem reveals a behavior of the Bayes estimator ($\widehat{\bfb}$) under the hyper-$g$ prior.

\begin{thm}\label{thm3.1}
(ELS) Under the hyper-$g$ prior, for the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq}, $\frac{||\widehat{\bld{\beta}} - \widehat{\bld{\beta}}_{LS}|| }{ ||\widehat{\bld{\beta}}_{LS}||} \rightarrow 0$  as $N\rightarrow \infty$, provided $n \geq a + p - 1$.
\end{thm}

The proof of the theorem is in Appendix \ref{appa1}. The theorem roughly indicates that when at least one of the coefficients in the model is large, the estimates under the hyper-$g$ prior are \emph{Essentially Least Squares}. The behavior of the hyper-$g$ prior in such a situation runs counter to the conventional wisdom that, for a low-information prior, small (near zero) coefficients should be shrunk substantially while larger coefficients should be left unchanged \citep{berger1985statistical}.  The next theorem, proved in Appendix~\ref{appa2}, shows that the hyper-$g$ prior suffers from what we call the \emph{Conditional Lindley's Paradox}.

\begin{thm} \label{thm3.2}
(CLP)
Consider the two models $M_1$ and $M_2$ such that
\begin{eqnarray} \label{TwoModels}
 M_1 &:& \bfy = \alpha \bone + X_1 \bfb_1 + \bfep \nonumber \\
 M_2 &:& \bfy = \alpha \bone + X_1 \bfb_1 + X_2 \bfb_2 + \bfep
\end{eqnarray}
where $\bfb_i$ is a vector of length $p_i > 0 \; \mbox{for} \; i=1,2$ and $p_1+p_2=p$.
Under the hyper-$g$ prior, when $||\bfb_1|| \rightarrow \infty \; (i.e, N \rightarrow \infty)$ in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq} and $n \geq a+p_1-1$, the Bayes factor $BF(M_2:M_1)$ comparing model $M_2$ to model $M_1$ goes to zero, irrespective of the data.
\end{thm}

The import of the theorem is that when comparing a pair of nested models, if at least one of the regression coefficients common to both models is large compared to the additional coefficients in the bigger model, the Bayes factor under the hyper-$g$ prior will place too much weight on the smaller model.  The limiting case with the size of the common coefficients growing infinitely large results in choice of the small model with probability tending to 1, leading to the conclusion that the predictors $X_2$ are, with certainty, unrelated to the response.  This behavior is unsettling since no matter how different from zero the additional coefficients in the big model are, the more important predictor(s) common to both models drive model choice toward the small model.

We note that the behavior of the Bayes factor under this limit cannot be attributed to $\sigma^2$, as the posterior of
$\sigma^2$ is well-behaved and converges to a proper probability distribution.

\begin{cor} \label{cor3.1}
Under the hyper-$g$ prior, the posterior distribution of $\sigma^2$ in the sequence of problems $\{\Psi_{N}\}$ defined in \eqref{eq:psiseq} converges to an $IG\left(\frac{n+1-a-p}{2},\frac{2}{(n-p-1)\widehat{\sigma}^2} \right)$ distribution when $n > a+p-1$.
\end{cor}

A proof is in Appendix~\ref{appb1} in the supplementary materials.
The \emph{CLP} coincides with Lindley's Paradox for any fixed $g$ prior, and as such it is easily shown that fixed $g$ priors are also adversely affected by the \emph{CLP}.

\subsubsection{The CLP in Other Mixtures of $\bfg$ Priors}

Theorem~\ref{thm3.2} describes the {\em CLP} under the hyper-$g$ prior. Other mixtures of $g$ priors exhibit the same behavior.
For example, \cite{maruyama2011fully} develop a generalized $g$ prior by specifying a prior on $\bfb$ through a prior on the rotated vector $W^T\bfb$, where $W$ is defined through the singular value decomposition $X=UDW^T$. In the simple situation where $X^T X$ is a block diagonal matrix, the generalized $g$ prior suffers from the \emph{CLP}.

\begin{thm}\label{thm3.3}
Consider the models in (\ref{TwoModels}) with the assumption that $X_1 \indep X_2$.  Under the generalized $g$ prior of \cite{maruyama2011fully},  as $N \rightarrow \infty$ in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq}, $BF(M_2:M_1) \rightarrow 0$ irrespective of the data.
\end{thm}

The robust prior of \cite{bayarri2012criteria} also suffers from the \emph{CLP} whether or not $X^T X$ is block diagonal.

\begin{thm}\label{thm3.4}
Consider the models in (\ref{TwoModels}) with $n > p_1 + 2$.  Under the robust prior of \cite{bayarri2012criteria} with the recommended hyperparameters ($a=1/2, b=1$ and $\rho=\frac{1}{p+1}$), as $N \rightarrow \infty$ in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq}, $BF(M_2:M_1) \rightarrow 0$ irrespective of the data.
\end{thm}

Proofs are in Appendices~\ref{appengeneralizedg} and \ref{appenb3} in the supplementary materials.

\section{Avoiding \emph{ELS} and \emph{CLP} Behaviors}\label{sec:newprior}

The \emph{ELS} and \emph{CLP} behaviors described in Section~\ref{sec:clp} for mixtures of $g$ priors arise as a result of the use of a single, latent scale parameter $g$ that is common to each predictor variable.  In order for the model to fit the data in the presence of one (or more) large coefficients, $g$ must be large (with high probability).  Because $g$ affects estimation of all coefficients \eqref{eq:shrink}, this has the side-effect that small coefficients are not shrunk, producing \emph{ELS} behavior.  The \emph{CLP} can be explained by an argument similar to the one that explains Lindley's Paradox: as the common parameter $g$ is driven to be larger and larger (by a portion of the data, in our case) the diminishing prior mass in the neighborhood near zero containing any small, nonzero coefficients effectively rules out these predictors.

As we show in this section, these behaviors can be avoided through the use of multiple latent mixing parameters in place of a single, common $g$.  This approach has a connection to the concept of ``local shrinkage,'' which has a rich history in the study of the related normal means problem, e.g.~\cite{strawderman1971proper} and \cite{berger1980robust}.  Recent research in this area includes \cite{scott:06}, \cite{carvalho2010horseshoe}, \cite{scott2010bayes}, \cite{polson2012half} and \cite{bhattacharya2014dirichlet}.
The use of multiple latent scale parameters in regression settings has typically focused on ridge-regression-like settings where regression coefficients are conditionally independent \emph{a priori} \citep[e.g.,][]{polson2010shrink, armagan2013generalized}.
\cite{polson2012local} consider local shrinkage in regression where the local shrinkage parameters are attached to linear combinations of the regression coefficients.  A similar setting is considered by \cite{west2003bayesian}.

Our approach is to endow collections of regression coefficients with their own, independent, mixture of $g$ priors.  Having latent
scale parameters $g_i$ that are local to collections of coefficients results in models that avoid \emph{ELS} and \emph{CLP} behavior under the conditions described in Section~\ref{sec:blockhgstudy}.  The extreme case where each predictor variable is associated with its own $g_i$ was described, but not pursued, by \cite{liang2008mixtures} as representing ``scale mixtures of independent $g$ priors.''  The approach we propose emerges as a more general version of this idea with added theoretical underpinning related to \emph{ELS} and the \emph{CLP}.

\subsection{Block $\bfg$ Priors}\label{sec:blockg}
We build a block $g$ prior distribution by partitioning the predictors into $k$ blocks, $X=(X_1, X_2, \ldots, X_k)$.
$X_i$ is a submatrix of dimension $n\times p_i$, $i=1,2,\ldots,k$.  The subscript $\bfgambig$ is suppressed here to simplify notation.  The regression setup for the block $g$ prior is
\begin{eqnarray} \label{eq:bhg}
\bfy \mid \alpha, \bfb, \sigma^2 &\sim& N( \alpha \bone + X\bfb , \sigma^2 I), \nonumber \\
\bfb \mid \bfg, \sigma^2 &\sim& N(\boldsymbol{0},A \sigma^2), \\
\mbox{and} \ \pi(\alpha,\sigma^2) &\propto& \frac{1}{\sigma^2}, \nonumber
\end{eqnarray}
where $A$ is a block diagonal matrix defined as
\begin{equation*}
 A = \left( \begin{array}{cccc}
    g_1 (X_1^T X_1)^{-1} & 0 &  \cdots & 0 \\
    0 & g_2 (X_2^T X_2)^{-1} & \cdots & 0 \\
    \vdots & \vdots &  \ddots & \vdots \\
		0 & 0 & \cdots & g_k (X_k^T X_k)^{-1} \\
		\end{array} \right). \\
\end{equation*}

The regression coefficients for the $k$ distinct groups of predictors are taken to be independent \textit{a priori}.  The separate scales $g_i$ allow differential shrinkage on distinct blocks, with the amount of shrinkage on a block governed almost exclusively by the block itself.  The block $g$ prior reduces to the ordinary $g$ prior when the design matrix X is block orthogonal with $k$ orthogonal blocks $X_1, X_2, \ldots, X_k$ and $\bfg=(g_1,g_2,\ldots,g_k)^T=g \bone_k$.

The blocks allow us to capture modeling concepts in our analysis.  In applied work, we motivate blocking in various ways \citep{som:14}.  The predictors that comprise a block may be different measures of a latent construct, they may represent a group of indicators, and so on.  In such cases, it is essential that the analysis be invariant to certain reparameterizations so that the coding of predictors within a block does not affect the analysis.  The block $g$ prior has this invariance (see Appendix~\ref{appb7}).

\subsubsection{Block Hyper-$\bfg$ Prior}\label{sec:blockhyperg}

The block hyper-$g$ prior arises as a specific mixture of block $g$ priors where the mixing distributions on the components of the vector $\bfg$ are independent hyper-$g$ priors:
\begin{equation}
	\pi(\bfg) = \prod_{i=1}^k \frac{a-2}{2}(1 + g_i)^{-a/2}, \, \ g_i > 0. \label{eq:priorg}
\end{equation}
We follow the recommendations in \cite{liang2008mixtures} regarding the choice of the hyperparameter $a$ and take $2 < a \leq 4$, with $a=3$ the default choice.  A more general form of the prior would allow each $g_i$ to have density $\pi_i$ with block-specific hyperparameters $a_i$.  To do so would, in our view, unnecessarily complicate the analysis.  While we study the behavior of the block hyper-$g$ prior in this paper, one can envision different versions of the block $g$ prior where other mixing distributions are used for the $g_i$ \citep[e.g., a block robust prior \emph{\`a la}][]{bayarri2012criteria}.

\subsection{Asymptotic Evaluations of the Block Hyper-$\bfg$ Prior}\label{sec:blockhgstudy}

We evaluate the behavior of the block hyper-$g$ prior under a limit similar to the one described in Section~\ref{sec:asymp}. Consider the model in \eqref{eq:bhg} and \eqref{eq:priorg}, with $\bfy = \alpha \bone + X_1 \bfb_1 + X_2 \bfb_2 + \cdots + X_k \bfb_k + \bfep$.  We define a sequence of problems $\Psi_N = (X_{1(N)}, \ldots, X_{k(N)},\alpha_N,$ $\bfb_{1(N)}, \ldots, \bfb_{k(N)},\bfep_N)$ where the only quantity that changes in the sequence is the group of regression parameters $\bfb_{1(N)}$:
\begin{eqnarray}\label{eq:psiseq2}
\Psi_N  = (X_{1},\ldots, X_{k}, \alpha, \bfb_{1(N)}, \bfb_2, \ldots, \bfb_{k}, \bfep)
\end{eqnarray}
with  $ ||\bfb_{1(N)}|| \rightarrow \infty$ as $N \rightarrow \infty$.
We use the following condition in the remainder.

\begin{cond}\label{eq:bhgorth}
The predictors and the response are centered and the design matrix is block orthogonal:
\begin{eqnarray*}
\bone \indep \bfy, X_1, X_2,\ldots,X_k  \; \mbox{and} \; X_i \indep X_j, \; \mbox{where} \; i \neq j.
\end{eqnarray*}
\end{cond}

The assumption of block orthogonality facilitates asymptotic analysis by providing simpler expressions for many posterior summaries. This condition is not essential to define the block $g$ or block hyper-$g$ prior.  Rather, it leads to the subsequent theoretical results.  Block orthogonality is commonly encountered in designed experiments and in analyses where covariates have been successively orthogonalized.   In cases where Condition \ref{eq:bhgorth} is not satisfied, a variation of the block $g$ prior \citep{som:14} can be used, for which variants of the ensuing results hold.  These results will be reported elsewhere.

Before providing the main results we summarize several aspects of the posterior distribution of the regression model defined by \eqref{eq:bhg} and \eqref{eq:priorg} subject to Condition~\ref{eq:bhgorth}.
The posterior mean of $\bfb$ given $\bfg$ is
\begin{equation}
\widehat{\bfb} = E(\bfb \mid \bfg, \bfy) = \left( \frac{g_1}{1+g_1} \widehat{\bfb}_{1,LS}^T ,\ldots, \frac{g_k}{1+g_k}\widehat{\bfb}_{k,LS}^T \right)^T, \label{eq:postmean}
\end{equation}
where $\widehat{\bfb}_{i,LS}$ denotes the component of the least squares estimator $\widehat{\bfb}_{LS}$ corresponding to block $i$.
The posterior density of $\bfg$ is
\begin{eqnarray*}
\pi(\bfg \mid \bfy) &\propto& \frac{\prod_{i=1}^k (1+g_i)^{-\frac{a+p_i}{2}} }{\|\bfy\|^{n-1} \left[ 1 - \sum_{i=1}^k \frac{g_i}{1+g_i} R_i^2 \right]^{(n-1)/2} }
\end{eqnarray*}
where $R_i^2 = \frac{\bld{y}^T P_{X_i}\bld{y}}{\bld{y}^T \bld{y}} ,\; i=1,2,\ldots,k$ and $P_{X_i}$ is the projection matrix for the column space of $X_i$. It will be useful to define $t_i =\frac{g_i}{1+g_i}$ for $i=1,\ldots,k$ so that, under a block orthogonal design, each $t_i$ represents the shrinkage factor for the $i^{th}$ block under a block $g$ prior with fixed $g$. Then
\begin{eqnarray*}
\pi(\bft \mid \bfy) \propto \prod_{i=1}^k (1-t_i)^{\frac{a+p_i}{2}-2} (1-\sum_{i=1}^k t_i R_i^2)^{-\frac{n-1}{2}}.
\end{eqnarray*}

The following lemma, similar to Lemma \ref{lem3.1}, is the building block for the main results in this section.

\begin{lem}\label{lem4.1}
For the regression model described by \eqref{eq:bhg} and \eqref{eq:priorg} and satisfying Condition~\ref{eq:bhgorth}, as $N \rightarrow \infty$  in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq2}, $R_1^2 \rightarrow 1$ and $R^2_i \rightarrow 0, \; \forall \; i\neq 1$.
\end{lem}

The first of the two main results in this section shows that \emph{ELS} behavior is avoided under the block hyper-$g$ prior.

\begin{thm} \label{thm4.1}
For the regression model described by \eqref{eq:bhg} and \eqref{eq:priorg} and satisfying Condition~\ref{eq:bhgorth},
\[
	E(\bfb \mid \bfy)  = \left( \begin{array}{c}
		E\left(\frac{g_1}{1+g_1}\mid \bfy \right) \widehat{\bfb}_{1,LS} \\
		\vdots \\
		E\left(\frac{g_k}{1+g_k}\mid \bfy \right) \widehat{\bfb}_{k,LS}
		\end{array} \right).
\]
Further assume that $n \geq a+p_1-1$. Then, as $N \rightarrow \infty$  in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq2}, $E\left(\frac{g_1}{1+g_1}\mid \bfy \right) \rightarrow 1$ and, for $i\neq 1$, $E\left(\frac{g_i}{1+g_i}\mid \bfy \right) \rightarrow \Delta_i$ with $ \frac{2}{a+p_i} \leq \Delta_i < 1 $.
\end{thm}
The theorem is proved in Appendix~\ref{appa4}.  Loosely, the theorem says that coefficients in the block with at least one large coefficient show \emph{ELS} behavior, while coefficients in the other blocks (where all coefficients are relatively smaller) do not display \emph{ELS} behavior and are shrunk.  The amount of shrinkage for the (relatively) small coefficients (blocks $i \neq 1$) is driven largely by the ratio of $\bfy^T P_{X_i} \bfy$ and $\widehat{\sigma}^2$.  The lower bound $\frac{2}{a+p_i}$ occurs when $R^2_i=0$ in which case $\widehat{\bfb}_{i,LS}=0$.  The block-specific shrinkage is the key to avoiding the \emph{CLP}, as is shown in the second main result of this section.

\begin{thm}\label{thm4.2}
Consider the two models $M_1$ and $M_2$ in (\ref{TwoModels}) with a block hyper-$g$ prior on $\bfb$ (with $k=2$) as in \eqref{eq:bhg} and \eqref{eq:priorg}. Assume that blocks $X_1$ and $X_2$ satisfy Condition~\ref{eq:bhgorth}  on the design. When $||\bfb_1|| \rightarrow \infty$ ($N \rightarrow \infty$) in the sequence $\{\Psi_N\}$ defined in \eqref{eq:psiseq2}, the Bayes factor $BF(M_2:M_1)$  is bounded away from zero.
\end{thm}

This theorem, proved in Appendix~\ref{appa45}, shows that the block hyper-$g$ prior avoids the {\em CLP}.  The limiting posterior distribution does not declare the regression coefficients for the second block to be zero and does not concentrate on $M_1$.  We believe this to be appropriate behavior, as the least squares estimate of these coefficients does not change in the sequence $\{ \Psi_N \}$ and the evidence in the data is neither conclusive that the coefficients are zero or that they are not zero.

As in Section~\ref{sec:clp}, we note that the posterior distribution of $\sigma^2$ in the sequence $\{ \Psi_N \}$ under the block hyper-$g$ prior is well-behaved. The posterior for $\sigma^2$ does not converge to a standard distribution as $N \rightarrow \infty$, but Corollaries \ref{cor4.1} and \ref{cor4.2} show that the center of the limit distribution is finite and has an upper bound that can be easily calculated.  The proofs of both corollaries can be found in supplementary materials (Appendices \ref{appb3} and \ref{appb4}).

\begin{cor}\label{cor4.1}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Condition~\ref{eq:bhgorth} and let $p=\sum_{i=1}^k p_i$. When $n > k(a-2)+p+1$, as $N \rightarrow \infty$ in the sequence $\{\Psi_N\}$ defined in \eqref{eq:psiseq2}, the sequence of posteriors of $\sigma^2$ converges to the distribution $F(\cdot)$ with density
\[ f(\sigma^2) \propto \frac{1}{(\sigma^2)^{\frac{n+1}{2}-\frac{ka+p}{2}+k}} \exp \Big[ -\frac{(n-p-1)\widehat{\sigma}^2}{2\sigma^2} \Big] \prod_{i=2}^k \gamma \Big(\frac{a+p_i}{2}-1,\frac{(X_i\widehat{\bld{\beta}}_i)^T (X_i\widehat{\bld{\beta}}_i)}{2\sigma^2} \Big) \]
where $\gamma(s,x)= \int_0^x t^{s-1} e^{-t} dt$ is the lower incomplete gamma function.
\end{cor}

\begin{cor}\label{cor4.2}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Condition~\ref{eq:bhgorth}.  Then in the sequence $\{ \Psi_N \}$ defined in \eqref{eq:psiseq2}, \[ \lim\limits_{N \rightarrow \infty} E(\sigma^2 \mid \bfy) \leq \frac{1}{n-1-a-p_1} \Big[ (n-p-1) \widehat{\sigma}^2 + \sum_{i=2}^k (X_i \widehat{\bfb_i})^T (X_i \widehat{\bfb_i}) \Big] \] when $n > a+p_1+1$.
\end{cor}

Note that the bound is finite for all problems in the sequence $\{\Psi_N \}$. The upper bound for the expectation is achieved by the ordinary hyper-$g$ prior (i.e., a block hyper-$g$ prior with $k=1$). In this case
\[ \lim_{N \rightarrow\infty} E(\sigma^2 \mid \bfy) = \frac{(n-p-1) \widehat{\sigma}^2}{n-p-a-1}
\]
which is consistent with  Corollary \ref{cor3.1}.

\section{Consistency of the Block Hyper-$\bfg$ Prior}\label{sec:consistency}

In this section, we analyze the block hyper-$g$ prior with respect to three existing notions of consistency: \emph{information consistency}, \emph{model selection consistency} and \emph{prediction consistency}.  All three are considered by \cite{liang2008mixtures} with respect to the hyper-$g$ prior, and the first two among the seven ``criteria for Bayesian model choice'' posited by \cite{bayarri2012criteria}.

\subsection{Information Consistency}
This form of consistency is directly related to the \textit{Information Paradox} described in Section 3.1.  \cite{liang2008mixtures} define a Bayesian normal linear regression model under a particular prior to be \emph{information consistent} if, under an appropriate limit on the data vector $\bfy$ for a \emph{fixed} sample size $n$,  $R^2_{\bfgam} \rightarrow 1$ for model $\Mgam$ implies $BF(\Mgam : \Mo) \rightarrow \infty$, where $\Mo$ is the null model.  \cite{bayarri2012criteria} provide a formal definition of \emph{information consistency} that applies to models other than the normal linear model.  The following theorem establishes information consistency of the block hyper-$g$ prior.

\begin{thm}\label{thm5.1}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Condition~\ref{eq:bhgorth}. The block hyper-$g$ prior is ``information consistent"  when either of two sufficient conditions hold: \\
(1) $R^2 \rightarrow 1$ and  $n > k(a-2)+p+1$, where $k$ is the total number of blocks, $p=\sum_{j=1}^k p_{j}$ and $p_{j}$ is the size of block $X_{j}$.  \\
(2) For some $i=1,\ldots,k$, $R_i^2 \rightarrow 1$ and  $n \geq a+p_{i}-1$, where $R_{i}^2$ is the component of $R^2$ corresponding to the $i^{th}$ orthogonal block.
\end{thm}

The proof of the theorem is in Appendix \ref{appa5}. Note that Condition (1) provides a form of the theorem where $R^2$ approaches 1 due to growth in size of any arbitrary set of coefficients.  Under Condition (2), the coefficients growing in size all belong to a single block.  Condition (1) requires a larger sample size than does Condition (2).

\subsection{Conditions and Assumptions}\label{sec:assume}
For the remaining two consistency results we revert to the traditional asymptotic setting where parameters are held fixed and the sample size increases.  Before proceeding, we first need to fix the notion of a ``true'' model from which the data $\bfy$ are assumed to have been generated. Assume that $B_T \subseteq \{1,2,\ldots,k\}$ denotes the indices of the blocks included in the true model $\Mt$, where each block has at least one non-zero coefficient.  Then $\Mt: \bfy = \alpha_{T} \bone +  X_{T} \bfb_{T} + \bfep = \alpha_{T} \bone + \sum\limits_{i \in B_T} X_{i,T} \bfb_{i,T} + \bfep$ denotes the true data generating process. Under the model $\Mt$ there are $|B_T| = k_T$ different blocks with separate and independent hyper-$g$ priors on each block.  The following basic model assumptions and conditions are used in the results.

\begin{cond}\label{cond5.1}
The $n \times p$ design matrix $X$ grows in size with the restriction that
\[ \lim_{n \rightarrow \infty} \frac{1}{n} X^T X = D,  \]
 for some $p \times p$ positive definite matrix $D$.
\end{cond}

The following condition is a direct consequence of Condition \ref{cond5.1} \citep{maruyama2011fully}.

\begin{cond}\label{cond5.2}
The design allows the true model $\Mt$ and any arbitrary model  $\Mgam \not \supseteq \Mt$ to be asymptotically  distinguishable:
\[  \lim_{n \rightarrow \infty} \frac{1}{n}  \bfb_{T}^T X_{T}^T (I - P_{X_{\bfgam}}) X_{T} \bfb_{T} = V_{\bfgam}  > 0.
\]
\end{cond}

These conditions are standard assumptions used to establish consistency of Bayesian procedures. \cite{fernandez2001benchmark}, \cite{liang2008mixtures}, \cite{maruyama2011fully} and \cite{bayarri2012criteria} also use these conditions (or slight variations) to demonstrate posterior model selection consistency and prediction consistency of their priors.

\subsection{Model Selection Consistency}\label{sec:modcon}
The second form of consistency we consider is posterior model selection consistency.  A Bayesian model is \emph{model selection consistent} if, when the data $\bfy$ have been generated by model $\Mt$, the posterior probability of model $\Mt$ converges in probability to 1 as the sample size $n \rightarrow \infty$ \citep{fernandez2001benchmark}. The relation between posterior model probabilities and Bayes factors ensures that this consistency criterion can be rephrased as
\begin{eqnarray} \label{eq:cons}
BF(\Mgam : \Mt) \stackrel{P}{\rightarrow} 0 \;  \mbox{ as } n \rightarrow \infty \mbox{ for any model } \Mgam \neq \Mt.
\end{eqnarray}
Criterion \eqref{eq:cons} is precisely the criterion for displaying pairwise consistency of Bayes factors in model selection, which in the fixed-$p$ case coincides with the usual model selection consistency criterion described earlier, also referred to as the strong model selection consistency property.

\begin{thm}\label{thm5.2}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Conditions~\ref{eq:bhgorth}, \ref{cond5.1} and \ref{cond5.2}. For any model $\Mgam$ such that $\Mgam \supset \Mt$ and all predictors in $\Mgam$ that are not in $\Mt$ are in blocks not in $\Mt$, $BF(\Mgam : \Mt) \stackrel{d}{\rightarrow} W_{\bfgam}$ as $n \rightarrow \infty$ for some non-degenerate random variable $W_{\bfgam}$. For all other models $M_{\bfgam}$, $BF(M_{\bfgam} : \Mt) \stackrel{P}{\rightarrow} 0$.
\end{thm}

The theorem is proved in Appendix~\ref{appa6}.
The block hyper-$g$ prior is not model selection consistent, as the Bayes factor in \eqref{eq:cons} does not converge to zero in all situations.  This is also the case for the hyper-$g$ prior of \cite{liang2008mixtures}. The defect in these priors is that, as $n \rightarrow \infty$, the priors do not stabilize.  This defect is fixed in the hyper-$g/n$ prior of \cite{liang2008mixtures} and can be fixed in similar fashion here to produce a model selection consistent block hyper-$g/n$ prior \citep{som:14}.

\subsection{Prediction Consistency}
{\em Prediction consistency} concerns the limiting behavior (as $n \rightarrow \infty$) of the Bayes-optimal prediction $\widehat{y}^*_n$ of the true, unknown response $y^*$ for a new vector of predictors $\bfx^* \in \mathbb{R}^p$.  When the true model is not known, the Bayes-optimal prediction under squared-error loss is the Bayesian model averaged prediction
\[
	\widehat{y}^*_n = E(\alpha \mid \bfy_n) + \sum_{\bfgam \in \Gamma} \pi(\Mgam \mid \bfy_n)\, \bfx^{* T} E(\bfb \mid \bfy_n, \Mgam),
\]
where we have subscripted with $n$ the components that depend on the sample size.  \emph{Prediction consistency} is achieved when $\widehat{y}^*_n \stackrel{P}{\rightarrow} E(y^*) = \alpha_T + \bfx^{*T} \bfb_T$ as $n \rightarrow \infty$. The following lemma and its extension are used in the main result on prediction consistency of the block hyper-$g$ prior.

\begin{lem} \label{lem5.1}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Condition~\ref{eq:bhgorth}. When $\Mt$ is the true model, for any $i \in B_T$
\[ \lim_{n \rightarrow \infty} \int_{(0,1)^{k_T}} \frac{g_i}{1+g_i} \; \pi(\bfg \mid \Mt, \bfy) d\bfg = 1.
\]
\end{lem}
The proof of the lemma is in Appendix \ref{appa7}.  The lemma leads to the following result.

\begin{cor}\label{cor5.1}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Condition~\ref{eq:bhgorth}. For any model $\Mgam$ containing the true model, i.e., for any $\Mgam \supseteq \Mt$,
\[ \lim_{n \rightarrow \infty} E \left( \frac{g_i}{1+g_i} \mid \Mgam, \bfy \right) = 1,\; \mbox{if } i \in B_T.
\]
\end{cor}

While the block hyper-$g$ prior is not model selection consistent, the next theorem, proved in Appendix~\ref{appa9}, shows that it is prediction consistent under Bayesian model averaging (\textit{BMA}).

\begin{thm}\label{thm5.3}
Consider a regression model of the form \eqref{eq:bhg} and \eqref{eq:priorg} which satisfies Conditions~\ref{eq:bhgorth},  \ref{cond5.1} and \ref{cond5.2}. The predictions under BMA are consistent for this model.
\end{thm}

\section{Discussion}\label{sec:disc}
We have identified two novel behaviors, \emph{Essentially Least Squares} estimation and the \emph{Conditional Lindley's Paradox}, that are exhibited by many common mixtures of $g$ priors in Bayesian regression.  Both behaviors stem from the use of a single latent scale parameter that is common to all regression coefficients.  We argue that \emph{ELS} behavior is, in general, undesirable, as it precludes shrinkage of small coefficients in the presence of large ones.  Similarly, we argue that priors exhibiting the \emph{CLP} should be avoided as, asymptotically, they can provide infinite evidence in support of a false hypothesis.  Our analyses are driven by a new,  \emph{conditional information asymptotic} that sheds light on a Bayesian linear model's behavior under a strengthening of the likelihood due to one component of the model.  This style of asymptotic is important in practice, as it is often the case that models are comprised of covariates with coefficients of differing magnitude.

With these considerations in mind, we developed a block hyper-$g$ prior as one possible remedy and provided conditions under which the prior does not suffer from either \emph{ELS} or the \emph{CLP}.  Traditional asymptotic analysis of the new prior revealed that, while consistent for prediction under {\em BMA}, model selection consistency is not achieved in all situations.  As stated in Section~\ref{sec:modcon}, the aspect of the prior causing this defect is the failure of the prior to stabilize as $n \rightarrow \infty$.  \cite{som:14} shows that model selection consistency can be achieved by defining a block hyper-$g/n$ prior, where the prior \eqref{eq:priorg} is replaced with
\[
	\pi(\bfg) = \prod_{i=1}^k \frac{a-2}{2n}(1 + g_i / n)^{-a/2}, \;\;\; g_i > 0.
\]
The scaling in this prior on $\bfg$ offsets the scaling in prior \eqref{eq:zgprior} on $\bfb_{\bfgam}$ much like in \cite{liang2008mixtures}.  The block hyper-$g/n$ prior shares many properties of the block hyper-$g$ prior and successfully avoids the new paradoxes in addition to providing consistency in all three aspects described in Section \ref{sec:consistency}. Properties of the block hyper-$g/n$ prior and derivations of new results will be elaborated on elsewhere.

While this paper contains theoretical developments, the new theory is connected to data analysis and raises practical issues.  One particular question is how to best select the groups or blocks of predictors in the design. To date, our data analyses under the block hyper-$g$ priors \citep{som:14} have been based on identifying predictor variables related to one another through a latent or theoretical construct. Predictors measuring the same construct are placed in the same block, as they are reasoned to likely have comparable coefficient sizes.  This suggests a single scale parameter for these related explanatory variables. In the absence of such knowledge, preliminary empirical research suggests that placing correlated predictors in the same block often leads to better performance. The existence of correlated blocks of predictors is sometimes taken to indicate the existence of previously unknown latent constructs. There is scope for theoretical investigation as to why this choice works  or if some other choice can be established as ``optimal" under specific settings.

Finally, the results presented in Sections~\ref{sec:newprior} and \ref{sec:consistency} required block orthogonality of the predictor variables (Condition~\ref{eq:bhgorth}). We note that this condition can be relaxed to obtain similar results under a modified version of the \emph{conditional information asymptotic} under suitable adjustments to the original formulation of a block $g$ prior  \citep{som:14}.  Results along these lines will be reported elsewhere.

\input{BlockHyperG_Appendix}

\bibliographystyle{apa}
\bibliography{BlockHyperG}

\input{BlockHyperG_Supplement}

\end{document}


TITLE: Compute $\lim_\limits{n \to \infty} \int_{0}^{1} f_n\,\mathrm d\lambda$
QUESTION [6 upvotes]: Let $f_n =\big[\cos\left(1+\sin(x^5)\right)\big]^n$ and consider $L_1\big([0,1], \mathcal{L}, \lambda\big)$ ($\mathcal{L}$ denotes the Lebesgue $-\,\sigma$ algebra and $\lambda$ the lebesgue measure) compute $$\lim_{n \to \infty} \int_0^1 f_n\,\mathrm d\lambda$$

First I note that $|f_n| \leq 1$, $\forall n \in \mathbb{N}$ and since $1 \in L_1([0,1], \mathcal{L}, \lambda)$ then $f_n \in L_1([0,1], \mathcal{L}, \lambda)$ then I try to show that
$$\lim_{n \to \infty} f_n=0$$
and next used the Lebesgue dominated convergence theorem, but I don’t sure to show that $\lim_\limits{n \to \infty} f_n=0\,.$
Any hint or help I will be very grateful.

REPLY [3 votes]: Note that $-1 \leqslant\sin(x^5) \leq 1$, and so $|\cos(1 + \sin(x^5))| < 1$ except when $\sin(x^5) = -1 \iff x^5 = 3\pi / 2 \pm 2k \pi$. Furthermore, we have that pointwise, whenever $|\cos(1 + \sin(x^5))| < 1$, $f_n \to 0$; so the only thing we need is that $x^5 = 3\pi / 2 \pm 2k \pi$ on a set of measure $0$. But this is easy, since there are countably many solutions, and countable sets have measure $0$.
And even then, there are no solutions on $[0,1]$, as Angelo pointed out. So you're good without even invoking anything about null sets!


text:
\section{Finite Union of Compact Sets is Compact}
Tags: Union, Set Union, Compact Spaces, Set Union

\begin{theorem}
Let $T = \left({S, \tau}\right)$ be a [[Definition:Topological Space|topological space]].
Let $n \in \N$ be a [[Definition:Natural Number|natural number]].
Let $\left\langle{U_i}\right\rangle_{1 \mathop \le i \mathop \le n}$ be a [[Definition:Finite Sequence|finite sequence]] of [[Definition:Compact Topological Subspace|compact subsets]] of $T$.
Let $\mathcal U_n := \displaystyle \bigcup_{i \mathop = 1}^n U_i$ be the [[Definition:Union of Family|union]] of $\left\langle{U_i}\right\rangle$.
Then $\mathcal U_n$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
\end{theorem}

\begin{proof}
Proof by [[Principle of Mathematical Induction|induction]]:
For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the [[Definition:Proposition|proposition]]:
:$\mathcal U_n := \displaystyle \bigcup_{i \mathop = 1}^n U_i$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
$P \left({0}\right)$ is the case:
:$\mathcal U_0 := \displaystyle \bigcup_{i \mathop = 1}^0 U_i$
From [[Union of Empty Set]]:
:$\displaystyle \bigcup_{i \mathop = 1}^0 U_i = \varnothing$
From [[Empty Set is Compact Space]] it follows that:
:$\mathcal U_0$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
$P \left({1}\right)$ is true, as this just says:
:$U_1$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
=== Basis for the Induction ===
$P \left({2}\right)$ is the case:
:$U_1 \cup U_2$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
which is proved as follows:
Let $\mathcal C$ be an [[Definition:Open Cover|open cover]] of $U_1 \cup U_2$.
Then $\mathcal C$ is an [[Definition:Open Cover|open cover]] of both $U_1$ and $U_2$.
As $U_1$ and $U_2$ are both [[Definition:Compact Topological Subspace|compact]] in $T$:
:$U_1$ has a [[Definition:Finite Subcover|finite subcover]] $C_1$ of $\mathcal C$
:$U_2$ has a [[Definition:Finite Subcover|finite subcover]] $C_2$ of $\mathcal C$.
Their [[Definition:Set Union|union]] $C_1 \cup C_2$ is a [[Definition:Finite Subcover|finite subcover]] of $\mathcal C$ for $U_1 \cup U_2$.
From [[Union of Finite Sets is Finite]] it follows that $C_1 \cup C_2$ is [[Definition:Finite Subcover|finite]].
As $\mathcal C$ is arbitrary, it follows by definition that $U_1$ and $U_2$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
This is our [[Principle of Mathematical Induction#Basis for the Induction|basis for the induction]].
=== Induction Hypothesis ===
Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.
So this is our [[Principle of Mathematical Induction#Induction Hypothesis|induction hypothesis]]:
:$\mathcal U_k := \displaystyle \bigcup_{i \mathop = 1}^k U_i$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
Then we need to show:
:$\mathcal U_{k+1} := \displaystyle \bigcup_{i \mathop = 1}^{k+1} U_i$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
=== Induction Step ===
This is our [[Principle of Mathematical Induction#Induction Step|induction step]]:
We have that:
:$\displaystyle \bigcup_{i \mathop = 1}^{k+1} U_i = \left({\bigcup_{i \mathop = 1}^k U_i}\right) \cup U_{k+1}$
By the [[Finite Union of Compact Sets is Compact#Induction Hypothesis|induction hypothesis]]:
:$\mathcal U_k$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
By the [[Finite Union of Compact Sets is Compact#Basis for the Induction|basis for the induction]]:
:$\mathcal U_k \cup U_{k+1}$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the [[Principle of Mathematical Induction]].
Therefore:
:$\displaystyle \forall n \in \N: \bigcup_{i \mathop = 1}^n U_i$ is [[Definition:Compact Topological Subspace|compact]] in $T$.
{{qed}}
[[Category:Compact Spaces]]
[[Category:Set Union]]
izenikmugsid70js3fh0qx26zm046b3
\end{proof}

config: wiki


TITLE: Graph Theory and Dijkstra's Algoirthm
QUESTION [1 upvotes]: I am trying to use Dijkstra's Algorithm to calculate the best route the score the most objectives in a game within 60 seconds. However, some objectives in the game grant more points when scored. Is there any way I can account for it? Using weighted graphs, I can make certain paths longer than others making it take more time in my situation, however it does not help me with my main issue. If anyone can help me in addressing this situation, or tell me about another pathfinding algorithm that may help me account for this, it would be greatly appreciated.

REPLY [0 votes]: Yes, you have to use weighted graph for problems like this. The Algorithm stays the same except that the length of paths change .


TITLE: limit of $ f(n) = 100 \left (1 - \frac{1}{n}\right) ^{ n}$
QUESTION [3 upvotes]: So I was daydreaming about math (like I do frequently) and I came up with this question/riddle.
Say you have a die. If you roll a 1 you lose, otherwise, you win. This die has n sides on it, and you roll the die n times. Are your odds better with a large n, or a small n?
If figured out that the function to calculate your odds of winning (with n sides and n rolls) is
$$ f(n) = 100 \left (1 - \frac{1}{n}\right) ^{ n}$$
Using this function, I found out the larger the n, the better your odds of not rolling a 1. I made a short python program here to try and see what it converges upon. It seems to converge upon 36.7877 ish, but how do I find out what the exact limit is?
I think that this might be an important number, and it reminds me of this question. I'm not claiming that this would be as important as e, but it seems like it should be important.
TL;DR What is the limit of
$\displaystyle f(n) = 100 \left (1 - \frac{1}{n}\right) ^{ n}$, as n approaches infinity?

REPLY [1 votes]: $$\begin{align*}
\lim_{n\to+\infty}100\left(1-\frac{1}{n}\right)^n&=
\lim_{n\to+\infty}100\left(1+\frac{1}{-n}\right)^n\\
&=\lim_{n\to+\infty}100\left[\left(1+\frac{1}{-n}\right)^{-n}\right]^{-1}\\
&=100e^{-1}\\
&=\frac{100}{e}.
\end{align*}
$$


TITLE: Projective dimension
QUESTION [2 upvotes]: Is it true that if a module has a free resolution of length $d$ then any of its submodule has a free resolution of length $\leq d$?

REPLY [1 votes]: Counterexamples can even be found in a domain, by taking rings of higher dimension or singular rings—once you're no longer over a PID, ideals will suffice.  Take $R = k[x,y]$, the module $M = R$ itself, and the submodule $M' = (x,y)$.  Or, take the ring $S = k[x,y]/(x^3-y^2)$, the module $N = S$ itself, and the submodule $N' = (x,y)$.


TITLE: Comparing two binomial proportions
QUESTION [0 upvotes]: Gallup runs a variety of opinion polls. In August of 2017 and again in August 2018, they asked survey participants about their feelings on the computer industry. Simplifying the results a bit: in 2017, 59% of those surveyed said they had positive feelings towards the computer industry. But in 2018, that percentage dropped to 45%. Let’s say there were 300 adults surveyed in 2017 and 400 adults surveyed in 2018.
Do you think there is sufficient evidence to say that the proportion of adults who felt positively towards the computer industry decreased between 2017 and 2018?
My solution: I got the error bound interval as (0.0645,0.2155), but how can I answer the above question?

REPLY [0 votes]: In 2017, you had $x_1= .59(300) = 177$  favorable
votes out of $n_1 =300,$ and in 2018 you had $x_2=.48(400) = 180$
favorable votes out of $n_2=400.$
In R, the procedure prop.test tests $H_0: p_1=p_2$
against $H_a: p_1 \ne p_2$ and provides a 95% confidence interval for $p_1 - p_2,$ as shown below. I declined a continuity
correction on account of the relatively
large sample sizes.
prop.test(c(177,180), c(300,400), cor=F)

        2-sample test for equality of proportions
        without continuity correction

data:  c(177, 180) out of c(300, 400)
X-squared = 13.445, df = 1, p-value = 0.0002456
 alternative hypothesis: two.sided
95 percent confidence interval:
 0.06601082 0.21398918
sample estimates:
prop 1 prop 2
  0.59   0.45

The null hypothesis is rejected at any reasonable
significance level on account of the P-value almost $0.$
[The chi-squared statistic $13.445$ is the square of
the z-score used in an approximate normal test.]
The CI for the difference in proportions is
$(0.066, 0.214).$ This is substantially the same
as your result. So you are on a correct track.
The slight discrepancy may be due
to the use of a continuity correction or to the
method of estimating the standard error of $\hat p_1 - \hat p_2.$
To make a confidence interval, the standard error
of the difference $\hat p_1 - \hat p_2$ is found
by estimating the variances of $\hat p_i = x_i/n_i$
separately, adding them, and taking the square root.
The R procedure for the hypothesis test above
uses the same standard error.
Some forms of the hypothesis test use a standard
error based on $p = p_1 = p_2,$ according to $H_0,$
and using $\hat p = (x_1+x_2)/(n_1+n_2).$ However, some statisticians say that
this 'pooled' method should not be used for making
the CI.
Overall, I have seen at least four versions of this
test in various authoritative textbooks and popular statistical software
programs--depending on whether a continuity correction
is used and how the standard error is estimated.


TITLE: Example of group of order $p^3$
QUESTION [2 upvotes]: Let $p$ be a prime number
I am trying to find an example of group of order $p^3$ that is non abelian.
I know that a group of order $p$ or $p^2$ is abelian, but how to find an example of non abelian group of order $p^3$?
Any insights would be helpful.

REPLY [3 votes]: Consider  group of all 3×3 upper triangular matrices  with diagonal entries 1  and non diagonal elements in $Z_p$ then for any prime p this group is a non abelian group of order $p^3$.
Hope it works


TITLE: How to find the roots of $x³-2$?
QUESTION [3 upvotes]: I'm trying to find the roots of $x^3 -2$, I know that one of the roots are $\sqrt[3] 2$ and $\sqrt[3] {2}e^{\frac{2\pi}{3}i}$ but I don't why.
The first one is easy to find, but the another two roots?
I need help
Thank you

REPLY [2 votes]: Let $x=z\sqrt[3]2$. Then $0=x^3-2=2z^3-2$ and so $z^3=1$. Write $z=e^{i\theta}$ and solve for $\theta$.