way, we can rewrite the above expression in a more compact form,

$\displaystyle B_{\zeta}^{\rm
tl}(\tau;\mathbf{p}_{1},\mathbf{p}_{2},\mathbf{p}_{3})$
$\displaystyle=12M_{P}^{2}\imaginary\\{\zeta_{p_{1}}(\tau)\zeta_{p_{2}}(\tau)\zeta_{p_{2}}(\tau)a_{s}^{2}\epsilon_{s}\dfrac{\differential}{\differential\tau^{\prime}}\left(\zeta^{*}_{p_{1}}(\tau^{\prime})\zeta^{*}_{p_{2}}(\tau^{\prime})\zeta^{*}_{p_{3}}(\tau^{\prime})\right)\evaluated{}_{\tau^{\prime}=\tau_{s}}\Bigg{\\}}-(s\leftrightarrow
e)\,,$ (167)

where we have used the first-order relation between $\zeta$ and $\delta\phi$.
As with the two-point correlation in Appendix G, a cancellation at the times
of the transitions makes that, in this case, the divergence of the bispectrum
disappear in the limit $\delta N\to 0$. We can now compute the bispectrum of
$\zeta$ directly in the $\zeta$-gauge using the in-in formalism with the
interaction

$\displaystyle
S\supset\frac{M_{P}^{2}}{2}\int\differential^{4}x\,a^{2}\,\epsilon\,\eta^{\prime}\,\zeta^{\prime}\,\zeta^{2}\,,$
(168)

which is the most relevant interaction in this type of models, as discussed in
Appendix G. We obtain the same expression for the tree-level bispectrum as the
eq. (167), i.e. the bispectrum obtained from the $\delta\phi$-gauge route; as
it should be. This is a further confirmation that employing the
$\delta\phi$-gauge to compute correlations of $\zeta$ in our model can be
convenient.

## References

  * Carr  _et al._ (2010) B. J. Carr, K. Kohri, Y. Sendouda, and J. Yokoyama, Phys. Rev. D 81, 104019 (2010), arXiv:0912.5297 [astro-ph.CO] .
  * Niikura  _et al._ (2019) H. Niikura _et al._ , Nature Astron. 3, 524 (2019), arXiv:1701.02151 [astro-ph.CO] .
  * Katz  _et al._ (2018) A. Katz, J. Kopp, S. Sibiryakov, and W. Xue, JCAP 12, 005 (2018), arXiv:1807.11495 [astro-ph.CO] .
  * Montero-Camacho  _et al._ (2019) P. Montero-Camacho, X. Fang, G. Vasquez, M. Silva, and C. M. Hirata, JCAP 08, 031 (2019), arXiv:1906.05950 [astro-ph.CO] .
  * Ballesteros  _et al._ (2020a) G. Ballesteros, J. Coronado-Blázquez, and D. Gaggero, Phys. Lett. B 808, 135624 (2020a), arXiv:1906.10113 [astro-ph.CO] .
  * Carr  _et al._ (2021) B. Carr, K. Kohri, Y. Sendouda, and J. Yokoyama, Rept. Prog. Phys. 84, 116902 (2021), arXiv:2002.12778 [astro-ph.CO] .
  * Green and Kavanagh (2021) A. M. Green and B. J. Kavanagh, J. Phys. G 48, 043001 (2021), arXiv:2007.10722 [astro-ph.CO] .
  * Carr and Hawking (1974) B. J. Carr and S. W. Hawking, Mon. Not. Roy. Astron. Soc. 168, 399 (1974).
  * Nakama  _et al._ (2014) T. Nakama, T. Harada, A. G. Polnarev, and J. Yokoyama, JCAP 01, 037 (2014), arXiv:1310.3007 [gr-qc] .
  * Musco (2019) I. Musco, Phys. Rev. D 100, 123524 (2019), arXiv:1809.02127 [gr-qc] .
  * Tsamis and Woodard (2004) N. C. Tsamis and R. P. Woodard, Phys. Rev. D 69, 084005 (2004), arXiv:astro-ph/0307463 .
  * Kinney (2005) W. H. Kinney, Phys. Rev. D 72, 023515 (2005), arXiv:gr-qc/0503017 .
  * Fixsen  _et al._ (1996) D. J. Fixsen, E. S. Cheng, J. M. Gales, J. C. Mather, R. A. Shafer, and E. L. Wright, Astrophys. J. 473, 576 (1996), arXiv:astro-ph/9605054 .
  * Kristiano and Yokoyama (2022) J. Kristiano and J. Yokoyama, (2022), arXiv:2211.03395 [hep-th] .
  * Schwinger (1961) J. S. Schwinger, J. Math. Phys. 2, 407 (1961).
  * Keldysh (1964) L. V. Keldysh, Zh. Eksp. Teor. Fiz. 47, 1515 (1964).
  * Weinberg (2005) S. Weinberg, Phys. Rev. D 72, 043514 (2005), arXiv:hep-th/0506236 .
  * Riotto (2023) A. Riotto, (2023), arXiv:2301.00599 [astro-ph.CO] .
  * Firouzjahi (2023a) H. Firouzjahi, (2023a), arXiv:2311.04080 [astro-ph.CO] .
  * Franciolini  _et al._ (2023) G. Franciolini, A. Iovino, Junior., M. Taoso, and A. Urbano, (2023), arXiv:2305.03491 [astro-ph.CO] .
  * Tada  _et al._ (2023) Y. Tada, T. Terada, and J. Tokuda, (2023), arXiv:2308.04732 [hep-th] .
  * Iacconi  _et al._ (2023) L. Iacconi, D. Mulryne, and D. Seery, (2023), arXiv:2312.12424 [astro-ph.CO] .
  * Ballesteros and Taoso (2018) G. Ballesteros and M. Taoso, Phys. Rev. D 97, 023501 (2018), arXiv:1709.05565 [hep-ph] .
  * Ballesteros  _et al._ (2020b) G. Ballesteros, J. Rey, M. Taoso, and A. Urbano, JCAP 07, 025 (2020b), arXiv:2001.08220 [astro-ph.CO] .
  * Wands (1999) D. Wands, Phys. Rev. D 60, 023507 (1999), arXiv:gr-qc/9809062 .
  * Leach and Liddle (2001) S. M. Leach and A. R. Liddle, Phys. Rev. D 63, 043508 (2001), arXiv:astro-ph/0010082 .
  * Leach  _et al._ (2001) S. M. Leach, M. Sasaki, D. Wands, and A. R. Liddle, Phys. Rev. D 64, 023512 (2001), arXiv:astro-ph/0101406 .
  * Chen (2010) X. Chen, Adv. Astron. 2010, 638979 (2010), arXiv:1002.1416 [astro-ph.CO] .
  * Senatore and Zaldarriaga (2010) L. Senatore and M. Zaldarriaga, JHEP 12, 008 (2010), arXiv:0912.2734 [hep-th] .
  * Weinberg (2008) S. Weinberg, Phys. Rev. D 78, 123521 (2008), arXiv:0808.2909 [hep-th] .
  * Weinberg (2011) S. Weinberg, Phys. Rev. D 83, 063508 (2011), arXiv:1011.1630 [hep-th] .
  * Hollik (1990) W. F. L. Hollik, Fortsch. Phys. 38, 165 (1990).
  * Bunch and Davies (1978) T. S. Bunch and P. C. W. Davies, Proc. Roy. Soc. Lond. A 360, 117 (1978).
  * Espinosa  _et al._ (2018) J. R. Espinosa, D. Racco, and A. Riotto, JCAP 09, 012 (2018), arXiv:1804.07732 [hep-ph] .
  * Gerstenlauer  _et al._ (2011) M. Gerstenlauer, A. Hebecker, and G. Tasinato, JCAP 06, 021 (2011), arXiv:1102.0560 [astro-ph.CO] .
  * Giddings and Sloth (2011) S. B. Giddings and M. S. Sloth, Phys. Rev. D 84, 063528 (2011), arXiv:1104.0002 [hep-th] .
  * Senatore and Zaldarriaga (2013) L. Senatore and M. Zaldarriaga, JHEP 01, 109 (2013), arXiv:1203.6354 [hep-th] .
  * Gorbenko and Senatore (2019) V. Gorbenko and L. Senatore, (2019), arXiv:1911.00022 [hep-th] .
  * Taoso and Urbano (2021) M. Taoso and A. Urbano, JCAP 08, 016 (2021), arXiv:2102.03610 [astro-ph.CO] .
  * Ezquiaga  _et al._ (2020) J. M. Ezquiaga, J. García-Bellido, and V. Vennin, JCAP 03, 029 (2020), arXiv:1912.05399 [astro-ph.CO] .
  * Figueroa  _et al._ (2021) D. G. Figueroa, S. Raatikainen, S. Rasanen, and E. Tomberg, Phys. Rev. Lett. 127, 101302 (2021), arXiv:2012.06551 [astro-ph.CO] .
  * Firouzjahi (2023b) H. Firouzjahi, JCAP 10, 006 (2023b), arXiv:2303.12025 [astro-ph.CO] .
  * Fumagalli (2023) J. Fumagalli, (2023), arXiv:2305.19263 [astro-ph.CO] .
  * Kristiano and Yokoyama (2023) J. Kristiano and J. Yokoyama, (2023), arXiv:2303.00341 [hep-th] .
  * Maldacena (2003) J. M. Maldacena, JHEP 05, 013 (2003), arXiv:astro-ph/0210603 .
  * Wang (2014) Y. Wang, Commun. Theor. Phys. 62, 109 (2014), arXiv:1303.1523 [hep-th] .
  * Burrage  _et al._ (2011) C. Burrage, R. H. Ribeiro, and D. Seery, JCAP 07, 032 (2011), arXiv:1103.4126 [astro-ph.CO] .
  * Senatore (2017) L. Senatore, in  _Theoretical Advanced Study Institute in Elementary Particle Physics: New Frontiers in Fields and Strings_ (2017) pp. 447–543, arXiv:1609.00716 [hep-th] .
  * Arnowitt  _et al._ (2008) R. L. Arnowitt, S. Deser, and C. W. Misner, Gen. Rel. Grav. 40, 1997 (2008), arXiv:gr-qc/0405109 .
  * Weinberg (2003) S. Weinberg, Phys. Rev. D 67, 123504 (2003), arXiv:astro-ph/0302326 .
  * Baumann (2022) D. Baumann,  _Cosmology_ (Cambridge University Press, 2022).
  * Arroja and Tanaka (2011) F. Arroja and T. Tanaka, JCAP 05, 005 (2011), arXiv:1103.1102 [astro-ph.CO] .
  * Gibbons and Hawking (1977) G. W. Gibbons and S. W. Hawking, Phys. Rev. D 15, 2752 (1977).
  * York (1972) J. W. York, Jr., Phys. Rev. Lett. 28, 1082 (1972).
  * Dyer and Hinterbichler (2009) E. Dyer and K. Hinterbichler, Phys. Rev. D 79, 024028 (2009), arXiv:0809.4033 [gr-qc] .
  * Malik and Wands (2009) K. A. Malik and D. Wands, Phys. Rept. 475, 1 (2009), arXiv:0809.4944 [astro-ph] .
  * Christopherson and Malik (2009) A. J. Christopherson and K. A. Malik, JCAP 11, 012 (2009), arXiv:0909.0942 [astro-ph.CO] .
  * Sugiyama  _et al._ (2013) N. S. Sugiyama, E. Komatsu, and T. Futamase, Phys. Rev. D 87, 023530 (2013), arXiv:1208.1073 [gr-qc] .
  * Braglia and Pinol (2024) M. Braglia and L. Pinol, (2024), arXiv:2403.14558 [astro-ph.CO] .
  * Chen  _et al._ (2006) X. Chen, M.-x. Huang, and G. Shiu, Phys. Rev. D 74, 121301 (2006), arXiv:hep-th/0610235 .
  * Bravo  _et al._ (2018) R. Bravo, S. Mooij, G. A. Palma, and B. Pradenas, JCAP 05, 024 (2018), arXiv:1711.02680 [astro-ph.CO] .


# A distributed classification/estimation algorithm for sensor
networks††thanks: A preliminary version of some of the results has appeared in
the proceedings of the 50st IEEE Conference on Decision and Control and
European Control Conference, Orlando, Florida, 12-15 December 2011.

