text:
\begin{document}

\title{Identifying interacting pairs of sites in infinite range Ising models}
\date{June 23, 2010}
\author{Antonio Galves\footnote{AG was partially supported by CNPq grant 305447/2008-4.
 This work is part of CNPq projects 476501/2009-1 and 485999/2007-2.}, Enza Orlandi \footnote{Partially supported by Prin07:20078XYHYS.} and Daniel Yasumasa Takahashi \footnote{Supported by FAPESP grant 2008/08171-0. }}

\maketitle

\begin{abstract}
We consider Ising models (pairwise interaction Gibbs probability measures) in $\Z^d$ with an infinite range potential. We address the problem of identifying pairs of interacting  sites from a finite sample of independent realizations of the Ising model. The sample contains only the values assigned by the Ising model to a finite set of sites in $\Z^d$. Our main result is an upperbound for the probability with our estimator to misidentify the pairs of interacting sites in this finite set.

\end{abstract}

\section{Introduction}

The class of Ising models is a popular family of exponential distributions on the set of binary configurations supported by a finite or a countable set of sites. The law of the Ising model is characterized by a pairwise potential, \textit{i.e.}, a family of real numbers $J(i,j)$ indexed by pairs of sites $(i,j)$. Originally introduced in statistical mechanics as a mathematical model for ferromagnetism, the Ising model has been extensively used, for instance, in computer vision \citep{Woods78, Besag93}, image processing \citep{Cross83}, neuroscience \citep{Schneidman06}, and as a general model in spatial statistics \citep{Ripley81}. The references given above are just starting points of a huge literature.   For a recent statistical physics oriented survey of rigorous mathematical results on  Gibbs distributions, including Ising models, we refer the reader to \citet{Presutti09}.

In this article we consider Ising models having $\Z^d$ as set of sites and with an infinite range potential. This means that we may have pairs of interacting sites $(i,j)$, with $|i-j|$ as big as we want, provided that they satisfy some minor requirements that will be given in Section \ref{sec:results}. By interacting sites, we mean that $J(i,j) \neq 0$. We address the statistical problem of identifying these pairs of interacting sites, given a finite sample of independent realizations of the Ising model.

The Ising model is supported by the set of infinite configurations $\{-1,+1\}^{\Z^d}$. However, from an applied statistics point of view, we cannot observe more than the projection of the Ising model on a finite subset of sites. Therefore, our sample will be constituted by the values that a finite sequence of independent realizations of the Ising model assign to a fixed finite set of sites. As a consequence, we can only identify pairs of interacting sites belonging to the finite set of sites we observe. This finite set of sites is arbitrary. The idea is to make its size increase together with the size of the sample.

We introduce an estimator for the set of interacting pairs of sites belonging to the finite set we observe.
This estimator can be informally described as follows. For each site $i$ in the observed finite set we estimate the conditional probability of the model in $i$, given the remaining sites in the finite set. Then we compare this empirical conditional probability with the empirical conditional probability on the same site $i$ given the remaining sites with the exception of another site $j$, with $j\neq i$. If the two conditional probabilities are statistically equal, we conclude that $J(i,j) = 0$. By \textit{statistically equal} we mean that the weighted difference between the two empirical probabilities is smaller than a certain threshold value, which depends on the size of the sample and on the number of observed sites.

The main result of present article is an upperbound for the probability of misidentifying the pairs of interacting sites in this finite set using our estimator. The proof of this theorem has two ingredients, which are interesting by themselves.

The first ingredient is an upperbound for the probability of misidentification for the Ising model with finite range potential. This is the content of Theorem \ref{teo:bounded}. This theorem applies to the usually considered situation \citep{Ravikumar10, Bento09, Bresler08} where the totality of interacting sites are  observed in the sample.
The second ingredient in the proof of our main theorem is a coupling result given in Theorem \ref{teo:dob}. It says that we can couple together an Ising model with infinite range potential and an Ising model with truncated finite range potential in such a way that the probability of discrepancy at a fixed site $i$ vanishes as the set of observed sites diverges to $\Z^d$. As a consequence of this result, we are able to bound above the probability of misidentification due to the fact that we are able to observe a finite set of sites, not the entire set of interacting sites.  The proof of this result uses Dobrushin's contraction method but this result, as far as we know, has not been presented in the literature. For a presentation of the contraction method in its original framework we refer the reader to \citet{Dobrushin68}.

 As a byproduct of our results, we also obtain an identification theorem for the case of the Ising model on a finite set of points. This finite case was recently studied in several papers, including \citet{Ravikumar10, Bento09, Bresler08}. The case of the Ising model with finite range and homogenous potential was recently studied by \cite{Csiszar06} using a BIC like approach. A comparative discussion of our results versus the ones presented in the above mentioned papers will be done in Section \ref{sec:discussion}.

This paper is organized as follows.   Notation, definitions and results are presented in Section \ref{sec:results}. In Section \ref{sec:simulation} we illustrate our theoretical results with a simulation experiment. Final remarks and a discussion of recent related results are given in Section \ref{sec:discussion}. The proofs of the theorems are presented in the Appendix 1.  Finally, Appendix 2 contains the pseudocode describing the algorithm to simulate the samples for the simulation study.

\section{Notation, definitions and results} \label{sec:results}

\begin{defin}
  A pairwise potential is a family $J=\{ J(i,j): ( i, j) \in \Z^d
  \times \Z^d \} $ of real numbers which satisfy the conditions
\begin{equation}
J(i,i)=0, \qquad   J(i,j)=J(j,i), \qquad  \sup_{i \in \Z^d} \sum_{j \in \Z^d}   |J(i,j)|  <\infty .
\end{equation}
\end{defin}

Let $A=\{-1,1\}$ be the basic binary set and $S=A^{\Z^d} $ be the set of spin configurations on the lattice $\Z^d$.  Fixed configurations will be denoted by lower case letters $x, \ldots$ whereas the capital letter $X$ will denote a random field. A point $ i \in \Z^d $ will be called a site.  For any $i \in \Z^d$, $x(i)$ will denote the value of the configuration $x$ at site $i$. Given a subset $F$ of $\Z^d$, we shall also denote $x(F)=\{x(i): i \in F\}$ and similarly for $X$.

\begin{defin}
The Ising model with pairwise potential $J$ is a random element $X$ with values on $S$, which distribution satisfies
\begin{equation*}
  \mathbb{P} \left( X (i) = x (i) | X (j)=x (j)\, ,\, j\neq i \right) =
\frac{1}{1 + \exp ( -2 \sum_{j\in \Z^d} J(i,j) x (i) x (j) )},
\end{equation*}
for all $i \in \Z^d$ and for any fixed $x \in S$.
\end{defin}
In the above definition the left hand side of the above equality denotes a version of the conditional
probability of $X (i)$ given that $X(j)=x(j)\, , \, j\neq i$.

Let $F$ be a finite subset of $\Z^d$.  We shall use the shorthand notation $p(x(F))$ and
$p( x(i) | x(F) )$ to denote, respectively, the probability $\mathbb{P}(X(F)=x(F))$ and the conditional probability $\mathbb{P}(X(i)=x(i) | X(F \setminus \{i\})=x(F \setminus \{i\}))$.

\begin{defin}
The interaction neighborhood $\mathcal{G}(i)$ of a site $i\in \Z^d$ is defined as
\begin{equation*}
\mathcal{G}(i)=\left\{ j \in \Z^d : J(i,j) \neq 0 \right\}.
\end{equation*}
\end{defin}

Let $B^L(i)=\{j \in \Z^d: |i-j|\leq L\}$ be the ball of radius $L \ge 1$ centered at site $i \in \Z^d$, where $|\cdot|$ is the maximum norm.
Our goal in this paper is to infer $\mathcal{G}(i) \cap B^L(i)$ from  the values of $X_1(B^L(i)), \ldots, X_n(B^L(i))$, when $n$ and $L$ are suitably scaled, where $X_1, \ldots, X_n$ are independent realizations of the Ising model $X$.

To do this, let us introduce for any finite set $F$ the empirical probability measure
\begin{equation*}
\hat{p}_n(x(F) )=\frac{1}{n} \sum_{k=1}^n\one\{X_k(F)=x(F)\},
\end{equation*}
where $\one$ denotes the indicator function. Given any site $j \in \Z^d$, we will also define the empirical conditional probability
$$\hat{p}_n(x(j) | x(F\setminus \{j\} ))=\frac{\hat{p}_n(x(F \cup \{j\}) )}{\hat{p}_n(x(F \setminus \{j\}) )}\; ,$$
if $\hat{p}_n(x(F \setminus \{j\}) ) > 0 $ and $ \hat{p}_n(x(j) | x(F\setminus \{j\} )) = 0$, otherwise.

For any fixed configuration $x(B^L(i))$ and any $j \in B^L(i)$ we define the empirical weighted distance between the conditional probabilities as follows
\begin{equation}\label{eq:difference}
\hat{D}_n(x(B^L(i)),j)=
\left|\hat{p}_n(x(i) | x(B^L(i)\setminus\{i\}))-\hat{p}_n(x(i) | x(B^L(i)\setminus\{i, j\}))\right|
\hat{p}_n(x(B^L(i)\setminus \{i\})\,.
\end{equation}
Note that $\hat{D}_n(x(B^L(i)),j)$ is a function of the sample $X_1,\ldots,X_n$ and is therefore a random variable.

We can now define our estimator.
\begin{defin} \label{def:estimatornei}
 For any site $i$ and range $L \ge 1$ the interaction neighborhood estimator  is  defined as follows
\[
\hat{V}^L_n(i)=\left\{ j \in B^L(i) : \max_{x(B^L(i))} \hat{D}_n(x(B^L(i)),j)  >  \epsilon \right\}\,.
\]
where the threshold $\epsilon$ is a suitable positive real number.
\end{defin}

Our first theorem shows that for a convenient threshold $\epsilon$, defined as a function of $L$ and $n$, the estimated interaction neighborhood $\hat{V}^L_n(i)$ recovers perfectly the set  $\mathcal{G}(i)$, when $L$ and $n$ are suitably scaled.

\begin{theo} \label{cor:1}
Let $i \in \Z^d$ and $X_1(B^L(i)), \ldots, X_n(B^L(i))$ be the projections of independent realizations of an Ising model whose pairwise potential satisfies conditions
\begin{equation} \label{cond:J}
\sup_{i\in \Z^d}\sum_{j\in \Z^d} |J(i,j)|=r<1
\end{equation}
and
\begin{equation}
\lim_{L \rightarrow \infty} \sup_{i\in \Z^d}\sum_{j\in \Z^d, |j-i|> L} |J(i,j)|e^{(2L)^d} = 0.
\end{equation}
Under these assumptions, if we choose the threshold $\epsilon=\epsilon(L,n)$ as
\begin{equation} \label{eq:thresholdstat}
\epsilon(L,n)=C\sqrt{\frac{(2L)^d}{n}\left(\frac{1+e^2}{e^2}\right)^{-(2L)^d}},
\end{equation}
where $C>0$ is an arbitrary constant and
$$L_n = \frac{1}{2}(0.79\log n)^{1/d},$$
then for any $i \in \Z^d$ the following assertions hold
\renewcommand{\labelenumi}{(\roman{enumi})}
\begin{enumerate}
\item for any $j \in \mathcal{G}(i)$, $\lim_{n\rightarrow \infty} \P\left(j \in \hat{V}^{L_n}_n(i)\right)=1$;
\item for any $j \notin \mathcal{G}(i)$, $\lim_{n\rightarrow \infty} \P\left(j \notin \hat{V}^{L_n}_n(i)\right)=1$.
\end{enumerate}

\end{theo}

\vspace{1cm}

Theorem \ref{cor:1} follows from an upperbound for the probability of misidentification of points in a suitably defined subset of $\mathcal{G}(i)\cap B^L(i)$, which holds for any choice of the sample size $n$, box size $L$, and threshold $\epsilon$. This is the content of the next theorem. To state it we need some extra definitions.

Given an integer $L \ge 1$ and a pairwise potential $J$, we denote $J^L$ the truncated potential defined as follows. For any pair of sites $i$ and $j$
\begin{equation} \label{trunJ}
J^L(i,j)=
\begin{cases}
 J(i,j)\; & \mbox{if } |i-j|\le L \\
  0\;, & \mbox{otherwise} .
\end{cases}
\,
\end{equation}
We shall also denote $X^L$ the corresponding Ising model with pairwise potential $J^L$.

Let $F$ be a finite subset of $\Z^d$. As before, we shall use the shorthand notation $p^L(x(F))$ and
$p^L( x(i) | x(F) )$ to denote, respectively, the probability $\mathbb{P}(X^L(F)=x(F))$ and the conditional probability $\mathbb{P}(X^L(i)=x(i) | X^L(F \setminus \{i\})=x(F \setminus \{i\} ))$.

\begin{defin} \label{def:rerldif}
Given a site $i \in \Z^d$ and integers $L$ and $n$, let
$$D(x(B^L(i)),j) = \left |p^L( x(i)|x(B^L(i)\setminus \{i\}))-p^L\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\right|p^L(x(B^L(i)\setminus \{i\})). $$
The interaction neighborhood $V^L(i)$ of $i$ is defined as

\begin{equation}  \label{eq:rerldif}
V^L(i)=\left\{ j \in B^L(i) : \max_{x(B^L(i))} D(x(B^L(i)),j)  > 2\epsilon \right\},
\end{equation}
where $\epsilon$ denotes the same threshold appearing in Definition \ref{def:estimatornei}.
\end{defin}

\begin{theo} \label{teo:main}
Let $i \in \Z^d, L\geq 1$, and $X_1(B^L(i)), \ldots, X_n(B^L(i))$ be the local projections of independent realizations of a Ising model whose pairwise potential satisfies
\begin{equation} \label{cond:J}
\sup_{i\in \Z^d}\sum_{j\in \Z^d} |J(i,j)|=r<1.
\end{equation}
Then for any site $i \in \Z^d$ and any threshold value $\epsilon > 0$, we have
\begin{align}
&\mathbb{P}\left(\hat{V}^L_n(i) \neq V^L(i) \right) \notag \\
& \le 4\exp\left(-\frac{n\epsilon^2}{8v+\frac{4}{3}\epsilon}+2(2L)^d \right) + \frac{1}{1-r}n(2L)^d\left(\sup_{i\in \Z^d}\sum_{ j \in \Z^d, |j-i| > L} |J(i,j)|\right)\,,\label{eq:uppermain1}
\end{align}
where
\begin{equation}
v=\sup_{x(B^L(i) )}\sup_{j \in B^L(i)}\left(1-p^L\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)p^L(x(B^L(i)\setminus \{j\}))\right).  \label{eq:variancemain}
\end{equation}
\end{theo}

