text:
\begin{document}

\title{{\large Random interlacements on Galton-Watson Trees}}

\author{Martin Tassy\\
\emph{\small }\\
{\scriptsize ENS cachan, antenne de bretagne}\\
{\scriptsize }\\
{\scriptsize June 2, 2010}}

\address{Martin Tassy, ENS Cachan, Antenne de Bretagne, Avenue Robert Schumann,
35170 Bruz, France}

\address{email: martin.tassy@ens-cachan.org}

\thanks{Martin Tassy wishes to thank Ji\v{r}� \v{C}ern� for scientific guidance
as well as the ETH Zurich, where this research was conducted, for
its hospitality and Professor A.S. Sznitman who gave him this opportunity
to work in Zurich.}
\begin{abstract}
We study the critical parameter $u^{*}$ of random interlacements
percolation (introduced by A.S Sznitman in \cite{Szn09}) on a Galton-Watson
tree conditioned on the non-extinction event. Starting from the previous
work of A. Teixeira in \cite{Tei09b}, we show that, for a given law
of a Galton-Watson tree, the value of this parameter is a.s. constant
and non-trivial. We also characterize this value as the solution of
a certain equation.
\end{abstract}
\maketitle

\section{introduction}

The aim of this note is to the study random interlacements model on
a Galton-Watson tree. We will mainly be interested in the critical
parameter of the model. In particular we want to understand whether
this parameter is non trivial (that is different from $0$ and $\infty$),
whether it is random and how it depends on the law of the Galton-Watson
tree. Our main theorem answers all of these questions and even goes
further by characterizing the critical parameter as the solution of
a certain equation.

The random interlacements model was recently introduced on $\mathbb{Z}^{d}$,
$d\geq3,$ by A.S. Sznitman in \cite{Szn09} and generalised to arbitrary
transient graphs by A. Teixeira in \cite{Tei09b}. It is a special
dependent site-percolation model where the set $\mathcal{I}$ of occupied
vertices on a transient graph $\left(G,\mathcal{E}\right)$ is constructed
as the trace left on $G$ by a Poisson point process on the space
of double infinite trajectories modulo time shift. The density of
the set $\mathcal{I}$ is determined by a parameter $u>0$ which comes
as a multiplicative parameter of the intensity measure of the Poisson
point process. In this paper, we will not need the complete construction
of the random interlacements percolation. For our purposes it will
be sufficient to know that the law $Q_{u}^{G}$ of the vacant set
$\mathcal{V}=G\setminus\mathcal{I}$ of the random interlacements
at level $u$ is characterized by \begin{equation}
Q_{u}^{G}\left[K\subset\mathcal{V}\right]=e^{-u\mbox{cap}_{G}\left(K\right)},K\subset G\mbox{ finite},\label{eq:formulecap}\end{equation}
where $\mbox{cap}_{G}\left(K\right)$ is the capacity of $K$ in $G$
(see Section 2 for definition). In addition to this formula we will
need the description of the distribution of the vacant cluster containing
a given vertex in the case when $G$ is a tree given in \cite{Tei09b}
which we state in Theorem \ref{thm:augusto perc-1} below.

The critical parameter $u_{G}^{*}$ of random interlacements on $G$
is defined as:\begin{equation}
u_{G}^{*}=\inf_{u\in\mathbb{R}^{+}}\left\{ u\,:\, Q_{u}^{G}\mbox{-a.s. all connected components of }\mathcal{V}\mbox{ are finite}\right\} .\label{eq:blabla}\end{equation}

In this article we take the graph $G$ to be a Galton-Watson rooted
tree $T$ defined on a probability space $\left(\Omega,\mathcal{A},\mathbb{P}\right)$,
conditioned on non-extinction. We denote by $\varnothing$ the root
of the tree, $\left(\rho_{i}\right)_{i\geq0}$ the offspring distribution
of the non-conditioned Galton-Watson process, $f$ its generating
function and $q$ is the probability of the extinction event. $\bar{\mathbb{P}}$
stands for the conditional law of the Galton-Watson tree on the non-extinction
event and $\bar{\mathbb{E}}$ for the corresponding conditional expectation.
We assume that $T$ is supercritical that is \begin{equation}
\sum_{i=0}^{\infty}i\rho_{i}>1\tag{\ensuremath{A0}}.\label{eq:a0}\end{equation}
If \eqref{eq:a0} is satisfied, then $\bar{\mathbb{P}}$ is well defined
and $T$ is $\bar{\mathbb{P}}$-a.s. transient, see for example Proposition
3.5 and Corollary 5.10 of \cite{LyonsPer}. Thus the random interlacements
are defined on $T$ and in particular $Q_{u}^{T}$ is $\bar{\mathbb{P}}$-a.s.
well-defined.

To state our principal theorem we introduce $\widetilde{T}$ the sub-tree
of $T$ composed of the vertices which have infinite descendence.
We recall the Harris decomposition (cf. Proposition 5.23 in \cite{LyonsPer}):
under $\bar{\mathbb{P}}$, $\widetilde{T}$ is a Galton-Watson tree
with generating function $\widetilde{f}$ given by\begin{equation}
\widetilde{f}\left(s\right)=\frac{f\left(q+\left(1-q\right)s\right)}{1-q}.\label{eq:ftilde}\end{equation}

\begin{thm}
\label{thm:main}Let $T$ be a Galton Watson tree with a law satisfying
\eqref{eq:a0}. Then there exists a non-random constant $u^{*}\in\left(0,\infty\right)$
such that \begin{equation}
\mbox{\ensuremath{u_{T}^{*}=u^{*}}\ensuremath{\,,\,\bar{\mathbb{P}}\mbox{-a.s.}}}\label{eq:b1}\end{equation}
Moreover if we denote by $\mathcal{L}_{\chi}\left(u\right)=\bar{\mathbb{E}}\left[e^{-u\mbox{cap}_{T}\left(\left\{ \varnothing\right\} \right)}\right]$
the annealed probability that the root is vacant at level $u$ (cf
\ref{eq:formulecap}), then $u^{*}$ is the only solution on $\left(0,\infty\right)$
of the equation\begin{equation}
\mbox{ \ensuremath{\left(\widetilde{f}^{-1}\right)'\left(\mathcal{L}_{\chi}\left(u\right)\right)=1}.}\label{eq:b2}\end{equation}

\end{thm}
The main difficulty in proving this theorem is the dependence present
in the model. More precisely, for any $x\in T$, the probability that
$x\in\mathcal{V}$ is given by\[
Q_{u}^{T}\left[x\in\mathcal{V}\right]=e^{-u\mbox{cap}_{T}\left(x\right)}.\]
The capacity $\mbox{cap}_{T}\left(x\right)$ depends on the whole
tree $T$. It is thus not possible to construct the component of the
vacant set containing the root of a given tree as a sequence of independent
generations, which is a key property when proving an analogous statement
for Bernoulli percolation on a Galton-Watson tree.

However, it turns out that despite this dependence, it is possible
to construct a recurrence relation under the annealed measure $\bar{\mathbb{P}}\otimes Q_{u}^{T}$
for a well chosen quantity related to the size of the cluster at a
given point (see \eqref{eq:reccant}). This is done in section 4.
Using this recurrence relation, it is possible to find an annealed
critical parameter $u^{*}$ and show that it is non-trivial. In section
3 we prove that $u_{T}^{*}$ is $\bar{\mathbb{P}}-$a.s. constant
and thus that $u_{T}^{*}=u^{*}$ for $\bar{\mathbb{P}}-$a.e. tree.
Section 2 introduces some preliminary definitions and recall some
useful results for random interlacements on trees.

\section{Definitions and preliminary results}

Let us introduce some notations first. For a given rooted tree $T$
and a vertex $x\in T\setminus\left\{ \varnothing\right\} $, we write
$\hat{x}$ for the closest ancestor of $x$ in $T$, $\left|x\right|$
for its distance to the root, $Z_{x}$ for the number of children
of $x$ and $\mbox{deg}_{T}\left(x\right)$ for its degree. We denote
by $T_{x}$ the sub-tree of $T$ containing $x$ and all its descendants.
If $T$ is a tree with root $\varnothing$, for every child $x$ of
$\varnothing$ we will say that $T_{x}$ is a descendant tree of $T$.
For any infinite rooted tree $T$, we denote by $\widetilde{Z}_{x}$
the number of children of $x$ in $\widetilde{T}$.

For a tree $T$ and a vertex $x$ of $T$, we denote by $P_{x}^{T}$
the law of a simple discrete time random walk $\left(X_{n}\right)_{n\geq0}$
started at $x$. For every set $K$ in $T$, we use $\widetilde{H}_{K}$
to denote the hitting time of the set $K$ defined by\begin{equation}
\widetilde{H}_{K}=\inf_{n\geq1}\left\{ n\,:\, X_{n}\in K\right\} .\end{equation}
We write $e_{K}^{T}$ for the equilibrium measure of $K$ in $T$
and $\mbox{cap}_{T}\left(K\right)$ for its total mass, also called
capacity of the set $K$:\begin{equation}
e_{K}^{T}\left(x\right)=\mbox{deg}_{T}\left(x\right)P_{x}^{T}\left[\widetilde{H}_{K}=\infty\right]1_{x\in K},\end{equation}
\begin{equation}
\mbox{cap}_{T}\left(K\right)=\sum_{x\in T}e_{K}^{T}\left(x\right)=\sum_{x\in K}\mbox{deg}_{T}\left(x\right)P_{x}^{T}\left[\widetilde{H}_{K}=\infty\right].\label{eq:capequa}\end{equation}

Then, according to Corollary 3.2 of \cite{Tei09b}, the definition
\eqref{eq:blabla} of the critical parameter $u_{T}^{*}$ is equivalent
to \begin{equation}
u_{T}^{*}=\inf_{u\in\mathbb{R}^{+}}\left\{ u:Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]>0\right\} .\end{equation}

Finally we recall Theorem 5.1 of \cite{Tei09b} which identifies the
law of the vacant cluster $\mathcal{C}_{x}$ on a fixes tree $T$
with the law of the vacant set left by inhomogeneous Bernoulli site
percolation. This theorem also allows us to compare random interlacements
on $T$ and random interlacements on its descendant trees.
\begin{thm}[Theorem 5.1 of \cite{Tei09b}]
\label{thm:augusto perc-1}Let $T$ be a transient rooted tree with
locally bounded degree. For every vertex $x\in T$ we consider a function
$h_{\textrm{T}}^{x}:T_{x}\rightarrow\left[0,1\right]$ given by:\begin{equation}
h_{\textrm{T}}^{x}\left(z\right)=\mbox{deg}_{T}\left(z\right)P_{z}^{T_{x}}\left[\widetilde{H}_{\left\{ z,\hat{z}\right\} }=\infty\right]P_{z}^{T_{x}}\left[\widetilde{H}_{\hat{z}}=\infty\right]1_{z\neq x}\label{eq:formulef}\end{equation}
and $h_{\textrm{T}}^{x}\left(x\right)=0.$ Conditionally on $\left\{ x\in\mathcal{V}\right\} $,
$\mathcal{C}_{x}\cap T_{x}$ has the same law under $Q_{u}^{T}$ as
the open cluster of $x$ in an inhomogeneous Bernoulli site-percolation
on $T_{x}$ where every site $z\in T_{x}$ is open independently with
probability \begin{equation}
p_{u}\left(z\right)=\exp\left(-uh_{T}^{x}\left(z\right)\right).\label{eq:probaaugusto}\end{equation}

\end{thm}

\section{$\bar{\mathbb{P}}$-a.s. constancy of $u^{*}$}

In this section we prove that for a given Galton-Watson tree $T$
satisfying \eqref{eq:a0} the critical parameter $u_{T}^{*}$ is $\bar{\mathbb{P}}$-a.s
constant. We will use Theorem \ref{thm:augusto perc-1} to prove a
zero-one law for the event $\left\{ Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]=0\right\} $.
The proof of this zero-one law is based on the following definition
and lemma which we learnt in \cite{LyonsPer}. We present here its
proof for sake of completeness.
\begin{defn}
\label{lem:hereditary}We say that a property $\mathcal{P}$ of a
tree is inherited if the two following conditions are satisfied:\begin{equation}
\mbox{\ensuremath{T\,}has \ensuremath{\mathcal{P}\,}\ensuremath{\Rightarrow}\ all descendents of \ensuremath{T}trees have \ensuremath{\mathcal{P}}.}\label{eq:condition3.2}\end{equation}
\begin{equation}
\mbox{All finite trees have \ensuremath{\mathcal{P}}.}\end{equation}