Fabio Fagnani) DISMA (Dipartimento di Scienze Matematiche), Politecnico di
Torino, Corso Duca degli Abruzzi, 24, I-10129 TO, (e-mail:
<EMAIL_ADDRESS>Sophie M. Fosson DET (Dipartimento di Elettronica e
Telecomunicazioni), Politecnico di Torino, Corso Duca degli Abruzzi, 24,
I-10129 TO (e-mail<EMAIL_ADDRESS>Chiara Ravazzi DET (Dipartimento
di Elettronica e Telecomunicazioni), Politecnico di Torino, Corso Duca degli
Abruzzi, 24, I-10129 TO (e-mail<EMAIL_ADDRESS>
###### Abstract

In this paper, we address the problem of simultaneous classification and
estimation of hidden parameters in a sensor network with communications
constraints. In particular, we consider a network of noisy sensors which
measure a common scalar unknown parameter. We assume that a fraction of the
nodes represent faulty sensors, whose measurements are poorly reliable. The
goal for each node is to simultaneously identify its class (faulty or non-
faulty) and estimate the common parameter.

We propose a novel cooperative iterative algorithm which copes with the
communication constraints imposed by the network and shows remarkable
performance. Our main result is a rigorous proof of the convergence of the
algorithm and a characterization of the limit behavior. We also show that, in
the limit when the number of sensors goes to infinity, the common unknown
parameter is estimated with arbitrary small error, while the classification
error converges to that of the optimal centralized maximum likelihood
estimator. We also show numerical results that validate the theoretical
analysis and support their possible generalization. We compare our strategy
with the Expectation-Maximization algorithm and we discuss trade-offs in terms
of robustness, speed of convergence and implementation simplicity.

###### keywords:

Classification, Consensus, Gaussian mixture models, Maximum-likelihood
estimation, Sensor networks, Switching systems.

##  1 Introduction

Sensor networks are one of the most important technologies introduced in our
century. Promoted by the advances in wireless communications and by the
pervasive diffusion of smart sensors, wireless sensor networks are largely
used nowadays for a variety of purposes, e.g., environmental and habitat
surveillance, health and security monitoring, localization, targeting, event
detection.

A sensor network basically consists in the deployment of a large numbers of
small devices, called sensors, that have the ability to perform measurements
and simple computations, to store few amounts of data, and to communicate with
other devices. In this paper, we focus on _ad hoc_ networks, in which
communication is local: each sensor is connected only with a restricted number
of other sensors. This kind of cooperation allows to perform elaborate
operations in a self-organized way, with no centralized supervision or data
fusion center, with a substantial energy and economic saving on processors and
communication links. This allows to construct large sensor networks at
contained cost.

A problem that can be addressed through ad hoc sensor networking is the
distributed estimation: given an unknown physical parameter (e.g., the
temperature in a room, the position of an object), one aims at estimating it
using the sensing capabilities of a network. Each sensor performs a (not
exact) measurement and shares it with the sensors with which it can establish
a communication; in turn, it receives information and consequently updates its
own estimate. If the network is connected, by iterating the sharing procedure,
the information propagates and a consensus can be reached. Neither centralized
coordinator nor data fusion center is present. The mathematical model of this
problem must envisage the presence of noise in measurements, which are
naturally corrupted by inaccuracies, and possible constraints on the network
in terms of communication, energy or bandwidth limitations, and of necessity
of quantization or data compression.

_Distributed estimation_ in ad hoc sensor networks has been widely studied in
the literature. For the problem of estimating an unknown common parameter,
typical approach is to consider distributed versions of classical maximum
likelihood (ML) or maximum-a-posteriori (MAP) estimators. Decentralization can
be obtained, for instance, through consensus type protocols (see [1], [2],
[3]) adapted to the communication graph of the network, or by belief
propagation methods [4] and [5].

A second important issue is _sensors’ classification_ , which we define as
follows [6]. Let us imagine that sensors can be divided into different classes
according to peculiar properties, e.g., measurements’ or processing
capabilities, and that no sensor knows to which class it belongs: by
classification, we then intend the labeling procedure that each sensor
undertakes to determine its affiliation. This task is addressed to a variety
of clustering purposes, for example, to rebalance the computation load in a
network where sensors can be distinguished according to their processing
power. On most occasions, sensors’ classification is faced through some
distributed estimation, the underlying idea being the following: each sensor
performs its measurement of a parameter, then iteratively modifies it on the
basis of information it receives; during this iterative procedure the sensor
learns something about itself which makes it able to estimate its own
configuration.

In this paper, we consider the following model: each sensor $i$ performs a
measurement $y_{i}=\theta^{\star}+\omega_{i}^{\star}\eta_{i}$, where
$\theta^{\star}\in\mathbb{R}$ is the unknown global parameter,
$\omega_{i}^{\star}>0$ is the unknown status of the sensor, and $\eta_{i}$ is
a Gaussian random noise. The more $\omega_{i}^{\star}$ is large, the more the
sensor $i$ is malfunctioning, that is, the quality if its measurement is low.
The $\omega_{i}^{\star}$ parameter is supposed to belong to a discrete set, in
particular in this paper we consider the binary case.

The goal of each unit $i$ is to estimate the parameter $\theta^{\star}$ and
the specific configuration $\omega^{\star}_{i}$. The presence of the common
unknown parameter $\theta^{\star}$ imposes a coupling between the different
nodes and makes the problem interesting.

An additive version of the aforementioned model has been studied in [7], where
measurement is given by $y_{i}=\theta^{\star}+\omega_{i}^{\star}+\eta_{i}$.
Another related problem is the so-called calibration problem [8, 9]: sensor
$i$ performs a noisy linear measurement $y_{i}=A_{i}\theta+\eta_{i}$ where the
unknown $\theta$ and $A_{i}$ are a vector and a matrix, respectively, while
$\eta_{i}$ is a noise; the goal consists in the estimation of $\theta$ and of
$A_{i}$, the latter being known as calibration problem.

All these are particular cases of the problem of the estimation of Gaussian
mixtures’ parameters [10, 11]. This perspective has been studied for sensor
networks in [12], [13], [14], and [15] where distributed versions of the
Expectation-Maximization (EM) algorithm have been proposed. A network is given
where each node independently performs the E-step through local observations.
In particular, in [14] a consensus filter is used to propagate the local
information. The tricky point of such techniques is the choice of the number
of averaging iterations between two consecutive M-steps, which must be
sufficient to reach consensus.

The aim of this paper is the development of a distributed, iterative procedure
which copes with the communication constraints imposed by the network and
computes an estimation ($\widehat{\theta},\widehat{\omega}$) approximating the
maximum likelihood optimal solution of the proposed problem. The core of our
methodology is an Input Driven Consensus Algorithm (IA for short), introduced
in [16], which takes care of the estimation of the parameter $\theta^{*}$. IA
is coupled with a classification step where nodes update the estimation of
their own type $\omega^{*}_{i}$ by a simple threshold estimator based on the
current estimation of $\theta^{*}$. The fact of using a consensus protocol
working on inputs instead, as more common, on initial conditions, is a key
strategic fact: it serves the purpose of using the innovation coming from the
units who are modifying the estimation of their status, as time passes by. Our
main theoretical contribution is a complete analysis of the algorithm in terms
of convergence and of behaviour with respect to the size of the network. With
respect to other approaches like distributed EM for which convergence results
are missing, this makes an important difference. We also present a number of
numerical simulations showing the remarkable performance of the algorithm
which, in many situations, outperform classical choices like EM.

The outline of the paper is the following. In Section 2 we shortly present
some graph nomenclature needed in the paper. Section 3 is devoted to a formal
description of the problem and to a discussion of the classical centralized
maximum likelihood solution. In Section 4, we present the details and the
analysis of our IA. Our main results are Theorems 1 and 2: Theorem 1 ensures
that, under suitable assumptions on the graph, the algorithm converges to a
local maximum of the log-likelihood function; Theorem 2 is a concentration
result establishing that when the number of nodes $N\to+\infty$, the estimate
$\widehat{\theta}$ converges to the true value $\theta^{*}$ (a sort of
asymptotic consistency). Finally, we also study the behavior of the discrete
estimate $\widehat{\omega}$ by analyzing the performance index the relative
classification error over the network when $N\to+\infty$ (see Corollary 4).
Section 5 contains a set of numerical simulations carried on different graph
architectures: complete, circulant, grids, and random geometric graphs.
Comparisons are proposed with respect to the optimal centralized ML solution
and also with respect to the EM solution. Finally, a long Appendix contains
all the proofs.

##  2 General notation and graph theoretical preliminaries

Throughout this paper, we use the following notational convention. We denote
vectors with small letters, and matrices with capital letters. Given a matrix
$M$, $M^{T}$ denotes its transpose. Given a vector $v$, $||v||$ denotes its
Euclidean norm. $\mathbf{1}_{A}$ is the indicator function of set $A$. Given a
finite set $\mathcal{V}$, $R^{\mathcal{V}}$ denotes the space of real vectors
with components labelled by elements of $\mathcal{V}$. Given two vectors
$x,z\in\mathbb{R}^{\mathcal{V}}$,
$\mathrm{d_{H}}(x,z)=|\\{i\in\mathcal{V}:x_{i}\neq z_{i}\\}|$. We use the
convention that a summation over an empty set of indices is equal to zero,
while a product over an empty set gives one.

A symmetric graph is a pair $\mathcal{G}=(\mathcal{V,E})$ where $\mathcal{V}$
is a set, called the set of vertices, and
$\mathcal{E}\subseteq\mathcal{V\times V}$ is the set of edges with the
property that $(i,i)\not\in\mathcal{E}$ for all $i\in\mathcal{V}$ and
$(i,j)\in\mathcal{E}$ implies $(j,i)\in\mathcal{E}$. $\mathcal{G}$ is strongly
connected if, for all $i,j\in\mathcal{V}$, there exist vertices $i_{1},\dots
i_{s}$ such that $(i,i_{1}),(i_{1},i_{2}),\dots,(i_{s},j)\in\mathcal{E}$. To
any symmetric matrix $P\in\mathbb{R}^{\mathcal{V}\times\mathcal{V}}$ with non-
negative elements, we can associate a graph
$\mathcal{G}_{P}=(\mathcal{V},\mathcal{E}_{P})$ by putting
$(i,j)\in\mathcal{E}_{P}$ if and only if $P_{ij}>0$. $P$ is said to be adapted
to a graph $\mathcal{G}$ if $\mathcal{G}_{P}\subseteq\mathcal{G}$. A matrix
with non-negative elements $P$ is said to be stochastic if
$\sum_{j\in\mathcal{V}}P_{ij}=1$ for every $i\in\mathcal{V}$. Equivalently,
denoting by ${\mathbbm{1}}$ the vector of all $1$ in
$\mathbb{R}^{\mathcal{V}}$, $P$ is stochastic if
$P{\mathbbm{1}}={\mathbbm{1}}$. $P$ is said to be primitive if there exists
$n_{0}\in\mathbb{N}$ such that $P^{n_{0}}_{ij}>0$ for every
$i,j\in\mathcal{V}$. A sufficient condition ensuring primitivity is that
$\mathcal{G}_{P}$ is strongly connected and $P_{ii}>0$ for some
$i\in\mathcal{V}$.

##  3 Bayesian modeling for estimation and classification

###  3.1 The model

In our model, we consider a network, represented by a symmetric graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$. $\mathcal{G}$ represents the system
communication architecture. We denote the number of nodes by
$N=|\mathcal{V}|$. We assume that each node $i\in\mathcal{V}$ measures the
observable

$y_{i}=\theta^{\star}+\omega^{\star}_{i}\eta_{i}$ (1)

where $\theta^{\star}\in\mathbb{R}$ is an unknown parameter, $\eta_{i}$’s
Gaussian noises $\mathsf{N}(0,1)$, $\omega^{\star}_{i}$’s Bernoulli random
variables taking values in $\\{\alpha,\beta\\}$ (with
${\mathbb{P}}(\omega^{\star}_{i}=\beta)=p$). We assume all the random
variables $\eta_{i}$’s and $\omega^{\star}_{i}$’s to be mutually independent.
Notice that each $y_{i}\in\mathbb{R}$ is a Gaussian mixture distributed
according to the probability density function

$\displaystyle
f(y_{i})=(1-p)f(y_{i}|\theta^{\star},\alpha)+pf(y_{i}|\theta^{\star},\beta)$
(2) $\displaystyle
f(y_{i}|\theta^{\star},x)=\frac{1}{x\sqrt{2\pi}}\mathrm{e}^{-\frac{(y_{i}-\theta^{\star})^{2}}{2x^{2}}}\quad
x\in\\{\alpha,\beta\\}.$ (3)

The binary model of $\omega^{\star}$ is motivated by different scenarios: as
an example, if $0<\alpha<<\beta$, the nodes of type $\beta$ may represent a
subset of faulty sensors, whose measurements are poorly reliable; the aim may
be the detection of faulty sensors in order to switch them off or neglect
their measurements, or for other clustering purposes. It is also realistic to
assume that some a-priori information about the quantity of faulty sensors is
extracted, e.g., from experimental data on the network, and it is conceivable
to represent such information as an a-priori distribution. This is why we
assume a Bernoulli distribution on each $\omega^{\star}_{i}$; on the other
hand, we suppose that no a-priori information is available on the unknown
parameter $\theta^{\star}$. However, the addition of an a priori probability
distribution on $\theta^{*}$ does not significantly alter our analysis and our
results.

###  3.2 The maximum likelihood solution

The goal is to estimate the parameter $\theta^{\star}$ and the specific
configuration $\omega^{\star}_{i}$ of each unit. Disregarding the network
constraints, a natural solution to our problem would be to consider a joint ML
in $\theta^{\star}$ and MAP in the $\omega^{\star}_{i}$’s (see [17, 18]). Let
$f(y,\omega|\theta)$ be the joint distribution of $y$ and $\omega$ (density in
$y$ and probability in $\omega$) given the parameter $\theta$, and consider
the rescaled log-likelihood function

$\displaystyle\begin{split}L_{N}(\theta,\omega)&:=\frac{1}{N}\log
f(y,\omega|\theta).\end{split}$ (4)

The hybrid ML/MAP solution, which for simplicity for now on we will refer to
as the ML solution, prescribes to choose $\theta$ and $\omega$ which maximize
$L_{N}(\theta,\omega)$

$(\widehat{\theta}^{\mathrm{ML}},\widehat{\omega}^{\mathrm{ML}}):=\underset{\theta\in\mathbb{R},\leavevmode\nobreak\
\omega\in\\{\alpha,\beta\\}^{\mathcal{V}}}{\mathrm{argmax\,}}L_{N}(\theta,\omega).$
(5)

Standard calculations lead us to

$L_{N}(\theta,\omega)=-\frac{1}{N}\sum_{j\in\mathcal{V}}\left(\frac{(y_{j}-\theta)^{2}}{2\beta^{2}}+{\mathbf{1}}_{\\{\omega_{j}=\alpha\\}}\left(\frac{(y_{j}-\theta)^{2}}{2}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)+\log\frac{1-p}{p}\frac{\beta}{\alpha}\right)\right)+c$
(6)

where $c$ is a constant. It can be noted that partial maximizations of
$L_{N}(\theta,\omega)$ with respect to just one of the two variables have
simple representation. Let

$\widehat{\theta}(\omega):=\underset{\theta}{\mathrm{argmax\,}}{L}_{N}(\theta,\omega)\qquad\widehat{\omega}(\theta):=\underset{\omega}{\mathrm{argmax\,}}L_{N}(\theta,\omega).$
(7)

Then

$\widehat{\theta}(\omega)=\frac{\sum_{j}y_{j}/\omega_{j}^{2}}{\sum_{j}1/\omega_{j}^{2}}\qquad\widehat{\omega}(\theta)_{i}=\begin{cases}\alpha&\text{if
}|y_{i}-{{\theta}}|<\delta\\\ \beta&\text{otherwise}\end{cases}$ (8)

where

$\delta=\sqrt{2\frac{\ln\left(\frac{1-p}{p}\frac{\beta}{\alpha}\right)}{\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}}}.$

The ML solution can then be obtained, for instance, by considering

$\widehat{\theta}^{\mathrm{ML}}=\underset{\theta}{\mathrm{argmax\,}}L(\theta,\widehat{\omega}(\theta))\,,\quad\widehat{\omega}^{\mathrm{ML}}=\widehat{\omega}(\widehat{\theta}^{\mathrm{ML}}).$
(9)

It should be noted how the computation of the
$(\widehat{\omega}^{\mathrm{ML}})_{i}$’s becomes totally decentralized once
$\widehat{\theta}^{\mathrm{ML}}$ has been computed. For the computation of
$\widehat{\theta}^{\mathrm{ML}}$ instead one needs to gather information from
all units to compute $L_{N}(\theta,\widehat{\omega}(\theta))$ and it is not at
all evident how this can be done in a decentralized way. Moreover, further
difficulties are caused by the fact that
$L_{N}(\theta,\widehat{\omega}(\theta))$ may contain many local maxima, as
shown in Figure 1.

It should be noted that $L_{N}(\theta,\widehat{\omega}(\theta))$ is
differentiable except at a finite number of points, and between two successive
non-differentiable points the function is concave. Therefore, the local maxima
of the function coincide with its critical points. On the other hand, the
derivative, where it exists, is given by

$\begin{split}\frac{d}{d\theta}L_{N}(\theta,\widehat{\omega}(\theta))&=\left(\frac{1}{\beta^{2}}-\frac{1}{\alpha^{2}}\right)\frac{1}{N}\sum_{i\in\mathcal{V}}(\theta-
y_{i}){\mathbf{1}}_{\\{|y_{i}-\theta|<\delta\\}}-\frac{1}{\beta^{2}}\left(\theta-\frac{1}{N}\sum_{i\in\mathcal{V}}y_{i}\right).\end{split}$
(10)

Stationary points can therefore be represented by the relation

$\theta=\frac{\frac{1}{\beta^{2}}\sum_{i}y_{i}+\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)\sum_{i}y_{i}{\mathbf{1}}_{\\{|y_{i}-\theta|<\delta\\}}}{N\frac{1}{\beta^{2}}+\sum_{i}{\mathbf{1}}_{\\{|y_{i}-\theta|<\delta\\}}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)}.$
(11)

A moment of thought shows us that (11) is equivalent to the relation
$\theta=\widehat{\theta}(\widehat{\omega}(\theta))$.

This representation will play a key role in the sequel of this paper.

Figure 1: $\alpha=0.3,\beta=10,p=0.25$: Plot of function
$L_{N}(\theta,\widehat{\omega}(\theta))$ as a function of $\theta$ and size
$N\in\\{50,100,400,500,1000,5000\\}$.

###  3.3 Iterative centralized algorithms

The computational complexity of the optimization problem (5) is practically
unfeasible in most situations. However, relations (8) suggest a simple way to
construct an iterative approximation of the ML solution (which we will denote
IML). The formal pattern is the following: fixed
$\widehat{\omega}^{(0)}=\alpha\mathbbm{1}$, for $t=0,1,\dots$, we consider the
dynamical system

$\displaystyle\widehat{\theta}^{(t+1)}=\frac{\sum_{j=1}^{N}y_{j}\left[\widehat{\omega}_{j}^{(t)}\right]^{-2}}{\sum_{j=1}^{N}\left[\widehat{\omega}_{j}^{(t)}\right]^{-2}}$
$\displaystyle\widehat{\omega}(\theta)^{(t+1)}_{i}=\begin{cases}\alpha&\text{if
}|y_{i}-{{\theta}}|<\delta\\\
\beta&\text{otherwise}\end{cases}\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \text{ for any }i=1,\dots,N.$