\vspace{1cm}
Theorem \ref{teo:main} applies also when the interaction graph is embedded in a finite set $\Lambda$ and we analyze a sample with the values the Ising model assigns to a smaller subset of sites in $\Lambda$. This is the content of the following corollary.

\begin{cor} \label{cor:2}
Let $i \in \Lambda \subset \Z^d$, $L\geq 1$, and  $X_1(B^L(i) \cap \Lambda), \ldots, X_n(B^L(i) \cap \Lambda)$ be the projections of independent realizations of a Ising model whose pairwise potential satisfies
\begin{equation}
J(i,j)=0\;\; \text{for} \;\; j \in \Z^d \setminus \Lambda
\end{equation}
and
\begin{equation} \label{cond:Jcor}
\sup_{i\in \Lambda}\sum_{j\in \Lambda} |J(i,j)|=r<1.
\end{equation}
Then for any site $i \in \Lambda$ and any threshold value $\epsilon > 0$, we have
\begin{align}
&\mathbb{P}\left(\hat{V}^L_n(i) \neq V^L(i) \right) \notag \\
& \le 4\exp\left(-\frac{n\epsilon^2}{8v+\frac{4}{3}\epsilon}+2(2L)^d \right) + \frac{1}{1-r}n(2L)^d\left(\sup_{i\in \Lambda}\sum_{ j \in \Lambda, |j-i| > L} |J(i,j)|\right)\,,
\end{align}
where $v$ is defined in (\ref{eq:variancemain}).
\end{cor}

The first ingredient in the proof of  Theorem \ref{teo:main} is an upperbound for the probability of misidentification of interacting pairs in the case of
a finite range interaction.   This is given in the next theorem.

\begin{theo} \label{teo:bounded}
Let $i \in \Z^d, L\geq 1$, and $X_1(B^L(i)), \ldots, X_n(B^L(i))$ be the projections of independent realizations of a Ising model whose pairwise potential satisfies
\begin{equation}
J(i,j)=0, \;\;\text{if}\;\; |i-j| > L.
\end{equation}
Then for any site $i \in \Z^d$ and any threshold value $\epsilon > 0$, we have
\[
\mathbb{P}\left(\hat{V}^L_n(i) \neq V^L(i) \right)
\le 4 \exp\left(-\frac{n\epsilon^2}{8v+\frac{4}{3}\epsilon} + 2(2L)^d \right)\,,
\]
where
\begin{equation*}
v=\sup_{x(B^L(i))}\sup_{j \in B^L(i)}(1-p\left(x(i) | x(B^L(i)\setminus \{i,j\})\right)p(x(B^L(i)\setminus \{j\}))).
\end{equation*}
\end{theo}

The second ingredient in the proof of Theorem \ref{teo:main} is a coupling result. To state it we first need to introduce the notion of coupling. This is done as follows.

Let $X$ be a Ising model with pairwise potential $J$.  For a fixed integer $L \ge 1$, let $J^L$ be the corresponding truncated potential defined as in (\ref{trunJ}).

\begin{defin}
A coupling between $X$ and $X^L$ is a random element $(\tilde{X} , \tilde{X}^L )$ taking values on $S\times S$ such that
\begin{enumerate}
\item $\tilde{X}$ has the same law as $X$;
\item $\tilde{X}^L$ has the same law as $X^L$.
\end{enumerate}
\end{defin}

The following theorem says that we can sample together $X$ and $X^L$ in such a way that the probability of discrepancy at the origin vanishes as $L$ diverges.

\begin{theo} \label{teo:dob}
If $J$ is pairwise potential which satisfies condition (\ref{cond:J}), \textit{i.e.},
\begin{equation*}
\sup_{i \in \Z^d}\sum_{j \in \Z^d}|J(i,j)| = r < 1
\end{equation*}
and $J^L$ is defined as in (\ref{trunJ}), then there exist a coupling $(\tilde{X} , \tilde{X}^L )$ such that for any $i \in \Z^d$ the following inequality holds
\begin{equation}
\P\left(\tilde{X}(i) \neq \tilde{X}^L(i) \right) \leq \frac{1}{1-r} \sup_{i\in \Z^d}\sum_{j \in \Z^d\setminus B^L(i)}|J(i,j)|. \label{bound2}
\end{equation}

\end{theo}

\section{Simulation experiments} \label{sec:simulation}

This section presents simulation experiments results that illustrates Theorem \ref{teo:main}.

The experiment was done with the Ising model on $B^3(0)$, where $B^3(0) \in \Z^d$ is the box with width 7 centered at the origin. The set of pairs of interaction sites was chosen randomly as follows. Each pair of sites $(i,j)$ inside $B^3(0)$  was included in the set of interacting pairs with probability $0.1$, independently of the others, with the restriction that the degree of each site was bounded above by 4. For each pair of interaction site we took $J(i,j) = 0.2$. The set of interacting pairs considered in the experiment is represented in Figure \ref{fig:interaction}.

\begin{figure}
\begin{center}
 \includegraphics[width=12cm]{InteractionGraph.eps}
 \caption{ \label{fig:interaction} \small Graph representing the interacting pairs of sites. The vertices represent the sites and the presence of edges between the vertices represent the existence of interaction. The sites interacting with site $(0,0)$ are indicated with bold grey edges. }
 \end{center}
\end{figure}