The zero-one law for Galton-Watson trees associated to such properties
is: \end{defn}
\begin{lem}
If $\mathcal{P}$ is an inherited property then, for every Galton-Watson
tree process $T$ satisfying \eqref{eq:a0}, $\bar{\mathbb{P}}\left[T\mbox{ has }\mathcal{P}\right]\in\left\{ 0,1\right\} $.\end{lem}
\begin{proof}
Let $E$ be the set of trees that have the property $\mathcal{P}$
and $Z_{\varnothing}$ the number of children of the root. Using condition
\eqref{eq:condition3.2} we can write\begin{eqnarray}
\mathbb{P}\left[T\in E\right] & = & \mathbb{E}\left[\mathbb{P}\left[T\in E|Z_{\varnothing}\right]\right]\label{eq:TdansE}\\
 & \leq & \mathbb{E}\left[\mathbb{P}\left[\left\{ \forall x:\left|x\right|=1,T_{x}\in E\right\} |Z_{\varnothing}\right]\right].\nonumber \end{eqnarray}
Conditionally on $Z_{\varnothing}$, the random trees $\left(T_{x}\right)_{x:\left|x\right|=1}$
are independent and have the same law as $T$. Hence the last inequality
is equivalent to \begin{eqnarray}
\mathbb{P}\left[T\in E\right] & \leq & \mathbb{E}\left[\left(\mathbb{P}\left[T\in E\right]\right)^{Z_{\varnothing}}\right]\label{eq:3.7}\\
 & \leq & f\left(\mathbb{P}\left[T\in E\right]\right).\nonumber \end{eqnarray}
By assumption \eqref{eq:a0} we know that $\rho_{i}>0$ for some $i\geq2$.
Therefore $f$ is strictly convex on $\left(0,1\right)$ with $f\left(q\right)=q$
and $f\left(1\right)=1$. Hence from \eqref{eq:3.7} we have $\mathbb{P}\left[T\in E\right]\in\left[0,q\right]\cup\left\{ 1\right\} $.
Since all finite trees have $\mathcal{P}$, and $\mathbb{P}\left[T\mbox{ is finite}\right]=q$,
we can deduce that $\mathbb{P}\left[T\in E\right]\in\left\{ q,1\right\} $
and consequently \begin{equation}
\bar{\mathbb{P}}\left[T\in E\right]=\frac{\mathbb{P}\left[\left\{ T\in E\right\} \cap\left\{ \left|T\right|=\infty\right\} \right]}{\mathbb{P}\left[\left\{ \left|T\right|=\infty\right\} \right]}\in\left\{ 0,1\right\} \end{equation}
which finishes the proof of the lemma.
\end{proof}
$\,$
\begin{proof}[Proof of \eqref{eq:b1}]
 To prove that $u_{T}^{*}$ is $\ensuremath{\bar{\mathbb{P}}\mbox{-a.s}}$
constant we show first that, for a tree $T$ with root $\varnothing$,
the property $\mathcal{P}_{u}$ defined by \begin{equation}
\mbox{\ensuremath{T}\mbox{ has} \ensuremath{\mathcal{P}_{u}}iff \ensuremath{T}is finite or \ensuremath{Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]=0},}\end{equation}
 is inherited. Since every finite tree has $\mathcal{P}_{u}$ by definition,
we just have to prove the statement \begin{equation}
\left\{ \exists x\in T,\left|x\right|=1:T_{x}\mbox{ has not }\mathcal{P}_{u}\right\} \Rightarrow\left\{ T\mbox{ has not }\mathcal{P}_{u}\right\} .\end{equation}
Let $x$ be a child of the root such that $\left|T_{x}\right|=\infty$
and $T_{x}$ has not $\mathcal{P}_{u}$ which can also be written
$Q_{u}^{T_{x}}\left[\left|\mathcal{C}_{x}\right|=\infty\right]>0$.
Since $T_{x}\subset T$, $T$ is not finite. We will show that $Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]>0$.

From the formula \eqref{eq:formulef} it follows that for every $z\in T_{x}\setminus\left\{ x\right\} $,
$h_{T}^{x}\left(z\right)=h_{T_{x}}^{x}\left(z\right)$. Using Theorem
\ref{thm:augusto perc-1} this means that, conditionally on $\left\{ x\in\mathcal{V}\right\} $,
the law of the cluster $\mathcal{C}_{x}\cap T_{x}$ under $Q_{u}^{T}$
and the law of the cluster $\mathcal{C}_{x}$ under $Q_{u}^{T_{x}}$
are both the same. In particular we have \begin{equation}
Q_{u}^{T}\left[|\mathcal{C}_{x}\cap T_{x}|=\infty|x\in\mathcal{V}\right]=Q_{u}^{T_{x}}\left[\left|\mathcal{C}_{x}\right|=\infty|x\in\mathcal{V}\right].\label{eq:3.10}\end{equation}
Moreover, we see from \eqref{eq:formulef} that $h_{T}^{x}\left(z\right)=h_{T}^{\varnothing}\left(z\right)$
for every $z\in T_{x}\setminus\left\{ x\right\} $. Applying Theorem
\ref{thm:augusto perc-1} to the clusters $\mathcal{C}_{\varnothing}$
and $\mathcal{C}_{x}$, we see that the law of $\mathcal{C}_{\varnothing}\cap T_{x}$
under $Q_{u}^{T}\left[.|\varnothing,x\in\mathcal{V}\right]$ is the
same as the law of $\mathcal{C}_{x}\cap T_{x}$ under $Q_{u}^{T}\left[.|x\in\mathcal{V}\right]$.
In particular we have \begin{equation}
Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}\cap T_{x}|=\infty|\varnothing,x\in\mathcal{V}\right]=Q_{u}^{T}\left[|\mathcal{C}_{x}\cap T_{x}|=\infty|x\in\mathcal{V}\right].\label{eq:3.11}\end{equation}
 Since on $\left\{ \varnothing,x\in\mathcal{V}\right\} $, $\varnothing$
and $x$ are in the same open cluster, we can rewrite \eqref{eq:3.10}
and \eqref{eq:3.11} as \begin{eqnarray}
Q_{u}^{T}\left[|\mathcal{C}_{x}\cap T_{x}|=\infty|\varnothing,x\in\mathcal{V}\right] & = & Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}\cap T_{x}|=\infty|\varnothing,x\in\mathcal{V}\right]\\
 & = & Q_{u}^{T}\left[|\mathcal{C}_{x}\cap T_{x}|=\infty|x\in\mathcal{V}\right]\nonumber \\
 & = & Q_{u}^{T_{x}}\left[\left|\mathcal{C}_{x}\right|=\infty|x\in\mathcal{V}\right]\nonumber \\
 & > & 0,\nonumber \end{eqnarray}
by hypothesis. Finally, since \begin{eqnarray}
Q_{u}^{T}\left[\varnothing,x\in\mathcal{V}\right] & = & e^{-u\mbox{cap}_{T}\left(\left\{ \varnothing,x\right\} \right)}>0,\end{eqnarray}
 this yields \begin{eqnarray}
0 & < & Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}\cap T_{x}|=\infty|\varnothing,x\in\mathcal{V}\right]Q_{u}^{T}\left[\varnothing,x\in\mathcal{V}\right]\leq Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}^{u}\right|=\infty\right]\end{eqnarray}
 which finishes the proof that $\mathcal{P}_{u}$ is inherited.

We can now apply Theorem \ref{lem:hereditary} and deduce that $\mathbb{\bar{P}}\left(T\mbox{ has }\mathcal{P}_{u}\right)\in\left\{ 0,1\right\} $.
Thus for every $s\in\mathbb{Q}^{+}$, there exists a set $A_{s}\subset\Omega$
such that $\bar{\mathbb{P}}\left[A_{s}\right]=1$ and $1_{Q_{s}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]>0}$
is constant on $A_{s}$. This yields \begin{equation}
T\rightarrow\inf_{s\in\mathbb{Q}^{+}}\left\{ u:Q_{s}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]>0\right\} \end{equation}
is constant on $A=\cap_{s\in\mathbb{Q}^{+}}A_{s}$ with $\bar{\mathbb{P}}\left[A\right]=1$.
But, since $u\mapsto Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]$
is decreasing, we also have: \begin{eqnarray}
u_{*}^{T} & = & \inf_{u\in\mathbb{R}^{+}}\left\{ u:Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]>0\right\} \\
 & = & \inf_{u\in\mathbb{Q}^{+}}\left\{ u:Q_{u}^{T}\left[|\mathcal{C}_{\varnothing}|=\infty\right]>0\right\} \mbox{.}\nonumber \end{eqnarray}
It follows directly that $u_{*}$ is $\mathbb{\bar{P}}\mbox{-a.s}$
constant.
\end{proof}

\section{Characterization of $u^{*}$}