The algorithm stops whenever
$|\widehat{\theta}^{(t+1)}-\widehat{\theta}^{(t)}|<\varepsilon$, for some
fixed tolerance $\varepsilon>0$.

A more refined iterative solution is given by the so-called Expectation-
Maximization (EM) algorithm [19]. The main idea is to introduce a hidden (say,
unknown and unobserved) random variable in the likelihood; then, at each step,
one computes the mean of the likelihood function with respect to the hidden
variable and finds its maximum. Such a method seeks to find the maximum
likelihood solution, which in many cases cannot be formulated in a closed
form. EM is widely and successfully used in many frameworks and in principle
it could also be applied to our problem. In our context, making the variable
$\omega$ to play the part of the hidden variable, equations for EM become (see
the tutorial [20] for their derivation)

Given $\widehat{\theta}^{(0)}\in\mathbb{R}$, for $t=0,1,\dots$,

  1. 1.

E-step: for all node $i\in\mathcal{V}$,

$q_{i}^{(t)}=\mathbb{P}\left(\widehat{\omega}_{i}^{(t)}=\alpha|y,\widehat{\theta}^{(t)}\right)=\frac{(1-p)f\left(y|\widehat{\omega}_{i}^{(t)}=\alpha,\widehat{\theta}^{(t)}\right)}{(1-p)f\left(y|\widehat{\omega}_{i}^{(t)}=\alpha,\widehat{\theta}^{(t)}\right)+pf\left(y|\widehat{\omega}_{i}^{(t)}=\beta,\widehat{\theta}^{(t)}\right)}.$

  2. 2.

M-step:

$\widehat{\theta}^{(t+1)}=\frac{\sum_{j\in\mathcal{V}}y_{j}\left(q_{j}^{(t)}\alpha^{-2}+(1-q_{j}^{(t)})\beta^{-2}\right)}{\sum_{j\in\mathcal{V}}q_{j}^{(t)}\alpha^{-2}+(1-q_{j}^{(t)})\beta^{-2}}.$

The algorithm stops whenever
$|\widehat{\theta}^{(t+1)}-\widehat{\theta}^{(t)}|<\varepsilon$, for some
fixed tolerance $\varepsilon>0$. It is worth to notice that $q_{i}^{(t)}$
computed in the E-step actually is the expectation of the binary random
variable $\mathbf{1}_{\\{\widehat{\omega}_{i}^{(t)}=\alpha\\}}$. On the other
hand $\widehat{\theta}^{(t+1)}$ computed in the M-step is the maximum of such
expectation.

An important feature of EM is that it is possible to prove the convergence of
the sequence $\\{\widehat{\theta}^{(t)}\\}_{\in\mathbb{N}}$ to a local maximum
of the expected value of the log-likelihood with respect to the unknown data
$\omega$, a result which is instead not directly available for IML. Both
algorithms however share the drawback of requiring centralization. Distributed
versions of the EM have been proposed (see, e.g., [12], [14]) but convergence
is not guaranteed for them. In Section 5 we will compare both these algorithms
against the distributed IA we are going to present in the next section. While
it is true that EM always outperforms IML, algorithm IA outperforms both of
them for small size algorithms, while shows comparable performance to EM for
large networks.

##  4 Input driven consensus algorithm

###  4.1 Description of the algorithm

In this section we propose a distributed iterative algorithm approximating the
centralized ML estimator. The algorithm is suggested by the expressions in (8)
and consists of the iteration of two steps: an averaging step where all units
aim at computing $\widehat{\theta}$ through a sort of Input Driven Consensus
Algorithm (IA) followed by an update of the classification estimation
performed autonomously by all units.

Formally, IA is parametrized by a symmetric stochastic matrix $P$, adapted to
the communication graph $\mathcal{G}$ ($P_{ij}>0$ if and only if,
$(i,j)\in\mathcal{E}$), and by a real sequence $\gamma^{(t)}\rightarrow 0$.
Every node $i$ has three messages stored in its memory at time $t$, denoted
with $\mu_{i}^{(t)},\nu_{i}^{(t)}$, and $\widehat{\omega}^{(t)}_{i}$. Given
the initial conditions $\mu_{i}^{(0)}=0,\nu_{i}^{(0)}=0$ and the initial
estimate $\widehat{\omega}_{i}^{(0)}=\alpha$, the dynamics consists of the
following steps.

  1. 1.

Average step:

$\displaystyle\mu_{i}^{(t+1)}$
$\displaystyle=(1-\gamma^{(t)}){\sum_{j}P_{ij}\mu_{j}^{(t)}}+\gamma^{(t)}{{y_{i}}{\left(\widehat{\omega}_{i}^{(t)}\right)^{-2}}}$
(12a) $\displaystyle\nu_{i}^{(t+1)}$
$\displaystyle=(1-\gamma^{(t)}){\sum_{j}P_{ij}\nu_{j}^{(t)}}+\gamma^{(t)}{{\left(\widehat{\omega}_{i}^{(t)}\right)^{-2}}}$
(12b) $\displaystyle\widehat{\theta}^{(t+1)}_{i}$
$\displaystyle={\mu_{i}^{(t+1)}}/{\nu_{i}^{(t+1)}}.$ (12c)

  2. 2.

Classification step:

$\widehat{\omega}_{i}^{(t+1)}=\widehat{\omega}_{i}(\widehat{\theta}^{(t+1)})=\left\\{\begin{array}[]{cl}\alpha&\text{if
}|y_{i}-\widehat{\theta}_{i}^{(t+1)}|<\delta\\\
\beta&\text{otherwise.}\end{array}\right.$ (13)

It should be noted that the algorithm provides a distributed protocol: each
node only needs to be aware of its neighbours and no further information about
the network topology is required.

###  4.2 Convergence

The following theorem ensures the convergence of IA. The proof is rather
technical and therefore deferred to Appendix A.

######  Theorem 1.

Let

  1. (a)

$\gamma^{(t)}\rightarrow 0$, $\gamma^{(t)}\geq 1/t$, and
$\gamma^{(t)}=\gamma^{(t+1)}+o(\gamma^{(t+1)})$ for $t\to+\infty$;

  2. (b)

$P\in\mathbb{R}_{+}^{\mathcal{V}\times\mathcal{V}}$ be a stochastic,
symmetric, and primitive matrix with positive eigenvalues.

Then, there exist $\widehat{\omega}^{{IA}}\in\\{\alpha,\beta\\}^{\mathcal{V}}$
and $\widehat{\theta}^{{IA}}\in{\mathbb{R}}$ such that

  1. 1.

$\lim_{t\rightarrow+\infty}\widehat{\omega}^{(t)}\stackrel{{\scriptstyle\text{a.s.}}}{{=}}\widehat{\omega}^{IA}\,,\qquad\lim_{t\rightarrow+\infty}\widehat{\theta}^{(t)}_{i}\stackrel{{\scriptstyle\text{a.s.}}}{{=}}\widehat{\theta}^{IA}$

for all $i\in\mathcal{V}$;

  2. 2.

they satisfy the relations

$\widehat{\theta}^{IA}=\widehat{\theta}(\widehat{\omega}^{IA})\,,\
\widehat{\omega}^{IA}=\widehat{\omega}(\widehat{\theta}^{IA}).$

A number of remarks are in order.

  * •

The assumption on the eigenvalues of $P$ is essentially a technical one: in
simulations it does not seem to have a crucial role, but we need it in our
proof of convergence. On the other hand, given any symmetric stochastic
primitive $P$, we cam consider a ’lazy’ version of it $P_{\tau}=(1-\tau)I+\tau
P$ and notice that for $\tau\in(0,1)$ sufficiently small, indeed $P_{\tau}$
will satisfy the assumption on the eigenvalues.

  * •

The requirement $\gamma^{(t)}\geq 1/t$ is not new in decentralized algorithms
(see for instance the Robbins-Monro algorithm, introduced in [21]) and serves
the need of maintaining ’active’ the system input for sufficiently long time.
Less classical is the assumption $\gamma^{(t)}\sim\gamma^{(t+1)}$ which is
essentially a request of regularity in the decay of $\gamma^{(t)}$ to $0$.
Possible choices of $\gamma^{(t)}$ satisfying the above conditions are
$\gamma^{(t)}=t^{-\zeta}$ for $\zeta\in(0,1)$, or $\gamma^{(t)}=t^{-1}(\ln
t)^{\alpha}$ for any $\alpha>0$.

  * •

The proof (see Appendix A) will also give an estimation on the speed of
convergence: indeed it will be shown that
$||\widehat{\theta}^{(t)}-\widehat{\theta}^{IA}||=O(\gamma^{(t)})$ for
$t\rightarrow\infty$.

  * •

Relations in item 2. implies that $\widehat{\theta}^{IA}$ is a local maximum
of the function $L_{N}(\theta,\widehat{\omega}(\theta))$ (see (11)).

###  4.3 Limit behavior

In this section we present results on the behavior of our algorithm for
$N\to+\infty$. All quantities derived so far are indeed function of network
size $N$. In order to emphasize the role of $N$, we will add an index $N$ when
dealing with quantities like $\theta^{\star}$ (e.g.
$\widehat{\theta}^{\text{ML}}_{N}$). Instead we will not add anything to
expressions where there are vectors $\omega$ involved since their dimension is
itself $N$.

Figure 1 shows a sort of concentration of the local maxima of
$L_{N}(\theta,\widehat{\omega}(\theta))$ to a global maximum for large $N$.
Considering that IA converges to a local maximum, this observation would lead
to the conclusion that, for large $N$, the IA resembles the optimal ML
solution. This section provides some results which make rigorous these
considerations.

Notice first that, applying the uniform law of large numbers [22] to the
expression (6), we obtain that, for any compact $K\subseteq\mathbb{R}$, almost
surely

$\lim\limits_{N\to+\infty}\max_{\theta\in
K}\left|L_{N}(\theta,\widehat{\omega}(\theta))-\int_{\mathbb{R}}\mathcal{J}(s,\theta)f(s)\mathrm{d}s\right|=0$
(14)

where

$\mathcal{J}(s,\theta)=-\left(\frac{(s-\theta)^{2}}{2\beta^{2}}+{\mathbf{1}}_{\\{\omega_{j}=\alpha\\}}\left(\frac{(s-\theta)^{2}}{2}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)+\log\frac{1-p}{p}\frac{\beta}{\alpha}\right)\right)+c$
(15)

where $c$ is the same constant as in (6). The limit function
$\int_{\mathbb{R}}\mathcal{J}(s,\theta)f(s)\mathrm{d}s$ turns out to be
differentiable for every value of $\theta$ and to have a unique stationary
point for $\theta=\theta^{*}$ which turns out to be the global minimum.
Unfortunately, this fact by itself does not guarantee that global and local
minima will indeed converge to $\theta^{*}$. In our derivations the properties
of the function $\int_{\mathbb{R}}\mathcal{J}(s,\theta)f(s)\mathrm{d}s$ will
not play any direct role and therefore they will not be proven here. The main
technical result which will be proven in Appendix B is the following:

######  Theorem 2.

Denote by $\mathcal{S}_{N}$ the set of local maxima of
$L(\theta,\widehat{\omega}(\theta))$. Then,

$\lim\limits_{N\to+\infty}\max\limits_{\xi\in{\mathcal{S}}_{N}}|\xi-\theta^{*}|=0$
(16)

almost surely and in mean square sense.

This has an immediate consequence,

######  Corollary 3.

$\lim\limits_{N\to+\infty}\widehat{\theta}^{IA}_{N}=\lim\limits_{N\to+\infty}\widehat{\theta}^{\mathrm{ML}}_{N}=\theta^{\star}$
(17)

almost surely and in mean square sense.

Regarding the classification error, we have instead the following result:

######  Proposition 4.

$\begin{split}\lim_{N\rightarrow+\infty}\
\frac{1}{N}\mathbb{E}d_{H}(\widehat{\omega}^{IA},\omega^{\star})&=\lim_{N\rightarrow+\infty}\
\frac{1}{N}\mathbb{E}d_{H}(\widehat{\omega}^{{\rm ML}},\omega^{\star})\\\
&=q(p,\alpha,\beta)\\\ \end{split}$ (18)

where

$q(p,\alpha,\beta)=(1-p)\mathrm{erfc}\left(\frac{\delta}{\alpha\sqrt{2}}\right)+p\left[1-\mathrm{erfc}\left(\frac{\delta}{\beta\sqrt{2}}\right)\right]$

and
$\mathrm{erfc}(x):=\frac{2}{\sqrt{\pi}}\int_{x}^{+\infty}\mathrm{e}^{-t^{2}}\mathrm{d}t$
is the complementary error function.

These results ensure that the IA performs, in the limit of large number of
units $N$, as the centralized optimal ML estimator. Moreover, they also show,
consistency in the estimation of the parameter $\theta^{\star}$. As expected,
for $N\to+\infty$ the classification error does not go to $0$ since the
increase of measurements is exactly matched by the same increase of variables
to be estimated. Consistency however is obtained when $p$ goes to zero since
we have that $\lim_{p\rightarrow 0}q(p,\alpha,\beta)=0.$ Moreover, notice that
the dependence of function $q$ on the parameters $\alpha$ and $\beta$ is
exclusively through their ratio $\beta/\alpha$. In particular, we have

$\lim_{\beta/\alpha\rightarrow+\infty}q(p,\alpha,\beta)=0\qquad\lim_{\beta/\alpha\rightarrow
1}q(p,\alpha,\beta)=1.$

##  5 Simulations

In this section, we propose some numerical simulations. We test our algorithm
for different graph architectures and dimensions, and we compare it with the
IML and EM algorithms. Our goal is to give evidence of the theoretical
results’ validity and also to evaluate cases that are not included in our
analysis: the good numerical outcomes we obtain suggest that convergence
should hold in broader frameworks. The numerical setting for our simulations
is now presented.

Model: the sensors perform measurements according to the model (1) with
$\theta^{\star}=0$, $\alpha=0.3$, $\beta=10$; the prior probability
$\mathbb{P}(\omega^{\star}_{i}=\beta)$ is equal to $p=0.25$.

Communication architectures: given a strongly connected symmetric graph
$\mathcal{G}=({\mathcal{V}},\mathcal{E})$, we use the so-called Metropolis
random walk construction for $P$ (see [23]) which amounts to the following: if
$i\neq j$