Samples of the Ising model on this finite graph  were generated using a Gibbs sampler.  More precisely, we considered  the Markov chain $(Y_t, Y'_t)$ taking values on $\{-1,+1\}^{2B^3(0)}$. The algorithm we used to generate the samples is described in the pseudocode Sample Generator presented in Appendix 2. We start with initial configurations $Y_0(i)=+1$ and $Y'_0(i)=-1$ for all $i \in B^3(0)$. We run the Markov chain until the first time $t \geq 1$ such that $Y_t=Y'_t$. At this time the Markov chain is in the stationary state and therefore the common configuration attained by $Y_t$ and $Y'_t$ is a realization of the Ising model.

The goal of simulation experiment was to identify the sites in $B^1(0)$ interacting with site $(0,0)$. Observe that there are two sites outside $B^1(0)$ which interact with $(0,0)$, namely $(0,3)$ and $(2,0)$.  We considered 39 different sample sizes, $n=500 + 250k $, where $k=0, \ldots, 38$ for the estimator $\hat{V}^1_n(0)$. The threshold used in the estimator $\hat{V}^1_n(0)$ was
$$\epsilon(L,n)=C\sqrt{\frac{1}{n}} $$
with $C \in [0.06, 0.09]$.
The probabilities of type 1 errors (false positives) and type 2  errors (false negatives) were  estimated by repeating the experiments 2000 times for each sample size.
The result is presented in Figure \ref{fig:FP_FN}.

\begin{figure}
\begin{center}
 \includegraphics[width=12cm]{FP_FN.eps}
 \caption{\label{fig:FP_FN} \small Graph of estimated probabilities of false positive and false negative identification using the estimator $\hat{V}^1_n(0)$ for different sample sizes. }
 \end{center}
\end{figure}

\section{Discussion} \label{sec:discussion}

Ising systems with infinite range potential are natural candidates to model population of neurons, protein networks, large computer networks, social networks, just to mention a few examples. This is due to the fact that the interaction potential describing the Ising model encodes the structure of conditional independence among the components of the system.

The examples mentioned above present all the following characteristics.  They are supported by a very large number of components. The activity of all the components of the system cannot be observed simultaneously.
Even worse, there is no clear \textit{a priori} candidate for the range of interactions between pairs of components.

Summarizing, in those systems, only a small set of components is observed, even if these components are under the influence of the totality of non-observed components.
This leads naturally to the following statistical question. Given a sample with the values assigned to a finite set of sites by a finite sequence of independent realizations of the Ising model on $\Z^d$,  how can we identify pairs of interacting sites belonging to this finite subset? This is precisely the question we address here. For the best of our knowledge, the present article is the first one to address this problem.

We use $\Z^d$ to represent the set of components of the system. This is just to have a convenient definition of distance between sites. However, it should be clear from our proofs that many other metric structures between the sites could be used instead of the $\ell_\infty$ distance considered here without significant change in the results of this article. Also, instead of using the $\ell_\infty$-ball $B^L(i)$ as set of observed sites, we could use any increasing sequence of finite sets $\Lambda^L \subset \Z^d$ such that $\cup_{L=1}^\infty  \Lambda^L=\Z^d$. It is an easy exercise to translate our results to this general framework.

Recently, \citet{Ravikumar10, Bento09, Bresler08}, and \citet{Csiszar06} addressed the problem of identification of interacting sites in the case of random fields, either on a finite set of sites or on an infinite set but with a finite range interaction.
Let us briefly discuss these results.

 \citet{Csiszar06} consider the case of homogeneous finite range Markov random fields in $\Z^d$. They use what they call the Pseudolikelihood Information Criterion (PIC) to identify the interaction neighborhood of a site.  The homogeneity of the model makes it possible to use as a sample the values assigned to a finite set of sites by a unique realization of the Markov random field.  The finiteness of the range of the Markov random field implies that the interaction neighborhood of a site will be entirely observed when the sample size increases. Therefore, they do not need to control the effect of non-observed sites as we do. In our Theorem \ref{teo:main} this corresponds to the second term of the upperbound.
They prove the consistency of their identification procedure when the size of the set of observed sites diverges. They do not give any explicit upperbound for the probability of misidentification when we only observe a finite set of sites. The asymptotic nature of the result presented in \citet{Csiszar06} it is an important difference between this article and ours. An interesting feature of their result is that it holds even when the Markov random field has phase transition. It is enough to apply the algorithm to a pure phase of the model to correctly identify the interaction neighborhood. This feature is also shared by our approach in the case of finite range Ising model. We recall that our Theorem \ref{teo:bounded} does not assume Dobrushin's condition and therefore holds also for finite range potentials with arbitrary high interaction values. In statistical physics language, Theorem \ref{teo:bounded} holds also for low temperature Ising models exhibiting phase transition.

\citet{Bresler08}  propose an algorithm which is similar in spirit to ours but without the weighting parameter. This article studies the problem in the case of random field on a finite set of sites. This paper does not consider the situation in which the number of sites supporting the probability measure increases when the sites of samples diverges. The fact the set of sites is finite and fixed plays a  crucial role in their approach and cannot be applied in an obvious way to the infinite range case considered in the present paper.

\citet{Ravikumar10} consider the $\ell_1$ pseudolikelihood estimator of the Ising model with increasing sample size and number of interacting sites. They assume that the totality of the interacting sites is observed.  Their algorithm seems to be fast enough in practice. However, their incoherence condition assumption seems to be very restrictive and difficult to check even for simple models. The very interesting article \citet{Bento09} shows that the probability that such a condition is satisfied for large random graphs is very small.

In \citet{Bento09} it is conjectured that the existence of efficient low complexity algorithm seems to be related to the absence of phase transition at least in the case of Ising models. This discussion is outside of the scope of the present article. However, it is worth mentioning that in our Theorems \ref{cor:1} and \ref{teo:main} we  assume Dobrushin's condition (\ref{cond:J}) which implies absence of phase transition (cf. \citet{Dobrushin68} or \citet{Presutti09}). In our case this condition is crucial to obtain an upper bound for the probability of discrepancy in a fixed finite region between the coupled versions of the infinite range and the truncated finite range potential Ising models. This makes it possible with high probability to identify pairs of interacting sites without inspecting distant pairs of sites. In particular, even in the case of a finite but very large set of sites our algorithm only needs to test pairs of sites belonging to a much smaller finite region. This is precisely the content of our Corollary \ref{cor:2}. As a consequence our algorithm only needs to check a small set of sites, which is  computationally less demanding than testing pairwise interaction in the whole set of sites.

 To conclude, we observe that our coupling approach can be used to extend in a straightforward way the results of   \citet{Ravikumar10, Bento09, Bresler08}, for the case of Ising model of infinite range interaction. To do this we just need to be sure that Dobrushin's condition (\ref{cond:J}) is satisfied.

\section{Acknowledgements}
The authors thank Luiz Lana and Matthieu Lerasle for many discussions during the period in which this paper was written. Part of this work was done during DYT stay at the Universit\'a di Roma Tre, Dipartmento di Matematica, Rome, Italy and during EO stay at the Universidade de S\~ao Paulo, Departamento de Estatística, NUMEC, S\~ao Paulo, Brazil.

\vspace{1cm}
\noindent{\bf \Large Appendix 1}

\section*{Proof of Theorem \ref{cor:1}}

We will first prove that
\begin{equation}
 \label{eq:equalsets}
\lim_{n \rightarrow \infty}V^{L_n}_n(i) = \mathcal{G}(i).
\end{equation}

For this we observe that for any $i \in \Z^d$
\begin{equation*}
\max_{x(B^L(i)\setminus \{i\})} p^L(x(B^L(i)\setminus \{i\})) \geq 2^{-(2L)^d+1}
\end{equation*}
and for any $j \in B^L(i)$ such that $J(i,k) \neq 0$ we have
\begin{align*}
&\left|p^L( x(i)|x(B^L(i)\setminus \{i\}))-p^L\left(x(i)|x(B^L(i)\setminus \{i,j\})\right) \right| \\
& \geq \frac{2e^{2r}}{(1+e^{2r})^2}|J(i,j)|\min_{x(j) \in \{-1,+1\}}  p^L(x(j) | x(B^L(i)\setminus \{i,j\})).
\end{align*}
Also
$$\min_{x(j) \in \{-1,+1\}}  p^L(x(j) | x(B^L(i)\setminus \{i,j\})) \geq \frac{1}{1+e^{2r}}.$$

From the above inequalities, we have
\begin{equation*}
\max_{x(B^L(i))} D(x(B^L(i)),j) \geq \frac{4e^{2r}}{(1+e^{2r})^3}|J(i,j)|2^{-(2L)^d}.
\end{equation*}

If $j \in \mathcal{G}(i)$, the right hand side of the last inequality is strictly positive. Therefore, from the above inequality a sufficient condition for this site $j$ to belong to $V^L(i)$ is that
$$\frac{4e^{2r}}{(1+e^{2r})^3}|J(i,j)|2^{-(2L)^d} \geq \epsilon(L,n).$$

Hence,  to equality (\ref{eq:equalsets}) holds it is enough that
\begin{equation} \label{eq:holdsok}
\lim_{n \rightarrow \infty} \frac{\epsilon(L_n,n)}{2^{-(2L_n)^d}} = 0.
\end{equation}
It is easy to check that the above condition holds for $L_n\leq \frac{1}{2}\left(0.79\log n\right)^{1/d}$ and with the  threshold
$$\epsilon(L_n,n)=C\sqrt{\frac{(2L_n)^d}{n}\left(\frac{1+e^{2}}{e^{2}}\right)^{-(2L_n)^d}}$$
as defined in (\ref{eq:thresholdstat}).

Now, we will prove
\begin{equation} \label{eq:consistency}
\lim_{n \rightarrow \infty}\mathbb{P}\left(\hat{V}^{L_n}_n(i) \neq V^L_n(i) \right) = 0.
\end{equation}
 For this, we have from inequality  (\ref{eq:uppermain1}) in Theorem \ref{teo:main} that if we prove
\begin{equation} \label{eq:nec1}
\lim_{n \rightarrow \infty} -\frac{n\epsilon(L_n,n)^2}{8v+\frac{4}{3}\epsilon(L_n,n)} + 2(2L_n)^d = -\infty,
\end{equation}
where $v$ is defined in  (\ref{eq:variancemain}), and also that
\begin{equation}  \label{eq:nec2}
\lim_{n \rightarrow \infty}n(2L_n)^d\left(\sup_{i\in \Z^d}\sum_{ j \in \Z^d, |j-i| > L_n} |J(i,j)|\right) = 0,
\end{equation}
we prove (\ref{eq:consistency}).

To prove (\ref{eq:nec1}), we first observe that
\begin{equation*}
1-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right) \geq \frac{1}{1+e^{2r}}
\end{equation*}
and
\begin{equation*}
\sup_{x(B^L(i)\setminus \{j\})} p(x(B^L(i)\setminus \{j\})) \geq 2^{-(2L)^d+1}.
\end{equation*}
From these inequalities we have that
\begin{equation*} \label{eq:remarkv}
v \geq   \left(\frac{2}{1+e^{2r}}\right)2^{-(2L)^d}.
\end{equation*}
The above inequality implies that for $L \leq \frac{1}{2}(0.79\log n)^{1/d}$ we have
\begin{equation*}
v \; \geq \; \left(\frac{2}{1+e^{2r}}\right)2^{-(2L)^d} \; \geq \; \frac{4}{3}\epsilon(L,n).
\end{equation*}
Therefore, we can bound below the first term in the exponent of the upperbound (\ref{eq:uppermain1}) as follows
\begin{equation} \label{eq:reduction}
\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n)} \geq \frac{n\epsilon(L,n)^2}{9v}.
\end{equation}

From  (\ref{eq:reduction}),  to obtain (\ref{eq:nec1}) it is enough that
\begin{equation*}
\lim_{L,n \rightarrow \infty} -\frac{n\epsilon(L,n)^2}{9v} + 2(2L)^d = - \infty.
\end{equation*}
This implies that
\begin{equation} \label{eq:satisfythres}
\epsilon(L,n) > C\sqrt{\frac{2(2L)^dv}{n}}.
\end{equation}

We will now find an upper bound for $v$.

From condition (\ref{cond:J}) it follows that
\begin{equation*}
1-p\left(x(i)/x(B^L(i)\setminus \{i,j\})\right) \leq \frac{e^{2r}}{1+e^{2r}}
\end{equation*}
and
\begin{equation*}
p(x(B^L(i)\setminus \{j\})) \leq \left(\frac{e^{2r}}{1+e^{2r}}\right)^{(2L)^d-1}.
\end{equation*}
These inequalities imply that
\begin{equation*}
v \leq   \left(\frac{1+e^{2r}}{e^{2r}}\right)^{-(2L)^d}.
\end{equation*}
From the above inequality and the fact that $r < 1$, the choice of $\epsilon(L,n)$ in (\ref{eq:thresholdstat}) satisfies (\ref{eq:nec1}).

To prove (\ref{eq:nec2}), note that $L = \frac{1}{2}(0.79\log n)^{1/d}$  implies that $n < e^{(2L)^d}$.
This concludes the proof of Theorem \ref{cor:1}.
\qed

\vspace{1cm}

\section*{Proof of Theorem \ref{teo:main} and Corollary \ref{cor:2}}

Let the integer $L \geq 1$ be fixed and let $(\tilde{X}_1,\tilde{X}_1^L), \ldots, (\tilde{X}_n,\tilde{X}_n^L)$ be $n$ independent copies of the pair $(\tilde{X}, \tilde{X}^L)$ which existence is guaranteed by Theorem \ref{teo:dob}.  The random elements $\tilde{X}_1, \ldots, \tilde{X}_n$ are independent copies of the Ising model $X$ with pairwise potential $J$.  The random elements $\tilde{X}^L_1, \ldots, \tilde{X}^L_n$ are independent copies of the Ising model $X^L$ with truncated pairwise potential $J^L$ defined as in (\ref{trunJ}).

Let us indicate explicitly the sample in all the statistics and events appearing in Theorem  \ref{teo:main} as functions either of the sample $\tilde{X}_1, \ldots, \tilde{X}_n$ or of the sample $\tilde{X}^L_1, \ldots, \tilde{X}^L_n$ . We start with notation of the empirical probability measures $\hat{p}_n$, as follows
\begin{align*}
&\hat{p}_n(x(F) )[\tilde{X}_1, \ldots, \tilde{X}_n]=\frac{1}{n} \sum_{k=1}^n\one\{\tilde{X}_k(F)=x(F)\}\\
&\hat{p}_n(x(F) )[\tilde{X}^L_1, \ldots, \tilde{X}^L_n]=\frac{1}{n} \sum_{k=1}^n\one\{\tilde{X}^L_k(F)=x(F)\}.
\end{align*}

To simplify the writing we shall use the short notation $$\tilde{\mathbf{X}}=(\tilde{X}_1, \ldots, \tilde{X}_n)\;\;\;\text{and}\;\; \;\tilde{\mathbf{X}}^L=(\tilde{X}^L_1, \ldots, \tilde{X}^L_n).$$

Now using either the empirical probability measures $\hat{p}_n(x(F) )[\tilde{\mathbf{X}}]$ or $\hat{p}_n(x(F) )[\tilde{\mathbf{X}}^L]$ we define the neighborhood estimators $\hat{V}^L_n(i)[\tilde{\mathbf{X}}]$ and $\hat{V}^L_n(i)[\tilde{\mathbf{X}}^L]$.

Now we are ready to conclude the proof.
An upperbound for the probability of misidentification for the sample $\tilde{X}_1, \ldots, \tilde{X}_n$ is given by
\begin{align*}
&\P\left(\hat{V}^L_n(i)[\tilde{\mathbf{X}}] \neq V^L(i) \right)\\
&\leq \P\left(\left\{\hat{V}^L_n(i)[\tilde{\mathbf{X}}] \neq V^L(i) \right\} \bigcap \bigcap_{k\in \{1,\ldots, n\}} \bigcap_{j\in B^L(i)} \left\{\tilde{X}_{k}^{L}(B^L(j))=\tilde{X}_{k}(B^L(j))\right\}\right)\\
&+\P\left(\bigcup_{ k\in \{1,\ldots, n\}} \bigcup_{j\in B^L(i)}\left\{X_{k}^{L}(j) \neq X_{k}(j) \right\} \right).
\end{align*}

By Theorem \ref{teo:dob}
\begin{equation*}
\P\left( \bigcup_{ k\in \{1,\ldots, n\}} \bigcup_{j\in B^L(i)}\left\{X_{k}^{L}(j) \neq X_{k}(j) \right\} \right)\\
\leq n(2L)^d\sup\left\{\sum_{ j \in \Z^d, |j-t| > L} |J(i,j)|: t \in \Z^d \right\}.
\end{equation*}