In this section we will show that $u^{*}$ is non-trivial and can
be obtained as the root of equation \eqref{eq:b2}. In order to make
our calculation more natural we will work with the modified tree $T'$
obtained by attaching an additional vertex $\Delta$ to the root of
$T$. This change is legitimate only if $T$ and $T'$ have the same
critical parameter $u^{*}$, which is equivalent to \begin{equation}
Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]>0\mbox{ iff }Q_{u}^{T'}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]>0.\label{eq:fifif}\end{equation}
 To prove \eqref{eq:fifif} observe that by Theorem \ref{thm:augusto perc-1}
that \begin{equation}
Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty|\varnothing\in\mathcal{V}\right]=Q_{u}^{T'}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty|\varnothing\in\mathcal{V}\right].\end{equation}
Since $Q_{u}^{T}\left[\varnothing\in\mathcal{V}\right]>0$ and $Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right]>0$
this is equivalent to\begin{equation}
\frac{Q_{u}^{T}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]}{Q_{u}^{T}\left[\varnothing\in\mathcal{V}\right]}=\frac{Q_{u}^{T'}\left[\left|\mathcal{C}_{\varnothing}\right|=\infty\right]}{Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right]}\end{equation}
so that \eqref{eq:fifif} holds and $u_{T}^{*}=u_{T'}^{*}$.

If $\left|x\right|\geq1$, $\left(T_{x}\right)'$ is isomorphic to
the tree obtained by attaching $\hat{x}$ to $T_{x}$ . We will thus
identify both trees and write $T_{x}^{'}$ for the tree $T_{x}\cup\left\{ \hat{x}\right\} $.

For every tree $T$ we define the random variable \begin{eqnarray}
\gamma\left(T\right) & = & P_{\varnothing}^{T'}\left[\widetilde{H}_{\Delta}=\infty\right].\label{eq:defgamma}\end{eqnarray}
The random variables $\left(\gamma\left(T_{x}\right)\right)_{\left|x\right|=1}$
are related to the random variable $\chi\left(T\right):=\mbox{cap}_{T'}\left(\varnothing\right)$
by \begin{eqnarray}
\chi\left(T\right) & := & \mbox{cap}_{T}\left(\varnothing\right)\label{eq:relation}\\
 & = & \mbox{cap}_{T'}\left(\varnothing\right)=\sum_{x\in\widetilde{T}:\left|x\right|=1}\gamma\left(T_{x}\right).\end{eqnarray}
The second equality is an easy consequence of definition of the capacity
and the third equality follows, using Markov property, from the following
computation: \begin{eqnarray}
\chi\left(T\right) & = & \left(Z_{\varnothing}+1\right)P_{\varnothing}^{T'}\left[\widetilde{H}_{\varnothing}=\infty\right]\nonumber \\
 & = & \left(Z_{\varnothing}+1\right)\sum_{x\in\widetilde{T}:\left|x\right|=1}P_{x}^{T'}\left[\widetilde{H}_{\varnothing}=\infty\right]P_{\varnothing}^{T'}\left[X_{1}=x\right]\nonumber \\
 & = & \left(Z_{\varnothing}+1\right)\sum_{x\in\widetilde{T}:\left|x\right|=1}\frac{1}{\left(Z_{\varnothing}+1\right)}P_{x}^{T}\left[\widetilde{H}_{\varnothing}=\infty\right]\label{eq:calabelpas}\\
 & = & \sum_{x\in\widetilde{T}:\left|x\right|=1}P_{x}^{T_{x}^{'}}\left[\widetilde{H}_{\varnothing}=\infty\right]=\sum_{x\in\widetilde{T}:\left|x\right|=1}\gamma\left(T_{x}\right).\nonumber \end{eqnarray}
The recursive structure of Galton-Watson tree implies that the random
variables $\left(\gamma\left(T_{x}\right)\right)_{\left|x\right|=1}$
are i.i.d. We can use this property and formula \eqref{eq:ftilde}
to express relation \eqref{eq:relation} in terms of Laplace transforms.
This yields\begin{eqnarray}
\mathcal{L}_{\chi}\left(u\right) & := & \bar{\mathbb{E}}\left[\exp\left(-u\mbox{cap}_{T'}\left(\varnothing\right)\right)\right]\label{eq:laplequa}\\
 & = & \bar{\mathbb{E}}\left[\bar{\mathbb{E}}\bigg[\exp(-u\sum_{x\in\widetilde{T}:\left|x\right|=1}\gamma\left(T_{x}\right))|\widetilde{Z}_{\varnothing}\bigg]\right]\nonumber \\
 & = & \bar{\mathbb{E}}\left[\bar{\mathbb{E}}\bigg[\prod_{x\in\widetilde{T}:\left|x\right|=1}\exp\left(-u\gamma\left(T_{x}\right)\right)|\widetilde{Z}_{\varnothing}\bigg]\right]\nonumber \\
 & = & \bar{\mathbb{E}}\left[\bar{\mathbb{E}}\left[\exp\left(-u\gamma\left(T\right)\right)\right]^{\widetilde{Z}_{\varnothing}}\right]\overset{\eqref{eq:ftilde}}{=}\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)\right).\nonumber \end{eqnarray}
Since $\left(\widetilde{f}^{-1}\right)'=\frac{1}{\widetilde{f}'\circ\widetilde{f}^{-1}}$,
this allows us to write \eqref{eq:b2} as\begin{equation}
\ensuremath{\frac{1}{\widetilde{f}'\circ\widetilde{f}^{-1}\left(\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)\right)\right)}=1}\end{equation}
and thus \begin{equation}
\tag*{(1.5)'}\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right)=1.\label{eq:laprime}\end{equation}
Moreover, $\widetilde{f}$ and $\widetilde{f}'$ being bijective,
the uniqueness of the solution is preserved. Thus from now on we will
consider \eqref{eq:b2} and \ref{eq:laprime} as equivalent.

We will now explicit a relation verified by the annealed probability
that $\mathcal{C}_{\textrm{\ensuremath{\varnothing}}}$ is infinite.
\begin{prop}
\label{pro:u*<infini}For a Galton-Watson process, $r^{u}=\bar{\mathbb{E}}\left[Q_{u}^{T}\left(\left|\mathcal{C}_{\textrm{\ensuremath{\varnothing}}}\right|=\infty\right)\right]$
is the largest root in $\left[0,1\right]$ of the equation\begin{eqnarray}
\mathcal{L}_{\chi}\left(u\right)-r^{u} & = & \widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r^{u}\right).\label{eq:laplace}\end{eqnarray}
\end{prop}
\begin{proof}
For every vertex $x\in T$, we introduce the notation \begin{equation}
\mathcal{D}_{x}=\left(\max_{y\in\mathcal{C}_{x}\cap\widetilde{T}_{x}}\left|y\right|\right)-\left|x\right|,\label{eq:reccant}\end{equation}
the relative depth of the cluster containing $x$. Since $\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}\geq n+1\right\} \subset\left\{ \varnothing\in\mathcal{V}\right\} $,
for every $n\in\mathbb{N}$, we have \begin{equation}
Q_{u}^{T'}\left[\left\{ \varnothing\in\mathcal{V}\right\} \cap\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1\right\} \right]=Q_{u}^{T'}\left(\varnothing\in\mathcal{V}\right)-Q_{u}^{T'}\left(\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}\geq n+1\right).\label{eq:prob}\end{equation}
 We can also write \begin{align}
Q_{u}^{T'}\left[\left\{ \varnothing\in\mathcal{V}\right\} \cap\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1\right\} \right] & =Q_{u}^{T'}\left[\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1|\varnothing\in\mathcal{V}\right]Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right]\nonumber \\
 & =Q_{u}^{T'}\left[\cup_{x\in\widetilde{T}:\left|x\right|=1}\left\{ \mathcal{D}_{\textrm{\ensuremath{x}}}<n\right\} |\varnothing\in\mathcal{V}\right]Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right].\label{eq:formulemagique}\end{align}
According to Theorem \ref{thm:augusto perc-1}, we know that conditionally
on $\left\{ \varnothing\in\mathcal{V}\right\} $, under $Q_{u}^{T'}$,
$\mathcal{C}_{\varnothing}$ has the same law as a cluster obtained
by Bernoulli site-percolation. Hence on $\left\{ \varnothing\in\mathcal{V}\right\} $,
the random variables $\left(\mathcal{D}_{x}\right)_{x\in\widetilde{T}:\left|x\right|=1}$
are independent under $Q_{u}^{T}$. Moreover for all vertices $x\in\widetilde{T}$
such that $\left|x\right|=1$ and every $z\in T_{x}^{'}\setminus\left\{ \varnothing\right\} $
we have the equality $h_{T}^{x}\left(z\right)=h_{T_{x}^{'}}^{x}\left(z\right)$.
This implies that \begin{eqnarray}
Q_{u}^{T'}\left[\mathcal{D}_{x}\geq n|\varnothing\in\mathcal{V}\right] & = & Q_{u}^{T_{x}^{'}}\left[\mathcal{D}_{x}\geq n|\varnothing\in\mathcal{V}\right].\end{eqnarray}
So that we can rewrite \eqref{eq:formulemagique} as\begin{align}
Q_{u}^{T'}\left[\left\{ \varnothing\in\mathcal{V}\right\} \cap\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1\right\} \right] & =\left(\prod_{x\in\widetilde{T}:\left|x\right|=1}Q_{u}^{T'}\left[\mathcal{D}_{x}<n|\varnothing\in\mathcal{V}\right]\right)Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right]\nonumber \\
 & =\left(\prod_{x\in\widetilde{T}:\left|x\right|=1}Q_{u}^{T_{x}^{'}}\left[\mathcal{D}_{x}<n|\varnothing\in\mathcal{V}\right]\right)Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right]\label{eq:premierpas}\\
 & =\left(\prod_{x\in\widetilde{T}:\left|x\right|=1}\left(1-\frac{Q_{u}^{T_{x}^{'}}\left[\mathcal{D}_{x}\geq n\right]}{Q_{u}^{T_{x}^{'}}\left[\varnothing\in\mathcal{V}\right]}\right)\right)Q_{u}^{T'}\left[\varnothing\in\mathcal{V}\right].\nonumber \end{align}
According to \eqref{eq:capequa} and \eqref{eq:blabla}, we have\begin{eqnarray}
Q_{u}^{T_{x}^{'}}\left[\varnothing\in\mathcal{V}\right] & = & \exp\left(-u\,\mbox{deg}_{T_{x}^{'}}\left(\varnothing\right)P_{x}^{T_{x}^{'}}\left[\widetilde{H}_{\varnothing}=\infty\right]\right)\label{eq:djadja}\\
 & = & \exp\left(-u\, P_{x}^{T'}\left[\widetilde{H}_{\varnothing}=\infty\right]\right)\nonumber \\
 & = & \exp\left(-u\,\gamma\left(T_{x}\right)\right).\nonumber \end{eqnarray}
Using \eqref{eq:relation} and \eqref{eq:djadja}, \eqref{eq:premierpas}
can be rewritten as \begin{align}
Q_{u}^{T'} & \left[\left\{ \varnothing\in\mathcal{V}\right\} \cap\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1\right\} \right]\nonumber \\
\,\, & =\left(\prod_{x\in\widetilde{T}:\left|x\right|=1}\left(1-Q_{u}^{T_{x}^{'}}\left[\mathcal{D}_{x}\geq n\right]e^{u\gamma\left(T_{x}\right)}\right)\right)e^{-u\sum_{x\in\widetilde{T}:\left|x\right|=1}\gamma\left(T_{x}\right)}\label{eq:lalere}\\
\,\, & =\prod_{x\in\widetilde{T}:\left|x\right|=1}\left(e^{-u\gamma\left(T_{x}\right)}-Q_{u}^{T_{x}^{'}}\left[\mathcal{D}_{x}\geq n\right]\right).\nonumber \end{align}
We can now finally prove \eqref{eq:laplace}. If we denote $r_{n}^{u}=\bar{\mathbb{E}}\left[Q_{u}^{T'}\left(\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}\geq n\right)\right]$,
we have

\begin{align}
\mathcal{L}_{\chi}\left(u\right)-r_{n+1}^{u}:= & \,\,\bar{\mathbb{E}}\left[e^{-u\mbox{cap}_{T'}\left(\varnothing\right)}-Q_{u}^{T'}\left(\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}\geq n+1\right)\right]\nonumber \\
= & \,\,\bar{\mathbb{E}}\left[Q_{u}^{T'}\left(\varnothing\in\mathcal{V}\right)-Q_{u}^{T'}\left(\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}\geq n+1\right)\right]\nonumber \\
\overset{\eqref{eq:prob}}{\,\,\,\,\,\,\,=} & \,\,\bar{\mathbb{E}}\left[Q_{u}^{T'}\left[\left\{ \varnothing\in\mathcal{V}\right\} \cap\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}<n+1\right\} \right]\right]\label{eq:recrecfrero}\\
\overset{\eqref{eq:lalere}}{\,\,\,\,\,\,\,=} & \,\,\bar{\mathbb{E}}\left[\prod_{x\in\widetilde{T}:\left|x\right|=1}\left(\exp\left(-u\gamma\left(T_{x}\right)\right)-Q_{u}^{T_{x}}\left(\mbox{ \ensuremath{\mathcal{D}_{x}}}\geq n\right)\right)\right]\nonumber \\
= & \,\,\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r_{n}^{u}\right).\nonumber \end{align}
The sequence $\left(r_{n}^{u}\right)_{n\in\mathbb{N}}$ is decreasing
by definition. Therefore it converges and its limit $r^{u}=\bar{\mathbb{E}}\left[Q_{u}^{T\text{\textasciiacute}}\left[\mathcal{D}_{\textrm{\ensuremath{\varnothing}}}=\infty\right]\right]$
verifies \begin{equation}
\begin{array}{ccc}
\mathcal{L}_{\chi}\left(u\right)-r^{u} & = & \widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r^{u}\right).\end{array}\label{eq:recurrence pn}\end{equation}
The function $\widetilde{f}$ is strictly convex by \eqref{eq:a0}.
Therefore the function \begin{equation}
x\mapsto\mathcal{L}_{\chi}\left(u\right)-\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-x\right)\end{equation}
 is strictly concave and the equation \begin{equation}
\mathcal{L}_{\chi}\left(u\right)-x=\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-x\right).\label{eq:lasteq}\end{equation}
has at most two roots in $[0,1$). According to \eqref{eq:laplequa},
$0$ is always a root. Assume that there exists another root $x_{0}$
in $\left(0,1\right)$. Then using the concavity we have \begin{equation}
x>\mathcal{L}_{\chi}\left(u\right)-\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-x\right)\label{eq:recrecfrade}\end{equation}
 on $\left(0,x_{0}\right)$. The sequence $\left(r_{n}^{u}\right)_{n\in\mathbb{N}}$
is positive and decreasing and verifies \eqref{eq:recrecfrero}. Thus
\eqref{eq:recrecfrade} and an easy recurrence shows that $\forall n\in\mathbb{N}$,
$r_{n}^{u}\geq x_{0}$. Since $r^{u}$ verifies \eqref{eq:recurrence pn},
$r^{u}$ a root of \eqref{eq:lasteq} and $r^{u}$ can only be $x_{0}$
in this case.

Finally, the tree $T$ have locally finite degree and thus $\left\{ \mathcal{D}_{\textrm{\ensuremath{\varnothing}}}=\infty\right\} =\left\{ \left|\mathcal{C}_{\textrm{\ensuremath{\varnothing}}}\right|=\infty\right\} $.
This yields \begin{equation}
r^{u}=\bar{\mathbb{E}}\left[Q_{u}^{T'}\left[\left|\mathcal{C}_{\textrm{\ensuremath{\varnothing}}}\right|=\infty\right]\right]\end{equation}
 is the largest root of \eqref{eq:laplace} in $\left(0,1\right)$
which finishes the proof of Proposition \ref{pro:u*<infini}.
\end{proof}
We are now able to deduce non-triviality and \ref{eq:laprime} from
the deterministic study of the roots of the equality \eqref{eq:laplace}.
\begin{proof}[Proof of \ref{eq:laprime}]
According to \eqref{eq:laplace}, we have that \begin{equation}
\begin{array}{ccc}
\mathcal{L}_{\chi}\left(u\right)-r^{u} & = & \widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r^{u}\right).\end{array}\end{equation}
 Using Taylor-Laplace formula, this can be rewritten:\begin{eqnarray}
0 & = & r^{u}-\mathcal{L}_{\chi}\left(u\right)+\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r^{u}\right)\nonumber \\
 & \overset{\eqref{eq:laplequa}}{=} & r^{u}-\left(\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)\right)-\widetilde{f}\left(\mathcal{L}_{\gamma}\left(u\right)-r^{u}\right)\right)\label{eq:4.20}\\
 & = & r^{u}\left(1-\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right)-r^{u}\intop_{0}^{1}\left(1-t\right)\widetilde{f}''\left(\mathcal{L}_{\gamma}\left(u\right)-tr^{u}\right)dt\right).\nonumber \end{eqnarray}
From Proposition \ref{pro:u*<infini} and the definition of $u^{*}$,
we can easily deduce that $u^{*}$ is the infimum over $u$ for which
the function \begin{equation}
g_{u}\left(x\right)=1-\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right)-x\intop_{0}^{1}\left(1-t\right)\widetilde{f}''\left(\mathcal{L}_{\gamma}\left(u\right)-tx\right)dt\end{equation}
has a positive root in $\left(0,1\right)$.

We first show that \begin{equation}
\mbox{\ensuremath{g_{u}}has a root in \ensuremath{\left(0,1\right)}iff \ensuremath{g_{u}\left(0\right)>0}.}\label{eq:rootajeje}\end{equation}
 According to \eqref{eq:ftilde}, the function $\widetilde{f}$ is
strictly convex. Therefore, for every $x\in\left(0,1\right)$ we have
\begin{equation}
x\intop_{0}^{1}\left(1-t\right)\widetilde{f}''\left(\mathcal{L}_{\gamma}\left(u\right)-tx\right)dt>0.\end{equation}
 In particular, we have $g_{u}\left(x\right)<g_{u}\left(0\right)$
for every $x\in\left(0,1\right)$. Moreover by definitions of $\gamma$
and $\chi$ we directly have $0<\chi\left(T\right)<\gamma\left(T\right)$
and thus \begin{equation}
\mathcal{L}_{\gamma}\left(u\right)<\mathcal{L}_{\chi}\left(u\right)<1.\end{equation}
Replacing $r^{u}$ by $\mathcal{L}_{\gamma}\left(u\right)$ in the
first line and the third line of \eqref{eq:4.20}, we obtain\begin{equation}
\mathcal{L}_{\gamma}\left(u\right)-\mathcal{L}_{\chi}\left(u\right)+\widetilde{f}\left(0\right)=\mathcal{L}_{\gamma}\left(u\right)g_{u}\left(\mathcal{L}_{\gamma}\left(u\right)\right).\end{equation}
This yields \begin{eqnarray}
g_{u}\left(\mathcal{L}_{\gamma}\left(u\right)\right) & = & \frac{\mathcal{L}_{\gamma}\left(u\right)-\mathcal{L}_{\chi}\left(u\right)}{\mathcal{L}_{\gamma}\left(u\right)}<0.\end{eqnarray}
Since $g_{u}$ is continuous, this finishes the proof of \eqref{eq:rootajeje}.

To finish the proof of \ref{eq:laprime} and non-triviality of $u^{*}$
we shoud show that \ref{eq:laprime} admits exactly one solution $u_{0}\in\left(0,\infty\right)$
and that\begin{equation}
\mbox{\ensuremath{g_{u}\left(0\right)>0}iff \ensuremath{u>u_{0}}.}\label{eq:rootahuhu}\end{equation}
 We have \begin{equation}
g_{u}\left(0\right)=1-\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right)\label{eq:g0}\end{equation}
 with $\widetilde{f}'\left(\cdot\right)=f'\left(q+\left(1-q\right)\cdot\right)$.
Since $f'$ is continuous, we can write\begin{eqnarray}
\lim_{u\rightarrow\infty}\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right) & = & \widetilde{f}'\left(\lim_{u\rightarrow\infty}\mathcal{L}_{\gamma}\left(u\right)\right)=f'\left(q\right)\\
\lim_{u\rightarrow0}\widetilde{f}'\left(\mathcal{L}_{\gamma}\left(u\right)\right) & = & \widetilde{f}'\left(\lim_{u\rightarrow0}\mathcal{L}_{\gamma}\left(u\right)\right)=f'\left(1\right).\nonumber \end{eqnarray}
Moreover since $f\left(q\right)=q$ and $f\left(1\right)=1$, the
strict convexity of $f$ given by \eqref{eq:a0} implies that $f'\left(q\right)<1$
and $f'\left(1\right)>1$. According to \eqref{eq:g0}, this means
that \begin{equation}
\lim_{u\rightarrow0}g_{u}\left(0\right)<0<\lim_{u\rightarrow\infty}g_{u}\left(0\right).\end{equation}
Finally $f'$ being increasing, $\widetilde{f}'$ is also increasing
and $u\mapsto g_{u}\left(0\right)$ is decreasing. Consequently, there
exist a unique $u_{0}\in\left(0,\infty\right)$ such that $g_{u_{0}}\left(0\right)=0$
(which is equivalent to $u_{0}$ is a solution of \ref{eq:laprime}
and we have \eqref{eq:rootahuhu}. This implies that $u^{*}=u_{0}$
and concludes our proof.
\end{proof}
\bibliographystyle{amsalpha}
\addcontentsline{toc}{section}{\refname}
\bibliography{Martin}

\end{document}

config: arxiv


text:
\section{Introduction}
\label{sec:intro}

Belief Propagation (BP) is a powerful iterative message passing
algorithm for graphical models \cite{Pea1988,MM2009,OS2001}. However,
it presents two main drawbacks when applied to highly connected
continuous variable problems: first, the need to work with continuous
probability distributions; and second, the necessity to iterate over
one such probability distribution for each pair of variables.

The first problem can be addressed by projecting the distributions onto a
finite number of moments \cite{sudderth2010nonparametric} and the second by
utilizing the Thouless-Andreson-Palmer (TAP) approach \cite{MM2009,OS2001}
where only single variable marginals are required. Approximate message
passing (AMP), first introduced in \cite{DMM2009}, is one
relaxation of BP that utilizes both of the aforementioned
approximations in order to
solve sparse estimation problems. In AMP's more general setting, as is
considered in Generalized AMP (GAMP) \cite{Ran2011}, the goal of the algorithm
is the
reconstruction of an $N$-dimensional sparse vector $\bf x$ given the
knowledge of an $M$-dimensional vector $\bf y$ obtained via a possibly
non-linear and/or probabilistic output function $h(z)$ performed on a
set of linear projections. Specifically,

\begin{equation}
y_{\mu} = h(z_{\mu}), \quad \text{where} \quad z_{\mu} = \sum_{i=1}^N \Phi_{\mu i}
x_i . \quad \footnotemark
\label{eq:forward_model}
\end{equation}

\footnotetext{In the present work, we use subscript notation to denote the individual coefficients of
vectors, i.e. $y_{\mu}$ refers to the $\mu^{th}$ coefficient of ${\bf y}$ where
$\mu \in \left\{1,2,\dots,M \right\}$, and the double-subscript notation to
refer to individual matrix elements in row-column order.}
For example, if $h(z)=z+\xi$
where $\xi$ is a zero-mean \iid Gaussian random variable, then $h(z)$ represents
an additive white Gaussian noise (AWGN) channel. With this output function,
in the setting $M \ll N$, \eqref{eq:forward_model} is simply the application of
Compressed Sensing (CS) \cite{CR2005a} under noise. AMP is currently
acknowledged as one of the foremost algorithms for such problems in terms of both
its computational efficiency and in the number of measurements required for
exact reconstruction of {\bf x}. In fact, with
properly chosen measurement matrices \cite{KMS2012b,KMS2012,donoho2012information},
one can achieve information-theoretically optimal reconstruction performance for
CS, a hitherto unachievable bound with standard convex optimization approaches.

Just as with any iterative algorithm, the convergence properties of
AMP are of chief analytical concern. Many rigorous results have been
obtained on the performance of AMP in the case of \iid and block \iid
matrices
\cite{BayatiMontanari10,donoho2012information}. Unfortunately,
while AMP performs well for zero-mean \iid projections, performance
tends to drastically decline if one moves away from these simple
scenarios. In fact, even for \iid matrices with a small positive mean,
the algorithm may violently diverge, leading to poor reconstruction
results \cite{CKZ2014}. This instability to slight variations from
these strict assumptions on the projections is a serious problem for
many practical applications of AMP.

The main theoretical reason for these convergence issues has been
identified in \cite{CKZ2014}. Namely, AMP's use of a parallel update,
instead of a sequential one, on the BP variables at each iteration.
Three strategies have been proposed in recent literature to avoid
this problem.
First,
one can highly damp the AMP iterations, as in \cite{KMS2012b,VS2013}.
However, this often requires a
damping factor so large that the cost, in terms of the number of iterations
until convergence, is prohibitive. Additionally, it is not
entirely clear how to determine an optimal damping factor to ensure convergence
in general.
Second,
one can modify the problem
{\it a posteriori} in order to come back to a more favorable situation. For
instance, one might remove the mean of the matrix and of the
measurements \cite{CKZ2014}, or one might modify the algorithm according
to the theoretical
spectrum of the operator $\Phi$ \cite{RSF2014,SAMP2014}, if it is known. This
knowledge about the operator may be prohibitive and could
therefore present a strong limitation in practice.
Third, one might take one step backward in approximation
from AMP to a BP-style iteration \cite{CKZ2014}. This amounts to a
huge cost in terms of both memory and computational efficiency
as there are $O(N^2)$ variables to update with BP as opposed to the the
$O(N)$ utilized in AMP.

In this contribution, we solve these problems by deriving a modified
and efficient AMP algorithm with greatly improved convergence
properties while preserving the $O(N)$ iteration and memory cost of
AMP. We accomplish this by a careful analysis of the relaxation leading from
BP to AMP where we preserve the sequential, or swept,
variable update pattern of BP in our AMP approach. This leads to a
slightly modified set of update rules for the AMP and GAMP algorithms without
affecting the fixed point in any way. The resulting algorithm, which we
denote as Swept AMP (\swamp), possesses
impressive empirical convergence properties. The derivation of \swamp~is
explained next in Sec.~\ref{sec:Derivingswamp}. We then report, in
Sec.~\ref{sec:Results}, numerical results for basic and 1-bit CS,
as well as for group testing. In all of these cases,
huge improvements over the state-of-the-art can be obtained while remaining
robust to projections with troublesome properties.


TITLE: Minimum number of generators for quotients of congruence subgroups of SL(2, Z)
QUESTION [5 upvotes]: For a given positive integer $N$ let $L(N)$ denote the principal congruence subgroup of $\operatorname{SL}(2, \mathbb{Z})$ of level $N$. It is known that $L(N)$ is a finitely generated free group. Let $T(N)$ denote the minimum number of generators. Let $r$ be a number strictly less than $T(N)$.
Question: Is there a congruence subgroup $L$ of $L(N)$ such that the minimum number of generators of $L(N)/L$ is at least $r$?

REPLY [9 votes]: $\DeclareMathOperator\SL{SL}$Not always. For simplicity, take $N$ a large prime $p$. Following user44191's suggestion in the comments, take $r$ to be $T(N)-1$.
Since any congruence subgroup contains a principal congruence subgroup, we may as well assume $L$ contains a principle congruence subgroup. We can write this as $L(p^e M)$ where $M$ is relatively prime to $M$. Then
$$L(p)/ L(p^eM) = \SL_2( \mathbb Z/M) \times \ker ( \SL_2(\mathbb Z/p^e) \to \SL_2( \mathbb Z/p))$$
Now $\SL_2(\mathbb Z/M)$ is a quotient of $\SL_2(\mathbb Z)$ and so can be generated by $2$ elements. The kernel $\ker ( \SL_2(\mathbb Z/p^e) \to \SL_2( \mathbb Z/p))$ is a $p$-group, so it can be generated by a number of elements equal to its $p$-rank, which is $3$. Thus the product can be generated by $5$ elements. (In fact, if we're careful, I'm pretty sure we can reduce this down to $3$, but this is unnecessary.)
Taking $p$ large enough that the principle congruence subgroup $L(p)$ has more than $5$ generators (i.e. taking $p>3$), we get a counterexample.

In the comments you ask whether, for each congruence subgroup $L$, there are congruence subgroups $L'' \subseteq L' \subseteq L$ such that the number of generators of $L'/ L''$ is at least half the number of generators of $L$.
The answer is no.
To see this, choose our congruence subgroup $L$ to be $L(p)$ for $p$ a large prime as above, and $T(p)$ the number of generators of $L$.
Let $[L:L']$ be the index of $L'$ in $L$. Because $L(p)$ is a free group on $T(p)$ generators, its subgroup $L'$ is a free group on $(T(p)-1) [L: L']+ 1$ generators and thus has generator rank at least $(T(p)-1) [L: L']+ 1$.
On the other hand, because $L/ L''$ can be generated by $5$ elements, it admits a surjection from a free group on $5$ generators, so its subgroup $L'/L''$, of index $[L:L']$, admits a surjection from a free group on $(5-1)[L:L']+1$ generators and thus has generator rank at most $4 [L:L']+1$.
To produce a counterexample, it suffices to have
$$ 4 [L:L']+1 <  \frac{ (T(p)-1) [L: L']+ 1}{2} $$
for which, given $[L:L']\geq 1$, it suffices to have $T(p)>10$, something that is easy to achieve for $p$ large enough.


TITLE: Trying to use induction to solve an inequality
QUESTION [0 upvotes]: So from what I've found using excel this inequality wholes true where n > 2 where n is in naturals
I have 2 questions. How would I do this not using excel? Would the easiest way be to use a calculator? I dont understand how else I would solve this equation (by maybe setting them equal and coming up with an answer between 2 and 3 and then rounding up).
In adition, I'm pretty sure the way to solve this is by using induction. So for my base case let N = 3. Then I will let n = k + 1 and need to show that 5^(k+1) + 6^(k+1) > 7^(k+1).
I can manipulate this into saying (5^k * 5) +  (6^k * 6) < (7^k * 7). But where would I go from here? I know I need to somehow use my IH but don't quote know how.
Thanks for the help.

REPLY [4 votes]: We can easily use induction. Base case: $n=3$, then $5^3+6^3=341<343=7^3$. Now the inductive hypotheses: let's assume it's true for some $n=k$, then \begin{align}
7^{k+1}&=7\cdot 7^k\\
&\stackrel{IH}{>}7(5^k+6^k)\\
&=7\cdot 5^k+7\cdot 6^k\\
&>5\cdot 5^k+6\cdot 6^k\\
&=5^{k+1}+6^{k+1}
\end{align}
and so, by the principle of mathematical induction, we're done, thus, the statement $5^k+6^k<7^k$ is true for any $n\geq 3$.


TITLE: Prove the inequality $ \sqrt{a^2 + b^2} \geq \frac{|a-b|}{\sqrt{2}}$
QUESTION [2 upvotes]: Please help me to prove the inequality
$$
\sqrt{a^2 + b^2} \geq \frac{|a-b|}{\sqrt{2}}.
$$

REPLY [1 votes]: Hint: Note that $(a-b)^2+(a+b)^2=2(a^2+b^2)$.


TITLE: BdMO 2016 National Secondary Problem 3.
QUESTION [13 upvotes]: $\triangle{ABC}$ is isosceles with $AB=AC$, $P$ is a point inside $\triangle {ABC}$ such that $\angle{BCP} = 30^{o}$, $\angle{APB} = 150 ^{o}$, $\angle{CAP}=39^{o}$. Find $\angle{BAP}$

This problem is from BdMO 2016 Nationals ( Secondary ), worth of $20$ points. I've tried it after the contest many many times. But couldn't find any solution. Any Hint/Full Solution will be helpful.

REPLY [3 votes]: Angle-chasing with notations found on the figure below gives all angles as functions of a unique unknown angle $s$, as follows

$$\left\{\begin{aligned}t&=&141-s\\u&=&210-s\\z&=&s-40\\y&=&231-2s \end{aligned}\right.\tag{1}$$
and
$$x=2s-210\tag{2}$$
Remarks: 1) the last equation in (1) takes into account the fact that angle in $B$ = angle in $C$.
2) In this last expression, as the considered angle is acute, we must have $0 \leq 231-2s<90 \ \iff \ $
$$70.5 < s <115.5\tag{3}$$
It remains to find $s$. Thus, we have to find another relationship that could be called a contiguity constraint for triangles $ABP$ and $APC$ ; this constraint will come from the law of sines in each triangle :
$$\dfrac{a}{\sin(231-2v)}=\dfrac{b}{\sin(150)} \ \ \text{and} \ \ \dfrac{a}{\sin(141-s)}=\dfrac{b}{\sin(s)}\tag{4}$$
Expressing ratio $a/b$ in two ways and taking into account the value $\sin 150 =\tfrac12$, we get :
$$\underbrace{\sin(141-s)-2\sin(s)\sin(231-2s)}_{= \ \sin(3s+39)}=0 \tag{4}$$
(We don't enter here into computational details)
(4) is possible iff
$$3s+39=0 \ \text{mod.} \ 180 \tag{5}$$
which, taking into account the range given by (3) enforces $3s+39=360 \ \iff s=107$. Plugging this value into (2) gives

$$x=13°$$


TITLE: Quartic equation $x^4-y^4=2$ over rationals
QUESTION [0 upvotes]: Was it already proved that $x^4-y^4=2$ has no solutions over rationals?

Or for simpler sub-problems $x^2-y^4=2$ or $x^4-y^2=2$.

REPLY [0 votes]: We have the following elementary proof there's no solution.
Let's rewrite the equation
$$ (x - y)(x + y)(x^2 + y^2) = x^4 - y^4 = 2z^4 $$
with $ x, y, z \in \mathbb Z $ and $ \gcd(x, y, z) = 1 $.
For all prime $ p \ne 2 $, we have $ 4 \mid 4v_p(z) = v_p(x - y) + v_p(x + y) + v_p(x^2 + y^2) $. As the $ \gcd $ of any two of $ x - y, x + y, x^2 + y^2 $ is at most $ 2 $ (well known result from cyclotomic polynomials, or basic $ \gcd $ manipulations), we also have that at most one of $ v_p(x - y), v_p(x + y), v_p(x^2 + y^2) $ is nonzero.
So $ 4 \mid v_p(x - y), v_p(x + y), v_p(x^2 + y^2) $, which implies that $ x - y, x + y, x^2 + y^2 $ are all three a $ 4 $-th power times a power of $ 2 $ (which we can assume to be one of $ 1, 2, 4, 8 $ by "absorbing" higher powers in
the $ 4 $-th power).
If one of $ x $ or $ y $ is even, then the other is too and $ 16 \mid 2z^4 $ which means that $ 2 \mid z, \gcd(x, y, z) $. Absurd. So $ x $ and $ y $ are both odd and $ v_2(x^2 + y^2) = 1 $.
We'll use the fact that $ 2(x^2 + y^2) = (x - y)^2 + (x + y)^2 $. We distinguish cases depending on how the $ 2 $s are distributed among the three factors:

$ x - y = a^4, x + y = b^4, x^2 + y^2 = 2c^4 $ which gives $ (a^2)^4 + (b^2)^4 = (2c^2)^2 $.
$ x - y = 2a^4, x + y = 8b^4, x^2 + y^2 = 2c^4 $ which gives $ (a^2)^4 + (2b^2)^4 = (c^2)^2 $.
$ x - y = 4a^4, x + y = 4b^4 $ implies that $ x = 2a^4 + 2b^4 $ is even (as well as $ y $). Absurd.
$ x - y = 8a^4, x + y = 2b^4 $ is the same as the second case but replacing $ y $ by $ -y $.

But $ a^4 + b^4 = c^2 $ is known to have no solutions in integers. One can prove this using the general form of a Pythagorean triple to derive an infinite descent.


text:
\section{Introduction}
\label{Sec_Introduction}

Let $M$ be an oriented Riemannian closed three--manifold.
Fix a $\Spin$--structure $\fs$ on $M$ and denote by $\slS$ the associated spinor bundle;
also fix a $\U(1)$--bundle $\sL$ over $M$, a positive integer $n \in \N$ and a $\SU(n)$--bundle $E$ together with a connection $B$.
We consider pairs $(A,\Psi) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS \otimes \sL)\)$ consisting of a connection $A$ on $\sL$ and an $n$--tuple of twisted spinors $\Psi$ satisfying the \emph{Seiberg--Witten equation with $n$ spinors}:
\begin{align}
  \label{Eq_nSW0}
  \begin{split}
    \slD_{A\otimes B} \Psi &= 0 \qand \\
    F_A &= \mu(\Psi).
  \end{split}
\end{align}
Here $\mu\co \Hom(E,\slS \otimes \sL) \to \fg_{\sL}\otimes \su(\slS) = i \su(\slS)$ is defined by
\begin{equation}
  \label{Eq_Mu}
  \mu(\Psi) := \Psi\Psi^* - \frac12|\Psi|^2\,\id_\slS
\end{equation}
and we identify $\Lambda^2 T^*\!M$ with $\su(\slS)$ via
\begin{equation}
  \label{Eq_Lambda=su}
  e^i\wedge e^j \mapsto \frac12[\gamma(e^i),\gamma(e^j)] = \epsilon_{ijk} \gamma(e^k).
\end{equation}

If $n=1$, then $E$ and $B$ are trivial, since $\SU(1) = \set{1}$, and \eqref{Eq_nSW0} is nothing but the classical Seiberg--Witten equation in dimension three, which has been studied with remarkable success, see, e.g., \cites{Chen1997,Lim2000,Kronheimer2007}.
A key ingredient in the analysis of \eqref{Eq_nSW0} with $n=1$ is the identity
\begin{equation*}
  \<\mu(\Psi)\Psi,\Psi\> = \frac12|\Psi|^4,
\end{equation*}
which combined with the Weitzenböck formula yields an a priori bound on $\Psi$ and, therefore, immediately gives compactness of the moduli spaces of solutions to \eqref{Eq_nSW0}.
After taking care of issues to do with transversality and reducibles,
counting solutions of \eqref{Eq_nSW0} leads to an invariant of three--manifolds.

The above identity does not hold for $n \geq 2$ and, more importantly, $\mu$ is no longer proper; hence, the $L^2$--norm of $\Psi$ is not bounded a priori.
From an analytical perspective the difficult case is when this $L^2$--norm becomes very large;
however, also the case of very small $L^2$--norm deserves special attention as it corresponds to reducible solutions of \eqref{Eq_nSW0}.
With this in mind it is natural to blow-up \eqref{Eq_nSW0}, that is, to consider triples $(A,\Psi,\alpha) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS\otimes \sL)\) \times [0,\pi/2]$ satisfying
\begin{equation}
  \label{Eq_nSW}
  \begin{split}
    \|\Psi\|_{L^2} &= 1, \\
    \slD_{A\otimes B} \Psi &= 0 \qand \\
    \sin(\alpha)^2 F_A &= \cos(\alpha)^2 \mu(\Psi),
  \end{split}
\end{equation}
c.f.~\cite{Kronheimer2007}*{Section 2.5}.
The difficulty in the analysis can now be understood as follows:
for $\alpha \in (0,\pi/2]$ equation \eqref{Eq_nSW} is elliptic (after gauge fixing), but as $\alpha$ tends to zero it becomes degenerate.

The following is the main result of this article:
\begin{theorem}
  \label{Thm_A}
  Let $(A_i,\Psi_i,\alpha_i) \in \sA(\sL) \times \Gamma\(\Hom(E,\slS\otimes \sL)\) \times (0,\pi/2]$ be a sequence of solutions of \eqref{Eq_nSW}.
  If $\limsup \alpha_i > 0$, then after passing to a subsequence and up to gauge transformations $(A_i,\Psi_i,\alpha_i)$ converges smoothly to a limit $(A,\Psi,\alpha)$.
  If $\limsup \alpha_i = 0$, then after passing to a subsequence the following holds:
  \begin{itemize}
    \item
      There is a closed nowhere-dense subset $Z \subset M$, a flat connection $A$ on $\sL|_{M\setminus Z}$ with monodromy in $\Z_2$ and $\Psi \in \Gamma\(M\setminus Z, \Hom(E,\slS\otimes \sL)\)$ such that $(A, \Psi, 0)$ solves \eqref{Eq_nSW}.
      $|\Psi|$ extends to a Hölder continuous function on all of $M$ and $Z = |\Psi|^{-1}(0)$.
    \item
      On $M \setminus Z$, up to gauge transformations, $A_i$ converges weakly in $W^{1,2}_\loc$ to $A$ and $\Psi_i$ converges weakly in $W^{2,2}_\loc$ to $\Psi$.
      There is a constant $\gamma > 0$ such that $|\Psi_i|$ converges to $|\Psi|$ in $C^{0,\gamma}$ on all of $M$.
  \end{itemize}
\end{theorem}

\begin{remark}
  \autoref{Thm_A} should be compared with the results of Taubes on $\PSL(2, \C)$--connections on three--manifolds with curvature bounded in $L^2$~\cite{Taubes2012}*{Theorem~1.1}.
  Our proof heavily relies on his insights and techniques.
\end{remark}

\begin{remark}
  Taubes' very recent work~\cite{Taubes2014}*{Theorems 1.2, 1.3, 1,4 and 1.5} implies detailed regularity properties for $Z$;
  in particular, $Z$ has Hausdorff dimension at most one.
  To see that his theorems apply in our situation note that $\sL|_{M\setminus Z}$ is the complexification of a real line bundle $\fl$.
\end{remark}

As is discussed in \autoref{App_Fueter}, gauge equivalence classes of nowhere-vanishing solutions of \eqref{Eq_nSW} with $\alpha = 0$ correspond to Fueter sections of a bundle $\fM$ with fibre $\mathring M_{1,n}$, the framed moduli space of centred charge one $\SU(n)$ ASD instantons on $\R^4$.
In particular, while \eqref{Eq_nSW} degenerates as $\alpha$ tends to zero, for $\alpha = 0$ it is equivalent to an elliptic partial differential equation, away from the zero-locus of $\Psi$.
Morally, this is why one can hope to prove \autoref{Thm_A}.

In view of \autoref{Thm_A}, the count of solutions of \eqref{Eq_nSW} can depend on the choice of (generic) parameters in $\sP$ (the space of metrics on $M$ and connections on $E$):
since $\mathring M_{1,n}$ is a cone and the Fueter equation has index zero, one expects Fueter sections of $\fM$ to appear (only) in codimension one;
thus, the count of solutions of \eqref{Eq_nSW} can jump along a path of parameters in $\sP$.
In other words:
there is a set $\sW \subset \sP$ of codimension one and the number of solutions of \eqref{Eq_nSW} depends on the connected component of $\sP\setminus\sW$.
In the study of gauge theory on $\rG_2$--manifolds the count of $\rG_2$--instantons also undergoes a jump whenever a solution of \eqref{Eq_nSW} with $\alpha=0$ appears, with $M$ an associative submanifold of a $\rG_2$--manifold and $B$ the restriction of a $\rG_2$--instanton to $M$, see~\cites{Donaldson2009,Walpuski2013a,Walpuski2013}.
So while both the count of $\rG_2$--instantons and the count of solutions of \eqref{Eq_nSW} cannot be invariants, there is hope that a suitable combination of counts of $\rG_2$--instantons and solutions of (generalisations of) \eqref{Eq_nSW} on associative submanifolds will yield an invariant of $\rG_2$--manifolds.
We will discuss this circle of ideas in more detail elsewhere.

\paragraph{Outline of the proof of \autoref{Thm_A}}
The Weitzenböck formula leads to a priori bounds which directly prove the first half of \autoref{Thm_A}.
The proof of the second half is more involved.
For a solution $(A,\Psi,\alpha)$ of \eqref{Eq_nSW}, we show that the (renormalised) $W^{2,2}_A$--norm of $\Psi$ on a ball $B_r(x)$ is uniformly bounded provided the radius is smaller than the \emph{critical radius}
\begin{equation*}
  \rho = \sup \set{ r : r^{1/2}\|F_A\|_{L^2(B_r(x))} \leq 1 }.
\end{equation*}
To control $\rho$ we use a \emph{frequency function} $\scN(r)$, which---roughly speaking---measures the vanishing order of $\Psi$ near $x$.
More precisely, we prove that there exists a constant $\omega > 0$, depending only on the geometry of $M$, such that $\scN(50r)\leq \omega$ implies $\rho\ge r$.
We also show that for any $\omega,\epsilon > 0$ there exists $r>0$ such that $\scN(r) \leq \omega$ provided $|\Psi|(x) \geq \epsilon$.
Thus, we can establish convergence outside the subset $Z = \set{ x \in M : \limsup |\Psi_i|(x)=0 }$.

\paragraph{Acknowledgements}

We would like to thank Cliff Taubes for helpful remarks on \cite{Taubes2012} and an anonymous referee for pointing out a mistake in an earlier version of this article.
The first named author was supported by the German Research Foundation (DFG) within the CRC 701.
The second named author was supported by European Research Council Grant 247331.
A large part of the work presented in this article has been carried out while the second named author was a postdoc at Imperial College London.

\begin{conventions*}
  We write $x \lesssim y$ (or $y \gtrsim x$) for $x \leq c y$ with $c > 0$ a universal constant, which depends only on the geometry of $M$, $E$ and $B$;
  should $c$ depend on further data we indicate that by a subscript.
  $O(x)$ denotes a quantity $y$ with $|y| \lesssim x$.
  We denote by $r_0$ a constant $0 < r_0 \ll 1$; in particular, $r_0 \leq {\rm injrad}(M)$.
  We assume that all radii $r$ on $M$ under consideration are less than $r_0$.
  Throughout the rest of this article $\sL$, $E$ and $B$ are fixed.
\end{conventions*}


TITLE: Maximization problem setup and analysis
QUESTION [1 upvotes]: So, I needed help in setting up the following:

A coffee company sells two types of breakfast blends.  They have on hand $132$ kg of dark roast and $84$ kg of hazelnut.  One breakfast blend will contain half dark roast and half hazelnut and will sell for $\$7$ per kg. The other breakfast blend will contain $3/4$ dark roast and $1/4$ hazelnut and will sell for $\$9.50$ per kg.

My approach:
I see this is an optimization problem and need to show that $132x_1 + 84x_2$ needs to be optimized but confused on the other constraints
I used the convex optimization polygon theory of checking on the endpoints and computing the maximal value, can someone check and elaborate further on the reply below?

REPLY [1 votes]: Hm, no, I do not agree with your approach. Let $x_1$ denote the number of "blend 1" breakfasts and $x_2$ the number of "blend 2" breakfasts that the company will sell. Then you want to maximize the profit of the company, which is $$\max 7x_1+9.5x_2$$ subject to (the capacity constraints) $$\frac12x_1+\frac34x_2\le132\\\frac12x_1+\frac14x_2\le84$$ where $0\le x_1,x_2$.


TITLE: Example of an integral not converging
QUESTION [1 upvotes]: Consider a measurable space $(\Omega,\mathcal{A},\mu)$ with $\mu(\Omega)<\infty$. Let $f_1,f_2,\ldots$ be bounded measurable functions so, that $f_n\to f$ uniformly. Then $f$ is measurable and integrable and $\int f_n\, d\mu\to\int f\, d\mu$.
    Find an example that shows that the condition $\mu(\Omega)<\infty$ is necessary.

Hello, I already proved the claim, but I did not find a counterexample yet that shows, that $\mu(\Omega)<\infty$ cannot be neglected.
Can you help me to find one?
My first idea was to consider $(\mathbb{R},\mathcal{B},\lambda)$, where $\lambda$ is the Lebesgue-measure. Anyway, it is $\lambda(\mathbb{R})=\infty$.

REPLY [5 votes]: On the real line, how about this: $$f_n(x)=\frac{\chi_{[-n,n]}(x)}{1+|x|}$$

REPLY [3 votes]: Take on the measure space you suggest $f_n(x):=\frac 1n\chi_{(0,n)}$.


TITLE: Name for two cycles that share edges or are connected by a path?
QUESTION [1 upvotes]: Suppose I have a finite graph with nodes $I=\{i_1, i_2, \dots, i_n\}$, $i_j$ is always connected to $i_{j+1}$ for $j<n$ (hence $i_1$ need not be connected to $i_n$), and there exist two cycles $C_1 = (i_1, i_2, \dots, i_T, i_1)$ and $C_2 = (i_A, i_{A+1}, \dots, i_n, i_A)$. What kind of properties does this graph or set of nodes have?
Case 1: $T \geq A$. This is like the graph pictured on the left.
$i_1 = A, i_2 = B, i_3 = C, i_4=i_A = D, i_5 = E, i_T=i_6 = F, i_7=G, i_8 = H, i_9=I.$
Case 2: $T < A$. This is like the graph pictured on the right.
$i_1 = K, i_2 = J, i_3 = i_T = L, i_4 = M, i_5 = i_A = N, i_6 = P, i_7 = i_n = O$.

I believe the entire graph is a trail. For the graph on the left we can construct a trail $(F,A,B,C,D,I,H,G,F,E,D)$. On the right, $(L,K,J,L,M,N,P,O,N)$. I know these are Eulerian trails because we use each edge once, but what if these are nodes are only part of a larger graph? Then we say this is an Eulerian subgraph. However, I don't want to rule out the fact that other edges might exist among the nodes in $I$. I am just saying that at least these edges exist.
My hypothesis is that $(i_T, \dots, i_1, \dots, i_T, \dots, i_n, i_A)$ is always a trail, where $i_A$ shows up in the middle either to the left or to the right of $i_T$ in that sequence above. Are there any other properties to discuss here, or is the existence of a trail all that can be guaranteed?

REPLY [1 votes]: I do believe that the graphs as you describe them, without additional edges, have an Eulerian trail, as there are 0 or 2 vertices of odd degree (see the Properties at https://en.wikipedia.org/wiki/Eulerian_path).  But if you are allowed additional edges, it suffices to add odd degree vertices and there's no trail.
For instance, add the $H, E$ edge in your graph on the left.  Or the $M, O$ edge on the right.


TITLE: Show that there is precisely one cyclic code C of length 4 and dimension 2. Write down all the codewords in C.
QUESTION [1 upvotes]: I have shown there is one cyclic code, put not sure how to calculate the codewords in C.
I think that the generator matrix is \begin{bmatrix}1&0&1&0\\0&1&0&1\end{bmatrix}
but am not sure, is that correct and if it is where do I go next?

REPLY [2 votes]: Without using much algebra, note that the standard assumption that
a cyclic code is also a linear code ensures that one of the codewords must be $0000$. Cyclic shifts of this codeword are also in the code.
Now, only three remaining codewords need to be considered. Any length-$4$
vector such as $0001$ which has four distinct cyclic shifts
$0001, 0010, 0100, 1000$ cannot be
a codeword in our cyclic code. A little thought (or just brute-force
writing out all $15$ possible codewords and discarding all that have
$4$ distinct cyclic shifts) then gets us to having $1111$ as another codeword, and $0101$ and $1010$ as the other two: they are the only
codewords with one distinct cyclic shift, and a cyclic shift of one
is the other (or itself).


text:
Following the notation in \cite{botev2017practical}, we first re-state (8) of it:
\begin{align*}
    H_l = B_l W_{l+1}^\top H_{l+1} W_{l+1} B_l + D_l,
\end{align*}
where $l$ is the index of layer. Hence, for a vector $\vs_l$,
\begin{align*}
    H_l \vs_l = B_l W_{l+1}^\top H_{l+1} W_{l+1} B_l \vs_l + D_l \vs_l.
\end{align*}
If we define $\vs_{l+1} = W_{l+1} B_l \vs_l$, we have
\begin{align*}
    H_l \vs_l = B_l W_{l+1}^\top H_{l+1} \vs_{l+1} + D_l \vs_l.
\end{align*}
If we further let $\vy_l = H_l \vs_l$, we have
\begin{align*}
    \vy_l = B_l W_{l+1}^\top \vy_{l+1} + D_l \vs_l.
\end{align*}

Hence, we can get the $(\vs_l, \vy_l)$ pairs for all layers as follows:
\begin{itemize}
    \item Choose an $\vs_1$.

    \item Get all $\vs_l$ by
    \begin{align*}
        \vs_{l+1} = W_{l+1} B_l \vs_l.
    \end{align*}

    \item Compute $\vy_L = H_L \vs_L$.

    \item Get all $\vy_l$ by
    \begin{align*}
        \vy_l = B_l W_{l+1}^\top \vy_{l+1} + D_l \vs_l.
    \end{align*}
\end{itemize}
(It seems to me that) This can be easily paralleled for the mini-batch case.

\subsection{Another concern about K-BFGS}

I always have another concern about K-BFGS, which is kind of a more fundamental issue beyond the various damping schemes. And it is becoming more and more worrying to me as we struggle with the damping part.

Note that in a classical BFGS method, the $(s,y)$ pair is (change in $x$, change in gradient). On the other hand, in K-BFGS, the Hessian (and its inverse $H_g$) we care about is w.r.t the pre-activation $h_l$. Consequently, the $(s_l, y_l)$ pair is (change in $h_l$, change in $dh_l$). ($l$ denotes the index of layer here.)

Currently, we get all $(s_l, y_l)$ pairs ($l=1,...,L$) at one shot, by updating W to be $W^+ = W + p$. Then, a forward and backward pass would give us all (change in $h_l$, change in $dh_l$) all at once. This is a highly efficient way. However, it seems to me that the resulting $(s_l, y_l)$ pairs are questionable.

To see why it is questionable: For a fixed $l$, if we only consider the network after layer $l$, the loss function is determined by $h_l$ and $(W_{l+1}, ..., W_L)$. In other words, we can rewrite the loss function to be $f=f(h_l, W_{l+1}, ..., W_{L})$. The Hessian we care about is the Hessian of $f$ w.r.t $h_l$. Hence, the correct $(s,y)$ pair for $h_l$ should be by changing $h_l$ while keeping $W_{l+1}, ..., W_L$ fixed.

However, recall that in K-BFGS, we get the $(s,y)$ pairs by changing $W$ (i.e. $W_1, ..., W_L$). Changing $W_1, ..., W_l$ gives us the change in $h_l$. But it also makes $W_{l+1}, ..., W_L$ change, which we don't want. As a result, it is hard to say whether the change in $dh_l$ comes from change in $h_l$ or change in $W_{l+1}, ..., W_L$. Thus, the $(s,y)$ pair becomes questionable.

Again, the current way of K-BFGS is purely for the purpose of efficient computation. To verify the above concern, we could try a less efficient way in which we get the $(s, y)$ pairs one layer at a time, which will eliminate the above issue. But, the computational complexity will rise from $O(L)$ to $O(L^2)$.


TITLE: Degree sequence of connected graphs
QUESTION [8 upvotes]: Given graph degree sequence . What is the condition that it can be degree sequence of connected graph. Can anyone please share link to theorem?

REPLY [3 votes]: Recently, there has been some new research on this problem. Delen and Cangul defined a new invariant for graphs (and degree sequences) called omega invariant which helps to determine many properties of all the realizations of a given degree sequence including connectedness, realizability, cyclicness, number of loops, multiple edges, chords, maximum cycle length etc., see [Delen, S., Cangul, I. N., A New Graph Invariant, Turkish Journal of Analysis and Number Theory, 6 (1), (2018), 30-33 DOI: 10.12691/tjant-6-1-4] for the definition and fundamental properties and [212)   Delen, S., Cangul, I. N., Extremal Problems on Components and Loops in Graphs, Acta Mathematica Sinica, English Series, 35 (2) (2019), 161-171,  https://doi.org/10.1007/s10114-018-8086-6, WOS:000458139300011 (https://link.springer.com/content/pdf/10.1007%2Fs10114-018-8086-6.pdf)] for some properties. Some results are as follows: If omega of a degree sequence is less than or equal to -4, all realizations of it must be disconnected. If omega is at least -2, then the realizations could be connected or disconnected (that is, DS is potentially connected). If omega = -2, then every connected realization must be acyclic (tree).If omega is non-negative, all realizations are cyclic, etc...
This new invariant also helps to prove many existing results like Edmonds' theorem.


TITLE: Need help getting started on probability question
QUESTION [2 upvotes]: Let $f_n$ be the density function and $F_n$ the cdf of the sum $S_n$ of n independent uniform (0, 1) random variables.
Show that on each of the n intervals ($i$ - $1$, $i$) for $i$ = $1$ to n, $f_n$ is equal to a polynomial of degree $n - 1$, and $F_n$ is equal to a polynomial of degree $n$.
I'm having trouble understanding where this polynomial is coming from. Am I supposed to deduce its equation from the information given? Any hints on how to start the problem would be greatly appreciated. Thanks!

REPLY [1 votes]: I'd to this by induction.
For $n=1$ this is trivially true.
For $n=2$, use the formula for the density of the sum of two random variables. You don't need to bother with finding the exact coefficients of $f_2$, it suffices to show that $f|_{[0,1]}$ and $f|_{[1,2]}$ are indeed polynomials of degree $1$.
For $n+1$, proceed as for $n=2$, except that one of the summands now has density $f_{n-1}$ instead of a uniform density on $[0,1]$. Again, you're not interested in the precise coefficients of $f_{n+1}$, you just need to show that $f_{n+1}|_{[i-1,i]}$ is a polynomial of degree $n$. You will of course need to use the corresponding property of $f_n$.
Finally, use that $f_n = F_n'$ to prove that $F_n$ has the desired properties too.


TITLE: How to obtain pressure from flow rate just near the outlet of pipe?
QUESTION [0 upvotes]: All i found related to this question is Hagen-Poiseuille equation, but it is not suitable for the ending of pipe.
I want to know what is the pressure of the gas after it is expelled from the pipe. I only know flow rate and diameter of pipe.

REPLY [2 votes]: If the gas velocity is subsonic, then the pressure at the outlet of the pipe is the ambient pressure.


TITLE: Example of Obstructed Galois Deformation Problem
QUESTION [3 upvotes]: A Galois deformation problem is said to be obstructed if we have a surjective map of Artinian rings $A_1 \to A_0$ (inducing the identity on residue fields $k$), with kernel $I$ such that $I\cdot m_{A_1} = 0$, and a Galois representation $\rho_0: G\to GL_N(A_0)$ that lacks a lift to $GL_N(A_1)$. This is equivalent to the non-triviality of the obstruction class $\mathcal{O}(\rho) \in H^2(\Pi, Ad(\overline{\rho_0})) \otimes I$, where $Ad(\overline{\rho})$ is a Galois module with action given by applying the residual representation $\overline{\rho}: G \to GL_N(k)$ and then conjugating. (This setup is taken from Barry Mazur's paper "Deforming Galois Representations.")
My question is, what is an example of such an obstruction?

REPLY [2 votes]: Suppose that $G = \mathbb{Z}/p = \langle \tau \rangle$. Then the universal deformation ring of the trivial representation $G \rightarrow \mathrm{GL}_1(\mathbb{F}_p) = \mathbb{F}^{\times}_p$ is
$$R = \mathbb{Z}_p[[X]]/((1+X)^p - 1).$$
The universal deformation is given explicitly by $G \rightarrow R^{\times}$ sending $\tau$ to $1+X$. There is a map:
$$\rho: G \rightarrow (\mathbb{F}_p[X]/X^p)^{\times}$$
by sending $\tau$ to $1+X$, since $(1+X)^p = 1+X^p = 1 \in \mathbb{F}_p[X]/X^p$. But this representation $\rho$ does not lift to a map to $(\mathbb{F}_p[X]/X^{p+1})^{\times}$, since $\tau$ would have to map to $1+X+vX^p$, and
$$(1+X+vX^p)^p \equiv 1 + X^p \mod X^{p+1}$$
whereas $\tau^p$ should map to $1$. So there is an obstruction to lifting. Let us see this obstruction as a 2 cocycle of the adjoint representation, which is the trivial representation in dimension one. There is a set theoretic lift of $\rho$ given by
$$\rho(\tau^k) = (1+X)^k$$
for $k = 0,1,\ldots,p-1$. This leads to the $2$-cocycle
$$c(\tau^r,\tau^s) = \rho(\tau^r) \rho(\tau^s) \rho(\tau^{r+s})^{-1} =
(1+X)^r (1+X)^s (1+X)^{-(r + s \bmod p)} =
\begin{cases} 1, & r + s < p \\
(1+X)^p=1+X^p, & r+s \ge p \end{cases}$$
interpreting this as being viewed in $\mathbb{F}_p$ via the isomorphism $a \mapsto 1 + a X^p \bmod X^{p+1}$, this is exactly the "carry" $2$-cocycle which generates $H^2(G,\mathbb{F}_p)$.
As for Galois groups, you could take $G$ to be the absolute Galois group of $\mathbb{Q}_q$ for a prime $q$ with $p \| q-1$. Then the pro-p abelian quotient of $G$ is exactly $G = \mathbb{Z}/p  \oplus \mathbb{Z}_p$, where the first factor is the inertia group generated by $\tau$. Then exactly as above the representation sending $\tau$ to $1 + X \mod (X^p,p)$ doesn't lift modulo $(X^{p+1},p)$ and the obstruction generates $H^2(G,\mathbb{F}_p) \simeq \mathbb{F}_p$.


TITLE: Doubt about Clausius Inequality
QUESTION [0 upvotes]: In his text "On the Application of the Theorem of the Equivalence of Transformations to Interior Work", Clausius wrote

If the cyclical process is not reversible, the equivalence values of the positive and negative transformations are not necessarily equal, but they can only differ in such a way that the positive transformations predominate.

Maybe my doubt is related to my inattention on reading the text, but which proposition he made use of in order to assert that the "net transformation" is necessarily positive?

REPLY [0 votes]: This is called Carnot's Theorem.  Maybe having the modern name will help.  https://en.wikipedia.org/wiki/Carnot%27s_theorem_(thermodynamics)


TITLE: Do pushouts of compactly generated Hausdorff spaces exist?
QUESTION [5 upvotes]: Let $A\to X$ and $A\to Y$ be maps of compactly generated Hausdorff spaces. Does the pushout $X\coprod_A Y$ in the category of compactly generated Hausdorff spaces exist? If necessary, one can assume that both these maps are cofibrations.

REPLY [4 votes]: Both categories $\mathbf{CG}$ and $\mathbf{Haus}$ have inclusion functors into $\mathbf{Top}$ which are part of an adjunction. While $\mathbf{CG}↪\mathbf{Top}$ is left adjoint to the functor $k$, with the counit being the identity map from the $k$-ification of $X$ to $X$ with its original topology, the inclusion $\mathbf{Haus}↪\mathbf{Top}$ is right adjoint to the functor $H$, the unit being the quotient map $X\twoheadrightarrow HX$ onto the largest Hausdorff quotient $HX$. These two categories are independent in the following sense:

The reflector $H:\mathbf{Top}\to\mathbf{Haus}$ restricts to a reflector $\mathbf{CG}\to\mathbf{CGHaus}$ since each quotient of a compactly generated spaces is again compactly generated.
The coreflector $k:\mathbf{Top}\to\mathbf{CG}$ restricts to a coreflector $k:\mathbf{Haus}\to\mathbf{CGHaus}$ since $k$ only refines the topology on a space.

The functor $H:\mathbf{CG}\to\mathbf{CGHaus}$ is a left adjoint, so it preserves colimits. That mean that for a diagram $D$ in $\mathbf{CGHaus}$ the colimit in $\mathbf{CGHaus}$ is the same as the Hausdorff quotient $H$ of the colimit in $\mathbf{CG}$, which coincides with the colimit of $D$ in $\mathbf{Top}$ as the inclusion $\mathbf{CG}↪\mathbf{Top}$ preserves colimits.
Dually, the functor $k:\mathbf{Haus}\to\mathbf{CGHaus}$ is a right adjoint, so it preserves limits. That means that for a diagram $D$ in $\mathbf{CGHaus}$ the limit in $\mathbf{CGHaus}$ is the same as the $k$-ification of the limit of $D$ in $\mathbf{Haus}$, which coincides with limit in $\mathbf{Top}$.
Since $\mathbf{Haus}$ is complete, so is $\mathbf{CGHaus}$. And since $\mathbf{CG}$ is cocomplete, so is $\mathbf{CGHaus}$.
So if you want the pushout in $\mathbf{CGHaus}$, then take the pushout in $\mathbf{Top}$ and apply the Hausdorff quotient $H$ to it.


TITLE: (Munkres) Clarification in picture/drawing about quotient topology induced on a set.
QUESTION [0 upvotes]: In Munkres, p.138, Section 22 (The Quotient Topology), example 3 he has the following:
Let $p$ be the map of the real line $\mathbb{R}$ onto the three-point set $A = \{a, b, c\}$. Defined by:
$p(x) = \begin{cases}
     a & \text{if $x > 0$} \\
     b & \text{if $x < 0$} \\
     c & \text{if $x = 0$}
     \end{cases}$

My questions: Why doesn't $c
$ have a circle around it? Why do both $a$ and $b$ have circles around them and then another circle around both? Basically how do you draw this in the first place?

REPLY [2 votes]: These circles tell you what the topology is on the set $\{a,b,c\}$, i.e. they tell you what subsets of $\{a,b,c\}$ are open.
The circle enclosing $a$ means that $\{a\}$ is an open set.
The circle enclosing $b$ means $\{b\}$ is an open set.
The circle enclosing both $a$ and $b$ means that $\{a,b\}$ is an open set.
And the circle enclosing all three of $a,b,c$ means that $\{a,b,c\}$ is an open set.
That's all of the open sets in this topology, with a single exception: the empty subset $\emptyset = \{\}$ is also open. Depending on one's taste in pictorial notation, perhaps one might be inclined to draw a circle enclosing nothing for this purpose.
Anyway, the lack of circle around $c$ tells you that $\{c\}$ is not an open set in this topology.


TITLE: is centrifugal release equal to explosive release
QUESTION [0 upvotes]: Scenario # 1
I put gunpowder and then a ball bearing in an old musket and fire the bullet.
Scenario # 2
Lets imagine I had a motor with a disk on it and there was the same ball bearing stuck on the edge of the disk somewhere. If I spin the motor up fast and then release the ball bearing somehow, it will fire off perpendicular to the tangent line of the release point. Lets imagine for the purposes of comparison, I spin up the motor with enough rpm such that the ball bearing’s velocity equaled the velocity of the musket shot in scenario 1.
Newton's 3rd law of motions states that "for every action there is an opposite and equal reaction". With that in mind, it shouldn’t really matter how I expelled the hunk of lead, would both systems react in the opposite direction the same at the moment of release? (I’m aware that the spinning system would have a torque while it was spinning, but lets ignore that)
The reason I’m asking that is; intuitively the ball bearing is desperate to escape the faster the disk is being spun. It would seem weird that it would suddenly kick the system backwards when it was already straining to leave the system the whole time. Also, there seems to be an intuitive difference because the expelling force in the spinning system is 90 degrees to the applied force.

REPLY [1 votes]: Newton's third law does not necessarily mean that when one object is kicked forward the other is kicked backward. What it means is that forces always come in pairs. If I press down on the floor with a certain force, then the floor pushes back on me with an equal and opposite force (provided I am not breaking the floor with the force I am exerting, obviously). This is the essence of Newton's third law.
When you fire a musket the gun powder explodes, and this explosion pushes on the ball bearing with a considerable amount of force. The ball bearing, in turn pushes back. You feel this sudden force pressing backward as a kick.
In the second scenario there is no kick because there is no sudden force being applied to the motor that pushes the ball bearing away. Think about the forces involved at the moment just before the ball is released. At this point there is only one thing keeping the ball moving in this circular path, and that is whatever is holding it to the disk. In order to move in a circular direction there must be a force on the ball bearing accelerating it toward the center of the disk. If there is, say, a latch holding the ball in place, then it is the normal force of the latch that achieves this. Thus, we have a reaction pair of forces that behaves according to Newton's third law (the latch pushing on the ball bearing and the ball bearing pushing back on the latch). Now, say that we can release this latch without otherwise disturbing the system. Suddenly, we have removed all forces acting on the ball bearing. Because there is no force present to accelerate the ball toward the center of the disk, it flies off in a tangential direction. There is no kick, because there is no reaction pair to cause a kick. The reason the ball flies off in a tangential direction is because there is a lack of forces keeping it moving in a circular direction.


text:
\section{Micro-macro decomposition and motivation }
\label{sec:model}

Following the micro-macro decomposition framework \cite{liu2004boltzmann,lemou2008new}, we reformulate \eqref{eq:f_model}. We first define a scattering operator $\mathcal{L} f=\lgl f \rgl - f$, and let $\Pi$ denote the $L^2$ projection onto the null space of $\mathcal{L}$: $\textrm{Null}(\mathcal{L})=\textrm{Span}\{1\}$.
 We then decompose $f$ orthogonally into $f=\rho +\vareps g$, where $\rho:= \Pi f= \lgl f \rgl$, and  $g:=\frac{1}{\vareps}({\bf{I}}-\Pi)f$ satisfying $\lgl g\rgl=0$. Finally  we apply  $\Pi$ and its orthogonal complement ${\bf{I}}-\Pi$ to
 \eqref{eq:f_model}, and obtain the micro-macro decomposed system:
\begin{subequations}
\label{eq:micro_macro}
\begin{align}
\label{eq:micro_macro_rho}
&\partial_t \rho + \partial_x \lgl vg \rgl = -\sigma_a \rho,\\
\label{eq:micro_macro_g}
\vareps& \partial_t g + ({\bf{I} }-\Pi)\partial_x (vg) + \frac{1}{\vareps}v\partial_x \rho = -\frac{\sigma_s}{\vareps} g -\vareps \sigma_a g.
\end{align}
\end{subequations}
Assume $\sigma_s(x)>0$. As the Knudsen number $\vareps\rightarrow 0$, \eqref{eq:micro_macro} formally converges to its diffusion limit
\begin{align}
\label{eq:diffusion_limit}
\sigma_s g= - v\partial_x \rho, \qquad \partial_t \rho = -\partial_x \lgl vg\rgl-\sigma_a\rho= \lgl v^2\rgl \partial_{x}(\partial_x\rho/\sigma_s)-\sigma_a \rho.
\end{align}

To define AP schemes with unconditional stability in the diffusive regime with $\vareps\ll1$, \cite{peng2019stability} applies a second reformulation to \eqref{eq:micro_macro}
 by adding the weighted diffusive term $\lgl v^2\rgl \partial_{x}(\omega\partial_x\rho/\sigma_s)$ to both sides of \eqref{eq:micro_macro_rho}:
\begin{subequations}
\label{eq:micro_macro_reformulation}
\begin{align}
\label{eq:micro_macro_rho_reformulation}
&\partial_t \rho + \partial_x \lgl v\left(g +v\omega(\partial_x\rho/\sigma_s)\;\right)\rgl = \lgl v^2\rgl \partial_{x}(\omega\partial_x\rho/\sigma_s) -\sigma_a \rho,\\
\label{eq:micro_macro_g_reformulation}
\vareps& \partial_t g + ({\bf{I} }-\Pi)\partial_x (vg) + \frac{1}{\vareps}v\partial_x \rho = -\frac{\sigma_s}{\vareps} g -\vareps \sigma_a g.
\end{align}
\end{subequations}
Here, $\omega$ is a non-negative numerical weight function, and it satisfies $\omega\rightarrow 1$ as $\vareps\rightarrow 0$.

In \cite{peng2019stability}, globally stiffly accurate IMEX-RK time discretizations are applied, where the weighted diffusive term $\lgl v^2\rgl \partial_{x}(\omega\partial_x\rho/\sigma_s)$ on the left hand side of \eqref{eq:micro_macro_rho_reformulation} is treated explicitly and that on the right hand side is treated implicitly.  With LDG methods further applied in space, the resulting schemes  are AP,
unconditionally stable in the diffusive regime, and they also show good performance numerically. However, the choice of $\omega$ is problem-dependent, and it can affect the performance of the methods (see. e.g. Examples 2, 4, 5  in  Section \ref{sec:numerical}).
Moreover, when $\sigma_s(x)$ is not constant,  a spatially dependent weight $\omega$ would  be preferred intuitively  in order to better capture the multiscale behavior. If such weight function is used, one would need to assume $\omega\partial_x \rho/\sigma_s$ to be continuous to ensure the local conservation, and this is apparently not physical due to the weight-dependence.
As far as we know, only weight functions that do not vary spatially have been considered in the literature.


TITLE: Finding A Subgroup of $A_n$ Isomorphic to $S_{n-2}$
QUESTION [1 upvotes]: I am asked to show there exists a subgroup of $A_n$ that is isomorphic to $S_{n-2}$ for $n \ge 3$. Here are some of my thoughts:
Certainly there exists a homomorphism $f : A_n \rightarrow S_n$---namely, take $f$ to be the inclusion map, $f(\sigma) = \sigma$. Because of this, $f^{-1}(S_n)$ will be a subgroup of $A_n$, and I suspect I can extend $f$ in someway to an isomormphism by defining $\varphi : S_{n-2} \rightarrow f^{-1}(S_n)$
I am not really sure how to move forward, but does this seem to be moving in the right direction? It seems that I want to take all even permutation $S_{n-2}$ and map them to themselves, and then take every odd permutation and "correct" it to become an even permutation, but I am not sure why this is right--or if it is even remotely correct. Can $\varphi$ map an odd permutation to an even permutation and still be an isomorphism? It doesn't seem that it could.

REPLY [2 votes]: If $\sigma\in S_{n-2}$ is even, map it to itself. Otherwise, map it to $\sigma\circ(n-1,n)$.


TITLE: Let $a>0$ and $z_{1}>0$. Let $z_{n+1}=[a+z_{n}]^{1/2}$ for $n \in N$. Determine if $z_{n}$ converges or diverges?
QUESTION [0 upvotes]: Let $a>0$ and $z_{1}>0$. Let $z_{n+1}=[a+z_{n}]^{1/2}$ for $n \in N$. Determine if $z_{n}$ converges or diverges?
I am trying to solve it using monotone convergence theorem.
If I let $z_{1} = a^{1/2}$
Then it is easy to show $z_{n}$ is monotonically increasing and bounded above by $1+2*{a}^{1/2}$ and hence convergent.
But I am unable to prove it as a whole for $z_{1}>0$
Please help.

REPLY [1 votes]: If the series converges to a limit $L$ then this limit satisfies
$$L=\sqrt{a+L}\ ,$$
that is, $L^2-L-a=0$, and so
$$L=\frac{1+\sqrt{1+4a}}{2}\ ,$$
where we have chosen the positive root since clearly $L\ge0$.
Now we prove that this really is the limit.  We have
$$\eqalign{
  z_{n+1}-L
  &=\sqrt{a+z_n}-L\cr
  &=\frac{z_n+a-L^2}{\sqrt{a+z_n}+L}\cr
  &=\frac{z_n-L}{\sqrt{a+z_n}+L}\cr}$$
and so
$$|z_{n+1}-L|<\frac1L|z_n-L|\ .$$
We have by induction
$$|z_{n+1}-L|<\frac1{L^n}|z_1-L|$$
and since $L>1$, the right hand side tends to zero as $n\to\infty$.  Therefore $z_n\to L$ as $n\to\infty$.