$P_{ij}=\left\\{\begin{array}[]{ll}0&{\rm if}\,(i,j)\not\in\mathcal{E}\\\
\left(\max\\{\mathrm{deg}(i)+1,\mathrm{deg}(j)+1\\}\right)^{-1}&{\rm
if}\,(i,j)\in\mathcal{E}\end{array}\right.$

where $\mathrm{deg}(i)$ denotes the degree (the number of neighbors) of unit
$i$ in the graph $\mathcal{G}$. $P$ constructed in this way is automatically
irreducible and aperiodic.

We consider the following topologies:

  1. 1.

Complete graph: $P_{ij}=\frac{1}{N}$ for every $i,j=1,\dots,N$; it actually
corresponds to the centralized case.

  2. 2.

Ring: $N$ agents are disposed on a circle, and each agent communicates with
its first neighbor on each side (left and right). The corresponding circulant
symmetric matrix $P$ is given by $P_{ij}=\frac{1}{3}$ for every
$i=2,\dots,N-1$ and $j\in\\{i-1,i,i+1\\}$; $P_{11}=P_{12}=P_{1N}=\frac{1}{3}$;
$P_{N1}=P_{NN-1}=P_{NN}=\frac{1}{3}$; $P_{ij}=0$ elesewhere.

  3. 3.

Torus-grid graph: sensors are deployed on a two dimensional grid and are each
connected with their four neighbors; the last node of each row of the grid is
connected with the first node of the same row, and analogously on columns, so
that a torus is obtained. The so-obtained graph is regular.

  4. 4.

Random Geometric Graph with radius $r=0.3$: sensors are deployed in the square
$[0,1]\times[0,1]$, their positions being randomly generated with a uniform
distribution; links are switched on between two sensors whenever the distance
is less than $r$. We only envisage connected realizations.

From Theorem 1, $P$ is required to possess positive eigenvalues: our intuition
is that these hypotheses, that are useful to prove the convergence of the IA,
are not really necessary. We test this conjecture on the ring graph, whose
eigenvalues are known [24] to be
$\lambda_{m}=\frac{1}{3}\left(1+2\cos\left(\frac{2\pi
m}{N}\right)\right),\quad m=0,\ldots,N-1$ and which are not necessarily
positive.

Algorithms: We implement and compare the following algorithms: IA with
$\gamma^{(t)}=1/t^{\zeta}$ for different choices of
$\zeta\in\\{0.5,0.7,0.9\\}$, and the two centralized iterative algorithms IML,
and EM described in Section 3.3.

(a) Complete graph.

(b) Ring.

(c) Grid.

(d) Random geometric graph.

Figure 2: Relative classification error

Outcomes: we show the performance of the aforementioned algorithms in terms of
classification error and of mean square error on the global parameter, in
function of the number of sensors $N$. All the outcomes are obtained averaging
over $400$ Monte Carlo runs.

We observe that the classification error (Figure 2) converges for $N\to\infty$
for all the considered algorithms. On the other hand, when $N$ is small, IA
performs better than IML and EM, no matter which graph topology has been
chosen: this suggests that decentralization is then not a drawback for IA.
Moreover, for smaller $\gamma^{(t)}$ (i.e., slowing down the procedure), we
obtain better IA performance in terms of classification. Nevertheless, this is
not universally true: in other simulations, in fact, we have noticed that if
$\gamma^{(t)}$ is too small, the performance are worse. This is not
surprising, since $\gamma^{(t)}$ determines the weights assigned to the
consensus and input driven parts, whose contributions must be somehow balanced
in order to obtain the best solution. An important point that we will study in
future is the optimization of $\gamma^{(t)}$, whose choice may in turn depend
on the graph topology and on the weights assigned in the matrix $P$.

Analogous considerations can be done for the mean square error on $\theta$:
when $N$ increases, the mean square error decays to zero.

We remark that convergence is numerically shown also for the ring topology,
which is not envisaged by our theoretical analysis. Hence, our guess is that
convergence should be proved even under weaker hypotheses on matrix $P$.

For the interested reader, a graphical user interface of our algorithm is
available and downloadable on
http://calvino.polito.it/$\sim$fosson/software.html.

##  6 Concluding remarks

In this paper, we have presented a fully distributed algorithm for the
simultaneous estimation and classification in a sensor network, given from
noisy measurements. The algorithm only requires the local cooperation among
units in the network. Numerical simulations show remarkable performance. The
main contribution includes the convergence of the algorithm to a local maximum
of the centralized ML estimator. The performance of the algorithm has been
also studied when the network size is large, proving that the solution of the
proposed algorithm concentrates around the classical ML solution.

Different variants are possible, for example the generalization to multiple
classes with unknown prior probabilities should be inferred. The choice of
sequence $\\{\gamma^{(t)}\\}_{t\in\mathbb{N}}$ is critical, since it
influences both convergence time and final accuracy; the determination of a
protocol for the adaptive search of sequence
$\\{\gamma^{(t)}\\}_{t\in\mathbb{N}}$ is left for a future work.

##  7 Acknowledgment

The authors wish to thank Sandro Zampieri for bringing the problem to our
attention and Luca Schenato for useful discussions. F. Fagnani and C. Ravazzi
further acknowledge the financial support provided by MIUR under the PRIN
project no. 20087W5P2K.

## References

  * [1] M. Huang and J. H. Manton, “Coordination and consensus of networked agents with noisy measurements: Stochastic algorithms and asymptotic behavior,” SIAM J. Control and Optimization, vol. 48, no. 1, pp. 134 – 161, 2009.
  * [2] R. Olfati-Saber, “Distributed kalman filter with embedded consensus filters,” in Proceedings of 44th IEEE Conference on Decision and Control, pp. 8179 – 8184, 2005.
  * [3] R. Olfati-Saber, “Kalman-consensus filter : Optimality, stability, and performance,” in Proceedings of 48th IEEE Conference on Decision and Control, pp. 7036 – 7042, 2009.
  * [4] C. Moallemi and B. V. Roy, “Consensus propagation,” IEEE Transactions on Information Theory, vol. 52, no. 11, pp. 4753 – 4766, 2006.
  * [5] V. Saligrama, M. Alanyali, and O. Savas, “Distributed detection in sensor networks with packet losses and finite capacity links,” IEEE Transactions on Signal Processing, vol. 54, no. 11, pp. 4118 – 4132, 2006.
  * [6] R. Duda, P. Hart, and D. Stork, Pattern Classification.  Wiley, 2001.
  * [7] A. Chiuso, F. Fagnani, L. Schenato, and S. Zampieri, “Gossip algorithms for simultaneous distributed estimation and classification in sensor networks,” IEEE Journal of Selected Topics in Signal Processing, pp. 691 – 706, 2011\.
  * [8] A. Dogandzic and B. Zhang, “Distributed estimation and detection for sensor networks using hidden markov random field models,” IEEE Transactions on Signal Processing, vol. 54, no. 8, pp. 3200 – 3215, 2006.
  * [9] N. Ramakrishnan, E. Ertin, and R. Moses, “Gossip-based algorithm for joint signature estimation and node calibration in sensor networks,” Selected Topics in Signal Processing, IEEE Journal of, vol. 5, no. 4, pp. 665 –673, 2011\.
  * [10] D. M. Titterington, A. F. M. Smith, and U. E. Makov, Statistical Analysis of Finite Mixture Distributions.  New York: John Wiley, 1985.
  * [11] R. A. Redner and H. F. Walker, “Mixture densities, maximum likelihood and the em algorithm,” SIAM Review, pp. 195–239, 1984.
  * [12] R. Nowak, “Distributed EM algorithms for density estimation and clustering in sensor networks,” IEEE Transactions on Signal Processing, vol. 51, no. 8, pp. 2245 – 2253, 2003.
  * [13] M. Rabbat and R. Nowak, “Distributed optimization in sensor networks,” in ISPN ’04: Proceedings of the 3rd international symposium on Information processing in sensor networks, 2004.
  * [14] D. Gu, “Distributed EM algorithms for gaussian mixtures in sensor networks,” IEEE Transactions on Neural Networks, vol. 19, no. 7, pp. 1154 – 1166, 2008.
  * [15] A. Das and M. Mesbahi, “Distributed linear parameter estimation over wireless sensor networks,” IEEE Transactions on Aerospace and Electronic Systems, vol. 45, no. 4, pp. 1293 – 1306, 2009.
  * [16] F. Fagnani, S. M. Fosson, and C. Ravazzi, “Input driven consensus algorithm for distributed estimation and classification in sensor networks,” in Proceedings of 50th IEEE Conference on Decision and Control, no. 20087, pp. 6654 – 6659, 2011.
  * [17] A. Yeredor, “The joint MAP-ML criterion and its relation to ML and to extended least-squares,” IEEE Transactions on Signal Processing, vol. 48, no. 12, pp. 3484 – 3492, 2000.
  * [18] H. V. Trees and K. Bell, eds., Bayesian Bounds for parameter estimation and nonlinear filtering/tracking.  Wiley & Sons, 2007.
  * [19] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum likelihood from incomplete data via the EM algorithm,” J. Roy. Statist. Soc. Ser. B, vol. 39, no. 1, pp. 1 – 38, 1977.
  * [20] J. Bilmes, “A gentle tutorial of the EM algorithm and its application to parameter estimation for Gaussian mixture and hidden Markov models,” Tech. Rep. TR-97-021, ICSI, 1997.
  * [21] H. Robbins and S. Monro, “A stochastic approximation method,” Annals of Mathematical Statistics, vol. 22, no. 3, pp. 400 – 407, 1951.
  * [22] D. Andrews, “Generic uniform convergence,” Econometric Theory, pp. 241 – 257, 1992.
  * [23] L. Xiao, S. Boyd, and S. Lall, “Distributed average consensus with time-varying metropolis weights,” available on www.stanford.edu/$\sim$boyd/papers/avg$\\_$metropolis.html, 2006.
  * [24] P. J. Davis, Circulant matrices.  A Wiley-Interscience Publication, Pure and Applied MathematicsJohn Wiley & Sons, New York-Chichester-Brisbane, 1979.
  * [25] F. R. Gantmacher, The theory of matrices.  New York: Chelsea publ., 1959.
  * [26] V. Borkar, Probability Theory.  New York: Springer-Verlag, 1995.

##  Appendix A Proof of Theorem 1

Consider the discrete-time dynamical system defined by the update equations
(12) and (13): the proof of its convergence is obtained through intermediate
steps.

  1. 1.

First, we show that, for sufficiently large $t$, vectors
$\mu^{(t)},\nu^{(t)}$, and $\widehat{\theta}^{(t)}$ are close to consensus
vectors and we prove their convergence, assuming $\widehat{\omega}^{(t)}$ has
already stabilized.

  2. 2.

Second, we prove the stabilization of $\widehat{\omega}^{(t)}$ in finite time,
by modelling the system in (12) and (13) as a switching dynamical system.

  3. 3.

Finally, combining these facts together we conclude the proof.

###  A.1 Towards consensus

We start with some notation: let
$\Omega:=I-N^{-1}\mathbbm{1}\mathbbm{1}^{\mathsf{T}}$; given
$x\in\mathbb{R}^{\mathcal{V}}$, let
$\overline{x}:=N^{-1}\mathbbm{1}^{\mathsf{T}}x$ so that
$x=\overline{x}\mathbbm{1}+\Omega x$.

Given a bounded sequence $u^{(t)}\in\mathbb{R}^{N}$, consider the dynamics

$\begin{split}x^{(t+1)}=\left(1-\gamma^{(t)}\right)Px^{(t)}+\gamma^{(t)}u^{(t)}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ t\in\mathbb{N}\end{split}$ (19)

where $x^{(0)}$ is any fixed vector, and where, we recall the standing
assumptions,

  1. (a)

$\gamma^{(t)}\in(0,1)$, $\gamma^{(t)}\geq 1/t$, $\gamma^{(t)}\searrow 0$ and
$\gamma^{(t)}=\gamma^{(t+1)}+o(\gamma^{(t+1)})$ for $t\to+\infty$;

  2. (b)

$P\in\mathbb{R}_{+}^{\mathcal{V}\times\mathcal{V}}$ is a stochastic,
symmetric, primitive matrix with positive eigenvalues.

A useful fact consequence of the assumptions on $\gamma^{(t)}$, is the
following:

$\prod\limits_{s=t_{0}}^{t-1}(1-\gamma^{(s)})\leq
e^{-\sum\limits_{s=t_{0}}^{t-1}1/s}\leq\frac{t_{0}}{t}\leq t_{0}\gamma^{(t)}$
(20)

for any choice of $t\geq t_{0}>0$.

On the other hand, as a consequence of the assumptions of $P$ (see [25]) we
have that $P^{t}\to N^{-1}\mathbbm{1}\mathbbm{1}^{T}$, or equivalently that
$P^{t}\Omega\to 0$ for $t\to+\infty$. More precisely, we can order the
eigenvalues of $P$ as $1=\mu_{1}>\mu_{2}\geq\cdots\geq\mu_{N}\geq 0$, and we
have that $||P^{t}\Omega||\leq\mu_{2}^{t}$.

######  Lemma 5.

It holds

$\Omega x^{(t)}=O(\gamma^{(t)})\,,\quad{\rm for}\;t\to+\infty.$

###### Proof.

From (19) and the fact that $\Omega P=P\Omega$ we get, for any fixed $t_{0}$
and $t\geq t_{0}$,

$\Omega x^{(t+1)}=\prod_{s=t_{0}}^{t}\left(1-\gamma^{(s)}\right)P^{t}\Omega
x^{(t_{0})}+\sum_{s=t_{0}}^{t}\prod_{k=s+1}^{t}\left(1-\gamma^{(k)}\right)\gamma^{(s)}P^{t-s}\Omega
u^{(s)}.$ (21)

This yields

$\displaystyle||\Omega x^{(t+1)}||_{2}$
$\displaystyle\leq\prod_{s=t_{0}}^{t}\left(1-\gamma^{(s)}\right)||\Omega
x^{(t_{0})}||_{2}+\sum_{s=t_{0}}^{t}\prod_{k=s+1}^{t}\left(1-\gamma^{(k)}\right)\gamma^{(s)}|\mu_{2}|^{t-s}||u^{(s)}||_{2}$
$\displaystyle\leq\prod_{s=t_{0}}^{t}\left(1-\gamma^{(s)}\right)||\Omega
x^{(t_{0})}||_{2}+K\sum_{s=t_{0}}^{t}\prod_{k=s+1}^{t}\left(1-\gamma^{(k)}\right)\gamma^{(s)}|\mu_{2}|^{t-s}$
(22)

with $K:=\max_{s}||u^{(s)}||_{2}$.

Fix now $0<\varepsilon<1-|\mu_{2}|$ and let $t_{0}\in\mathbb{N}$ be such that
$\frac{\gamma^{(t+1)}}{\gamma^{(t)}}\in(1-\varepsilon,1)$ for all $t\geq
t_{0}$. Hence, for $t\geq s\geq t_{0}$, we have that
$\gamma^{(s)}<\frac{\gamma^{(t)}}{(1-\varepsilon)^{t-s}}$. Consider now the
estimation (A.1) with this choice of $t_{0}$. We get

$\displaystyle||\Omega x^{(t+1)}||_{2}$
$\displaystyle\leq\prod_{s=t_{0}}^{t}\left(1-\gamma^{(s)}\right)||\Omega
x^{(t_{0})}||_{2}+K\gamma^{(t)}\sum_{s=t_{0}}^{t}\left(\frac{|\mu_{2}|}{1-\varepsilon}\right)^{t-s}$
$\displaystyle\leq\prod_{s=t_{0}}^{t}\left(1-\gamma^{(s)}\right)||\Omega
x^{(t_{0})}||_{2}+\frac{K\gamma^{(t)}}{1-\frac{|\mu_{2}|}{1-\varepsilon}}.$

Using now (20) the proof is completed. ∎

######  Proposition 6.

If $\exists\ t_{0}\in\mathbb{N}$ s.t. $u^{(t)}=u$ $\forall t\geq t_{0}$ then

$\lim_{t\rightarrow+\infty}x^{(t)}=\overline{u}\mathbbm{1}.$

###### Proof.

Write $x^{(t)}=\overline{x}^{(t)}\mathbbm{1}+\Omega x^{(t)}$ and notice that
from Lemma 5 it is sufficient to prove that
$\lim_{t\rightarrow+\infty}\overline{x}^{(t)}\mathbbm{1}=\overline{u}\mathbbm{1}.$
From (19) and the fact that ${\mathbbm{1}}^{T}P={\mathbbm{1}}^{T}$, we obtain

$\overline{x}^{(t)}-\overline{u}=\prod_{s=t_{0}}^{t-1}(1-\gamma^{(s)})(\overline{x}^{(s)}-\overline{u})$

which goes to zero from the non-summability of $\gamma^{(t)}$. ∎

We now apply these results to the analysis of $\widehat{\theta}^{(t)}$. We
start with a representation result.

######  Lemma 7.

It holds, for $t\to+\infty$,

$\widehat{\theta}^{(t)}=\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}\mathbbm{1}+\frac{1}{\bar{\nu}^{(t)}}\Omega\left(\mu^{(t)}-\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}\nu^{(t)}\right)+o\left(\gamma^{(t)}\right).$
(23)

###### Proof.

For any $i\in\mathcal{V}$,