Now, we observe that in the set
$$ \bigcap_{k\in \{1,\ldots, n\}} \bigcap_{j\in B^L(i)} \left\{\tilde{X}_{k}^{L}(B^L(j))=\tilde{X}_{k}(B^L(j))\right\}$$
the following holds
$$\hat{V}^L_n(i)[\tilde{\mathbf{X}}] =\hat{V}^L_n(i)[\tilde{\mathbf{X}}^L].$$

Hence
\begin{align}
 &\P\left(\left\{\hat{V}^L_n(i)[\tilde{\mathbf{X}}] \neq V^L(i) \right\}  \bigcap \bigcap_{k\in \{1,\ldots, n\}} \left\{\tilde{X}_{k}^{L}(B^L(i))=\tilde{X}_{k}(B^L(i))\right\}\right) \notag\\
 &=\P\left(\left\{\hat{V}^L_n(i)[\tilde{\mathbf{X}}^L] \neq V^L(i) \right\}  \bigcap \bigcap_{k\in \{1,\ldots, n\}} \left\{\tilde{X}_{k}^{L}(B^L(i))=\tilde{X}_{k}(B^L(i))\right\}\right) \notag\\
 &\leq \P\left(\hat{V}^L_n(i)[\tilde{\mathbf{X}}^L] \neq V^L(i)  \right) . \label{eq:probultimo}
 \end{align}

 Since Theorem \ref{teo:bounded} provides an upperbound for the last term in (\ref{eq:probultimo}), we have
 \begin{align*}
 &\P\left(\left\{\hat{V}^L_n(i)[\tilde{\mathbf{X}}] \neq V^L(i) \right\}  \bigcap \bigcap_{k\in \{1,\ldots, n\}} \left\{\tilde{X}_{k}^{L}(B^L(i))=\tilde{X}_{k}(B^L(i))\right\}\right) \\
 &\leq 4\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n)}+2(2L)^d \right).
\end{align*}
This concludes the proof of Theorem \ref{teo:main}.

\qed

 To prove Corollary \ref{cor:2} we observe that the finite volume case is equivalent to consider the pairwise potential satisfying
 \begin{equation}
J(i,j)=0\;\; \text{for} \;\; j \in \Z^d \setminus V
\end{equation}
  in the $\Z^d$ case.

 \section*{Proof of Theorem \ref{teo:bounded} }

For convenience of the reader, before the proof let us recall the classical inequality of Bernstein which will be used in the sequence.

\noindent {\bf Bernstein inequality}
Let $\xi_1, \ldots, \xi_n$ be i.i.d. random variables with $|\xi_1| \leq b$ a.s. and $\E[\xi_1^2] \leq v < \infty$. Then the following inequality holds
\begin{equation*}
\P\left(\left|\frac{1}{n}\sum_{k=1}^n\xi_k - \E[\xi_1] \right| \geq \epsilon \right) \leq 2 \exp \left(-\frac{n \epsilon^2}{2(v+\frac{1}{3}b\epsilon)}\right).
\end{equation*}
For a proof of this inequality, we refer the reader to \citet{Massart03}.

To begin the proof of Theorem \ref{teo:bounded}, let us denote
\begin{equation}\label{fpositive}
\mathcal{O}^L_n(i)=\left\{ j \in \hat{V}^L_n(i): j\in B^L(i)\setminus V^L(i) \right\}
\end{equation}
the event of {\sl false positive identification}.

The event of {\sl false negative identification} is defined as
\begin{equation}\label{fnegative}
\mathcal{U}^L_n(i)=\left\{j \in B^L(i) \setminus \hat{V}^L_n(i): j\in  V^L(i) \right\}.
\end{equation}

We observe that
$$\{\hat{V}^L_n(i) \neq V^L(i)\} = \mathcal{O}^L_n(i) \cup \mathcal{U}^L_n(i).$$

We will first  obtain an upperbound for the probability of event false positive identification.
Observe that
\begin{equation} \label{eq:over1}
\mathbb{P}\left(\mathcal{O}^L_n(i) \right) \leq  \sum_{x(B^L(i))}\;\; \sum_{j \in  B^L(i)\setminus V^L(i)}  \mathbb{P}\left( \hat{D}_n(x(B^L(i)),j) > \epsilon(L,n) \right)\, .
\end{equation}

Let us fix $j \in B^L(i)\setminus V^L(i)$ and $x(B^L(i))\in \{-1,+1\}^{B^L(i)}$.
To obtain an upperbound for the right hand side of (\ref{eq:over1}) we first observe that
\begin{align}
&\hat{D}_n(x(B^L(i)),j) \notag\\
&\leq \left|\hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus\{i\}))\right|\notag\\
&+\left|\frac{\hat{p}_n(x(B^L(i)\setminus \{j\}))}{\hat{p}_n(x(B^L(i)\setminus \{i,j\}))}-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\right|\hat{p}_n(x(B^L(i)\setminus \{i\})). \label{eq:eqdup}
\end{align}
This inequality was obtained by adding and subtracting $$p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus\{i\}))$$ in expression (\ref{eq:difference}).

Since
$$0\leq \frac{\hat{p}_n(x(B^L(i)\setminus \{i\}))}{\hat{p}_n(x(B^L(i)\setminus \{i,j\}))}\leq 1,$$
we finally obtain the upperbound
\begin{align}
&\hat{D}_n(x(B^L(i)),j) \notag \\
&\leq \left|\hat{p}_n(x(B^L(i)))-p\left(x(i) | x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i\}))\right|\notag\\
&+\left|\hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i) | x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\}))\right|. \label{eq:upp1}
\end{align}

Therefore,
\begin{align*}
&\mathbb{P}\left( \hat{D}_n(x(B^L(i)),j) > \epsilon(L,n) \right)\\
& \leq \mathbb{P}\left( \left|\hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i\}))\right| > \frac{1}{2}\epsilon(L,n)\right) \\
& +  \mathbb{P}\left( \left|\hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\}))\right|> \frac{1}{2}\epsilon(L,n)\right).
\end{align*}

 The classical Bernstein inequality provides the following upperbounds for the terms in the right hand side of the above equation
\begin{align}
&\mathbb{P}\left( \left|\hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i\}))\right| > \frac{1}{2}\epsilon(L,n)\right) \notag \\
&\leq 2\exp\left(-\frac{n\epsilon(L,n)^2}{8v_1+\frac{4}{3}\epsilon(L,n))} \right), \label{eq:firstbound}
\end{align}
where
\begin{equation}
v_1=\sup_{x(B^L(i))}\sup_{j \in B^L(i)}(1-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)p(x(B^L(i)))). \label{eq:variance1}
\end{equation}
Also
\begin{align}
&\mathbb{P}\left( \left|\hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\}))\right| > \frac{1}{2}\epsilon(L,n)\right) \notag \\
&\leq 2\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n))} \right), \label{eq:secbound}
\end{align}
where
\begin{equation}
v=\sup_{x(B^L(i))}\sup_{i,j \in B^L(i)}(1-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)p(x(B^L(i)\setminus \{j\}))). \label{eq:variance2}
\end{equation}

Summing up inequalities (\ref{eq:firstbound}) and (\ref{eq:secbound})  for all configurations $x(B^L(i))$ and all sites $j \in B^L(i)\setminus V^L(i)$ we obtain the following upperbound for the probability of false positive identification
\begin{align}
&\mathbb{P}\left(\mathcal{O}^L_n(i) \right) \notag\\
&\leq 4 (|B^L(i)|-|V^L(i)|)\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n))} \right) \notag\\
&\leq 4 (|B^L(i)|-|V^L(i)|)\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n))}  \right). \label{eq:over}
\end{align}

We will now obtain an upperbound for the probability of false negative identification.
For any $j \in V^L(i)$ we have
\begin{equation} \label{eq:over}
\mathbb{P}\left(j \notin \hat{V}^L_n(i)\right) = \P\left( \bigcap_{x(B^L(i))} \left \{\hat{D}_n(x(B^L(i),j)) \leq \epsilon(L,n)  \right\}\right).
\end{equation}
To obtain an upperbound for (\ref{eq:over}), it is enough to obtain an upperbound for
\begin{equation}
 \P\left(\hat{D}_n(x(B^L(i),j)) \leq \epsilon(L,n) \right) \label{eq:simplebound}
 \end{equation}
where $x(B^L(i))$ is any fixed configuration. In particular, we can take a configuration which maximizes
\begin{equation} \label{eq:threshold}
\left |p( x(i)|x(B^L(i)\setminus \{i\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\right|p(x(B^L(i)\setminus \{i\}).
\end{equation}

To do this, we first obtain a lower bound for $\hat{D}_n(x(B^L(i)),j)$ in the same way we obtained the upperbound in (\ref{eq:upp1}).
\begin{align*}
&\hat{D}_n(x(B^L(i)),j)\notag\\
&\geq \left|\hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus\{i\}))\right|\notag\\
&-\left|\hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\}))\right|\frac{\hat{p}_n(x(B^L(i)\setminus \{i\}))}{\hat{p}_n(x(B^L(i)\setminus \{i,j\}))}.\notag
\end{align*}
Observing again that
$$0\leq \frac{\hat{p}_n(x(B^L(i)\setminus \{i\}))}{\hat{p}_n(x(B^L(i)\setminus \{i,j\}))}\leq 1$$
we finally obtain the lower bound
\begin{align}
&\hat{D}_n(x(B^L(i)),j) \notag\\
& \geq \left|\hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus\{i\}))\right|\notag\\
&-\left|\hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\}))\right|. \label{eq:low2}
\end{align}

To make formulas shorter let us call for the moment
\begin{equation*}
 W = \hat{p}_n(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus\{i\}))
\end{equation*}
and
\begin{equation*}
 R = \hat{p}_n(x(B^L(i)\setminus \{j\}))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)\hat{p}_n(x(B^L(i)\setminus \{i,j\})).
\end{equation*}

With this new notation, using inequalities (\ref{eq:upp1}) and (\ref{eq:low2}) we obtain
\begin{equation}
\left| \hat{D}_n(x(B^L(i))) - |W| \right| \leq |R |. \label{eq:enquadra}
\end{equation}

A straightforward computation shows that
\begin{equation*}
\mathbb{E}[W] = p(x(B^L(i)))-p\left(x(i)|x(B^L(i)\setminus \{i,j\})\right)p(x(B^L(i)\setminus\{i\})).
\end{equation*}
Assuming that $j \in V^L(i)$ and that configuration $x(B^L(i))$ maximizes ($\ref{eq:threshold}$), we have that
$$|\mathbb{E}[W] | \geq 2\epsilon(L,n).$$
Therefore to bound (\ref{eq:simplebound}) for $j \in \Gamma^L_n(i)$, it is enough to have an upperbound for
\begin{equation*}
 \P\left( \left| \hat{D}_n(x(B^L(i)), j) -  |\mathbb{E}[W] |\right|  \geq \epsilon(L,n) \right).
\end{equation*}

To do this, we observe that
\begin{equation*}
\left| \hat{D}_n(x(B^L(i)), j) -  |\mathbb{E}[W] |\right| \notag
\leq \left| \hat{D}_n(x(B^L(i)), j) -  |W| \right| + \left| |W| -  |\mathbb{E}[W] |  \right|. \notag
\end{equation*}

Then, using inequality (\ref{eq:enquadra}) we have
\begin{equation}
\left| \hat{D}_n(x(B^L(i)), j) -  |\mathbb{E}[W] |\right|
\leq |R| + \left| W -  \mathbb{E}[W]  \right|. \label{eq:lowerinv}
\end{equation}

Now, by (\ref{eq:lowerinv})
\begin{align}
 & \P\left( \left| \hat{D}_n(x(B^L(i)), j) -  |\mathbb{E}[W] |\right|  \geq \epsilon(L,n) \right)\\
& \leq \P\left(|R| \geq \frac{1}{2}\epsilon(L,n) \right) + \P\left(\left| W -  \mathbb{E}[W]  \right| \geq \frac{1}{2}\epsilon(L,n) \right).
\end{align}

Note that $\mathbb{E}[R] = 0$, thus by Bernstein inequality
\begin{equation} \label{eq:under1}
\P\left(|R| \geq \frac{1}{2}\epsilon(L,n) \right) \leq 2\exp\left(-\frac{3n\epsilon(L,n)^2}{4(6v+\epsilon(L,n))} \right),
\end{equation}
where $v$ is the same in (\ref{eq:variance2}).
By Bernstein inequality also we have
\begin{equation} \label{eq:under2}
 \P\left(\left| W -  \mathbb{E}[W]  \right| \geq \frac{1}{2}\epsilon(L,n) \right) \leq 2\exp\left(-\frac{3n\epsilon(L,n)^2}{4(6v_1+\epsilon(L,n))} \right),