$\displaystyle\frac{\mu_{i}^{(t)}}{\nu_{i}^{(t)}}-\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}$
$\displaystyle=\frac{\mu_{i}^{(t)}}{\nu_{i}^{(t)}}-\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}+\frac{\mu_{i}^{(t)}}{\bar{\nu}^{(t)}}-\frac{\mu_{i}^{(t)}}{\bar{\nu}^{(t)}}$
$\displaystyle=\frac{\mu_{i}^{(t)}-\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}+\mu_{i}^{(t)}\left(\frac{1}{\nu_{i}^{(t)}}-\frac{1}{\bar{\nu}^{(t)}}\right)$
$\displaystyle=\frac{1}{\bar{\nu}^{(t)}}\left(\Omega\mu^{(t)}\right)_{i}-\frac{\mu_{i}^{(t)}}{\nu_{i}^{(t)}\bar{\nu}^{(t)}}\left(\Omega\nu^{(t)}\right)_{i}.$

It follows from Lemma 5 that
$\mu^{(t)}=\bar{\mu}^{(t)}\mathbbm{1}+O(\gamma^{(t)})$ and
$\nu^{(t)}=\bar{\nu}^{(t)}\mathbbm{1}+O(\gamma^{(t)})$ for $t\to+\infty$. This
and the fact that $\bar{\nu}^{(t)}$ is bounded away from $0$ (indeed
$\bar{\nu}^{(t)}\geq\alpha^{-2}$ for all $t>0$), yields

$\displaystyle\frac{\mu_{i}^{(t)}}{\nu_{i}^{(t)}\bar{\nu}^{(t)}}\left(\Omega\nu^{(t)}\right)_{i}$
$\displaystyle=\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}\left[\frac{\left(\Omega\nu^{(t)}\right)_{i}}{\bar{\nu}^{(t)}}\right]\left(1+O\left(\gamma^{(t)}\right)\right)$

from which thesis follows. ∎

We can now present our first convergence result.

######  Corollary 8.

It holds, for $t\to+\infty$,

$\bar{\widehat{\theta}}^{(t)}=\frac{\bar{\mu}^{(t)}}{\bar{\nu}^{(t)}}+o(\gamma^{(t)})\,,\quad\Omega\widehat{\theta}^{(t)}=O(\gamma^{(t)}).$

###### Proof.

Both relations are obtained from (23). The first one is immediate. The second
one follows from Lemma 5 and the fact that $\bar{\nu}^{(t)}$ stays bounded
away from $0$. ∎

Corollary 8 says that the estimate $\widehat{\theta}^{(t)}$ is close to a
consensus for sufficiently large $t$. Something more precise can be stated if
we know that if $\widehat{\omega}^{(t)}$ stabilizes at finite time as
explained in the next result.

######  Corollary 9.

If $\exists\ t_{0}\in\mathbb{N}$ s.t.
$\widehat{\omega}^{(t)}=\widehat{\omega}^{IA}$ $\forall t\geq t_{0}$ then

$\lim_{t\rightarrow+\infty}\widehat{\theta}^{(t)}=\widehat{\theta}(\widehat{\omega}^{IA})=\frac{\sum_{i\in\mathcal{V}}{y_{i}}{\left[\widehat{\omega}^{IA}_{i}\right]^{-2}}}{\sum_{i\in\mathcal{V}}{\left[\widehat{\omega}^{IA}_{i}\right]^{-2}}}\mathbbm{1}.$

###### Proof.

Proposition 6 guarantees that $\mu^{(t)}$ and $\nu^{(t)}$ converge to
$\frac{1}{N}\sum_{i\in\mathcal{V}}y_{i}[\widehat{\omega}^{IA}_{i}]^{-2}\mathbbm{1}$
and
$\frac{1}{N}\sum_{i\in\mathcal{V}}[\widehat{\omega}^{IA}_{i}]^{-2}\mathbbm{1}$,
respectively. This yields the thesis. ∎

###  A.2 Stabilization of $\widehat{\omega}^{(t)}$

We are going to prove that vector $\widehat{\omega}^{(t)}$ almost surely
stabilizes in finite time: this, by virtue of previous considerations will
complete our proof. To prove this fact will take lots of effort and will be
achieved through several intermediate steps.

We start observing that, since $\widehat{\omega}^{(t)}$ can only assume values
in a finite set, equations in (12) and (13) can be conveniently modeled by a
switching system as shown below.

For reasons which will be clear below, in this subsection we will replace the
configuration space $\\{\alpha,\beta\\}^{\mathcal{V}}$ with the augmented
state space $\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}$. If
$\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}$, define

$\displaystyle\Theta_{\omega}=\\{x\in\mathbb{R}^{\mathcal{V}}:$
$\displaystyle|x_{i}-y_{i}|<\delta,\text{if }\omega_{i}=\alpha,x_{i}\geq
y_{i}+\delta,\text{if }\omega_{i}=\beta+,x_{i}\leq y_{i}-\delta,\text{if
}\omega_{i}=\beta-\\}.$

We clearly have
$\mathbb{R}^{\mathcal{V}}=\bigcup_{\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}}\Theta_{\omega}$.

On each $\Theta_{\omega}$ the dynamical system is linear. Indeed, define the
maps
$f_{\omega}:\mathbb{R}\times\mathbb{R}^{\mathcal{V}}\rightarrow\mathbb{R}^{\mathcal{V}}$
and
$g_{\omega}:\mathbb{R}\times\mathbb{R}^{\mathcal{V}}\rightarrow\mathbb{R}^{\mathcal{V}}$
by

$\displaystyle[f_{\omega}(t,x)]_{i}$
$\displaystyle=(1-\gamma^{(t)})[Px^{(t)}]_{i}+\gamma^{(t)}\frac{y_{i}}{\omega_{i}^{2}}$
$\displaystyle[g_{\omega}(t,x)]_{i}$
$\displaystyle=(1-\gamma^{(t)})[Px^{(t)}]_{i}+\gamma^{(t)}\frac{1}{\omega_{i}^{2}}$

where, conventionally, $\omega_{i}^{2}=\beta^{2}$ if
$\omega_{i}=\beta+,\beta-$. Then, if
$\widehat{\theta}^{(t)}\in\Theta_{\omega}$, (12a), (12b), and (12c) can be
written as

$\mu^{(t+1)}=f_{{{\omega}}}(t,\mu^{(t)})\qquad\nu^{(t+1)}=g_{{{\omega}}}(t,\nu^{(t)})$
$\widehat{\theta}^{(t+1)}_{i}={\mu_{i}^{(t+1)}}/{\nu_{i}^{(t+1)}}.$

Notice that this is a closed-loop switching system, since the switching policy
is determined by $\widehat{\theta}^{(t)}$. It is clear that the stabilization
of $\widehat{\omega}^{(t)}$ is equivalent to the fact that there exist an
${\omega}\in\\{\alpha,\beta+,\beta-\\}^{N}$ and a time $\widetilde{t}$ such
that $\widehat{\theta}^{(t)}\in\Theta_{{\omega}}$ for all
$t\geq\widetilde{t}$.

From Corollary 9 candidate limit points for $\widehat{\theta}^{(t)}$ are

${\widehat{\theta}}(\omega)\mathbbm{1}=\frac{\sum_{i\in\mathcal{V}}y_{i}\omega_{i}^{-2}}{\sum_{i\in\mathcal{V}}\omega_{i}^{-2}}\mathbbm{1}\qquad\omega\in\\{\alpha,\beta+,\beta-\\}^{N}.$

Also, from Proposition 8, the dynamics can be conveniently analysed by
studying it in a neighborhood of the line
$\Lambda=\\{\lambda\mathbbm{1}|\lambda\in\mathbb{R}\\}$.

We now make an assumption which holds almost everywhere with respect to the
choice of $y_{i}$’s and, consequently, does not entail any loss of generality
in our proof.

ASSUMPTION:

  * •

$y_{i}-y_{j}\not\in\\{0,\pm\delta,\pm 2\delta\\}$ for all $i\neq j$;

  * •

${\widehat{\theta}}(\omega)-y_{i}\not\in\\{\pm\delta\\}$ for all
$\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}$ and for all $i$.

This assumption has a number of consequences which will be used later on:

  1. (C1)

${\widehat{\theta}}(\omega){\mathbbm{1}},y_{i}{\mathbbm{1}}\in\bigcup_{\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}}{\rm
int}(\Theta_{\omega})$ for all
$\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}$ and for all
$i\in\mathcal{V}$;

  2. (C2)

$\Lambda\cap\bar{\Theta}_{\omega}\cap\bar{\Theta}_{\omega^{\prime}}\cap\bar{\Theta}_{\omega^{\prime\prime}}=\emptyset$
for any triple of distinguished
$\omega,\omega^{\prime},\omega^{\prime\prime}$. In other terms, $\Lambda$
always crosses boundaries among regions $\Theta_{\omega}$ at internal point of
faces.

We now introduce some further notation, which will be useful in the rest of
the paper.

$\displaystyle\Theta^{\epsilon}:=\\{x\in\mathbb{R}^{\mathcal{V}}:||\Omega
x||_{2}<\epsilon\\},\quad\Theta^{\epsilon}_{\omega}:=\Theta^{\epsilon}\cap\Theta_{\omega}$
$\displaystyle\Gamma:=\\{\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}:\
\Theta_{\omega}\cap\Lambda\neq\emptyset\\}.$

For any $\omega\in\Gamma$ consider

$\Pi_{\omega}=\\{\pi=\bar{\Theta}_{\omega}\cap\bar{\Theta}_{\omega^{\prime}}:\
\mathrm{d_{H}}(\omega,\omega^{\prime})=1,\ \pi\cap\Lambda=\emptyset\\}$

and define
$\sigma_{\omega}:=\min_{\pi\in\Pi_{\omega}}\mathrm{d}(\Theta_{\omega}\cap\Lambda,\pi)>0$111
$\mathrm{d}(\Theta_{\omega}\cap\Lambda,\pi)$ denotes the distance between the
two sets $\Theta_{\omega}\cap\Lambda$ and the set $\pi$.

In the sequel, we will use the natural ordering on $\Lambda$: given the sets
$X,Y\subseteq\Lambda$, $X<Y$ means that $x<y$ for all $x\in X$ and $y\in Y$.

######  Definition 10.

Given two elements $\omega,\ \omega^{\prime}\in\Gamma$, we say that
$\omega^{\prime}$ is the future-follower of $\omega$ (or also that $\omega$ is
the past-follower of $\omega^{\prime}$) if the following happens:

  1. (A)

There exists $i_{0}$ such that $\omega_{i}=\omega^{\prime}_{i}\text{ for all
}\,i\neq i_{0}\text{ and }\omega_{i_{0}}\neq\omega^{\prime}_{i_{0}}$;

  2. (B)

$\Theta_{\omega}\cap\Lambda<\Theta_{\omega^{\prime}}\cap\Lambda$.

Notice that, in order for $\omega$ and $\omega^{\prime}$ to satisfy definition
above, it must necessarily happen that either $\omega_{i_{0}}=\alpha$ and
$\omega^{\prime}_{i_{0}}=\beta+$, or $\omega_{i_{0}}=\beta-$ and
$\omega^{\prime}_{i_{0}}=\alpha$. Given $\omega\in\Gamma$, its future-follower
(if it exists) will be denoted by $\omega^{+}$. It is clear that (because of
property (C2) described above) that we can order elements in $\Gamma$ as
$\omega^{1},\omega^{2},\dots,\omega^{M}$ in such a way that
$\omega^{r+1}=(\omega^{r})^{+}$ for every $r=1,\dots,M-1$.

Given $\omega\in\Gamma$, consider the following subsets of $\mathbb{R}^{N}$
(see Fig. 3):

$\displaystyle\mathcal{M}_{\omega}^{\epsilon}$
$\displaystyle:=\left\\{x\in\Theta_{\omega}^{\epsilon}:\overline{x}\mathbbm{1}+\Omega
z\in\Theta_{\omega}^{\epsilon},\leavevmode\nobreak\ \forall
z:||z||_{2}<\epsilon\right\\}$
$\displaystyle\mathcal{L}_{\omega,\omega^{+}}^{\epsilon}$
$\displaystyle:=\left\\{x\in\Theta^{\epsilon}:\mathcal{M}_{\omega}^{\epsilon}\cap\Lambda<\bar{x}<\mathcal{M}_{\omega^{+}}^{\epsilon}\cap\Lambda\right\\}.$

(with the implicit assumption that
$\mathcal{L}_{\omega,\omega^{+}}^{\epsilon}=\emptyset$ if $\omega^{+}$ does
not exist.) We clearly have
$\Theta^{\epsilon}=\bigcup_{\omega\in\Gamma}\mathcal{M}_{\omega}^{\epsilon}\cup\mathcal{L}_{\omega,\omega^{+}}^{\epsilon}$.

Figure 3: Given the couple $(\omega,\omega^{\prime})$ the sets
$\mathcal{L}_{\omega,\omega^{\prime}}^{\epsilon}$ and
$\mathcal{M}_{\omega}^{\epsilon}$ are visualized.

Notice that, because of property (C1), we can always choose
$\epsilon_{0}\in(0,\min_{\omega\in\Gamma}\sigma_{\omega})$ such that

$\displaystyle{\widehat{\theta}}(\omega)\mathbbm{1},y_{i}\mathbbm{1}\in\bigcup_{\omega^{\prime}\in\Gamma}\mathcal{M}_{\omega^{\prime}}^{\epsilon_{0}}\qquad\forall\omega\in\Gamma,\forall
i\in\mathcal{V}.$

This implies that there exists $\tilde{c}>0$ such that

$\mathrm{d}\left(\bigcup_{\omega^{\prime}\in\Gamma}\partial_{\Lambda}\left(\mathcal{M}_{\omega^{\prime}}^{\epsilon}\cap\Lambda\right),\\{{\widehat{\theta}}(\omega),y_{i}\\}\right)\geq\tilde{c},\quad\forall\epsilon\leq\epsilon_{0}$
(24)

where $\partial_{\Lambda}(\cdot)$ denotes the boundary of a set in the
relative topology of $\Lambda$.

Fix now $\epsilon\leq\epsilon_{0}$ and choose $t_{\epsilon}$ such that
$\widehat{\theta}^{(t)}\in\Theta^{\epsilon}$ for all $t\geq t_{\epsilon}$ (it
exists by Corollary 8). From now on we consider times $t\geq t_{\epsilon}.$
Our aim is to prove through intermediate steps the following facts

  * F1)

if ${\widehat{\theta}}(\omega)\in\mathcal{M}^{\epsilon}_{\omega}$ then
$\mathcal{M}^{\epsilon}_{\omega}$ is an _asymptotically invariant_ set for
$\widehat{\theta}^{(t)}$, namely, when $t$ is sufficiently large, if
$\widehat{\theta}^{(t)}\in\mathcal{M}^{\epsilon}_{\omega}$ then
$\widehat{\theta}^{(t+1)}\in\mathcal{M}^{\epsilon}_{\omega}$;

  * F2)

if ${\widehat{\theta}}(\omega)\notin\mathcal{M}^{\epsilon}_{\omega}$ then
$\widehat{\theta}^{(t)}\notin\mathcal{M}^{\epsilon}_{\omega}$ for $t$
sufficiently large;

  * F3)

$\widehat{\theta}^{(t)}\notin\bigcup_{\omega\in\\{\alpha,\beta+,\beta-\\}^{\mathcal{V}}}\mathcal{L}^{\epsilon}_{\omega,\omega^{+}}$
for $t$ sufficiently large.

#### F1) Asymptotic invariance of $\mathcal{M}_{\omega}^{\epsilon}$ when
${\widehat{\theta}}(\omega)\mathbbm{1}\in\mathcal{M}^{\epsilon}_{\omega}$

######  Lemma 11.

If $\widehat{\theta}^{(t)}\in\Theta_{\omega}$ then there exists
$c^{(t)}\in[\alpha^{2}/\beta^{2},\beta^{2}/\alpha^{2}]$ and
$r^{(t)}=o(\gamma^{(t)})$ for $t\to+\infty$ such that

$\overline{\widehat{\theta}}^{(t+1)}=\overline{\widehat{\theta}}^{(t)}+c^{(t)}\gamma^{(t)}\left({\widehat{\theta}}(\omega)-\overline{\widehat{\theta}}^{(t)}\right)+r^{(t)}$
(25)

###### Proof.

If $\widehat{\theta}^{(t)}\in\Theta_{\omega}$ then

$\displaystyle\frac{\overline{\mu}^{(t+1)}}{\overline{\nu}^{(t+1)}}-\frac{\overline{\mu}^{(t)}}{\overline{\nu}^{(t)}}$
$\displaystyle=\frac{(1-\gamma^{(t)})\overline{\mu}^{(t)}+\gamma^{(t)}N^{-1}\sum_{i=1}^{N}y_{i}\omega_{i}^{-2}}{(1-\gamma^{(t)})\overline{\mu}^{(t)}+\gamma^{(t)}N^{-1}\sum_{i=1}^{N}\omega_{i}^{-2}}-\frac{\overline{\mu}^{(t)}}{\overline{\nu}^{(t)}}$
$\displaystyle=\frac{\overline{\nu}^{(t)}\gamma^{(t)}N^{-1}\sum_{i=1}^{N}y_{i}\omega_{i}^{-2}-\overline{\mu}^{(t)}\gamma^{(t)}N^{-1}\sum_{i=1}^{N}\omega_{i}^{-2}}{\overline{\nu}^{(t+1)}\overline{\nu}^{(t)}}$
$\displaystyle=\gamma^{(t)}\frac{N^{-1}\sum_{i=1}^{N}\omega_{i}^{-2}}{\overline{\nu}^{(t+1)}}{\left({\widehat{\theta}}(\omega)-\frac{\overline{\mu}^{(t)}}{\overline{\nu}^{(t)}}\right)}$

Choosing
$c^{(t)}=\frac{N^{-1}\sum_{i=1}^{N}\omega_{i}^{-2}}{\overline{\nu}^{(t+1)}}\in[\alpha^{2}/\beta^{2},\beta^{2}/\alpha^{2}]$
and using Corollary 8 thesis easily follows. ∎

######  Proposition 12 (Proof of F1)).

There exists $t^{\prime}\geq t_{\epsilon}$ such that, if
${\widehat{\theta}}(\omega)\mathbbm{1}\in\Theta_{\omega}$, then

$\widehat{\theta}^{(t)}\in\mathcal{M}^{\epsilon}_{\omega}\;\Rightarrow\;\widehat{\theta}^{(t+1)}\in\mathcal{M}^{\epsilon}_{\omega}\quad\forall
t\geq t^{\prime}\,.$

###### Proof.

Consider the relation (25). If
$\widehat{\theta}^{(t)}\in\mathcal{M}^{\epsilon}_{\omega}$ and if $t$ is large
enough so that $c^{(t)}\gamma^{(t)}<1$ , we have, by convexity, that

$z:=\overline{\widehat{\theta}}^{(t)}+c^{(t)}\gamma^{(t)}\left({\widehat{\theta}}(\omega)-\overline{\widehat{\theta}}^{(t)}\right)\in\mathcal{M}^{\epsilon}_{\omega}.$

Moreover, because of (24) and the fact that $c^{(t)}$ is bounded away from
$0$, there exists $c^{\prime}>0$ such that
$\mathrm{d}(z,\partial(\mathcal{M}^{\epsilon}_{\omega}\cap\Lambda))\geq
c^{\prime}\gamma^{(t)}$. Proof is then completed by selecting $t^{\prime}\geq
t_{\epsilon}$ such that $c^{(t)}\gamma^{(t)}<1$ and
$|r(t)|<c^{\prime}\gamma^{(t)}/2$ for all $t\geq t^{\prime}$. ∎

### F2) Transitivity of $\mathcal{M}^{\epsilon}_{\omega}$ when
${\widehat{\theta}}(\omega)\mathbbm{1}\notin\mathcal{M}_{\omega}^{\epsilon}$

Our next goal is to prove that if
${\widehat{\theta}}(\omega)\mathbbm{1}\notin\mathcal{M}^{\epsilon}_{\omega}$,
then, at a certain time $t$, $\widehat{\theta}^{(t)}$ will definitively be
outside $\mathcal{M}^{\epsilon}_{\omega}$. A technical lemma based on
convexity arguments is required.

######  Lemma 13.

Let $\omega\in\Gamma$ be such that there exists its future-follower
$\omega^{+}$. Then,

$\begin{array}[]{lcl}{\widehat{\theta}}(\omega)\mathbbm{1}>\Theta_{\omega}\cap\Lambda&\Rightarrow&{\widehat{\theta}}(\omega^{+})\mathbbm{1}>\Theta_{\omega}\cap\Lambda\\\
{\widehat{\theta}}(\omega^{+})\mathbbm{1}<\Theta_{\omega^{+}}\cap\Lambda&\Rightarrow&{\widehat{\theta}}(\omega)\mathbbm{1}<\Theta_{\omega^{+}}\cap\Lambda.\end{array}$

###### Proof.

Suppose $\omega_{i}=\omega^{+}_{i},\forall i\neq i_{0}$ and
$\omega_{i_{0}}=\beta-$, $\omega^{+}_{i_{0}}=\alpha$ (the other case can be
treated in an analogous way). Pick $x^{\prime}\in\Theta_{\omega}\cap\Lambda$
and $x^{\prime\prime}\in\Theta_{\omega^{+}}\cap\Lambda$. From
$|x^{\prime\prime}-y_{i_{0}}|<\delta$, and $|x^{\prime}-y_{i_{0}}|>\delta$ it
immediately follows that $x^{\prime\prime}>y_{i_{0}}-\delta,\
x^{\prime}<y_{i_{0}}-\delta$ and, in particular, the fact

$y_{i_{0}}\mathbbm{1}>\Theta_{\omega}\cap\Lambda\,.$ (26)

Notice now that

$\displaystyle{\widehat{\theta}}(\omega^{+})$
$\displaystyle=\frac{y_{i_{0}}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}+\frac{\sum\limits_{i\in\mathcal{V}\setminus{i_{0}}}\frac{y_{i}}{{\omega^{+}_{i}}^{2}}+\frac{y_{i_{0}}}{\beta^{2}}}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}$
$\displaystyle=\frac{y_{i_{0}}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}+\frac{{\widehat{\theta}}(\omega)\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega_{i}}^{2}}}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}$
$\displaystyle=\frac{y_{i_{0}}\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}+\frac{{\widehat{\theta}}(\omega)\left[\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}-\left(\frac{1}{\alpha^{2}}-\frac{1}{\beta^{2}}\right)\right]}{\sum\limits_{i\in\mathcal{V}}\frac{1}{{\omega^{+}_{i}}^{2}}}.$

In Figures 4 and 5 a picture of the various points is depicted when
${\widehat{\theta}}(\omega)>\Theta_{\omega}\cap\Lambda$.

$\Lambda$$\Theta_{\omega}$$\Theta_{\omega^{+}}$$y_{i_{0}}\mathbbm{1}$${\widehat{\theta}}(\omega^{+})\mathbbm{1}$${\widehat{\theta}}(\omega)\mathbbm{1}$

(a) $y_{i_{0}}<y_{\omega^{+}}<y_{\omega}$.

$\Lambda$$\Theta_{\omega}$$\Theta_{\omega^{+}}$${\widehat{\theta}}(\omega)\mathbbm{1}$${\widehat{\theta}}(\omega^{+})\mathbbm{1}$$\bar{y}_{i_{0}}\mathbbm{1}$

(b) $y_{i_{0}}<{\widehat{\theta}}(\omega^{+})<{\widehat{\theta}}(\omega)$.

Figure 4:
$\omega_{i_{0}}=\beta,{\widehat{\theta}}(\omega)\mathbbm{1}>\Theta_{\omega}\cap\Lambda$
$\Lambda$$\Theta_{\omega}$$\Theta_{\omega^{+}}$${\widehat{\theta}}(\omega)\mathbbm{1}$${\widehat{\theta}}(\omega^{+})\mathbbm{1}$$\bar{y}_{i_{0}}\mathbbm{1}$
Figure 5: ${\widehat{\theta}}(\omega)\mathbbm{1}>\Theta_{\omega}\cap\Lambda$

A convexity argument and the use of (26) now allow to conclude. ∎

######  Proposition 14 (Proof of F2)).

If ${\widehat{\theta}}(\omega)\mathbbm{1}\notin\Theta_{\omega}$, then there
exists $t^{\prime\prime}$ such that
$\widehat{\theta}^{(t)}\notin\Theta_{\omega}^{\epsilon}$ $\forall
t>t^{\prime\prime}$.

###### Proof.

Suppose ${\widehat{\theta}}(\omega)\mathbbm{1}>\Theta_{\omega}\cap\Lambda$
(the case when is $<$ can be treated analogously). Lemma 13 implies that
${\widehat{\theta}}(\omega^{+})\mathbbm{1}>\Theta_{\omega}\cap\Lambda$. Let
$\tilde{c}$ be the constant given in (24) and put

$A:=\\{x\in\Theta^{\epsilon}_{\omega}\cup\Theta^{\epsilon}_{\omega^{+}}\;|\;\overline{x}\leq\alpha:=\min\\{{\widehat{\theta}}(\omega),{\widehat{\theta}}(\omega^{+})\\}-\tilde{c}/2\\}.$

Consider the relation (25) and choose $t_{1}$ in such a way that

$\bar{\widehat{\theta}}^{(t+1)}-\bar{\widehat{\theta}}^{(t)}\leq
c_{2}(\max\\{y_{i}\\}-\min\\{y_{i}\\})\gamma^{(t)}+r(t)<\tilde{c}/2$ (27)

and $|r(t)|<\alpha^{2}\tilde{c}\gamma^{(t)}/4\beta^{2}$ for all $t\geq t_{1}$.
It also follows from (25) that, if for some $t\geq t_{1}$
$\widehat{\theta}^{(t)}\in A$, then,

$\overline{\widehat{\theta}}^{(t+1)}\geq\overline{\widehat{\theta}}^{(t)}+\alpha^{2}{\tilde{c}}\
\gamma^{(t)}/{4\beta^{2}}.$ (28)

Owing to the non-summability of $\gamma^{(t)}$ it follows that if
$\widehat{\theta}^{(t)}$ enters in $\Theta^{\epsilon}_{\omega}$ for some
$t\geq t_{1}$, then, in finite time it will enter into
$A\setminus\Theta^{\epsilon}_{\omega}$ and then it will finally exit $A$. In
particular there must exist $t_{2}\geq t_{1}$ such that
$\overline{\widehat{\theta}}^{(t_{2})}>\alpha$. We now prove that
$\overline{\widehat{\theta}}^{(t_{2})}{\mathbbm{1}}>\Theta_{\omega}$ for every
$t\geq t_{2}$. If not there must exist a first time index $t_{3}>t_{2}$ such
that $\overline{\widehat{\theta}}^{(t_{3})}<\alpha-\tilde{c}$. Because of
(27), it must be that
$\overline{\widehat{\theta}}^{(t_{3}-1)}<\alpha-\tilde{c}/2$ but this
contradicts the fact that on $A$, $\overline{\widehat{\theta}}^{(t)}$ is
increasing (28). ∎

### F3) Transitivity of
$\bigcup_{\omega,\omega^{+}\in\\{\alpha,\beta+\beta-\\}^{N}}\mathcal{L}_{\omega,\omega^{+}}$

We start with the following technical result concerning the general system
(19).

######  Lemma 15.

Let $x^{(t)}$ be the sequence defined in (19) and suppose that there exists a
strictly increasing sequence of switching times
$\\{\tau_{k}\\}_{k=0}^{+\infty}$ such that