\end{equation}
where $v_1$ is the same in (\ref{eq:variance1}).

Combining (\ref{eq:under1}) and (\ref{eq:under2}) we have for $j \in V^L(i)$
\begin{equation*}
  \mathbb{P}\left(j \notin \hat{V}^L_n(i)\right) \leq 4\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n))}\right).
\end{equation*}

From this, it follows that
\begin{equation}
  \mathbb{P}\left( \mathcal{U}^L_n(i) \right) \leq 4|V^L(i)|\exp\left(-\frac{n\epsilon(L,n)^2}{8v+\frac{4}{3}\epsilon(L,n))} \right). \label{eq:under}
\end{equation}

Adding (\ref{eq:over}) and (\ref{eq:under}) we conclude the proof of Theorem (\ref{teo:bounded}).

\section*{Proof of Theorem \ref{teo:dob}}

  Let $z,z' \in \{-1,+1\}^{\Z^d}$ be two fixed configurations. For a fixed $i \in \Z^d$ and an integer $L\ge 1$, let $(Y^z_t, Y^{z',L}_t)$ be a discrete time
  Markov chain taking values on $\{-1,+1\}^{2B^L(i)}$ with the following features.

  \begin{enumerate}
  \item The Ising model on $\{-1,+1\}^{B^L(i)}$ with pairwise potential $J$ and boundary condition $z (B^L(i)^c)$ is reversible with respect to the first marginal $Y^z_t$.
  \item The Ising model on $\{-1,+1\}^{B^L(i)}$ with pairwise potential $J^L$ and  boundary condition $z'(B^L(i)^c)$ is reversible with respect to the first marginal $Y^{z',L}_t$.
  \item The coupling chain $(Y^z_t, Y^{z',L}_t)$ is irreducible and aperiodic, and has an unique invariant probability measure. Taking into the account items (1) and (2), this unique invariant probability measure is a coupling between the Ising models on
  $\{-1,+1\}^{B^L(i)}$ with interaction potentials $J$ and $J^L$ and boundary conditions $z (B^L(i)^c)$ and $z'(B^L(i)^c)$ respectively.
  \end{enumerate}

    We now construct $(Y^z_t, Y^{z',L}_t)$ with $ t \in \mathbb{N}$. This can be done as follows. Let  $(I_t )_{t\ge 1}$ be an independent sequence of random variables uniformly distributed on $B^L(i)$. For any $j \in B^L(i)$ and $y\in \{-1,+1\}^{B^L(i)}$, let also the probabilities $p_j(\cdot \;|\;y)$ and
$p^L_j(\cdot \;| \;y)$ on $\{-1,+1\}$ be defined as follows.
\[
p_j(+1\;|\;y)=\left \{1+e^{-2\sum_{k\in B^L(i)}J(j,k)y(k)-2\sum_{k\notin
    B^L(i)}J(j,k)z(k)}\right \}^{-1}\, ,
\]
\[
p^L_j(+1\;|\;y)=\left \{1+e^{-2\sum_{k\in
    B^L(i)}J^L(j,k)y(k)-2\sum_{k\notin B^L(i)}J^L(j,k)z'(k)}\right \}^{-1}\,
.
\]

For any pair $(y, y')\in \{-1,+1\}^{2B^L(i)}$, let $(\xi_t^{j, y, y'})_{t\geq 1}$, be an i.i.d. sequence of random variables taking values on  $\{-1,+1\}^2$ with distribution
\begin{align}
&\P\left(\xi_t^{j, y, y'}=(s,s)\right)=\min\left\{p_j(s|y), p^L_j(s|y') \right\} , \notag\\
&\P\left( \xi_t^{j, y, y'}=(s,-s)\right)=\max\left\{p_j(s|y)-p^L_j(s|y'), 0 \right\} ,\label{eq:couplenondiag}
\end{align}
for any $s \in \{-1,+1\}$.

Finally, let us assume that the sequences
$(I_t )_{t\ge 1}$ and
$(\xi_t^{j ,y, y'})_{t \ge 1}$, with $(y,y')\in \{-1,+1\}^{2B^L(i)}$ and $j\in B^L(i)$
 are all independent. The Markov chain $(Y^z_t, Y^{z',L}_t)$ is constructed as follows.
For any $t\ge 1$ and any $j \in B^L(i)$
\begin{equation*}
(Y^z_t(j), Y^{z',L}_t(j))=(Y^z_{t-1}(j), Y^{z',L}_{t-1}(j))\, ,\, \text{\;if\;} j\neq I_t\,
\end{equation*}
and
\begin{equation}
(Y^z_t(j), Y^{z',L}_t(j))=\xi_{t-1}^{j,Y^z_{t-1}, Y^{z',L}_{t-1}}\, ,\, \text{\;if\;} j= I_t\;. \label{eq:couplingp}
\end{equation}

We stress the fact that the probabilities $p_j(\cdot|y)$ and
$p_j^L(\cdot|y)$ depend on the fixed configurations $z(B^L(i)^c) \in
\{-1,+1\}^{B^L(i)^c}$ and $z'\in \{-1,+1\}^{B^L(i)^c}$ respectively. As a
consequence the law of the Markov chain $(Y^z_t, Y^{z',L}_t)$ depends on the
pair of fixed configurations $(z(B^L(i)^c),z'(B^L(i)^c))$. Moreover these probabilities do
not depend on the value of $y(j)$; they depend only on the values of $y(k), k \in
B^L(i)\setminus {j}$ and $z(B^L(i)^{c})$ and $z(B^L(i)^{c})$. Therefore,
a more explicit notation should mention all these details. This would
produce cumbersome things like $p_j(s|y(B^L(i)\setminus {j}), z(B^L(i)^{c}))$,
$p^L_j(s|y(B^L(i)\setminus {j}), z'(B^L(i)^{c}))$. Hence we decided to use a simplified notation.

Let us assume that the initial value $(Y_0^z, Y_0^{z',L})$ of the
chain is chosen according to its unique invariant probability measure.  For
every integer $t\geq 1$ we have
\begin{align}
  \P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\right)&= \P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\;  I_t \neq i  \right )\notag \\
  &+\P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\; I_t =
      i \right ).\label{eq:DobSeparate}
\end{align}

For the first term in the left hand side of the above equation we have
\begin{equation}
\P\left( Y^z_t(i) \neq Y^{z',L}_t(i)\;,\; I_t \neq i \right )=\frac{|B^L(i)|-1}{|B^L(i)|}\P\left(Y^z_{t-1}(i) \neq Y^{z',L}_{t-1}(i) \right). \label{eq:firstsepdob}
\end{equation}
 Substituting (\ref{eq:firstsepdob})  in (\ref{eq:DobSeparate}), we obtain
\begin{equation}
\frac{1}{|B^L(i)|}\P\left(Y^z_t(i) \neq Y^{z',L}_t(i) \right)= \P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\; I_t = i\right ).\label{eq:DobDivide}
\end{equation}

Now, we have
\begin{align}
&\P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\,,\,I_t = i \right)\notag \\
&=\P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\;I_t = i \;,\;  Y^z_{t-1}(j) = Y^{z',L}_{t-1}(j)\;\; \text{for all}\;\; j\in B^L(i) \right ) \notag \\
&+ \P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\;I_t = i  \; ,\; Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j) \;\text{for some} \;j\in B^L(i)  \right ).\label{eq:dobsep}
\end{align}

Using  (\ref{eq:couplenondiag}) and (\ref{eq:couplingp} ), the first term in the right hand side of  (\ref{eq:dobsep}) is bounded above by
\begin{equation}
2\sup_{y\in \{-1,1\}^{B^L(i)}}  \left (p_j(s|y)-p^L_j(s|y) \right) \P\left( I_t = i\;,\; Y^z_{t-1}(j) = Y^{z',L}_{t-1}(j)\;\; \text{for all}\;\; j\in B^L(i) \right). \label{eq:dobestimate1}
\end{equation}

Using the Mean Value Theorem, we have
\begin{equation}
\sup_{y\in \{-1,1\}^{B^L(i)}} \left (p_j(s|y)-p^L_j(s|y) \right) \leq \frac{1}{2}\sum_{l \notin B^L(i)}|J(i,l)|.\label{eq:dobestimate2}
\end{equation}
Therefore an upperbound for expression (\ref{eq:dobestimate1}) is given by
\begin{align}
 &\frac{1}{|B^L(i)|}\sum_{l \notin B^L(i)}|J(i,l)| \P\left(Y^z_{t-1}(j) = Y^{z',L}_{t-1}(j)\;\; \text{for all}\;\; j\in B^L(i) \right)\notag\\
 &=\frac{1}{|B^L(i)|}\sum_{l \notin B^L(i)}|J(i,l)| \left[1 - \P\left(  Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j) \; \text{for some}\; j \in B^L(i) \right )\right] \label{eq:outside2}
\end{align}

Let now study the second term of the right hand side of (\ref{eq:dobsep}). We first rewrite it as
\begin{equation*}
\sum_{\substack{U \subset B^L(i)\\U\neq \emptyset }}\P\left(Y^z_t(i) \neq Y^{z',L}_t(i)\;,\; I_t = i\;,\;\bigcap_{j \in U} \{Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j)\}\;,\; \bigcap_{j \in B^L(i) \setminus U} \{Y^z_{t-1}(j) = Y^{z',L}_{t-1}(j)\} \right ). \label{eq:111}
\end{equation*}

Therefore, proceeding as in (\ref{eq:dobestimate1}) and (\ref{eq:dobestimate2}), we obtain the following upperbound for the second term in the right hand side of (\ref{eq:dobsep})
\begin{align}
&\frac{1}{|B^L(i)|} \sum_{\substack{U \subset B^L(i)\\U\neq \emptyset }}\sum_{l \notin B^L(i)}|J(i,l)|\P\left( \bigcap_{j \in U} \{Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j)\}\; , \;\bigcap_{k\in B^L(i)\setminus U} \{Y^z_{t-1}(k) = Y^{z',L}_{t-1}(k)\}\right)\notag \\
&+ \frac{1}{|B^L(i)|}\sum_{\substack{U \subset B^L(i)\\U\neq \emptyset }}\sum_{l \in U}|J(i,l)|\P\left(  \bigcap_{j \in U} \{Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j)\}\; , \; \bigcap_{k\in B^L(i)\setminus U} \{Y^z_{t-1}(k) = Y^{z',L}_{t-1}(k)\}\right). \label{eq:sum1}
\end{align}

The first part of the right hand side of (\ref{eq:sum1}) can be rewritten as
\begin{equation}
\frac{1}{|B^L(i)|}\sum_{l \notin B^L(i)}|J(i,l)|\P\left(Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j) \; \text{for some}\; j \in B^L(i)  \right ).\label{eq:firstdob}
\end{equation}

The second part of (\ref{eq:sum1}) can be rewritten as
\begin{equation*}
\frac{1}{|B^L(i)|}\sum_{l \in B^L(i)}\sum_{U \subset B^L(i): l \in U}|J(i,l)|\P\left( \bigcap_{j \in U} \{Y^z_{t-1}(j) \neq Y^{z',L}_{t-1}(j)\}\bigcap_{k\in B^L(i)\setminus U} \{Y^z_{t-1}(k) = Y^{z',L}_{t-1}(k)\}\right)
\end{equation*}
and this is equal to
\begin{equation}
\frac{1}{|B^L(i)|}\sum_{l \in B^L(i)}|J(i,l)|\P\left( Y^z_{t-1}(l) \neq Y^{z',L}_{t-1}(l) \right). \label{eq:seconddob2}
\end{equation}

Collecting together  (\ref{eq:dobsep}),  (\ref{eq:outside2}),  (\ref{eq:firstdob}), (\ref{eq:seconddob2}), we finally get the upperbound
\begin{equation}
\P\left(Y^z_t(i) \neq Y^{z',L}_t(i) \right) \leq \sum_{l \notin B^L(i)}|J(i,l)| +\sum_{l \in B^L(i)}|J(i,l)|\P\left(Y^z_{t-1}(l) \neq Y^{z',L}_{t-1}(l) \right). \label{eq:almostlastupper}
 \end{equation}

 To conclude the proof of the theorem, let  $Z$ and $Z'$ be two independent copies of the Ising models on
 $\{-1,+1\}^{\Z^d}$ with potentials $J$ and $J^L$, respectively. For a fixed realization of the pair $Z$ and $Z'$, construct as before the coupled chains $(Y^Z_t, Y^{Z',L}_t)$ taking values on $\{-1,+1\}^{2B^L(i)}$, and having  $Z(B^L(i)^c)$ and $Z'(B^L(i)^c)$ as boundary conditions.

Using inequality (\ref{eq:almostlastupper}) and taking the expectation with respect to $(Z,Z')$, we have
\begin{equation} \label{eq:inefinal}
\mathbb{E}\left[\P\left(Y^Z_t(i) \neq Y^{L,Z'}_t(i)  \right)\right] \leq \sum_{l \notin B^L(i)}|J(i,l)| +\sum_{l \in B^L(i)}|J(i,l)|\mathbb{E}\left[\P\left(Y^Z_{t-1}(l) \neq Y^{L,Z'}_{t-1}(l) \right)\right].
 \end{equation}
  Now observe that
\begin{equation*}
\mathbb{E}\left[\P\left(Y^Z_t(j) \neq Y^{L,Z'}_t(j)  \right)\right]  = \P\left(Y(j) \neq Y^L(j) \right),
 \end{equation*}
 for any $j \in B^L(i)$, where  $Y(j)$ and $Y^L(j)$ are the projections on site $j$ of realizations of the Ising model with pairwise potential $J$ and $J^L$, respectively.
 From this identity and inequality (\ref{eq:inefinal}), it follows that
 \begin{equation*}
 \P\left(Y(i) \neq Y^L(i) \right) \leq \sum_{l \notin B^L(i)}|J(i,l)| +\sum_{l \in B^L(i)}|J(i,l)|\P\left(Y(l) \neq Y^L(l)\right).
 \end{equation*}
Finally, taking the supremum for all $i \in \Z^d$ we have
\begin{equation*}
\sup_{i\in \Z^d}\P\left(Y(i) \neq Y^L(i) \right) \leq \sup_{i\in \Z^d}\sum_{l \notin B^L(i)}|J(i,l)| +r\sup _{i\in \Z^d}\P\left( Y(i) \neq Y^L(i)\right),
 \end{equation*}
  which concludes the proof.

\newpage
\noindent {\bf \Large Appendix 2}
\section*{Pseudocode of the algorithm Sample Generator}

\begin{algorithm}[h]  \label{alg:sampler}
{\bf \normalsize Algorithm}{\;\;Sample generator}
\begin{algorithmic}[1]
\FOR {$k: 1 \to n$}
\STATE {$t=0$ and $Y_t(i) = +1$ and $Y'_t(i)=-1$ for all $i \in B^L(0)$.}
\WHILE {$Y_t \neq Y'_t$}
\STATE $t \gets t+1$
\STATE {Generate a random variable $I_t $ uniformly distributed on $B^L(0)$.}
\FOR {$j \in B^L(0)$}
\IF{ $j=I_t$ }
\STATE {Choose $(s,s') \in \{-1,1\}^2$ with probability
\begin{align*}
&P_j\left(s,s' | y, y' \right)=\min\left\{p_j(s|y), p_j(s|y') \right\}, \; \text{if} \; s=s' \notag\\
&P_j\left(s,s' | y, y' \right)=\max\left\{p_j(s|y)-p_j(s|y'), 0 \right\}, \; \text{if} \; s\neq s'
\end{align*}
where for any $y\in \{-1,+1\}^{B^L(0)}$ is given by

\[
p_j(s\;|\;y)=\left \{1+e^{-2s\sum_{k\in B^L(0)}J(j,k)y(k)}\right \}^{-1}.
\]
}
\STATE  $Y_t(j) \gets s$ and $Y'_t(j) \gets s'$,
\ELSE
\STATE $Y_t(j) \gets Y_{t-1}(j)$ and $Y'_t(j) \gets Y'_{t-1}(j)$
\ENDIF
\ENDFOR
\ENDWHILE
\STATE $X_k=Y_t$
\ENDFOR
\RETURN Sample $X_1, \ldots, X_n$.
\end{algorithmic}
\end{algorithm}

\bibliographystyle{plainnat}
\bibliography{Identify_Ising}

\end{document}


TITLE: Give an example of a function from $\mathbb N \to \mathbb N$ that satisfied
QUESTION [0 upvotes]: For each of the following properties give an example of a function from  $\mathbb N \to \mathbb N$ that satisfied:
(a) one-to-one but not onto
(b) onto but not one-to-one
(c) both onto and one-to-one
(d) neither one-to-one nor onto
In part (b), the model answer uses $f(n)= \max\{\}$, I got confused, what's the relationship between maximum and surjective function?

REPLY [0 votes]: Some possibilities:
$1)$  How about $f(x)=2x\,,\forall x\in\mathbb N$.
$2)$ $f(x)=\begin{cases}1, x=1\\x-1, x\neq1\end{cases}$
$3)f(x)=x\,,\forall x\in\mathbb N$
$4)f(x)=1\,,\forall x\in\mathbb N$


text:
\begin{document}
	\allowdisplaybreaks
\maketitle
\input{abstract}
\input{intro}
\input{mathDefs}
\input{algo}
\input{algoArxiv}

\input{algAss}
\input{oldLemmas}
\input{lemBoundGrad}
\input{lemBoundPhi}
\section{New Lemmas Needed to Derive Convergence Rates}\label{secNew}
\input{lemBoundalpha}
\input{convRateLemmas}

\input{funcValsMPlusNTerms}

\input{strongMonotonePart1}
\input{strongMonotoneLinearConv}
\input{boundE5}
\end{proof}

\input{nIs1}
\bibliographystyle{spmpsci}
\bibliography{refs}

\end{document}

config: arxiv


TITLE: $K=\{v\in V:\|v\|\leqslant 1\}$ is compact $\iff\dim V<\infty$.
QUESTION [0 upvotes]: $V$ is a vector space and metric $d: V\times V\to\Bbb R; \,(x,y)\mapsto\|x-y\|$ gives a entirely metric space.
I have to show that: $K=\{v\in V:\|v\|\leqslant 1\}\text{ is compact }\,\iff\dim V<\infty$.
My idea: For finitely many linearly independent vectors $v_1,\ldots,v_k + 1$ we can construct a vector $v_k + 1$ which has a distance from $\operatorname{span}(\{v_1,\ldots,v_k\})$ ,which is $1$.
Maybe work with this or any other ideas how to prove this?

REPLY [1 votes]: Use the rint of @Cheesecake. If $m=\text{dim}V < \infty$, take a sequence $(x_n)_n \in K$. Let's show that it has convergent subsequence. But by definition $||x_i|| \leq 1$ for all $i$, and each $x_i$ is written as a linear combination of the $ V $ base, say $x_i = \alpha^1_i e^1+ \ldots+\alpha^m_i e^m$. As the norms in finite dimension in $\mathbb{R}^n $(or $\mathbb{K}^n $) are equivalent,
$$1 \geq ||x_i|| =  ||\alpha^1_i e^1+ \ldots+\alpha^m_i e^m|| \geq c (\sum_{j=1}^{m}|\alpha^j_i|) = c||| (\alpha^1_i ,\ldots,\alpha^m_i) ||| $$
for all $i\in \mathbb{N}$. By Bolzano Weierstrass Theorem $((\alpha^1_i ,\ldots,\alpha^m_i))_{i=1}^{\infty}$ have a subsequence convergent, say $((\alpha^1_{i_k} ,\ldots,\alpha^m_{i_k}))_{k=1}^{\infty} \longrightarrow (\beta^1,\ldots, \beta^m)$. Then
$$|| \sum_{j=1}^{m} \alpha^j_{i_k}e^j - \sum_{j=1}^{m}\beta^je^j ||\leq \sum_{j=1}^{m} |\alpha^j_{i_k}-\beta^j| = \dfrac{1}{c}|||(\alpha^1_{i_k} ,\ldots,\alpha^m_{i_k})-(\beta^1,\ldots, \beta^m) ||| \longrightarrow 0$$
when $k$ goes to $\infty$. Hence $\lim_{k \rightarrow \infty} x_{i_k} = \lim_{k \rightarrow \infty} \sum_{j=1}^{m} \alpha^j_{i_k}e^j = \sum_{j=1}^{m}\beta^je^j.$ For the second part use the Hint of @Johnduck, or more precisely use the Riesz Lemma: https://en.wikipedia.org/wiki/Riesz%27s_lemma
and build a sequence that has no convergent subsequence with the following argument: choose any $ x_1 \in K $, consider the subspace generated by $ x_1 $ (it will be closed), by Riesz's Lemma, there is $ x_2 \in K $ such that $ || x_1-x_2 || \geq 1/2 $. Now consider $\text{Span}\{x_1,x_2\}$ by the Riesz Lemma, there is $ x_3 \in K $ with $ || x_1 - x_3 || \geq 1/2 $ and $ || x_2 - x_3 || \geq 1/2 $, as the dimension of $ V $ and infinite, this construction never stops.


TITLE: Vector field notation - what is the law of multiplication?
QUESTION [0 upvotes]: You are given three  smooth vector fields on a differentiable manifold $M$. Take the Lie bracket:
$[X,Y]f=X(Yf)-Y(Xf)$
My question is what is the law of multiplication between $X$ and $Y$? Composition of functions?
If the vector field can be written as $X=X^\mu\partial_\mu$, then the above expression becomes:
$[X,Y]f=X^\mu(\partial_\mu Y^\nu)\partial_\nu f +X^\mu Y^\mu \partial_\mu \partial_\nu f-Y^\nu(\partial_\nu X^\mu)\partial_\mu f - Y^\nu X^\mu \partial_\nu \partial_\mu f$
Why is it allowed to change the order of $Y^\nu$ and $X^\mu$ and of the derivatives?

REPLY [1 votes]: Recall that vector fields are given by derivations on the space of smooth functions. That is, they are maps
$$
D_X : C^\infty(M) \to C^\infty(M)
$$
In that case, it is really just the composition
$$
C^\infty(M) \xrightarrow{X} C^\infty(M) \xrightarrow{Y} C^\infty(M)
$$
In coordinates, of course, this is just taking successive derivatives.


TITLE: Evaluating the Definite Integral $\int_{0}^{1}\frac{2 \sin \pi x \cos \pi x}{1+x^2}dx$
QUESTION [3 upvotes]: How can I find this integral
  $$I=\int_{0}^{1}\frac{2 \sin \pi x \cos \pi x}{1+x^2}dx$$

Any trick that could compute the definite integral is acceptable. However, it will be more challenging to find a primitive.
Any hint or help is appreciated.

My Work
I just wrote the integral as
$$I=\int_{0}^{1}\frac{\sin 2 \pi x}{1+x^2}dx$$
Then, I decided to introduce
$$J(\alpha)=\int_{0}^{1}\frac{\sin \alpha x}{1+x^2}dx$$
and solve a more general problem. Hence, we would have $I=J(2\pi)$ as a special result. But I don't know how to go further. I tried integration by parts and substitutions but to no avail!

REPLY [2 votes]: We need
$$I = \int_0^1 \dfrac{\sin(2\pi x)}{1+x^2}dx = \sum_{k=0}^{\infty} (-1)^k \int_0^1 x^{2k}\sin(2\pi x)dx$$
We have
\begin{align}
I_{k} & = \int_0^1 x^{2k}\sin(2\pi x) dx \\
&= -\dfrac1{2\pi} \int_0^1 x^{2k} d\left(\cos(2\pi x)\right) \\
&= -\dfrac1{2\pi}\left(1-2k\int_0^1 x^{2k-1}\cos(2\pi x)dx\right)\\
& = -\dfrac1{2\pi} \left(1-\dfrac{k}{\pi}\int_0^1x^{2k-1}d\left(\sin(2\pi x)\right)\right) \\
&= -\dfrac1{2\pi}\left(1+\dfrac{k(2k-1)}{\pi}I_{k-1}\right)
\end{align}
Hence, we obtain $$I = \sum_{k=0}^{\infty} (-1)^k I_k$$
where $I_k$ satisfies the recurrence $$I_k = -\dfrac1{2\pi}\left(1+\dfrac{k(2k-1)}{\pi}I_{k-1}\right)$$ with $I_0 = 0$.

Note for @ClaudeLeibovici: I just made sure that this is due to catastrophic cancellation in finite precision. You might already be familiar with this, but still. Below is the results I obtain using an adaptive Gaussian quadrature for $I_k$ accurate up to $14$ digits on a $64$ bit machine and using the recurrence done on a $64$ bit machine. One always needs to be careful evaluating even a simple recurrence as I have written here. The recurrence arising out of this question goes into my teaching list when I discuss evaluating recurrences in class the next time :-).

The C++ code evaluating the recurrence is shown below.
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<vector>

double PI   =   3.141592653589793238;

int main(int argc, char* argv[]) {
    int n   =   atoi(argv[1]);
    std::vector<double> I;
    I.push_back(0.0);
    for (int k=1; k<=n; ++k) {
        double temp =   -0.5/PI*(1.0+k*(2.0*k-1.0)/PI*I[k-1]);
        I.push_back(temp);
    }
    for (int j=0; j<=n; ++j) {
        std::cout << "Term " << j << " is: " << std::setprecision(15) << I[j] << "\n";
    }
    double S    =   0.0;
    for (int j=0; j<=n; j+=2) {
        S+=I[j];
    }
    for (int j=1; j<=n; j+=2) {
        S-=I[j];
    }
    std::cout << "\nThe integral is: " << S << "\n";
}


TITLE: Lesser known examples of perseverance with a successful ending
QUESTION [6 upvotes]: The stories of Wiles, of Perelman, and of Zhang, are very well-known to illustrate that sometimes great results are achieved through particularly long perseverance.

What are lesser known-examples of that kind ?

These need not be epoch-making results like those mentioned, but, say, they required at least 6 or 7 years of dedicated effort (not necessarily by a single person, and also not necessarily a first-time paper i.e. a paper correcting a previously incomplete attempt also would qualify as a good answer).
Edit: to clarify, I do not have in mind long endeavours by many people over centuries like Galois Theory, really just a particular theorem within the lifetime of their author(s).
P.s. if moderators could help make this question community-wiki, that would be great, thank you.

REPLY [2 votes]: I'm not sure if you're insisting on examples in which a mathematician (or group of mathematicians) works single-mindedly on a single problem for many years and finally conquers the problem.  If so, then the following might not qualify.  But it might qualify if your conditions are not as stringent as that.  I quote from Ilse Fischer's response to being awarded the AMS Robbins Prize.

The idea of working on Robbins' last open conjecture on alternating sign matrices slowly manifested in my mind when I was writing a grant proposal about 10 years ago, when I identified it as an ultimate, albeit unrealistic, goal. In the beginning I hardly dared spend much time on it, but every now and then I discussed it with other combinatorialists. Roger Behrend and Matjaž Konvalinka were obviously among them, but I also had a particularly fruitful exchange with Arvind Ayyer back in 2012, which led us to several conjectures on the enumeration of extreme diagonally and antidiagonally symmetric alternating sign matrices of odd order. About three years later, Arvind, Roger, and I were able to prove these conjectures, and to some extent also this work paved the way for the eventual proof of Robbins' conjecture. I feel deeply honored and moved to receive, together with Matjaž and Roger, the David P. Robbins Prize.


TITLE: Computing $H^\ast(S^1,\underline{\mathbb{Z}})$
QUESTION [2 upvotes]: I am trying to compute $H^\ast(S^1, \underline{\mathbb{Z}})$. Here is my approach: Let $U=S^1\setminus \{(1,0)\}$ and $V=S^{1}\setminus \{(-1,0)\}$. Then $U\simeq \{\ast\} \simeq V$ and $U\cap V \simeq \{\ast\} \sqcup \{\ast\}$. Since $S^{1}$ is connected, $H^{0}(S^1, \underline{\mathbb{Z}})=\underline{\mathbb{Z}}(S^1)=\mathbb{Z}$. By Mayer-Vietoris, we have $H^{i}(S^1, \underline{\mathbb{Z}})=0$ for $i\geq 2$ as it lies between two zeros. Moreover, $H^{0}(U,\underline{\mathbb{Z}}) \oplus H^{0}(V,\underline{\mathbb{Z}})=\mathbb{Z} \oplus \mathbb{Z}$ and $H^{0}(U\cap V, \underline{\mathbb{Z}})=H^{0}(\{\ast\},\underline{\mathbb{Z}})\oplus H^{0}(\{\ast\},\underline{\mathbb{Z}})=\mathbb{Z}\oplus \mathbb{Z}$, hence we have an exact sequence,
$$0\to \mathbb{Z} \xrightarrow{\alpha} \mathbb{Z} \oplus \mathbb{Z} \xrightarrow{\beta} \mathbb{Z}\oplus \mathbb{Z} \to H^{1}(S^1,\underline{\mathbb{Z}}) \to 0
$$
Thus, $H^{1}(S^1,\underline{\mathbb{Z}}) = \mathbb{Z}^2/\beta(\mathbb{Z}^2)$. Since $\beta(\mathbb{Z}^2)\cong \mathbb{Z}^2/\alpha(\mathbb{Z})$ and $\alpha(\mathbb{Z})$ is free of rank $1$, I feel like $H^1(S^1,\underline{\mathbb{Z}})=\mathbb{Z}$ but I don't think I can really conclude it without computing what $\alpha$ and $\beta$ actually do ($\alpha$ should just map $1$ to $(1,1)$). Is there a way of concluding $H^1(S^1,\underline{\mathbb{Z}})=\mathbb{Z}$ just by looking at the ranks (like it is possible to look at the dimension if this was a sequence of vector spaces)?

REPLY [1 votes]: Perhaps you could think about what the generators of $H^0$ actually are. For example, if $X$ is path-connected, then $H^0(X)$ has a single generator. This generator is a functional: you "feed in" a 0-cycle (i.e. a bunch of points) and this functional "spits out" a number equal to the number of points that you fed in. If $X$ has multiple path components, then $H^0(X)$ has multiple generators, associated to the various path components. You feed in a 0-cycle, and the generator spits out how many of the points in the 0-cycle lie in the path component that the generator is associated to.
Now let's work out how the morphisms in the Mayer-Vietoris sequence act. Given 0-cycles $\sigma_U$ and $\sigma_V$ in $U$ and $V$ respectively, and given a element $\psi \in H^0(S^1)$, we have
$$ \alpha(\psi)(\sigma_U ) = \psi(i_1(\sigma_U)), \\\alpha(\psi)(\sigma_V) = - \psi(i_2(\sigma_V)),$$
where $i_1: U \to S^1$ and $i_2 : V \to S^1$ are the inclusions. This is by the definition of the Mayer-Vietoris sequence.
Similarly, given a 0-cycle $\sigma_{U \cap V} $ in $U \cap V$, and given an element $\psi_U \in H^0(U )$ and an element $\psi_V \in H^0(V)$,
$$ \beta(\psi_U \oplus \psi_V)(\sigma_{U \cap V}) = \psi_U(j_1(\sigma_{U \cap V})) + \psi_V(j_2(\sigma_{U \cap V})),$$
where $j_1: U \cap V \to U$ and $j_2: U \cap V \to V$ are the natural inclusions.
Combining our description of the generators of the zeroth cohomology groups with our understanding of how the Mayer-Vietoris morphisms act, it shouldn't be too hard to see that
$$ \alpha = \left( \begin{array}{c} 1 \\ -1 \end{array}\right), \ \ \ \beta= \left( \begin{array}{c} 1 & 1 \\ 1 & 1 \end{array}\right).$$
[Alternatively, you can avoid these difficulties by working with reduced cohomology! The Mayer-Vietoris sequence for reduced cohomology gives the long exact sequence
$$ 0 \to 0 \to 0 \to \mathbb Z \to H^1(S^1) \to 0$$
which gives you the answer you want immediately.]


TITLE: Covariance of stochastic process
QUESTION [4 upvotes]: I need to calculate the expected value $\mathbb{E}[\eta(s) \cdot \eta( \tilde{s} )]$, where $\eta$ is an Ornstein-Uhlenbeck process defined by the stochastic differential equation
\begin{equation*}
\tau_{\eta} \frac{d \eta(t)}{dt} = - \eta(t) + \sqrt{2(\tau + \tau_{\eta})} \sigma \xi(t).
\end{equation*}
$\tau, \tau_{\eta}, \sigma \in \mathbb{R}$ are constants and $\xi(t)$ is an Gaussian white noise process $ \xi(t) = \frac{dW(t)}{dt}$. \
The needed expected value is equal to the Covariance $Cov(\eta(s), \eta(\tilde{s}))$, if he Ornstein-Uhlenbeck processes have mean zero. I also calculated the explicit solution of the SDE
\begin{align*}
\eta(s) = \exp \left( - \frac{s}{\tau_{\eta}}  \right) \left[ \eta_0 + \int_0^s \frac{1}{\tau_{\eta}}  \exp \left(  \frac{x}{\tau_{\eta}}  \right)
 \sqrt{2(\tau + \tau_{\eta}) } \sigma dW_x \right],
\end{align*}
where $W_x$ is a Brownian motion.
I inserted the solution of the stochastic differential equation  in the expected value with two different time variables $s, \tilde{s}$. Because the increments of the Brownian motion have mean zero, the mixed terms are zero. This leads to
\begin{align*}
\mathbb{E} \left[ \eta(s) \cdot \eta(\tilde{s}) \right] &=
\mathbb{E} \left[ \exp \left( - \frac{s + \tilde{s}}{\tau_{\eta}}  \right) \eta_0^2 \right]
+ \mathbb{E} \left[  n_0^2 + \int_0^s \int_0^{\tilde{s}} \frac{1}{\tau_{\eta}^2}  \exp \left(  \frac{x + y}{\tau_{\eta}}  \right) \cdot 2(\tau + \tau_{\eta}) \sigma^2 dW_x dW_y   \right]
\end{align*}
How can I calculate the expected value of the last double integral.
It probably has something to do with the Covariance of the 2 Brownian motions $dW_x, dW_y$.

REPLY [4 votes]: The explicit solution of your SDE is of the form
$$
\eta(s)=e^{-f(s)}\Big[\eta_0+\int_0^sae^{f(x)}\,dW_x\Big]\,.
$$
The expectation $E[\eta(s)\,\eta(\tilde s)]$ is easily obtained from $E[\int_0^se^{f(x)}\,dW_x]=0$ and
$$
E\Big[\int_0^se^{f(x)}\,dW_x\cdot\int_0^\tilde{s}e^{f(x)}\,dW_x\Big]=\int_0^{\min(s,\tilde s)}e^{2f(x)}\,dx\,.
$$


TITLE: How to calculate Jordan basis when the $(A-\lambda I)^2=0$
QUESTION [0 upvotes]: \begin{align}A&=\begin{pmatrix}3&1&1\\-3&-1&-3\\2&2&4\end{pmatrix}\\\\
J&=\begin{matrix}2&1&0\\0&2&0\\0&0&2\end{matrix}\end{align}
I want to know about "Jordan basis" of this problem
I already calculate Jordan Form.
and then, Use the fact that $AQ = QJ$
\begin{align}(A-2I)V_1 &= 0\\
(A-2I)V_2 &= V_1\\
(A-2I)V_3 &= 0\end{align}
so I finally get $V_1$ and $V_3$. $$V_1 = (-1, 1, 0)\\ V_3 = (-1, 0, 1)$$
but $V_2$ is not clear because $$(A-2I)^2 \times V_2 = (A-2I)V_1 = 0$$
In this situation how can I get the $V_2$?

REPLY [0 votes]: I think the problem is that you made an unfortunate choice of $V_1$. Had you instead used $V_1=(1,-3,2)$ (which is $(-3)(-1,1,0)+(2)(-1,0,1)$) you would have had no difficulty finding $V_2$ such that $(A-2I)V_2=V_1$. Then you can still use $V_3=(-1,0,1)$.


TITLE: Proving a function is holomorphic
QUESTION [0 upvotes]: The problem is this:
Let the matric $J$ be$$ J = \begin{bmatrix}0 & -1\\1 & 0\end{bmatrix}$$
Let $f : \Omega \rightarrow \mathbb{R}^2$be an $\mathbb{R}$- differentiable function defined on $\Omega \subset \mathbb{R}^2$.
a) Show that $f \in O(\Omega)$ if and only if for any $(x, y) \in \Omega$ we have $J \circ d_{(x,y)}f = d_{(x,y)}f \circ J$.
b) Show that $f \in O(\Omega)$ if and only if for any $(x, y) \in \Omega$ and any $\theta \in \mathbb{R}$ we have $R_{\theta} \circ d_{(x, y)}f = d_{(x, y)}f \circ R_{\theta}$ where $R_{\theta} : \mathbb{R}^2 \rightarrow \mathbb{R}^2$ denotes the rotation of angle $\theta$.
c) Let $\theta \in \mathbb{R}$. Assume that $R_{\theta} \circ d_{(x, y)}f = d_{(x, y)}f \circ R_{\theta}$ for any $(x, y) \in \Omega$. Is $f \in O(\Omega)$?
I don't know how to even start  with this and i'm not sure I understood the questions with the notation used..
Any help would be much appreciated

REPLY [0 votes]: Hint: $f$ is $\Bbb C$-derivable in $c$ iff is $\Bbb R$-differentiable in $c$ and the differential in $c$ is $\Bbb C$-linear. This imposes a condition on the partial derivatives of $f$. Namely, the Cauchy-Riemann equations. Check that (a) is equivalent to the Cauchy-Riemann equations...


TITLE: Numerical Analysis converging sequence question
QUESTION [1 upvotes]: Show that the sequence $p=10^{-2n}$ converges to zero with order $2$.
How many steps, $n$, will it take before this sequence is within $10^{-8}$ of zero?
Construct a sequence that converges with order $4$.

REPLY [0 votes]: For (1) and (3), you need to use the definition:
Definition: We say that the sequence converges with order $q$ to $L$ for $q>1$ if
$$ \lim_{k\to \infty} \frac{|x_{k+1}-L|}{|x_k-L|^q} = \mu \,\big|\; \mu > 0.$$


TITLE: Increasing network throughput by cutting routes
QUESTION [10 upvotes]: Suppose we model traffic flow between two points with a directed graph. Each route has either a constant travel time or one that linearly increases with traffic. We assume that each driver wishes to minimise their own travel time and we assume that the drivers form a Nash equilibria. Can removing a route ever decrease the average travelling time?
Note that the existence of multiple Nash equilibria makes this question a bit complicated. To clarify, I am looking for a route removal that will guarantee a decrease in the average traveling time regardless of the Nash equilibria that are chosen before and after.

REPLY [2 votes]: The form this question is usually asked is whether adding a route can increase the average traveling time, and this is known as Braess's paradox.  The Wiki article gives an explicit example in which the travel time on some of the routes depends on the traffic.


TITLE: Divisibility of coefficients of power series
QUESTION [3 upvotes]: Let $f = a_0 + a_1t + a_2t^2 + \cdots$ be a power series with coefficients in $\mathbb{Z}$. Let $p$ be a prime number, and suppose $p$ does not divide all of the coefficients of $f$. That is to say, $p$ does not divide $f$ in the ring $\mathbb{Z}[[t]]$.
Let $P(X)\in\mathbb{Z}[X]$ be a polynomial, such that $p$ does not divide $P(X)$. Could $p$ divide $P(f)$ (in $\mathbb{Z}[[t]]$?

REPLY [0 votes]: I think your question is not sufficiently sharply focused. My example is $f(t)=1+pt$, $P(t)=-1+t$, so that $(P\circ f)(t)=pt$.


TITLE: Find a Basis for the subspace S of Vector Space V
QUESTION [0 upvotes]: What is the method for finding a general solution?
For example.
Let S be the subspace of V, where V = all [2x2] symmetric matrices.
So A transpose(A^t) = A.

What is a Basis for subspace S? I can't find an examples of this. I have been trying to use properties of Linearly Independant Combo's and Vector Spaces but I'm coming up with a whole lot of nonsense.

REPLY [2 votes]: $\text{Hint:}\\
        \begin{pmatrix}
        a_{11} & a_{12} &...& a_{1n} \\
        a_{12} & a_{22} &...& a_{2n} \\
...&...&...&...\\
        a_{1n} & a_{2n} &...& a_{nn} \\
        \end{pmatrix}
=\left\{a_{11}\begin{pmatrix}
        1 & 0 &...& 0 \\
        0 & 0 &...& 0 \\
...&...&...&...\\
        0&0&...&0 \\
        \end{pmatrix}+a_{22}\begin{pmatrix}
        0 & 0 &...& 0 \\
        0 & 1 &...& 0 \\
...&...&...&...\\
        0&0&...&0 \\
        \end{pmatrix}+...+a_{nn}\begin{pmatrix}
        0 & 0 &...& 0 \\
        0 & 0 &...& 0 \\
...&...&...&...\\
        0&0&...&1 \\
        \end{pmatrix}\right\}+\left\{a_{12}\begin{pmatrix}
        0 & 1 &...& 0 \\
        1 & 0 &...& 0 \\
...&...&...&...\\
        0&0&...&0 \\
        \end{pmatrix}+...+a_{1n}\begin{pmatrix}
        0 & 0 &...& 1 \\
        0 & 0 &...& 0 \\
...&...&...&...\\
        1&0&...&0 \\
        \end{pmatrix}\right\}$

REPLY [0 votes]: Hint:
Show that a basis of the symmetric $2\times 2$-matrices is given by $$\left\{\begin{pmatrix}1 & 0 \\ 0 & 0\end{pmatrix},\quad \begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix},\quad \begin{pmatrix}0 & 0 \\ 0 & 1\end{pmatrix}\right\}.$$


TITLE: Roots of $x^4 -6x^3 +x^2+10x +1=0$
QUESTION [3 upvotes]: How can one prove that the following function has 4 real roots?
$$x^4 -6x^3 +x^2 +10x+1=0$$
The problem is that roots don't seem to be possible to compute by hand.

REPLY [1 votes]: Another cheaty proof. $p(x)=0$ is equivalent to:
$$f(x)=(x+1)^2(x-4)^2 = 14x+15 =g(x).$$
Since for $x\in\{-\infty,-1,0,4,+\infty\}$ the relations between the LHS and the RHS are $>,<,>,<,>$ we must have four real roots in the intervals $(-\infty,-1),(-1,0),(0,4),(4,+\infty)$.
By the Rouché theorem, all the roots lie in the ball having center $x=\frac{3}{2}$ and radius $\rho=\frac{9}{2}$, hence in $(-3,6)$, so the previous intervals become $(-3,-1),(-1,0),(0,4),(4,6)$.


TITLE: Why is the Mandelbrot Set to the power of 2?
QUESTION [0 upvotes]: I've been looking at the Mandelbrot set and playing around with the powers on it. In the sense that I know the equation is $z^2 +c$, and I've been changing up the $2$. As it happens gradual increases in the power have interesting effects, but I can't find much about them online. Why is it that the set uses the power $2$ as opposed to anything else?
Also, on a side note, does anyone know an explanation as to why the Mandelbrot set is shaped the way it is? With the different sections in it, and the symmetry about the real axis?
Thanks :)

REPLY [5 votes]: Why? Well, because the Mandelbrot set is defined to be the set of parameters $c$ for which $z^2 + c$ does not escape to infinity.
Quadratic polynomials are the first simplest example of functions whose iterations give an interesting dynamics, hence they are widely studied.
If you change power of the polynomial, you are going to get a different dynamics and and a different set in the parameter space.

What follows is an overview of facts about the Mandelbrot set, as an exhaustive explanation would be worth a long book.
About symmetries and properties: A lot of properties of the Mandelbrot set are currently being studied and they stay open questions (e.g. MLC, the local connectivity of the set), while many others are known. Lot of interest in dynamics is about the measure and/or dimension of the set and its boundary, for instance.
The Mandelbrot set is symmetric with respect the $x$-axis, simply because you can prove that if $c \in M$, the Mandelbrot set, then $\overline{c} \in M$ as well.
Also, the set is often divided in different components (for instance, hyperbolic components) depending on the nature of the fixed point. The main cardioid is made of polynomials $z^2+c$ for which the fixed point is attracting. Hyperbolic components are conjectured to be dense, but that is also an open problem (related to the above mentioned MLC conjecture).
Regarding self-similarity, the Mandelbrot set is not self-similar. Several progresses have been done until recent years, to determine around what points it is actually self-similar.
Renormalization gives you that the Mandelbrot set is actually quasi-self-similar, i.e. it contains copies of itself (often called "baby Mandelbrot sets") at any scale. Note that this result is highly non-trivial and extremely fascinating.

A quick googling led me to the Multibrot set, which you might be interested in.


TITLE: Banach Spaces which are not $L^p$
QUESTION [3 upvotes]: Most of the times, when I think of Banach Spaces I think of $L^p$ spaces. I would like to know if there is any Banach space which can not be written as $L^p$ space. Please also indicate any applications of such spaces. Thanks

REPLY [1 votes]: For spaces with APPLICATIONS, you can try Sobolev spaces and things like that.


TITLE: Alternating sum over collections closed under containment
QUESTION [9 upvotes]: Let $\mathscr{C}$ be a collection of subsets of a finite set $P$. Assume $\mathscr{C}$ is closed under containment: if $S\subset P$ is in $\mathscr{C}$, then every set $S'\subset P$ containing $S$ is in $\mathscr{C}$.
What can we say about
$$\sum_{S\in \mathscr{C}} (-1)^{|S|},$$ where $|S|$ is the number of elements of $S$? In particular, is the absolute value of this sum bounded
by the number of minimal elements of $\mathscr{C}$, i.e.,
$$\left|\sum_{S\in \mathscr{C}} (-1)^{|S|}\right| \leq |\{S\in \mathscr{C}:\not \exists S'\subsetneq S \;\text{s.t.}\; S'\in \mathscr{C}\}|?$$

REPLY [8 votes]: There is an interpretation of your inequality using simplicial complex and $h$-vector. Namely, let $\Delta$ be the set of all $P-S$ with $S$ in your set. Then $\Delta$ is a collection closed under inclusion, hence a simplicial complex.
The invariant you are interested in is, up to sign, the alternating sum of $f_i$: the number of $i$-dim faces of $\Delta$. Then, by a well-known formula, it is equal to $|h_d|$, where $h_i$ forms the $h$-vector of $\Delta$, and $d-1$ is the dimension of $\Delta$.
The right hand side of the inequality you are interested in is the number of facets (maximal elements) of $\Delta$. As people have pointed out, in general the inequality you want does not hold.
However, I would like to point out that it is likely to hold under certain extra topological/homological  assumptions. For instance, if $\Delta$ is Cohen-Macaulay, then all the $h_i$ are non-negative, and the number of facets is $f_{d-1}=\sum_{i\geq 0} h_i\geq h_d$, which is what you need. In fact, as $h_0=1$ and $h_1=n-d$ where $n=|P|$, you get something a little stronger.
One can prove other inequalities for $h_i$ under weaker conditions. For example, if $\Delta$ satisfies Serre's conditions $(S_{r})$,  one still have non-negativity of $h_{\leq r}$, a result first proved by Murai-Terai.  I discussed some of them in a recent talk (but it is perhaps a bit algebraic).


text:
\begin{abstract}
  We study a natural intrinsic definition of geometric simplices in Riemannian manifolds of arbitrary dimension $n$, and exploit these simplices to obtain  criteria for triangulating compact Riemannian manifolds.  These geometric simplices are defined using Karcher means. Given a finite set of vertices in a convex set on the manifold, the point that minimises the weighted sum of squared distances to the vertices is the Karcher mean relative to the weights. Using barycentric coordinates as the weights, we obtain a smooth map from the standard Euclidean simplex to the manifold.  A Riemannian simplex is defined as the image of this barycentric coordinate map. In this work we articulate criteria that guarantee that the barycentric coordinate map is a smooth embedding. If it is not, we say the Riemannian simplex is degenerate.  Quality measures for the ``thickness'' or ``fatness'' of Euclidean simplices can be adapted to apply to these Riemannian simplices. For manifolds of dimension 2, the simplex is non-degenerate if it has a positive quality measure, as in the Euclidean case. However, when the dimension is greater than two, non-degeneracy can be guaranteed only when the quality exceeds a positive bound that depends on the size of the simplex and local bounds on the absolute values of the sectional curvatures of the manifold. An analysis of the geometry of non-degenerate Riemannian simplices leads to conditions which guarantee that a simplicial complex is homeomorphic to the manifold.
\end{abstract}

\paragraph{Keywords.} Karcher means, barycentric coordinates, triangulation, Riemannian manifold, sampling conditions, Riemannian simplices