$u_{i}^{(s+1)}=u_{i}^{(s)}\quad\forall i\neq i_{0}\quad\text{and}\quad\forall
s\in[\tau_{0},+\infty[$ $u_{i_{0}}^{(s)}=\begin{cases}v^{\prime}&\forall s\in
I^{\prime}:=\bigcup_{k=0}^{+\infty}[\tau_{2k},\tau_{2k+1})\\\
v^{\prime\prime}&\forall s\in
I^{\prime\prime}:=\bigcup_{k=0}^{+\infty}[\tau_{2k+1},\tau_{2k+2}).\end{cases}$

Then, for every $\delta>0$, there exists $\bar{t}_{\delta}$ and two sequences
$a_{\delta}^{(t)}\geq 0$ and $b_{\delta}^{(t)}\leq\delta\gamma^{(t)}$, such
that

$\displaystyle\left(\Omega\left(x^{(t+1)}-x^{(t)}\right)\right)_{i_{0}}\\!\\!\\!=A_{\delta}^{(t)}\gamma^{(t)}\left(v^{\prime}-v^{\prime\prime}\right)+b_{\delta}^{(t)}$

for $t\in I^{\prime}$ with $t\geq\bar{t}_{\delta}$.

###### Proof.

Let $\phi_{j}\in\mathbb{R}^{\mathcal{V}}$ be an orthonormal basis of
eigenvectors for $P$ relative to the eigenvalues
$1=\lambda_{1}>\lambda_{2}\geq\cdots\geq\lambda_{N}\geq 0$. Also assume we
have chosen $\phi_{1}=N^{-1/2}\mathbbm{1}$.

We put

$F^{(t)}:=\frac{\prod_{k=0}^{t}\left(1-\gamma^{(k)}\right)}{\gamma^{(t)}}$

and we notice that

$\frac{F^{(s+1)}}{F^{(s)}}=(1-\gamma^{(s+1)})\frac{\gamma^{(s)}}{\gamma^{(s+1)}}\to
1\,,\;{\rm for}\;s\to+\infty.$

Fix $\epsilon$ in such a way that $\lambda_{2}(1+\epsilon)<1$ and choose
$s_{0}$ such that

$\frac{F^{(s+1)}}{F^{(s)}}\leq 1+\epsilon\,,\;\forall s\geq s_{0}.$

Let $t_{0}\geq s_{0}$ to be fixed later. From (21) we can write

$\displaystyle\Omega(x^{(t+1)}-x^{(t)})=$
$\displaystyle=\prod_{s=t_{0}}^{t-1}\left(1-\gamma^{(s)}\right)\left[\left(1-\gamma^{(t)}\right)P-I\right]P^{t-t_{0}}\Omega
x^{(t_{0})}$
$\displaystyle+\sum_{s=t_{0}}^{t}\prod_{k=s+1}^{t}\left(1-\gamma^{(k)}\right)\gamma^{(s)}P^{t-s}\Omega
u^{(s)}-\sum_{s=t_{0}}^{t-1}\prod_{k=s+1}^{t-1}\left(1-\gamma^{(k)}\right)\gamma^{(s)}P^{t-s-1}\Omega
u^{(s)}v$
$\displaystyle=\prod_{s=t_{0}}^{t-1}\left(1-\gamma^{(s)}\right)\left[\left(1-\gamma^{(t)}\right)P-I\right]P^{t-t_{0}}\Omega
x^{(t_{0})}$
$\displaystyle+\gamma^{(t)}\sum_{s=t_{0}-1}^{t-1}P^{t-s-1}\frac{F^{(t)}}{F^{(s+1)}}\Omega
u^{(s+1)}-\gamma^{(t-1)}\sum_{s=t_{0}}^{t-1}P^{t-s-1}\frac{F^{(t-1)}}{F^{(s)}}\Omega
u^{(s)}$
$\displaystyle=\prod_{s=t_{0}}^{t-1}\left(1-\gamma^{(s)}\right)\left[\left(1-\gamma^{(t)}\right)P-I\right]P^{t}\Omega
x^{(t_{0})}$ (29)
$\displaystyle+(\gamma^{(t)}-\gamma^{(t-1)})\sum_{s=t_{0}}^{t-1}P^{t-s-1}\frac{F^{(t-1)}}{F^{(s)}}\Omega
u^{(s)}+\gamma^{(t)}P^{t-t_{0}}\frac{F^{(t-1)}}{F^{(t_{0})}}\Omega
u^{(t_{0})}$ (30)
$\displaystyle+\gamma^{(t)}\sum_{s=t_{0}}^{t-1}P^{t-s-1}\left(\frac{F^{(t)}}{F^{(s+1)}}-\frac{F^{(t-1)}}{F^{(s)}}\right)\Omega
u^{(s+1)}$ (31)
$\displaystyle+\gamma^{(t)}\sum_{s=t_{0}}^{t-1}P^{t-s-1}\frac{F^{(t-1)}}{F^{(s)}}\Omega\left(u^{(s+1)}-u^{(s)}\right).$
(32)

It follows from the assumptions on $P$, the assumptions on $\gamma^{(t)}$ and
relation (20) that the terms (29) and (30) are both $o(\gamma^{(t)})$ for
$t\to+\infty$. We now estimate (31):

$\displaystyle\left|\left|\sum_{s=t_{0}}^{t-1}P^{t-s-1}\left(\frac{F^{(t)}}{F^{(s+1)}}-\frac{F^{(t-1)}}{F^{(s)}}\right)\Omega
u^{(s+1)}\right|\right|_{2}=$
$\displaystyle\left|\left|\sum_{s=t_{0}}^{t-1}\frac{F^{(t-1)}}{F^{(s)}}\left(\frac{F^{(t)}}{F^{(t-1)}}\frac{F^{(s)}}{F^{(s+1)}}-1\right)P^{t-s-1}\Omega
u^{(s+1)}\right|\right|_{2}\leq$
$\displaystyle\sum_{s=t_{0}}^{t-1}[\lambda_{2}(1+\epsilon)]^{t-s-1}\left|\left(\frac{F^{(s)}}{F^{(s+1)}}-1\right)\right|K\leq$
$\displaystyle\frac{K}{1-\lambda_{2}(1+\epsilon)}\beta_{t_{0}}$ (33)

where

$K=\max||u^{(s)}||_{2}\,,\quad\beta_{t_{0}}:=\sup\limits_{t\geq s\geq
t_{0}}\left|\left(\frac{F^{(t)}}{F^{(t-1)}}\frac{F^{(s)}}{F^{(s+1)}}-1\right)\right|.$

We now concentrate on the component $i_{0}$ of the term (32). Using the
spectral decomposition of $P$ and the assumptions on $u^{(t)}$, we can write,

$\displaystyle\left[\sum_{s=t_{0}}^{t-1}P^{t-s-1}\frac{F^{(t-1)}}{F^{(s)}}\Omega\left(u^{(s+1)}-u^{(s)}\right)\right]_{i_{0}}=$
(34) $\displaystyle\sum\limits_{j\geq
2}(\phi_{j})_{i_{0}}^{2}\sum\limits_{h:t_{0}\leq\tau_{h}\leq
t-1}\lambda_{j}^{t-\tau_{h}}\frac{F(t-1)}{F(\tau_{h}-1)}(-1)^{h}(v^{\prime}-v^{\prime\prime}).$
(35)

If $t\in I^{\prime}$, the above expression can be rewritten as

$\sum\limits_{j\geq
2}(\phi_{j})_{i_{0}}^{2}\sum\limits_{k:t_{0}\leq\tau_{2k}\leq
t-1}\left[\lambda_{j}^{t-\tau_{2k}}\frac{F(t-1)}{F(\tau_{2k}-1)}-\lambda_{j}^{t-\tau_{2k-1}}\frac{F(t-1)}{F(\tau_{2k-1}-1)}\right](v^{\prime}-v^{\prime\prime}).$

Notice that

$\lambda_{j}^{t-\tau_{2k}}\frac{F(t-1)}{F(\tau_{2k}-1)}-\lambda_{j}^{t-\tau_{2k-1}}\frac{F(t-1)}{F(\tau_{2k-1}-1)}=\lambda_{j}^{t-\tau_{2k}}\frac{F(t-1)}{F(\tau_{2k}-1)}\left(1-\lambda_{j}^{\tau_{2k}-\tau_{2k-1}}\frac{F(\tau_{2k}-1)}{F(\tau_{2k-1}-1)}\right)>0$

(we have used the fact that $0\leq\lambda_{j}(1+\epsilon)<1$ for all $j\geq
2$). To complete the proof now proceed as follows. For a fixed $\delta>0$,
choose $t_{0}\geq s_{0}$ in such a way that (33) is below $\delta/2$. Then,
fix $\bar{t}_{\delta}\geq t_{0}$ in such a way that the summation of (29) and
(30) is below $\delta\gamma^{(t)}/2$ for $t\geq\bar{t}_{\delta}$. It is now
sufficient to define

$a_{\delta}^{(t)}:=\sum\limits_{j}(\phi_{j})_{i_{0}}^{2}\sum\limits_{k:t_{0}\leq\tau_{2k}\leq
t-1}\left[\lambda_{j}^{t-\tau_{2k}-1}\frac{F(t-1)}{F(\tau_{2k}-1)}-\lambda_{j}^{t-\tau_{2k-1}}\frac{F(t-1)}{F(\tau_{2k-1}-1)}\right]$

and $b_{\delta}^{(t)}$ equal to the sum of the terms (29), (30), and (31), ∎

######  Proposition 16 (Proof of F3)).

There exists $t^{\prime\prime\prime}\in\mathbb{N}$ such that

$\widehat{\theta}^{(t)}\not\in\bigcup_{\omega,\omega^{\prime}\in\\{\alpha,\beta\\}^{N}}\mathcal{L}_{\omega,\omega^{+}}$
(36)

for all $t>t^{\prime\prime\prime}$.

###### Proof.

In view of the results in Propositions 12 and 14, and the fact that
$\widehat{\theta}^{(t+1)}-\widehat{\theta}^{(t)}$ goes to $0$ for
$t\to+\infty$, if (36) negation of (36) yields that there exists
$\omega\in\Gamma$ such that
$\widehat{\theta}^{(t)}\in\mathcal{L}_{\omega,\omega^{+}}$ for $t$ large
enough. Now, if
$\widehat{\theta}^{(t)}\in\mathcal{L}_{\omega,\omega^{+}}\cap\Theta_{\omega}$
(or if
$\widehat{\theta}^{(t)}\in\mathcal{L}_{\omega,\omega^{+}}\cap\Theta_{\omega^{+}}$)
for $t$ sufficiently large, a straightforward application of (25) would imply
that $\widehat{\theta}^{(t)}$ would necessarily exit
$\mathcal{L}_{\omega,\omega^{+}}$ in finite time. Therefore, it must hold that
$\widehat{\theta}^{(t)}$ keeps switching, for large $t$, between
$\mathcal{L}_{\omega,\omega^{+}}\cap\Theta_{\omega}$ and
$\mathcal{L}_{\omega,\omega^{+}}\cap\Theta_{\omega^{+}}$.

From Lemma 7 and Corollary 8 we can write

$\displaystyle\widehat{\theta}^{(t+1)}-\widehat{\theta}^{(t)}=$
$\displaystyle\left(\frac{{\bar{\widehat{\theta}}}^{(t+1)}}{{\bar{\nu}}^{(t+1)}}-\frac{{\bar{\widehat{\theta}}}^{(t)}}{{\bar{\nu}}^{(t)}}\right){\mathbbm{1}}+\frac{1}{{\bar{\nu}}^{(t)}}\left[\Omega\left(\mu^{(t+1)}-\mu^{(t)}\right)-\frac{{\bar{\mu}}^{(t)}}{{\bar{\nu}}^{(t)}}\Omega\left(\nu^{(t+1)}-\nu^{(t)}\right)\right]+o(\gamma^{(t)})$

Define now

$I^{\prime}:=\\{t\,|\,\widehat{\theta}^{(t)}\in\Theta_{\omega}\\}\,,\quad
I^{\prime\prime}:=\\{t\,|\,\widehat{\theta}^{(t)}\in\Theta_{\omega^{+}}\\}$

and put $v^{\prime}=1/\omega_{i_{0}}^{2}$ and
$v^{\prime\prime}=1/\omega_{i_{0}}^{+2}$. From Lemma 11, and applying Lemma 15
to $\mu^{(t)}$ and $\nu^{(t)}$, we get that for $t\in I^{\prime}$ sufficiently
large, it holds

$\widehat{\theta}^{(t+1)}_{i_{0}}-\widehat{\theta}^{(t)}_{i_{0}}=c^{(t)}\gamma^{(t)}(\bar{y}_{\omega}-\overline{\widehat{\theta}}^{(t)})+\frac{1}{\bar{\nu}^{(t)}}\gamma^{(t)}a^{(t)}_{\delta}\left(v^{\prime}-v^{\prime\prime}\right)(y_{i_{0}}-\overline{\widehat{\theta}}^{(t)})+a^{(t)}_{\delta}+r^{(t)}.$
(37)

If ${\widehat{\theta}}(\omega)>\Theta_{\omega}\cap\Lambda$, then also, by
Lemma 13, $\bar{y}_{\omega^{+}}>\Theta_{\omega}\cap\Lambda$. This, using (25),
would imply that $\widehat{\theta}^{(t)}$ would necessarily exit
$\mathcal{L}_{\omega,\omega^{+}}$ in finite time. Therefore, we must have
${\widehat{\theta}}(\omega)<\Theta_{\omega}\cap\Lambda$. Hence,
$\bar{y}_{\omega}-\overline{\widehat{\theta}}^{(t)}<0$. Moreover, it is easy
to check that in any case
$\left(v^{\prime}-v^{\prime\prime}\right)(y_{i_{0}}-\overline{\widehat{\theta}}^{(t)})<0$.
Recall now the definition of the constant $\tilde{c}$ in (24) and notice that,
since $\widehat{\theta}^{(t)}\in\mathcal{L}_{\omega,\omega^{+}}$,

$c^{(t)}\gamma^{(t)}(\bar{y}_{\omega}-\overline{\widehat{\theta}}^{(t)})\leq-\alpha^{2}\tilde{c}/4\beta^{2}\gamma^{(t)}.$

Choose now $\delta$ such that $\delta<\alpha^{2}\tilde{c}/16\beta^{2}$ and
$\bar{t}\geq\bar{t}_{\delta}$ such that $r(t)<\delta\gamma^{(t)}$. It then
follows from (37) that for $t\in I^{\prime}$ and $t\geq\bar{t}$, it holds

$\widehat{\theta}^{(t+1)}_{i_{0}}-\widehat{\theta}^{(t)}_{i_{0}}\leq-\alpha^{2}\tilde{c}/8\beta^{2}\gamma^{(t)}<0.$

This says that as long as $\widehat{\theta}^{(t)}\in\Theta_{\omega}$, its
$i_{0}$-th component decreases. But this entails that $\widehat{\theta}^{(t)}$
can never leave $\Theta_{\omega}$, which contradicts the infinite switching
assumption and thus implies the thesis. ∎

###  A.3 Proof of Theorem 1

Propositions 12, 14, and 16 imply that there exists
$\widehat{\omega}^{IA}\in\\{\alpha,\beta\\}^{\mathcal{V}}$ such that
$\widehat{\theta}^{(t)}\in\Theta_{\widehat{\omega}^{IA}}$ for $t$ sufficiently
large. This immediately implies that
$\widehat{\omega}^{(t)}=\widehat{\omega}^{IA}$ for $t$ sufficiently large.
Corollary 9 implies that
$\widehat{\theta}^{IA}=\lim_{t\rightarrow+\infty}\widehat{\theta}^{(t)}=\hat{\theta}(\widehat{\omega}^{IA})$
Finally, since
$\hat{\theta}(\widehat{\omega}^{IA})\in\Theta_{\widehat{\omega}^{IA}}$, we
also have that $\widehat{\omega}^{IA}=\hat{\omega}(\widehat{\theta}^{IA})$.

##  Appendix B Proof of concentration results

###  B.1 Preliminaries

For a more efficient parametrization of the stationary points, we introduce
the notation:

$\omega\in\\{\alpha,\beta\\}^{\mathcal{V}}\quad\Theta_{\omega}:=\\{x\in\mathbb{R}\,|\,|x-y_{i}|<\delta\,\Leftrightarrow\,\omega_{i}=\alpha\\}$
(38)

It is then straightforward to check from (11) that the set of local maxima
${\mathcal{S}}_{N}$ can be represented as

${\mathcal{S}}_{N}:=\\{\theta=\widehat{\theta}(\omega)\,|\,\omega\in\\{\alpha,\beta\\}^{\mathcal{V}},\;\widehat{\theta}(\omega)\in\Theta_{\omega}\\}.$
(39)

Since,

$\Theta_{\omega}\neq\emptyset\;\Leftrightarrow\;\omega=\widehat{\omega}(x)\,\hbox{\rm
for some}\;x\in\mathbb{R}$ (40)

for analysing the set ${\mathcal{S}}_{N}$ we can restrict to consider $\omega$
of type $\omega=\widehat{\omega}(x)$. Consider the sequence of random
functions $\gamma_{N}(x):=\widehat{\theta}(\widehat{\omega}(x))$.

From (8), applying the strong law of large numbers, we immediately get that

$\lim_{N\rightarrow+\infty}\gamma_{N}(x)\stackrel{{\scriptstyle\mathrm{a.s.}}}{{=}}\gamma_{\infty}(x):=\frac{\mathbb{E}(y_{1}\widehat{\omega}(x)_{1}^{-2})}{\mathbb{E}(\widehat{\omega}(x)_{1}^{-2})}.$
(41)

Something stronger can indeed be said by a standard use of Chernoff bound
[26]:

######  Lemma 17.

For every $\epsilon>0$, there exists $q<1$ such that, for any
$x\in\mathbb{R}$,

$\mathbb{P}\left(\left|\gamma_{N}(x)-\gamma_{\infty}(x)\right|>\epsilon\right)\leq
2q^{N}.$

###### Proof.

Let $a_{i}=y_{i}\omega_{N}(x)_{i}^{-2}$ and $b_{i}=\omega_{N}(x)_{i}^{-2}$
with $i\in\\{1,\ldots,N\\}$ and let $a$ and $b$ denote the corresponding
expected values.

By Chernoff’s bound and by Hoeffding’s inequality we have, respectively, that

$\displaystyle\mathbb{P}\left(\left|\frac{1}{N}\sum_{i=1}^{N}a_{i}-a\right|\geq\epsilon_{1}\right)\leq
q_{1}^{N}\qquad\mathbb{P}\left(\left|\frac{1}{N}\sum_{i=1}^{N}b_{i}-b\right|\geq\epsilon_{2}\right)\leq
2q_{2}^{N}$

with

$q_{1}=e^{-\frac{\alpha^{2}\epsilon_{1}^{2}}{4}}\qquad
q_{2}=e^{-2\epsilon_{2}^{2}\left(\alpha^{-2}-\beta^{-2}\right)^{-2}}.$ (42)

Fix $\epsilon_{1}<\frac{\epsilon}{2b\beta^{4}}$ and
$\epsilon_{2}<\frac{\epsilon}{2|a|\beta^{4}}$, then

$\displaystyle\mathbb{P}\left(\left|\bar{y}_{\omega_{N}(x)}-y_{\infty}(x)\right|>\epsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{\left|\frac{1}{N}\sum_{i=1}^{N}a_{i}-a\right|b+|a|\left|b-\frac{1}{N}\sum_{i=1}^{N}b_{i}\right|}{b\frac{1}{N}\sum_{i=1}^{N}b_{i}}>\epsilon\right)$
$\displaystyle\leq
q_{1}^{N}+q_{2}^{N}+\mathbf{1}_{\left\\{\beta^{4}({\epsilon_{1}b+|a|\epsilon_{2}})>\epsilon\right\\}}$
$\displaystyle=q_{1}^{N}+q_{2}^{N}$

where the last step follows by the way $\epsilon_{1}$ and $\epsilon_{2}$ have
been chosen.

There is still a point to be understood: in our derivation $q_{1}$ and $q_{2}$
depend on the choice of $x$ through $a$ and $b$. However, it is immediate to
check that $a$ and $b$ are both bounded in $x$. This allows to conclude. ∎

From (41) is immediate to see that $\gamma_{\infty}$ is a bounded function of
class $C^{1}$ and it has an important property which will be useful later on.

######  Lemma 18.

There exists a constant $C>0$ such that

$\displaystyle x-\gamma_{\infty}(x)\geq C(x-\theta^{*})\;\quad{\rm
if}\,x\in(\theta^{\star},+\infty)$ $\displaystyle\gamma_{\infty}(x)-x\geq
C(\theta^{*}-x)\;\quad{\rm if}\,x\in(-\infty,\theta^{\star})$
$\displaystyle\gamma_{\infty}(\theta^{*})=\theta^{*}$

###### Proof.

If $x\in(\theta^{\star},+\infty)$ and $f$ is the density of each $y_{i}$ (a
mixture of two Gaussians) then

$\displaystyle x-y_{\infty}(x)$
$\displaystyle=\frac{\frac{1}{\alpha^{2}}\int_{x-\delta}^{x+\delta}{(x-t)f(t)}\mathrm{d}t+\frac{1}{\beta^{2}}\int_{\mathbb{R}\setminus(x-\delta,x+\delta)}{(x-t)f(t)}\mathrm{d}t}{\frac{1}{\alpha^{2}}\int_{x-\delta}^{x+\delta}{f(t)}\mathrm{d}t+\frac{1}{\beta^{2}}\int_{\mathbb{R}\setminus(x-\delta,x+\delta)}{f(t)}\mathrm{d}t}$
$\displaystyle\geq\frac{\frac{1}{\beta^{2}}\int_{\mathbb{R}}{(x-t)f(t)}\mathrm{d}t}{\frac{1}{\alpha^{2}}\int_{x-\delta}^{x+\delta}{f(t)}\mathrm{d}t+\frac{1}{\beta^{2}}\int_{\mathbb{R}\setminus(x-\delta,x+\delta)}{f(t)}\mathrm{d}t}$

where the last inequality follows from the fact that
$\int_{x-\delta}^{x+\delta}{(x-t)f(t)}\mathrm{d}t\geq 0$. We conclude that

$\displaystyle x-y_{\infty}(x)$
$\displaystyle\geq\frac{\frac{1}{\beta^{2}}(x-\theta^{\star})}{\frac{1}{\alpha^{2}}\int_{x-\delta}^{x+\delta}{f(t)}\mathrm{d}t+\frac{1}{\beta^{2}}\int_{\mathbb{R}\setminus(x-\delta,x+\delta)}{f(t)}\mathrm{d}t}>0.$

Second statement if $x\in(-\infty,\theta^{\star})$ can be verified in a
completely analogous way. The third statement then simply follows by
continuity. ∎

We now come to a key result.

######  Lemma 19.

For any fixed $\epsilon>0$, there exist $\tilde{q}\in(0,1)$ and $\chi>0$ such
that

$\mathbb{P}\left(\gamma_{N}(x)\in\Theta_{\widehat{\omega}(x)}\right)\leq\chi\tilde{q}^{N}$
(43)

for all $x$ such that $|x-\theta^{\star}|>\epsilon$.

###### Proof.

We assume $x>\theta^{\star}+\epsilon$ (the other case
$x<\theta^{\star}-\epsilon$ being completely equivalent). Fix
$\epsilon^{\prime}\in(0,C\epsilon)$ where $C$ was defined in Lemma 18 and
estimate as follows

$\begin{split}\mathbb{P}\left(\gamma_{N}(x)\in\Theta_{\widehat{\omega}(x)}\right)&\leq\mathbb{P}\left(\gamma_{N}(x)\in\Theta_{\widehat{\omega}(x)}\,,\;|\gamma_{N}(x)-\gamma_{\infty}(x)|\leq\epsilon^{\prime}\right)\\\
&+\mathbb{P}\left(|\gamma_{N}(x)-\gamma_{\infty}(x)|>\epsilon^{\prime}\right).\end{split}$
(44)

Using Lemma 18 we get

$\left\\{|\gamma_{N}(x)-\gamma_{\infty}(x)|\leq\epsilon^{\prime}\right\\}\subseteq\left\\{\gamma_{N}(x)\leq
x-(C\epsilon-\epsilon^{\prime})\right\\}.$

Thus

$\begin{split}&\left\\{\gamma_{N}(x)\in\Theta_{\widehat{\omega}(x)},|\gamma_{N}(x)-\gamma_{\infty}(x)|\leq\epsilon^{\prime}\right\\}\\\
&\qquad\subseteq\\{\nexists
i\,:\,y_{i}\in(\gamma_{N}(x)-\delta,\gamma_{N}(x)-\delta+\min\\{C\epsilon-\epsilon^{\prime},\delta\\})\\}\end{split}$

and, consequently, the first term in (44) can be estimated as

$\begin{split}\mathbb{P}&\left(\gamma_{N}(x)\in\Theta_{\widehat{\omega}_{N}(x)}\,,\;|\gamma_{N}(x)-\gamma_{\infty}(x)|\leq\epsilon^{\prime}\right)\leq\left(1-\int_{\gamma_{N}(x)-\delta}^{\gamma_{N}(x)-\delta+\min\\{C\epsilon-\epsilon^{\prime},\delta\\}}f(y)dy\right)^{N}\end{split}$
(45)

where $f(y)$ is the density of each $y_{i}$. Considering now that $f(y)$ is
bounded away from $0$ on any bounded interval, that
$|\gamma_{N}(x)-\gamma_{\infty}(x)|\leq\epsilon^{\prime}$ and that
$\gamma_{\infty}(x)$ is a bounded function, we deduce that the right hand side
of (45) can be uniformly bounded as $\tilde{q}^{N}$ for some
$\tilde{q}\in(0,1)$. Substituting in (44), and using Lemma 17 we finally
obtain the thesis. ∎

###  B.2 Proof of Theorem 2

Define

$\mathcal{A}_{N}(\epsilon):=\left\\{\exists\omega\in\\{\alpha,\beta\\}^{\mathcal{V}}:\widehat{\theta}(\omega)\in\Theta_{\omega},|\widehat{\theta}(\omega)-\theta^{\star}|>\epsilon\right\\}$

for any $\epsilon>0$ and

$\displaystyle\mathcal{B}_{1}$ $\displaystyle:=\left\\{\exists
i\in\mathcal{V}:|y_{i}-\theta^{\star}|>N\right\\}$
$\displaystyle\mathcal{B}_{2}$
$\displaystyle:=\left\\{\exists(i,j)\in\mathcal{V}\times{\mathcal{V}}:|y_{i}-y_{j}|<N^{-4}\right\\}$
$\displaystyle\mathcal{B}_{3}$
$\displaystyle:=\\{\exists(i,j)\in\mathcal{V}\times{\mathcal{V}}:|y_{i}-y_{j}|\in\left(2\delta,2\delta+{N^{-4}}\right\\}$

and estimate
$\mathbb{P}\left(\mathcal{A}_{N}(\epsilon)\right)\leq\mathbb{P}\left(\mathcal{A}_{N}(\epsilon),\mathcal{B}_{1}^{c}\cap\mathcal{B}_{2}^{c}\cap\mathcal{B}_{3}^{c}\right)+\mathbb{P}(\mathcal{B}_{1})+\mathbb{P}(\mathcal{B}_{2})+\mathbb{P}(\mathcal{B}_{3})$.
Standard considerations allow to upper bound the probability of each event
$\mathcal{B}_{i}$ by a common term $K/N^{2}$. We now focus on the estimation
of the first term. The crucial point is that, the condition
$\mathcal{B}_{1}^{c}\cap\mathcal{B}_{2}^{c}\cap\mathcal{B}_{3}^{c}$ allow us
to reinforce condition (40) in the sense that all $\omega$ for which
$\Theta_{\omega}\neq\emptyset$ can be obtained as $\omega=\widehat{\omega}(x)$
as $x$ varies in a set whose cardinality is polynomial in $N$. Specifically,
define

$Z=\\{\zeta_{j}=\theta^{\star}-N-\delta+{j}{N^{-4}}:j\in\mathbb{N},j\leq
j_{\rm max}\\}$

where $j_{\rm max}:=\lceil N^{4}(2N+2\delta)\rceil$ and notice that, assuming
that the $y_{i}$’s satisfy $\mathcal{B}_{2}^{c}\cap\mathcal{B}_{3}^{c}$, we
have that $\widehat{\omega}(\zeta_{j})$ and $\widehat{\omega}(\zeta_{j+1})$
differ in at most one component and that
$\widehat{\omega}(x)\in\\{\widehat{\omega}(\zeta_{j}),\widehat{\omega}(\zeta_{j+1})\\}$
for every $x\in[\zeta_{j},\zeta_{j+1}]$. Moreover, because of
$\mathcal{B}_{1}^{c}$ we have that
$\widehat{\omega}(x)_{i}=\widehat{\omega}(\zeta_{0})_{i}=\beta$ for all
$x\leq\theta^{\star}_{N}-\delta$ and for all $i$. Similarly,
$\widehat{\omega}(x)_{i}=\widehat{\omega}(\zeta_{j_{\rm max}})_{i}=\beta$ for
all $x\geq\theta^{\star}+N+\delta$ and for sll $i$. In other terms, under the
assumption that the $y_{i}$’s satisfy
$\mathcal{B}_{1}^{c}\cap\mathcal{B}_{2}^{c}\cap\mathcal{B}_{3}^{c}$, it holds
$\\{\omega\in\\{\alpha,\beta\\}^{\mathcal{V}}\;|\;\Theta_{\omega}\neq\emptyset\\}=\\{\widehat{\omega}(x)\;|\;x\in
Z\\}$. Hence,

$\displaystyle\mathbb{P}$
$\displaystyle\left(\mathcal{A}_{N}(\epsilon),\mathcal{B}_{1}^{c}\cap\mathcal{B}_{2}^{c}\cap\mathcal{B}_{3}^{c}\right)\leq$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{\zeta\in
Z}\left\\{\gamma_{N}(\zeta)\in\Theta_{\widehat{\omega}(\zeta)},|\gamma_{N}(\zeta)-\theta^{\star}|>\epsilon\right\\}\right)$
$\displaystyle\leq\mathbb{P}\left(\bigcup_{\zeta\in
Z}\left\\{\gamma_{N}(\zeta)\in\Theta_{\widehat{\omega}(\zeta)},|\gamma_{\infty}(\zeta)-\theta^{\star}|>\epsilon/2\right\\}\right)+$
$\displaystyle+\mathbb{P}\left(|\gamma_{N}(\zeta)-\gamma_{\infty}(\zeta)|\leq\epsilon/2\right).$

Notice that, because of the continuity of $\gamma_{\infty}$, there exists
$\tilde{\epsilon}>0$ such that
$|\gamma_{\infty}(\zeta)-\theta^{\star}|>\epsilon/2\;\Rightarrow\;|\zeta-\theta|>\tilde{\epsilon}$.
We can then use Lemma 19,

$\displaystyle\mathbb{P}\left(\bigcup_{\zeta\in
Z}\left\\{\gamma_{N}(\zeta)\in\Theta_{\widehat{\omega}(\zeta)},|\gamma_{\infty}(\zeta)-\theta^{\star}|>\epsilon/2\right\\}\right)$
$\displaystyle\qquad\leq|Z|\mathbb{P}\left(\gamma_{N}(\zeta)\in\Theta_{\widehat{\omega}(\zeta)},|\gamma_{N}(\zeta)-\theta^{\star}|>\epsilon\right)\leq
cN^{5}\tilde{q}^{N}$

where $c$ and $\tilde{q}$ are those coming from Lemma 19 relatively to
$\tilde{\epsilon}$. Putting together all the estimations we have obtained and
using Lemma 17, we finally obtain that there exists $\chi>0$ such that
$\mathbb{P}\left(\mathcal{A}_{N}(\epsilon)\right)\leq\chi/N^{2}$. Using Borel-
Cantelli Lemma and standard arguments, it follows now that the relation (16)
hold in an almost surely sense.

It remains to be shown convergence in mean square sense. For this we need to
go back to the form (10) of the derivative of
$L(\theta,\widehat{\omega}(\theta))$. The key observation is that the second
additive term in the right hand side of (10) can be bounded uniformly in
modulus by some constant $C$. If we denote
$\bar{\gamma}_{N}=N^{-1}\sum_{i}y_{i}$, this implies that the function is
increasing for $\theta>\bar{\gamma}_{N}+\beta^{2}C$ and decreasing for
$\theta<\bar{\gamma}_{N}-\beta^{2}C$. Hence, necessarily,

$|\xi-\bar{\gamma}_{N}|\leq\beta^{2}C\;\ \forall\xi\in{\mathcal{S}}_{N}.$ (46)

On the other hand, by the law of large numbers, $\bar{\gamma}_{N}$ almost
surely converges to $\theta^{\star}$ and this implies, by the previous part of
the theorem that $\max\limits_{\xi\in{\mathcal{S}}_{N}}|\xi-\bar{\gamma}_{N}|$
converges to $0$. This, together with (46), yields
$\mathbb{E}\max\limits_{\xi\in{\mathcal{S}}_{N}}|\xi-\bar{\gamma}_{N}|^{2}\to
0$ for $N\to+\infty$. Since by the ergodic theorem also
$\mathbb{E}|\bar{\gamma}_{N}-\theta^{\star}|^{2}\to 0$ for $N\to+\infty$, the
proof is complete.

###  B.3 Proof of Proposition 4

We prove it for $\widehat{\omega}^{\mathrm{IA}}$, the other verification being
completely equivalent). If $\sigma\in\\{\alpha,\beta\\}$, we define

$\begin{split}f(\theta,\sigma)&=\mathbb{P}(\widehat{\omega}(\theta)_{i}\neq\sigma\;|\;\omega^{\star}_{i}=\sigma)\\\
&=\begin{cases}\frac{1}{\sqrt{2\pi\sigma^{2}}}\int_{{\theta}-\delta}^{{\theta}+\delta}\mathrm{e}^{-\frac{(s-\theta^{\star})^{2}}{2\sigma^{2}}}\mathrm{d}s\qquad\
\ \text{if }\sigma=\beta\\\
1-\frac{1}{\sqrt{2\pi\sigma^{2}}}\int_{{\theta}-\delta}^{{\theta}+\delta}\mathrm{e}^{-\frac{(s-\theta^{\star})^{2}}{2\sigma^{2}}}\mathrm{d}s\quad\text{if
}\sigma=\alpha\end{cases}\end{split}$

(notice that $f$ does not depend on $i$). We can compute

$\begin{split}\frac{1}{N}\mathbb{E}d_{H}(\widehat{\omega}^{\mathrm{IA}},\omega^{\star})&=\frac{1}{N}\sum\limits_{i}\mathbb{P}(\widehat{\omega}^{\mathrm{IA}}_{i}\neq\omega^{\star}_{i})\\\
&=p\mathbb{E}f(\widehat{\theta}^{\mathrm{IA}},\alpha)+(1-p)\mathbb{E}f(\widehat{\theta}^{\mathrm{IA}},\beta).\end{split}$

Since $f(\theta,\sigma)$ is a $C^{1}$ function of $\theta$, we immediately
obtain that

$|\mathbb{E}f(\widehat{\theta}^{\mathrm{IA}},\sigma)-\mathbb{E}f(\theta^{\star},\sigma)|\leq
C\mathbb{E}|\widehat{\theta}^{\mathrm{IA}}-\theta^{\star}|$

and, by Corollary 3, this last expression converges to $0$, for $N\to+\infty$.
Hence,

$\frac{1}{N}\mathbb{E}d_{H}(\widehat{\omega}^{\mathrm{IA}},\omega^{\star})=p\mathbb{E}f(\theta^{\star},\alpha)+(1-p)\mathbb{E}f(\theta^{\star},\beta).$

Straightforward computation now proves the thesis.