# Gravitational Lensing of the Cosmic Neutrino Background

Joshua Yao-Yu Lin  Gilbert Holder

(August 27, 2024)

###### Abstract

We study gravitational lensing of the cosmic neutrino background. This signal
is undetectable for the foreseeable future, but there is a rich trove of
information available. At least some of the neutrinos from the early universe
will be non-relativistic today, with a closer surface of last scattering
(compared to the cosmic microwave background) and with larger angles of
deflection. Lensing of massive neutrinos is strongly chromatic: both the
amplitude of lensing and the cosmic time at which the potential is traversed
depend on neutrino momentum, in principle giving access to our entire causal
volume, not restricted to the light cone. As a concrete example, we focus on
the case where the cosmic neutrino background would be strongly lensed when
passing through halos of galaxy clusters and galaxies. We calculate the
Einstein radius for cosmic neutrinos and investigate the impact of neutrino
mass.

##  1 Introduction

In the usual thermal history of the early universe, cosmic neutrinos, also
known as relic neutrinos, decouple just seconds after the Big Bang [1]. These
neutrinos tremendously outnumber baryons in the universe; however, due to
their very weak interactions with ordinary matter, no direct detection has yet
been achieved [2]. Several papers have discussed the possibility of detecting
cosmic neutrinos and their anisotropy [3, 4]. This will be tremendously
challenging and is unlikely to be achieved soon, but there is at present no
fundamental impediment to such detection.

Since there is anisotropy in the cosmic neutrino background (C${\nu}$B) [5],
it should ultimately be possible to detect gravitational lensing of the cosmic
neutrino background. As we will show below, the non-zero mass of at least two
neutrino types leads to several effects that make the cosmic neutrino
background and its gravitational lensing a unique source of information on the
growth of structure in the universe that can be used to probe the three-
dimensional structure of the universe and its time evolution, rather than the
usual restriction of being on the past light-cone.

Gravitational lensing of the C${\nu}$B is similar to cosmic microwave
background (CMB) lensing [6] in many respects. We show below that there are
several important differences arising from the fact that neutrinos are massive
[7, 8]. Although the individual masses of neutrinos are so far unknown, we
have constraints from several measurements [9] that suggest that neutrino
masses are expected to be in the range of several tens of meV, making the rest
mass energy of many of these neutrinos larger than their thermal energy.

Since neutrinos are massive, they must travel more slowly than light. The last
scattering surface (LSS) for massive neutrinos is, therefore, closer to us
than the LSS for CMB photons, by an amount that depends on the momentum of the
neutrinos being measured and their mass [10]. The background neutrinos passing
through our detectors today are physically sourced from a different three-
dimensional location in space than the background photons. In the absence of
gravitational deflections, those locations simply correspond to different
physical locations along a single line of sight, depending on the mass and
momentum of each neutrino. Furthermore, they pass through the intervening
structures in the universe at a time that depends on neutrino mass and
momentum, allowing neutrinos of different momenta to track the time evolution
of individual structures. Finally, the amount of deflection also depends on
the neutrino mass and momentum, allowing the same lens to be probed at a
variety of impact parameters, all using neutrinos from the big bang.

In total, this presents a remarkable cache of information: the three-
dimensional gravitational potential of the observable universe as a movie,
limited only by causality and the poor prospects for imminent detection.

In this work, we will focus on the simple case of strong lensing [11], as it
captures many of the important physical effects, and we use a thin lens
approximation, as is often done for photons. For all the calculations in this
paper, we assume a flat $\Lambda\textrm{CDM}$ expansion history and use
Planck15 [12] for all cosmological parameters ($H_{0}=67.7$ km/s/Mpc ,
$\Omega_{m}=0.307$). The neutrino background temperature today is
$T_{\nu}=1.95K=1.68\times 10^{-4}$ eV.

##  2 Lensing properties of massive cosmic neutrinos

Massless neutrinos would follow the same lensing equations as photons, as
would sufficiently energetic neutrinos. For photons passing a point mass
gravitational lens, the Einstein radius is given by $\theta_{E,\gamma}^{\rm
PT}=\sqrt[]{\frac{4GM}{c^{2}}\frac{D_{LS}}{D_{S}D_{L}}}$, where $D_{S}$ is the
comoving distance from observer to the source (surface of last scattering),
$D_{L}$ is the comoving distance from observer to the lens, and $D_{LS}$ is
the distance between lens and source. For a singular isothermal sphere (SIS)
lens, the Einstein radius is $\theta_{E,\gamma}^{\rm
SIS}=\frac{4\pi\sigma_{v}^{2}}{c^{2}}\frac{D_{LS}}{D_{S}}$, where $\sigma_{v}$
represents the velocity dispersion of the lens galaxy.

For massive neutrinos, there are several differences from the massless case.
First, the massive neutrinos no longer propagate at the speed of light $c$.
Instead, they propagate with a time-varying velocity. We define the neutrino
momentum today as $p_{0}$; the momentum of neutrinos at earlier times, when
the scale factor of the universe relative to today is $a(t)$, follows $a\times
p(a)=p_{0}$.

The momentum distribution of cosmic neutrinos follows a Fermi-Dirac
distribution that is established in the first seconds after the big bang, when
cosmic neutrinos were still ultra-relativistic. We can therefore follow
previous work [10], assuming zero chemical potential and no additional heating
from electron-positron annihilation [13], to determine the momentum
probability distribution:

$\frac{dP}{dp_{0}}=\frac{2}{3\zeta(3)k_{B}^{3}T_{\nu}^{3}}\frac{p_{0}^{2}/c^{3}}{\mathit{e}^{p_{0}/k_{B}T_{\nu}}+1}$
(2.1)

where $k_{B}$ is the Boltzmann constant. The neutrino speed today is related
to its momentum today as $p_{0}=\gamma_{0}m_{\nu}v_{0}$. The reshifted
velocity can then be expressed as a function of scale factor $a$ and $v_{0}$.

$v(a)=\frac{v_{0}}{\sqrt[]{a^{2}+\frac{v_{0}^{2}}{c^{2}}(1-a^{2})}}$ (2.2)

For a neutrino of a particular mass and momentum today, we define the velocity
of the neutrino as it passes through a lens when the universe has a particular
scale factor as $v_{lens}(a)$. For a neutrino with that speed, the angle of
deflection as it passes a mass distribution would be [14]

$\alpha(R)=\frac{4GM(R)}{Rc^{2}}\frac{c^{2}+v_{lens}^{2}}{2v_{lens}^{2}}\ ,$
(2.3)

where $\alpha(R)$ represents the angle of deflection of a neutrino that passes
a distance $R$ from the center of mass, and $M(R)$ represents the mass
interior to that radius. While very large angles of bending angle would
require ray tracing simulations, we focus here on deflections that are still
degree-scale rather than radian-scale. This is the Born approximation, and it
definitely breaks down when the incoming neutrino is nearly bound. The
deflections here are large compared to the case of photons, but for typical
cosmic neutrinos they are still a small fraction of a radian. Hence, the thin
lens approximation could give us first order estimation about the Einstein
Radius. Using the lens equation [15] , we can get the Einstein radius for a
point mass:

$\theta_{E}^{\rm
PT}=\bigg{[}\frac{4GM}{c^{2}}\Big{(}\frac{c^{2}+v_{lens}^{2}}{2v_{lens}^{2}}\Big{)}\frac{D_{LS}}{D_{S}D_{L}}\bigg{]}^{\frac{1}{2}}\
,$ (2.4)

and for a singular isothermal sphere (SIS):

$\theta_{E}^{\rm
SIS}=\frac{4\pi\sigma_{v}^{2}}{c^{2}}\Big{(}\frac{c^{2}+v_{lens}^{2}}{2v_{lens}^{2}}\Big{)}\frac{D_{LS}(v_{0},D_{L})}{D_{S}(v_{0})}\
,$ (2.5)

where

$D_{L}=\int^{1}_{a_{lens}}\frac{da}{a^{2}H(a)}v(a)\ ,$ (2.6)

$D_{S}(v_{0})=\int^{1}_{a_{s}}\frac{da}{a^{2}H(a)}v(a)\ ,$ (2.7)

and

$D_{LS}(v_{0},D_{L})=D_{S}(v_{0})-D_{L}\ .$ (2.8)

Figure 1 shows the Einstein radii of SIS lenses at three selected distances
$D_{L}$ . There are several important lensing properties for cosmic neutrinos.

Neutrinos within a given mass eigenstate have a momentum distribution
following the Fermi-Dirac distribution (equation 2.1). Different momenta, even
for the same mass, therefore correspond to different Einstein radii. Hence the
lensing of neutrinos could provide rich information about the lens potential.

Massive neutrinos can have a wide range in their distance to their surfaces of
last scattering, depending on their velocity today, and possibly very
different from that of the CMB [10]. It is possible that a neutrino’s surface
of last scattering could be closer than the physical position of the
gravitational lens (e.g. a galaxy cluster), leading to a cutoff in lensing
when $D_{S}=D_{L}$.

Figure 1: Einstein radii of massive neutrinos passing through singular
isothermal spheres (SIS) with $\sigma_{v}=1000$ km/s with $D_{L}=100$, $500$,
and $1000$ Mpc. The velocity probability distribution follows Fermi-Dirac
distribution, we label three specific cases with $m_{\nu}=0.1$, $0.05$, and
$0.01$ eV. The smaller the v, it would cause larger angle of deflection.
However, it would also decrease the distance between the lens and the surface
of last scattering, hence decrease the delecting angle. For each lens
position, it would correspond to a certain $v_{0}$ that maximize the Einstein
Ring.

Neutrinos propagate in mass eigenstates but they are observed in flavor
eigenstates, corresponding to a combination of the 3 different mass
eigenstates described by the PMNS matrix [16, 17]. When we observe the lensing
pattern for cosmic neutrinos of fixed direction and momentum in a particular
flavor state, we are measuring a superposition of three mass eigenstates. A
fixed momentum will correspond to three possible velocities, leading to a
superposition of three different lensed neutrino maps, each corresponding to a
different unlensed source plane and a different lookback time to the lens. If
the masses and mixings are known, it would be possible to take combinations of
lensing maps constructed at different momenta to get the time evolution of
individual lenses. For unlensed lines of sight going through the exact center
of the halo, there would be three Einstein rings, corresponding to the three
mass eigenstates as shown in figure 2. Integrating over momenta, the thickness
of individual rings is related to the neutrino momentum distribution following
Fermi-Dirac statistics.

Only the lensing of the neutrino background fluctuations can be detected, as
Liouville’s theorem ensures that the mean flux is unchanged. The correlation
structure of the intrinsically statistically isotropic fluctuations (i.e.,
there is no preferred orientation on the sky for the fluctuations) is
distorted by gravitational lensing. For example, the correlations along the
Einstein ring would be strongly oriented along the tangential direction,
coming from the lensing of intrinsic fluctuations along the unlensed line of
sight that have equal correlations in all directions. Therefore, the lensing
effect would look similar to Figure 1 in [18]. The Einstein ring is a
preferred place in the lensed image where the source-plane isotropic
correlations become ring-like in the image.

We ignore momentum shifts due to decaying or growing potentials (ISW effects)
and time delay effects that come from increased time of travel across
gravitational potentials leading to the surface of last scattering being at a
shorter distance. These are important effects for low-speed neutrinos that
should be investigated in future work.

For visualization, we show the lensing of the neutrino background for
neutrinos only directly along the line of sight through the center of the
lens, as these would have the most dramatic distortion of their correlations,
lensed to form Einstein Rings.

(a) Neutrino flux for all mass eigenstates

(b) Neutrino flux for electron neutrinos

(c) Neutrino flux for muon neutrinos

(d) Neutrino flux for tau neutrinos

Figure 2: Lensed image for neutrinos detected as electron neutrinos
originating from the line of sight directly through the center of the lens,
showing three Einstein rings. The relative fluxes of the rings depend on
mixing angles and neutrino hierarchy models: left shows the normal hierarchy,
right shows the inverted one, both assuming the lightest neutrino is massless.
Here we assume masses of neutrinos $\Delta m_{12}^{2}=8\times 10^{-5}eV,\Delta
m_{23}^{2}=2.32\times 10^{-3}eV$, and the lightest neutrino mass eigenstate is
$10^{-5}$ eV. We are plotting a particular momentum bin, which is the peak of
the momentum distribution described by the Fermi-Dirac distribution with the
lens is placed at $500$ Mpc away from the observer.

The lookback time is the age of the universe relative to today at which a
cosmic event occurred, and can be calculated from the scale factor of the
universe when the neutrino passed a location a distance $D_{L}$. Since
neutrinos can travel with different velocities, the lookback time to a lensing
event at fixed distance $D_{L}$ for neutrinos with different velocities can be
different. Neutrinos pass the lens at different epochs for the lens. figure 3
shows the neutrino lookback time for different velocities today.

Figure 3: Time (relative to today) that massive cosmic neutrinos pass through
a gravitational lens at distance $D_{L}$, for several different measured
velocities today (in units of the speed of light). There is a cutoff when the
lookback time approach the age of the universe, as $D_{L}$ approaches the
surface of last scattering $D_{S}$.

If the gravitational lens is evolving, neutrinos with different velocities
could be used to measure the time evolution. Dark matter halos grow as a
function of cosmic time through accretion and repeated mergers. Neutrinos with
different velocities today passed through the lens halo at different times.
Therefore, they experienced different deflections due to the mass evolution of
the lens halo. In a SIS model, $\theta_{E}^{\rm
SIS}(v_{0})\propto\sigma_{v}^{2}(a_{lens})$, where $a_{lens}$ is a function of
$D_{L}$ and $v_{0}$ described in eqn. 2.6. Neutrinos with larger momentum
enter the lens halo later; if the lens halo mass is growing with time, these
neutrinos would experience deeper potentials and hence have larger
deflections.

##  3 Discussion and Conclusion

Gravitational lensing leads to a breaking of statistical isotropy; the
correlations in the neutrino background will have spatial variations induced
by lensing, exactly as happens for the lensing of the CMB. The Einstein ring
is the most eye-catching breaking of statistical isotropy by lensing: the
unlensed positive or negative fluctuation at a particular momentum will get
lensed into a complete annulus of positive or negative intensity relative to
the cosmic mean. There will be three such rings for each lens, corresponding
to the three mass eigenstates. Elsewhere in the image, the unlensed
fluctuations will similarly have their correlations distorted, but less
dramatically. For simplicity, we focus on Einstein rings to understand the
information content of the lensing of the neutrino background. In general,
something akin to the quadratic estimator used for CMB lensing [18] could be
used to extract information from the weak lensing of the neutrino background.
The Einstein radius is determined by the mass enclosed in the region at the
time when neutrinos at a given speed pass through the lens potential. In this
work, we assume the lens potential to be constant for simplicity and focus on
the splitting of mass eigenstates for the Einstein rings. Understanding the
time evolution of the lens potential and its connection with neutrino lensing
will be an interesting extension in future work.

Using neutrinos of a single mass, one could imagine the following program to
map out a structure at some fixed distance: mapping the gravitational lensing
effects at a fixed momentum (which corresponds for a single mass eigenstate to
a particular velocity today) to map the spatial variation of the lens
potential, while repeating this at various measured momenta to obtain the time
evolution of the lens. The three mass eigenstates lead to three superposed
independent versions of this program. While lensing studies with photons give
the state of the lens only at a single moment in time, neutrino lensing can
reconstruct the full time evolution of gravitational potentials inside the
light cone.

Different momenta indeed came from a different radial distance and hence we
would probe a different region of the source. Hence, we present the result in
individual momentum bins. Averaging over momenta will mix together both the
sources (from different line of sight locations) and the lenses (at different
times) in a complicated way.

Neutrino oscillations in the usual sense are not directly relevant in this
case, as the mass eigenstates, equally populated in the early universe, get
dispersed along the line of sight by their different propagation speeds. For
neutrinos emitted from a single location in space, the wave packets for each
mass eigenstate will be widely separated today. In addition, the lens will
also act as a spectrometer, splitting the mass eigenstates in the angular
direction. Therefore, the probability to measure the lensing-induced
correlations in particular flavor eigenstates becomes deterministic. For
example, at a given momentum and flavor there would be three Einstein Rings
due to the three mass eigenstates, with the relative amplitudes of each ring
set by mixing angles, as shown in figure 2 .

Motion of the lens halos would also affect how neutrinos are deflected. In
this paper, we assume all the lenses are in a fixed co-moving frame. However,
in reality the foreground halos can have peculiar velocities and therefore
induce a slingshot effect. At early time, the neutrinos will be relativistic,
so the effect would be small. At late times, neutrinos will have larger
deflections, possibly leading to larger changes in the momentum of neutrinos.

These lensing effects can only be seen using the anisotropies in the neutrino
background [19, 18, 20, 21]. Substantially complicating the interpretation
will be the strong late-time evolution of the neutrino fluctuations arising
from the linear and non-linear integrated Sachs-Wolfe effects [22]. This is an
interesting but challenging project that we leave for future investigations.

In summary, we have shown that gravitational lensing of the cosmic neutrino
background is in principle an extremely rich source of information, containing
the imprint of the gravitational evolution of the entire three-dimensional
universe within our causal horizon.

## ACKNOWLEDGMENT

The authors would like to thank Sunny Tang, Arka Banerjee, Po-Wen Chang, Mark
Chen, and Patrick Draper for useful discussions. This work is supported by
Brand and Monica Fortner, and NSF AST-17-15717. GH is a fellow in the Gravity
and the Extreme Universe program of CIfAR. This research was supported in part
by the Perimeter Institute for Theoretical Physics. Research at Perimeter
Institute is supported by the Government of Canada through the Department of
Innovation, Science, and Economic Development, and by the Province of Ontario
through the Ministry of Research and Innovation.

## References

  * [1] G. Mangano, G. Miele, S. Pastor, T. Pinto, O. Pisanti and P. D. Serpico, _Relic neutrino decoupling including flavour oscillations_ , _Nuclear Physics B_ 729 (2005) 221 [hep-ph/0506164].
  * [2] A. Faessler, R. Hodák, S. Kovalenko and F. Šimkovic, _Can one measure the Cosmic Neutrino Background?_ , _International Journal of Modern Physics E_ 26 (2017) 1740008 [1602.03347].
  * [3] M. Lisanti, B. R. Safdi and C. G. Tully, _Measuring anisotropies in the cosmic neutrino background_ , _Phys. Rev. D_ 90 (2014) 073006.
  * [4] R. J. Michney and R. R. Caldwell, _Anisotropy of the cosmic neutrino background_ , _J. Cosmol. Astropart. Phys._ 1 (2007) 014 [astro-ph/0608303].
  * [5] S. Hannestad and J. Brandbyge, _The cosmic neutrino background anisotropy—linear theory_ , _Journal of Cosmology and Astroparticle Physics_ 2010 (2010) 020.
  * [6] A. Lewis and A. Challinor, _Weak gravitational lensing of the CMB_ , _Phys. Rep._ 429 (2006) 1 [astro-ph/0601594].
  * [7] J. Lesgourgues and S. Pastor, _Massive neutrinos and cosmology_ , _Phys. Rep._ 429 (2006) 307 [astro-ph/0603494].
  * [8] S. Petcov, _The nature of massive neutrinos_ , _Advances in High Energy Physics_ 2013 (2013) .
  * [9] F. Capozzi, E. Di Valentino, E. Lisi, A. Marrone, A. Melchiorri and A. Palazzo, _Global constraints on absolute neutrino masses and their ordering_ , _Phys. Rev. D_ 95 (2017) 096014 [1703.04471].
  * [10] S. Dodelson and M. Vesterinen, _Cosmic Neutrino Last Scattering Surface_ , _Physical Review Letters_ 103 (2009) 171301 [0907.2887].
  * [11] P. Schneider, J. Ehlers and E. E. Falco, _Gravitational Lenses_. Springer Berlin Heidelberg, 1992, 10.1007/978-3-662-03758-4.
  * [12] Planck Collaboration, P. A. R. Ade, N. Aghanim, M. Arnaud, M. Ashdown, J. Aumont et al., _Planck 2015 results. XIII. Cosmological parameters_ , _Astron. Astrophys._ 594 (2016) A13 [1502.01589].
  * [13] S. Dodelson and M. S. Turner, _Nonequilibrium neutrino statistical mechanics in the expanding Universe_ , _Phys. Rev. D_ 46 (1992) 3372.
  * [14] B. R. Patla, R. J. Nemiroff, D. H. H. Hoffmann and K. Zioutas, _Flux Enhancement of Slow-moving Particles by Sun or Jupiter: Can They be Detected on Earth?_ , _Astrophys J._ 780 (2014) 158 [1305.2454].
  * [15] R. Kormann, P. Schneider and M. Bartelmann, _Isothermal elliptical gravitational lens models_ , _Astron. Astrophys._ 284 (1994) 285.
  * [16] Z. Maki, M. Nakagawa and S. Sakata, _Remarks on the unified model of elementary particles_ , _Progress of Theoretical Physics_ 28 (1962) 870.
  * [17] B. Pontecorvo, _Inverse beta processes and nonconservation of lepton charge_ , _Sov. Phys. JETP_ 7 (1958) 172.
  * [18] W. Hu and T. Okamoto, _Mass reconstruction with cosmic microwave background polarization_ , _The Astrophysical Journal_ 574 (2002) 566.
  * [19] W. Hu and S. Dodelson, _Cosmic microwave background anisotropies_ , _Annual Review of Astronomy and Astrophysics_ 40 (2002) 171\.
  * [20] R. E. Lopez, S. Dodelson, A. Heckler and M. S. Turner, _Precision detection of the cosmic neutrino background_ , _Physical Review Letters_ 82 (1999) 3952.
  * [21] R. J. Michney and R. R. Caldwell, _Anisotropy of the cosmic neutrino background_ , _Journal of Cosmology and Astroparticle Physics_ 2007 (2007) 014.
  * [22] A. Cooray, _Nonlinear integrated sachs-wolfe effect_ , _Physical Review D_ 65 (2002) 083518.


# Structure of optimal strategies for remote estimation over Gilbert-Elliott
channel with feedback

Jhelum Chakravorty  Electrical and Computer Engineering
McGill University, Montreal, Canada
Email<EMAIL_ADDRESS>Aditya Mahajan  Electrical and
Computer Engineering
McGill University, Montreal, Canada
Email<EMAIL_ADDRESS>
###### Abstract

We investigate remote estimation over a Gilbert-Elliot channel with feedback.
We assume that the channel state is observed by the receiver and fed back to
the transmitter with one unit delay. In addition, the transmitter gets
ack/nack feedback for successful/unsuccessful transmission. Using ideas from
team theory, we establish the structure of optimal transmission and estimation
strategies and identify a dynamic program to determine optimal strategies with
that structure. We then consider first-order autoregressive sources where the
noise process has unimodal and symmetric distribution. Using ideas from
majorization theory, we show that the optimal transmission strategy has a
threshold structure and the optimal estimation strategy is Kalman-like.

##  I Introduction

###  I-A Motivation and literature overview

We consider a remote estimation system in which a sensor/transmitter observes
a first-order Markov process and causally decides which observations to
transmit to a remotely located receiver/estimator. Communication is expensive
and takes place over a Gilbert-Elliot channel (which is used to model channels
with burst erasures). The channel has two states: off state and on state. When
the channel is in the off state, a packet transmitted from the sensor to the
receiver is dropped. When the channel is in the on state, a packet transmitted
from the sensor to the receiver is received without error. We assume that the
channel state is causally observed at the receiver and is fed back to the
transmitter with one-unit delay. Whenever there is a successful reception, the
receiver sends an acknowledgment to the transmitter. The feedback is assumed
to be noiseless.

At the time instances when the receiver does not receive a packet (either
because the sensor did not transmit or because the transmitted packet was
dropped), the receiver needs to estimate the state of the source process.
There is a fundamental trade-off between communication cost and estimation
accuracy. Transmitting all the time minimizes the estimation error but incurs
a high communication cost; not transmitting at all minimizes the communication
cost but incurs a high estimation error.

The motivation of remote estimation comes from networked control systems. The
earliest instance of the problem was perhaps considered by Marschak [1] in the
context of information gathering in organizations. In recent years, several
variations of remote estimation has been considered. These include models that
consider idealized channels without packet drops [2, 3, 4, 5, 6, 7, 8, 9] and
models that consider channels with i.i.d. packet drops [10, 11].

The salient features of remote estimation are as follows:

  1. (F1)

The decisions are made sequentially.

  2. (F2)

The reconstruction/estimation at the receiver must be done with zero-delay.

  3. (F3)

When a packet does get through, it is received without noise.

Remote estimation problems may be viewed as a special case of real-time
communication [12, 13, 14, 15]. As in real-time communication, the key
conceptual difficulty is that the data available at the transmitter and the
receiver is increasing with time. Thus, the domain of the transmission and the
estimation function increases with time.

To circumvent this difficulty one needs to identify sufficient statistics for
the data at the transmitter and the data at the receiver. In the real-time
communication literature, dynamic team theory (or decentralized stochastic
control theory) is used to identify such sufficient statistics as well as to
identify a dynamic program to determine the optimal transmission and
estimation strategies. Similar ideas are also used in remote-estimation
literature. In addition, feature (F3) allows one to further simplify the
structure of optimal transmission and estimation strategies. In particular,
when the source is a first-order autoregressive process, majorization theory
is used to show that the optimal transmission strategies is characterized by a
threshold [5, 6, 7, 11, 10]. In particular, it is optimal to transmit when the
instantaneous distortion due to not transmitting is greater than a threshold.
The optimal thresholds can be computed either using dynamic programming [5, 6]
or using renewal relationships [16, 10].

All of the existing literature on remote-estimation considers either channels
with no packet drops or channels with i.i.d. packet drops. In this paper, we
consider packet drop channels with Markovian memory. We identify sufficient
statistics at the transmitter and the receiver. When the source is a first-
order autoregressive process, we show that threshold-based strategies are
optimal but the threshold depends on the previous state of the channel.

###  I-B The communication system

####  I-B1 Source model

The source is a first-order time-homogeneous Markov process
$\\{X_{t}\\}_{t\geq 0}$, $X_{t}\in\mathcal{X}$. For ease of exposition, in the
first part of the paper we assume that $\mathcal{X}$ is a finite set. We will
later argue that a similar argument works when $\mathcal{X}$ is a general
measurable space. The transition probability matrix of the source is denoted
by $P$, i.e., for any $x,y\in\mathcal{X}$,

$P_{xy}\coloneqq\mathds{P}(X_{t+1}=y\mid X_{t}=x).$

####  I-B2 Channel model

The channel is a Gilbert-Elliott channel [17, 18]. The channel state
$\\{S_{t}\\}_{t\geq 0}$ is a binary-valued first-order time-homogeneous Markov
process. We use the convention that $S_{t}=0$ denotes that the channel is in
the off state and $S_{t}=1$ denotes that the channel is in the on state. The
transition probability matrix of the channel state is denoted by $Q$, i.e.,
for $r,s\in\\{0,1\\}$,

$Q_{rs}\coloneqq\mathds{P}(S_{t+1}=s|S_{t}=r).$

The input alphabet $\bar{\mathcal{X}}$ of the channel is
$\mathcal{X}\cup\\{\mathfrak{E}\\}$, where $\mathfrak{E}$ denotes the event
that there is no transmission. The channel output alphabet $\mathcal{Y}$ is
$\mathcal{X}\cup\\{\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$, where the symbols
$\mathfrak{E}_{0}$ and $\mathfrak{E}_{1}$ are explained below. At time $t$,
the channel input is denoted by $\bar{X}_{t}$ and the channel output is
denoted by $Y_{t}$.

The channel is a channel with state. In particular, for any realization
$(\bar{x}_{0:T},s_{0:T},y_{0:T})$ of $(\bar{X}_{0:T},S_{0:T},Y_{0:T})$, we
have that

$\mathds{P}(Y_{t}=y_{t}\mid\bar{X}_{0:t}=\bar{x}_{0:t},S_{0:t}=s_{0:t})\\\
=\mathds{P}(Y_{t}=y_{t}\mid\bar{X}_{t}=\bar{x}_{t},S_{t}=s_{t})$ (1)

and

$\mathds{P}(S_{t}=s_{t}\mid\bar{X}_{0:t}=\bar{x}_{0:t},S_{0:t-1}=s_{0:t-1})\\\
=\mathds{P}(S_{t}=s_{t}\mid S_{t-1}=s_{t-1})=Q_{s_{t-1}s_{t}}$ (2)

Note that the channel output $Y_{t}$ is a deterministic function of the input
$\bar{X}_{t}$ and the state $S_{t}$. In particular, for any
$\bar{x}\in\bar{\mathcal{X}}$ and $s\in\\{0,1\\}$, the channel output $y$ is
given as follows:

$y=\begin{cases}\bar{x},&\text{if $\bar{x}\in\mathcal{X}$ and $s=1$}\\\
\mathfrak{E}_{1},&\text{if $\bar{x}=\mathfrak{E}$ and $s=1$}\\\
\mathfrak{E}_{0},&\text{if $s=0$}\end{cases}$

This means that if there is a transmission (i.e., $\bar{x}\in\mathcal{X}$) and
the channel is on (i.e., $s=1$), then the receiver observes $\bar{x}$.
However, if there is no transmission (i.e., $\bar{x}=\mathfrak{E}$) and the
channel is on (i.e., $s=1$), then the receiver observes $\mathfrak{E}_{1}$, if
the channel is off, then the receiver observes $\mathfrak{E}_{0}$.

####  I-B3 The transmitter

There is no need for channel coding in a remote-estimation setup. Instead, the
role of the transmitter is to determine which source realizations need to be
transmitted. Let $U_{t}\in\\{0,1\\}$ denote the transmitter’s decision. We use
the convention that $U_{t}=0$ denotes that there is no transmission (i.e.,
$\bar{X}_{t}=\mathfrak{E}$) and $U_{1}=1$ denotes that there is transmission
(i.e., $\bar{X}_{t}=X_{t}$).

Transmission is costly. Each time the transmitter transmits (i.e., $U_{t}=1$),
it incurs a cost of $\lambda$.

####  I-B4 The receiver

At time $t$, the receiver generates an estimate $\hat{X}_{t}\in\mathcal{X}$ of
$X_{t}$. The quality of the estimate is determined by a distortion function
$d\colon\mathcal{X}\times\mathcal{X}\to\mathds{R}_{\geq 0}$.

###  I-C Information structure and problem formulation

It is assumed that the receiver observes the channel state causally. Thus, the
information available at the receiver111We use superscript $1$ to denote
variables at the transmitter and superscript $2$ to denote variables at the
receiver. is

$I^{2}_{t}=\\{S_{0:t},Y_{0:t}\\}.$

The estimate $\hat{X}_{t}$ is chosen according to

$\hat{X}_{t}=g_{t}(I^{2}_{t})=g_{t}(S_{0:t},Y_{0:t}),$ (3)

where $g_{t}$ is called the _estimation rule_ at time $t$. The collection
$\bm{g}\coloneqq(g_{1},\dots,g_{T})$ for all time is called the _estimation
strategy_.

It is assumed that there is one-step delayed feedback from the receiver to the
transmitter.222Note that feedback requires two bits: the channel state $S_{t}$
is binary and the channel output $Y_{t}$ can be communicated by indicating
whether $Y_{t}\in\mathcal{X}$ or not (i.e., transmitting an ack or a nack).
Thus, the information available at the transmitter is

$I^{1}_{t}=\\{X_{0:t},U_{0:t-1},S_{0:t-1},Y_{0:t-1}\\}.$

The transmission decision $U_{t}$ is chosen according to

$U_{t}=f_{t}(I^{1}_{t})=f_{t}(X_{0:t},U_{0:t-1},S_{0:t-1},Y_{0:t-1}),$ (4)

where $f_{t}$ is called the _transmission rule_ at time $t$. The collection
$\bm{f}\coloneqq(f_{1},\dots,f_{T})$ for all time is called the _transmission
strategy_.

The collection $(\bm{f},\bm{g})$ is called a _communication strategy_. The
performance of any communication strategy $(\bm{f},\bm{g})$ is given by

$J(\bm{f},\bm{g})=\mathds{E}\bigg{[}\sum_{t=0}^{T}\lambda
U_{t}+d(X_{t},\hat{X}_{t})\bigg{]}$ (5)

where the expectation is taken with respect to the joint measure on all system
variables induced by the choice of $(\bm{f},\bm{g})$.

We are interested in the following optimization problem.

######  Problem 1.

In the model described above, identify a communication strategy
$(\bm{f}^{*},\bm{g}^{*})$ that minimizes the cost $J(\bm{f},\bm{g})$ defined
in (5).

##  II Main results

###  II-A Structure of optimal communication strategies

Two-types of structural results are established in the real-time communication
literature: (i) establishing that part of the data at the transmitter is
irrelevant and can be dropped without any loss of optimality; (ii)
establishing that the common information between the transmitter and the
receiver can be “compressed” using a belief state. The first structural
results were first established by Witsenhausen [12] while the second
structural results were first established by Walrand Varaiya [13].

We establish both types of structural results for remote estimation. First, we
show that $(X_{0:t-1},U_{0:t-1})$ is irrelevant at the transmitter (Lemma 1);
then, we use the common information approach of [19] and establish a belief-
state for the common information $(S_{0:t},Y_{0:t})$ between the transmitter
and the receiver (Theorem 1).

######  Lemma 1.

For any estimation strategy of the form (3), there is no loss of optimality in
restricting attention to transmission strategies of the form

$U_{t}=f_{t}(X_{t},S_{0:t-1},Y_{0:t-1}).$ (6)

The proof idea is similar to [14]. We show that
$\\{X_{t},S_{0:t-1},Y_{0:t-1}\\}_{t\geq 0}$ is a controlled Markov process
controlled by $\\{U_{t}\\}_{t\geq 0}$. See Section III for proof.

Now, following [19], for any transmission strategy $\bm{f}$ of the form (6)
and any realization $(s_{0:T},y_{0:T})$ of $(S_{0:T},Y_{0:T})$, define
$\varphi_{t}\colon\mathcal{X}\to\\{0,1\\}$ as

$\varphi_{t}(x)=f_{t}(x,s_{0:t-1},y_{0:t-1}),\quad\forall x\in\mathcal{X}.$

Furthermore, define conditional probability measures $\pi^{1}_{t}$ and
$\pi^{2}_{t}$ on $\mathcal{X}$ as follows: for any $x\in\mathcal{X}$,

$\displaystyle\pi^{1}_{t}(x)$
$\displaystyle\coloneqq\mathds{P}^{\bm{f}}(X_{t}=x\mid
S_{0:t-1}=s_{0:t-1},Y_{0:t-1}=y_{0:t-1}),$ $\displaystyle\pi^{2}_{t}(x)$
$\displaystyle\coloneqq\mathds{P}^{\bm{f}}(X_{t}=x\mid
S_{0:t}=s_{0:t},Y_{0:t}=y_{0:t}).$

We call $\pi^{1}_{t}$ the _pre-transmission belief_ and $\pi^{2}$ the _post-
transmission belief_. Note that when $(S_{0:T},Y_{0:T})$ are random variables,
then $\pi^{1}_{t}$ and $\pi^{2}_{t}$ are also random variables which we denote
by $\Pi^{1}_{t}$ and $\Pi^{2}_{t}$.

For the ease of notation, for any $\varphi\colon\mathcal{X}\to\\{0,1\\}$ and
$i\in\\{0,1\\}$, define the following:

  * •

$B_{i}(\varphi)=\\{x\in\mathcal{X}:\varphi(x)=i\\}$.

  * •

For any probability distribution $\pi$ on $\mathcal{X}$ and any subset
$\mathcal{A}$ of $\mathcal{X}$, $\pi(\mathcal{A})$ denotes
$\sum_{x\in\mathcal{A}}\pi(x)$.

  * •

For any probability distribution $\pi$ on $\mathcal{X}$, $\xi=\pi|_{\varphi}$
means that $\xi(x)=\mathds{1}_{\\{\varphi(x)=0\\}}\pi(x)/\pi(B_{0}(\varphi))$.

######  Lemma 2.

Given any transmission strategy $\bm{f}$ of the form (6):

  1. 1.

there exists a function $F^{1}$ such that

$\pi^{1}_{t+1}=F^{1}(\pi^{2}_{t})=\pi^{2}_{t}P.$ (7)

  2. 2.

there exists a function $F^{2}$ such that

$\pi^{2}_{t}=F^{2}(\pi^{1}_{t},\varphi_{t},y_{t}).$ (8)

In particular,

$\pi^{2}_{t}=\begin{cases}\delta_{y_{t}}&\mbox{if $y_{t}\in\mathcal{X}$}\\\
\pi^{1}_{t}|_{\varphi_{t}},&\mbox{if $y_{t}=\mathfrak{E}_{1}$}\\\
\pi^{1}_{t},&\mbox{if $y_{t}=\mathfrak{E}_{0}$}.\end{cases}$ (9)

Note that in (7), we are treating $\pi^{2}_{t}$ as a row-vector and in (9),
$\delta_{y_{t}}$ denotes a Dirac measure centered at $y_{t}$. The update
equations (7) and (8) are standard non-linear filtering equations. See Section
III for proof.

######  Theorem 1.

In Problem 1, we have that:

  1. 1.

_Structure of optimal strategies:_ There is no loss of optimality in
restricting attention to optimal transmission and estimation strategies of the
form:

$\displaystyle U_{t}$ $\displaystyle=f^{*}_{t}(X_{t},S_{t-1},\Pi^{1}_{t}),$
(10) $\displaystyle\hat{X}_{t}$ $\displaystyle=g^{*}_{t}(\Pi^{2}_{t}).$ (11)

  2. 2.

_Dynamic program:_ Let $\Delta(\mathcal{X})$ denote the space of probability
distributions on $\mathcal{X}$. Define value functions
$V^{1}_{t}\colon\\{0,1\\}\times\Delta(\mathcal{X})\to\mathds{R}$ and
$V^{2}_{t}\colon\\{0,1\\}\times\Delta(\mathcal{X})\to\mathds{R}$ as follows.

$\displaystyle V^{1}_{T+1}(s,\pi^{1})=0,$ (12) and for $t\in\\{T,\dots,0\\}$
$\displaystyle\begin{lgathered}V^{1}_{t}(s,\pi^{1})=\min_{\varphi\colon\mathcal{X}\to\\{0,1\\}}\Big{\\{}\lambda\pi^{1}(B_{1}(\varphi))\\\
\quad{}+W^{0}_{t}(\pi^{1},\varphi)\pi^{1}(B_{0}(\varphi))+\smashoperator[]{\sum_{x\in
B_{1}(\varphi)}^{}}W^{1}_{t}(\pi^{1},\varphi,x)\pi^{1}(x)\Big{\\}}\end{lgathered}V^{1}_{t}(s,\pi^{1})=\min_{\varphi\colon\mathcal{X}\to\\{0,1\\}}\Big{\\{}\lambda\pi^{1}(B_{1}(\varphi))\\\
\quad{}+W^{0}_{t}(\pi^{1},\varphi)\pi^{1}(B_{0}(\varphi))+\smashoperator[]{\sum_{x\in
B_{1}(\varphi)}^{}}W^{1}_{t}(\pi^{1},\varphi,x)\pi^{1}(x)\Big{\\}}$ (15)
$\displaystyle
V^{2}_{t}(s,\pi^{2})=\min_{\hat{x}\in\mathcal{X}}\sum_{x\in\mathcal{X}}d(x,\hat{x})\pi^{2}(x)+V^{1}_{t+1}(s,\pi^{2}P),$
(16)

where,

$\displaystyle W^{0}_{t}(\pi^{1},\varphi)$
$\displaystyle=Q_{s0}V^{2}_{t}(0,\pi^{1})+Q_{s1}V^{2}_{t}(1,\pi^{1}|_{\varphi}),$
$\displaystyle W^{1}_{t}(\pi^{1},\varphi,x)$
$\displaystyle=Q_{s0}V^{2}_{t}(0,\pi^{1})+Q_{s1}V^{2}_{t}(1,\delta_{x}).$

Let $\Psi_{t}(s,\pi^{1})$ denote the arg min of the right hand side of (15).
Then, the optimal transmission strategy of the form (10) is given by

$f^{*}_{t}(\cdot,s,\pi^{1})=\Psi_{t}(s,\pi^{1}).$

Furthermore, the optimal estimation strategy of the form (11) is given by

$g^{*}_{t}(\pi^{2})=\arg\min_{\hat{x}\in\mathcal{X}}\sum_{x\in\mathcal{X}}d(x,\hat{x})\pi^{2}(x).$
(17)

The proof idea is as follows. Once we restrict attention to transmission
strategies of the form (6), the information structure is partial history
sharing [19]. Thus, one can use the common information approach of [19] and
obtain the structure of optimal strategies. See Section III for proof.

######  Remark 1.

The first term in (15) is the expected communication cost, the second term is
the expected cost-to-go when the transmitter does not transmit, and the third
term is the expected cost-to-go when the transmitter transmits. The first term
in (16) is the expected distortion and the second term is the expected cost-
to-go.

######  Remark 2.

Although the above model and result are stated for sources with finite
alphabets, they extend naturally to general state spaces (including Euclidean
spaces) under standard technical assumptions. See [20] for details.

###  II-B Optimality of threshold-based strategies for autoregressive source

In this section, we consider a first-order autoregressive source
$\\{X_{t}\\}_{t\geq 0}$, $X_{t}\in\mathds{R}$, where the initial state
$X_{0}=0$ and for $t\geq 0$, we have that

$X_{t+1}=aX_{t}+W_{t},$ (18)

where $a\in\mathds{R}$ and $W_{t}\in\mathds{R}$ is distributed according to a
symmetric and unimodal distribution with probability density function $\mu$.
Furthermore, the per-step distortion is given by $d(X_{t}-\hat{X}_{t})$, where
$d(\cdot)$ is a even function that is increasing on $\mathds{R}_{\geq 0}$. The
rest of the model is the same as before.

For the above model, we can further simplify the result of Theorem 1. See
Section IV for the proof.

######  Theorem 2.

For a first-order autoregressive source with symmetric and unimodal
disturbance,

  1. 1.

_Structure of optimal estimation strategy:_ The optimal estimation strategy is
given as follows: $\hat{X}_{0}=0$, and for $t\geq 0$,

$\hat{X}_{t}=\begin{cases}a\hat{X}_{t-1},&\mbox{if
$Y_{t}\in\mathcal{\\{}\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$}\\\
Y_{t},&\mbox{if $Y_{t}\in\mathds{R}$}\end{cases}$ (19)

  2. 2.

_Structure of optimal transmission strategy:_ There exist threshold functions
$k_{t}\colon\\{0,1\\}\to\mathds{R}_{\geq 0}$ such that the following
transmission strategy is optimal:

$f_{t}(X_{t},S_{t-1},\Pi^{1}_{t})=\begin{cases}1,&\mbox{if
$|X_{t}-a\hat{X}_{t-1}|\geq k_{t}(S_{t-1})$}\\\
0,&\mbox{otherwise}.\end{cases}$ (20)

######  Remark 3.

As long as the receiver can distinguish between the events $\mathfrak{E}_{0}$
(i.e., $S_{t}=0$) and $\mathfrak{E}_{1}$ (i.e., $U_{t}=0$ and $S_{t}=1$), the
structure of the optimal estimator does not depend on the channel state
information at the receiver.

######  Remark 4.

It can be shown that under the optimal strategy, $\Pi^{2}_{t}$ is symmetric
and unimodal around $\hat{X}_{t}$ and, therefore, $\Pi^{1}_{t}$ is symmetric
and unimodal around $a\hat{X}_{t-1}$. Thus, the transmission and estimation
strategies in Theorem 2 depend on the pre- and post-transmission beliefs only
through their means.

######  Remark 5.

Recall that the distortion function is even and increasing. Therefore, the
condition $|X_{t}-a\hat{X}_{t-1}|\geq k_{t}(S_{t-1})$ can be written as
$d(X_{t}-a\hat{X}_{t-1})\geq\tilde{k}_{t}(S_{t-1})\coloneqq
d(k_{t}(S_{t-1}))$. Thus, the optimal strategy is to transmit if the per-step
distortion due to not transmitting is greater than a threshold.

##  III Proof of the structural results

###  III-A Proof of Lemma 1

Arbitrarily fix the estimation strategy $\bm{g}$ and consider the _best
response_ strategy at the transmitter. We will show that
$\tilde{I}^{1}_{t}\coloneqq(X_{t},S_{0:t-1},Y_{0:t-1})$ is an information
state at the transmitter.

Given any realization $(x_{0:T},s_{0:T},y_{0:T},u_{0:T})$ of the system
variables $(X_{0:T},S_{0:T},Y_{0:T},U_{0:T})$, define
$i^{1}_{t}=(x_{0:t},s_{0:t-1},y_{0:t-1},\allowbreak u_{0:t-1})$ and
$\tilde{\imath}^{1}_{t}=(x_{t},s_{0:t-1},y_{0:t-1})$. Now, for any
$\breve{\imath}^{1}_{t+1}=(\breve{x}_{t+1},\breve{s}_{0:t},\breve{y}_{0:t})=(\breve{x}_{t+1},\breve{s}_{t},\breve{y}_{t},\breve{\imath}^{1}_{t})$,
we use the shorthand
$\mathds{P}(\tilde{\imath}^{1}_{t+1}|\tilde{\imath}^{1}_{0:t},u_{0:t})$ to
denote
$\mathds{P}(\tilde{I}^{1}_{t+1}=\breve{\imath}^{1}_{t+1}|\tilde{I}^{1}_{0:t}=\tilde{i}^{1}_{0:t},U_{0:t}=u_{0:t})$.
Then,

$\displaystyle\hskip-20.00003pt\mathds{P}(\breve{\imath}^{1}_{t+1}|i^{1}_{t},u_{t})=\mathds{P}(\breve{x}_{t+1},\breve{s}_{t},\breve{y}_{t},\breve{\imath}^{1}_{t}|x_{0:t},s_{0:t-1},y_{0:t-1},u_{0:t})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathds{P}(\breve{x}_{t+1},\breve{s}_{t},\breve{y}_{t},\breve{\imath}^{1}_{t}|x_{0:t},\bar{x}_{0:t},s_{0:t-1},y_{0:t-1},u_{0:t})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\mathds{P}(\breve{x}_{t+1}|x_{t})\mathds{P}(\breve{y}_{t}|\bar{x}_{t},\breve{s}_{t})\mathds{P}(\breve{s}_{t}|s_{t-1})\mathds{1}_{\\{\breve{\imath}^{1}_{t}=\tilde{\imath}^{1}_{t}\\}}$
$\displaystyle=\mathds{P}(\breve{\imath}^{1}_{t+1}|\tilde{\imath}^{1}_{t},u_{t})$
(21)

where we have added $\bar{x}_{0:t}$ in the conditioning in $(a)$ because
$\bar{x}_{0:t}$ is a deterministic function of $(x_{0:t},u_{0:t})$ and $(b)$
follows from the source and the channel models. By marginalizing (21), we get
that for any
$\breve{\imath}^{2}_{t}=(\breve{s}_{t},\breve{y}_{t},\breve{\imath}^{1}_{t})$,
we have

$\mathds{P}(\breve{\imath}^{2}_{t}|i^{1}_{t},u_{t})=\mathds{P}(\breve{\imath}^{2}_{t}|\tilde{\imath}^{1}_{t},u_{t})$
(22)

Now, let $c(X_{t},U_{t},\hat{X}_{t})=\lambda U_{t}+d(X_{t},\hat{X}_{t})$
denote the per-step cost. Recall that $\hat{X}_{t}=g_{t}(I^{2}_{t})$. Thus, by
(22), we get that

$\mathds{E}[c(X_{t},U_{t},\hat{X}_{t})|i^{1}_{t},u_{t}]=\mathds{E}[c(X_{t},U_{t},\hat{X}_{t})|\tilde{\imath}^{1}_{t},u_{t}].$
(23)

Eq. (21) shows that $\\{\tilde{I}^{1}_{t}\\}_{t\geq 0}$ is a controlled Markov
process controlled by $\\{U_{t}\\}_{t\geq 0}$. Eq. (23) shows that
$\tilde{I}^{1}_{t}$ is sufficient for performance evaluation. Hence, by Markov
decision theory [21], there is no loss of optimality in restricting attention
to transmission strategies of the form (6).

###  III-B Proof of Lemma 2

Consider

$\displaystyle\pi^{1}_{t+1}(x_{t+1})$
$\displaystyle=\mathds{P}(x_{t+1}|s_{0:t},y_{0:t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\mathds{P}(x_{t+1}|x_{t})\mathds{P}(x_{t}|s_{0:t},y_{0:t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}P_{x_{t}x_{t+1}}\pi^{2}_{t}(x_{t})=\pi^{2}_{t}P$
(24)

which is the expression for $F^{1}(\cdot)$.

For $F^{2}$, we consider the three cases separately. For
$y_{t}\in\mathcal{X}$, we have

$\pi^{2}_{t}(x)=\mathds{P}(X_{t}=x|s_{0:t},y_{0:t})=\mathds{1}_{\\{x=y_{t}\\}}.$
(25)

For $y_{t}\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$, we have

$\displaystyle\pi^{2}_{t}(x)$
$\displaystyle=\mathds{P}(X_{t}=x|s_{0:t},y_{0:t})$
$\displaystyle=\frac{\mathds{P}(X_{t}=x,y_{t},s_{t}|s_{0:t-1},y_{0:t-1})}{\mathds{P}(y_{t},s_{t}|s_{0:t-1},y_{0:t-1})}$
(26)

Now, when $y_{t}=\mathfrak{E}_{0}$, we have that

$\displaystyle\hskip-20.00003pt\mathds{P}(x_{t},y_{t},s_{t}|s_{0:t-1},y_{0:t-1})=\mathds{P}(y_{t}|x_{t},\varphi_{t}(x_{t}),s_{t})Q_{s_{t-1}s_{t}}\pi^{1}_{t}(x_{t})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\begin{cases}Q_{s_{t-1}1}\pi^{1}_{t}(x_{t}),&\text{if
$\varphi_{t}(x_{t})=0$ and $s_{t}=1$}\\\ 0,&\text{otherwise}\end{cases}$ (27)

where $(a)$ is obtained from the channel model. Substituting (27) in (26) and
canceling $Q_{s_{t-1}1}\mathds{1}_{\\{s_{t}=1\\}}$ from the numerator and the
denominator, we get (recall that this is for the case when
$y_{t}=\mathfrak{E}_{0}$),

$\displaystyle\pi^{2}_{t}(x)$
$\displaystyle=\frac{\mathds{1}_{\\{\varphi_{t}(x)=0\\}}\pi^{1}_{t}(x)}{\pi^{1}_{t}(B_{0}(\varphi))}.$
(28)

Similarly, when $y_{t}=\mathfrak{E}_{1}$, we have that

$\displaystyle\hskip-20.00003pt\mathds{P}(x_{t},y_{t},s_{t}|s_{0:t-1},y_{0:t-1})=\mathds{P}(y_{t}|x_{t},\varphi_{t}(x_{t}),s_{t})Q_{s_{t-1}s_{t}}\pi^{1}_{t}(x_{t})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\begin{cases}Q_{s_{t-1}0}\pi^{1}_{t}(x_{t}),&\text{if
$s_{t}=0$}\\\ 0,&\text{otherwise}\end{cases}$ (29)

where $(b)$ is obtained from the channel model. Substituting (29) in (26) and
canceling $Q_{s_{t-1}0}\mathds{1}_{\\{s_{t}=0\\}}$ from the numerator and the
denominator, we get (recall that this is for the case when
$y_{t}=\mathfrak{E}_{1}$),

$\pi^{2}_{t}(x)=\pi^{1}_{t}(x).$ (30)

By combining (25), (28) and (30), we get (9).

###  III-C Proof of Theorem 1

Once we restrict attention to transmission strategies of the form (6), the
information structure is partial history sharing [19]. Thus, one can use the
common information approach of [19] and obtain the structure of optimal
strategies.

Following [19], we split the information available at each agent into a
“common information” and “local information”. Common information is the
information available to all decision makers in the future; the remaining data
at the decision maker is the local information. Thus, at the transmitter, the
common information is $C^{1}_{t}\coloneqq\\{S_{0:t-1},Y_{0:t-1}\\}$ and the
local information is $L^{1}_{t}\coloneqq X_{t}$. Similarly, at the receiver,
the common information is $C^{2}_{t}\coloneqq\\{S_{0:t},Y_{0:t}\\}$ and the
local information is $L^{2}_{t}\coloneqq\emptyset$. When the transmitter makes
a decision, the state (sufficient for input output mapping) of the system is
$(X_{t},S_{t-1})$; when the receiver makes a decision, the state of the system
is $(X_{t},S_{t})$. By [19, Proposition 1], we get that the sufficient
statistic $\Theta^{1}_{t}$ for the common information at the transmitter is

$\Theta^{1}_{t}(x,s)=\mathds{P}(X_{t}=x,S_{t-1}=s|S_{0:t-1},Y_{0:t-1}),$

and the sufficient statistic $\Theta^{2}_{t}$ for the common information at
the receiver is

$\Theta^{2}_{t}(x,s)=\mathds{P}(X_{t}=x,S_{t}=s|S_{0:t},Y_{0:t}).$

Note that $\Theta^{1}_{t}$ is equivalent to $(\Pi^{1}_{t},S_{t-1})$ and
$\Theta^{2}_{t}$ is equivalent to $(\Pi^{2}_{t},S_{t})$. Therefore, by [19,
Theorem 2], there is no loss of optimality in restricting attention to
transmission strategies of the form (10) and estimation strategies of the form

$\hat{X}_{t}=g_{t}(S_{t},\Pi^{2}_{t}).$ (31)

Furthermore, the dynamic program of 1 follows from [19, Theorem 3].

Note that the right hand side of (16) implies that $\hat{X}_{t}$ does not
depend on $S_{t}$. Thus, instead of (31), we can restrict attention to
estimation strategy of the form (11). Furthermore, the optimal estimation
strategy is given by (17).

##  IV Proof of optimality of threshold-based strategies for autoregressive
source

###  IV-A A change of variables

Define a process $\\{Z_{t}\\}_{t\geq 0}$ as follows: $Z_{0}=0$ and for $t\geq
0$,

$Z_{t}=\begin{cases}aZ_{t-1},&\mbox{if
$Y_{t}\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$}\\\ Y_{t},&\mbox{if
$Y_{t}\in\mathcal{X}$}\end{cases}$

Note that $Z_{t}$ is a function of $Y_{0:t-1}$. Next, define processes
$\\{E_{t}\\}_{t\geq 0}$, $\\{E^{+}_{t}\\}_{t\geq 0}$, and
$\\{\hat{E}_{t}\\}_{t\geq 0}$ as follows:

$E_{t}\coloneqq X_{t}-aZ_{t-1},\quad E^{+}_{t}\coloneqq
X_{t}-Z_{t},\quad\hat{E}_{t}\coloneqq\hat{X}_{t}-Z_{t}$

The processes $\\{E_{t}\\}_{t\geq 0}$ and $\\{E^{+}_{t}\\}_{t\geq 0}$ are
related as follows: $E_{0}=0$, $E^{+}_{0}=0$, and for $t\geq 0$

$\displaystyle E^{+}_{t}$ $\displaystyle=\begin{cases}E_{t},&\mbox{if
$Y_{t}\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$}\\\ 0,&\mbox{if
$Y_{t}\in\mathcal{X}$}\end{cases}$ and $\displaystyle E_{t+1}$
$\displaystyle=aE^{+}_{t}+W_{t}.$

Since $X_{t}-\hat{X}_{t}=E^{+}_{t}-\hat{E}_{t}$, we have that
$d(X_{t}-\hat{X}_{t})=d(E^{+}_{t}-\hat{E}_{t})$.

It turns out that it is easier to work with the processes $\\{E_{t}\\}_{t\geq
0}$, $\\{E^{+}_{t}\\}_{t\geq 0}$, and $\\{\hat{E}_{t}\\}_{t\geq 0}$ rather
than $\\{X_{t}\\}_{t\geq 0}$ and $\\{\hat{X}_{t}\\}_{t\geq 0}$.

Next, redefine the pre- and post-transmission beliefs in terms of the error
process. With a slight abuse of notation, we still denote the (probability
density) of the pre- and post-transmission beliefs as $\pi^{1}_{t}$ and
$\pi^{2}_{t}$. In particular, $\pi^{1}_{t}$ is the conditional pdf of $E_{t}$
given $(s_{0:t-1},y_{0:t-1})$ and $\pi^{2}_{t}$ is the conditional pdf of
$E^{+}_{t}$ given $(s_{0:t},y_{0:t})$.

Let $H_{t}\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1},1\\}$ denote the event
whether the transmission was successful or not. In particular,

$H_{t}=\begin{cases}\mathfrak{E}_{0},&\mbox{if $Y_{t}=\mathfrak{E}_{0}$}\\\
\mathfrak{E}_{1},&\mbox{if $Y_{t}=\mathfrak{E}_{1}$}\\\ 1,&\mbox{if
$Y_{t}\in\mathds{R}$}.\end{cases}$

We use $h_{t}$ to denote the realization of $H_{t}$. Note that $H_{t}$ is a
deterministic function of $U_{t}$ and $S_{t}$.

The time-evolutions of $\pi^{1}_{t}$ and $\pi^{2}_{t}$ is similar to Lemma 2.
In particular, we have

######  Lemma 3.

Given any transmission strategy $\bm{f}$ of the form (4):

  1. 1.

there exists a function $F^{1}$ such that

$\pi^{1}_{t+1}=F^{1}(\pi^{2}_{t}).$ (32)

In particular,

$\pi^{1}_{t+1}=\begin{cases}\tilde{\pi}^{2}_{t}\star\mu,&\mbox{if
$y_{t}\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1}\\}$}\\\ \mu,&\mbox{if
$y_{t}\in\mathds{R}$},\end{cases}$ (33)

where $\tilde{\pi}^{2}_{t}$ given by
$\tilde{\pi}^{2}_{t}(e)\coloneqq(1/|a|)\pi^{2}_{t}(e/a)$ is the conditional
probability density of $aE^{+}_{t}$, $\mu$ is the probability density function
of $W_{t}$ and $\star$ is the convolution operation.

  2. 2.

there exists a function $F^{2}$ such that

$\pi^{2}_{t}=F^{2}(\pi^{1}_{t},\varphi_{t},h_{t}).$ (34)

In particular,

$\pi^{2}_{t}=\begin{cases}\delta_{0},&\mbox{if $h_{t}=1$}\\\
\pi^{1}_{t}|_{\varphi_{t}},&\mbox{if $h_{t}=\mathfrak{E}_{1}$}\\\
\pi^{1}_{t},&\mbox{if $h_{t}=\mathfrak{E}_{0}$}.\end{cases}$ (35)

The key difference between Lemmas 2 and 3 (and the reason that we work with
the error process $\\{E_{t}\\}_{t\geq 0}$ rather than $\\{X_{t}\\}_{t\geq 0}$)
is that the function $F^{2}$ in (34) depends on $h_{t}$ rather than $y_{t}$.
Consequently, the dynamic program of Theorem 1 is now given by

$\displaystyle V^{1}_{T+1}(s,\pi^{1})=0,$ (36) and for $t\in\\{T,\dots,0\\}$
$\displaystyle\begin{lgathered}V^{1}_{t}(s,\pi^{1})=\min_{\varphi\colon\mathds{R}\to\\{0,1\\}}\Big{\\{}\lambda\pi^{1}(B_{1}(\varphi))\\\
\quad{}+W^{0}_{t}(\pi^{1},\varphi)\pi^{1}(B_{0}(\varphi))+W^{1}_{t}(\pi^{1},\varphi)\pi^{1}(B_{1}(\varphi))\Big{\\}}\end{lgathered}V^{1}_{t}(s,\pi^{1})=\min_{\varphi\colon\mathds{R}\to\\{0,1\\}}\Big{\\{}\lambda\pi^{1}(B_{1}(\varphi))\\\
\quad{}+W^{0}_{t}(\pi^{1},\varphi)\pi^{1}(B_{0}(\varphi))+W^{1}_{t}(\pi^{1},\varphi)\pi^{1}(B_{1}(\varphi))\Big{\\}}$
(39) $\displaystyle
V^{2}_{t}(s,\pi^{2})=D(\pi^{2})+V^{1}_{t+1}(s,F^{1}(\pi^{2})),$ (40)

where,

$\displaystyle W^{0}_{t}(\pi^{1},\varphi)$
$\displaystyle=Q_{s0}V^{2}_{t}(0,\pi^{1})+Q_{s1}V^{2}_{t}(1,\pi^{1}|_{\varphi}),$
$\displaystyle W^{1}_{t}(\pi^{1},\varphi)$
$\displaystyle=Q_{s0}V^{2}_{t}(0,\pi^{1})+Q_{s1}V^{2}_{t}(1,\delta_{0}),$
$\displaystyle D(\pi^{2})$
$\displaystyle=\min_{\hat{e}\in\mathds{R}}\int_{\mathds{R}}d(e-\hat{e})\pi^{2}(e)de.$

Again, note that due to the change of variables, the expression for
$W^{1}_{t}$ does not depend on the transmitted symbol. Consequently, the
expression for $V^{1}_{t}$ is simpler than that in Theorem 1.

###  IV-B Symmetric unimodal distributions and their properties

A probability density function $\pi$ on reals is said to be _symmetric and
unimodal ( $\mathrm{SU}$)_ around $c\in\mathds{R}$ if for any
$x\in\mathds{R}$, $\pi(c-x)=\pi(c+x)$ and $\pi$ is non-decreasing in the
interval $(-\infty,c]$ and non-increasing in the interval $[c,\infty)$.

Given $c\in\mathds{R}$, a prescription $\varphi\colon\mathds{R}\to\\{0,1\\}$
is called _threshold based around $c$_ if there exists $k\in\mathds{R}$ such
that

$\varphi(e)=\begin{cases}1,&\mbox{if $|e-c|\geq k$}\\\ 0,&\mbox{if
$|e-c|<k$}.\end{cases}$

Let $\mathcal{F}(c)$ denote the family of all threshold-based prescription
around $c$.

Now, we state some properties of symmetric and unimodal distributions..

######  Property 1.

If $\pi$ is $\mathrm{SU}(c)$, then

$c\in\arg\min_{\hat{e}\in\mathds{R}}\int_{\mathds{R}}d(e-\hat{e})\pi(e)de.$

For $c=0$, the above property is a special case of [5, Lemma 12]. The result
for general $c$ follows from a change of variables.

######  Property 2.

If $\pi^{1}$ is $\mathrm{SU}(0)$ and $\varphi\in\mathcal{F}(0)$, then for any
$h\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1},1\\}$, $F^{2}(\pi^{1},\varphi,h)$ is
$\mathrm{SU}(0)$.

######  Proof:.

We prove the result for each $h\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1},1\\}$
separately. Recall the update of $\pi^{1}$ given by (35). For
$h_{t}=\mathfrak{E}_{0}$, $\pi^{2}=\pi^{1}$ and hence $\pi^{2}$ is
$\mathrm{SU}(0)$. For $h_{t}=\mathfrak{E}_{1}$, $\pi^{2}=\pi^{1}|_{\varphi}$;
if $\varphi\in\mathcal{F}(0)$, then
$\pi^{1}(x)\mathds{1}_{\\{\varphi(x)=0\\}}$ is $\mathrm{SU}(0)$ and hence
$\pi^{1}$ is $\mathrm{SU}(0)$. For $h_{t}=1$, $\pi^{2}=\delta_{0}$, which is
$\mathrm{SU}(0)$.

######  Property 3.

If $\pi^{2}$ is $\mathrm{SU}(0)$, then $F^{1}(\pi^{2})$ is also
$\mathrm{SU}(0)$.

######  Proof:.

Recall that $F^{1}$ is given by (33). The property follows from the fact that
convolution of symmetric and unimodal distributions is symmetric and unimodal.

###  IV-C $\mathrm{SU}$ majorization and its properties

For any set $\mathcal{A}$, let $\mathcal{I}_{\mathcal{A}}$ denote its
indicator function, i.e., $\mathcal{I}_{\mathcal{A}}(x)$ is $1$ if
$x\in\mathcal{X}$, else $0$.

Let $\mathcal{A}$ be a measurable set of finite Lebesgue measure, its
_symmetric rearrangement_ $\mathcal{A}^{\sigma}$ is the open interval centered
around origin whose Lebesgue measure is same as $\mathcal{A}$.

Given a function $\ell\colon\mathds{R}\to\mathds{R}$, its super-level set at
level $\rho$, $\rho\in\mathds{R}$, is $\\{x\in\mathds{R}:\ell(x)>\rho\\}$. The
_symmetric decreasing rearrangement_ $\ell^{\sigma}$ of $\ell$ is a symmetric
and decreasing function whose level sets are the same as $\ell$, i.e.,

$\ell^{\sigma}(x)=\int_{0}^{\infty}\mathcal{I}_{\\{z\in\mathds{R}:\ell(z)>\rho\\}^{\sigma}}(x)d\rho.$

Given two probability density functions $\xi$ and $\pi$ over $\mathds{R}$,
$\xi$ _majorizes_ $\pi$, which is denoted by $\xi\succeq_{m}\pi$, if for all
$\rho\geq 0$,

$\int_{|x|\geq\rho}\xi^{\sigma}(x)dx\geq\int_{|x|\geq\rho}\pi^{\sigma}(x)dx.$

Given two probability density functions $\xi$ and $\pi$ over $\mathds{R}$,
$\xi$ _SU majorizes_ $\pi$, which we denote by $\xi\succeq_{a}\pi$, if $\xi$
is $\mathrm{SU}$ and $\xi$ majorizes $\pi$.

Now, we state some properties of SU majorization from [5].

######  Property 4.

For any $\xi\succeq_{a}\pi$, where $\xi$ is $\mathrm{SU}(c)$ and for any
prescription $\varphi$, let $\theta\in\mathcal{F}(c)$ be a threshold-based
prescription such that

$\xi(B_{i}(\theta))=\pi(B_{i}(\varphi)),\quad i\in\\{0,1\\}.$

Then, $\xi|_{\theta}\succeq_{a}\pi|_{\varphi}.$ Consequently, for any
$h\in\\{\mathfrak{E}_{0},\mathfrak{E}_{1},1\\}$,

$F^{2}(\xi,\theta,h)\succeq_{a}F^{2}(\pi,\varphi,h).$

For $c=0$, the result follows from [5, Lemma 7 and 8]. The result for general
$c$ follows from change of variables.

######  Property 5.

For any $\xi\succeq_{m}\pi$, $F^{1}(\xi)\succeq_{a}F^{1}(\pi)$.

This follows from [5, Lemma 10].

Recall the definition of $D(\pi^{2})$ given after (40).

######  Property 6.

If $\xi\succeq_{a}\pi$, then

$D(\pi)\geq D(\pi^{\sigma})\geq D(\xi^{\sigma})=D(\xi).$

This follows from [5, Lemma 11].

###  IV-D Qualitative properties of the value function and optimal strategy

######  Lemma 4.

The value functions $V^{1}_{t}$ and $V^{2}_{t}$ of (36)–(40), satisfy the
following property.

  1. (P1)

For any $i\in\\{1,2\\}$, $s\in\\{0,1\\}$, $t\in\\{0,\dots,T\\}$, and pdfs
$\xi^{i}$ and $\pi^{i}$ such that $\xi^{i}\succeq_{a}\pi^{i}$, we have that
$V^{i}_{t}(s,\xi^{i})\leq V^{i}_{t}(s,\pi^{i})$.

Furthermore, the optimal strategy satisfies the following properties. For any
$s\in\\{0,1\\}$ and $t\in\\{0,\dots,T\\}$:

  1. (P2)

if $\pi^{1}$ is $\mathrm{SU}(c)$, then there exists a prescription
$\varphi_{t}\in\mathcal{F}(c)$ that is optimal. In general, $\varphi_{t}$
depends on $\pi^{1}$.

  2. (P3)

if $\pi^{2}$ is $\mathrm{SU}(c)$, then the optimal estimate $\hat{E}_{t}$ is
$c$.

######  Proof:.

We proceed by backward induction. $V^{1}_{T+1}(s,\pi^{1})$ trivially satisfies
the (P1). This forms the basis of induction. Now assume that
$V^{1}_{t+1}(s,\pi^{1})$ also satisfies (P1). For $\xi^{2}\succeq_{a}\pi^{2}$,
we have that

$\displaystyle V^{2}_{t}(s,\pi^{2})$
$\displaystyle=D(\pi^{2})+V^{1}_{t+1}(s,F^{1}(\pi^{2}))$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}D(\xi^{2})+V^{1}_{t+1}(s,F^{1}(\xi^{2}))$
$\displaystyle=V^{2}_{t}(s,\xi^{2}),$ (41)

where $(a)$ follows from Properties 5 and 6 and the induction hypothesis. Eq.
41 implies that $V^{2}_{t}$ also satisfies (P1).

Now, consider $\xi^{1}\succeq_{a}\pi^{1}$. Let $\varphi$ be the optimal
prescription at $\pi^{1}$. Let $\theta$ be the threshold-based prescription
corresponding to $\varphi$ as defined in Property 3. By construction,

$\pi^{1}(B_{0}(\varphi))=\xi^{1}(B_{0}(\theta))\quad\text{and}\quad\pi^{1}(B_{1}(\varphi))=\xi^{1}(B_{1}(\theta)).$

Moreover, from Property 3 and (41),

$W^{0}_{t}(\pi^{1},\varphi)\geq W^{0}_{t}(\xi^{1},\theta)\quad\text{and}\quad
W^{1}_{t}(\pi^{1},\varphi)\geq W^{1}_{t}(\xi^{1},\theta).$

Combining the above two equations with (39), we get

$\displaystyle V^{1}_{t}(s,\pi^{1})$
$\displaystyle=\lambda\pi^{1}(B_{1}(\varphi))+W^{0}(\pi^{1},\varphi)\pi^{1}(B_{0}(\varphi))$
$\displaystyle\quad+W^{1}(\pi^{1},\varphi)\pi^{1}(B_{1}(\varphi))$
$\displaystyle\geq\lambda\xi^{1}(B_{1}(\theta))+W^{0}(\xi^{1},\theta)\xi^{1}(B_{0}(\theta))$
$\displaystyle\quad+W^{1}(\xi^{1},\theta)\xi^{1}(B_{0}(\theta))$
$\displaystyle\geq V^{1}_{t}(s,\xi^{1})$ (42)

where the last inequality follows by minimizing over all $\theta$. Eq. (42)
implies that $V^{1}_{t}$ also satisfies (P1). Hence, by the principle of
induction, (P1) is satisfied for all time.

The argument in (42) also implies (P2). Furthermore, (P3) follows from
Property 1.

###  IV-E Proof of Theorem 2

We first prove a weaker version of the structure of optimal transmission
strategies. In particular, there exist threshold functions
$\tilde{k}_{t}\colon\\{0,1\\}\times\Delta(\mathds{R})\to\mathds{R}_{\geq 0}$
such that the following transmission strategy is optimal:

$f_{t}(X_{t},S_{t-1},\Pi^{1}_{t})=\begin{cases}1,&\mbox{if
$|X_{t}-aZ_{t-1}|\geq\tilde{k}_{t}(S_{t-1},\Pi^{1}_{t})$}\\\
0,&\mbox{otherwise}.\end{cases}$ (43)

or, equivalently, in terms of the $\\{E_{t}\\}_{t\geq 0}$ process:

$f_{t}(E_{t},S_{t-1},\Pi^{1}_{t})=\begin{cases}1,&\mbox{if
$|E_{t}|\geq\tilde{k}_{t}(S_{t-1},\Pi^{1}_{t})$}\\\
0,&\mbox{otherwise}.\end{cases}$ (44)

We prove (44) by induction. Note that $\pi^{1}_{0}=\delta_{0}$ which is
$\mathrm{SU}(0)$. Therefore, by (P2), there exists a threshold-based
prescription $\varphi_{0}\in\mathcal{F}(0)$ that is optimal. This forms the
basis of induction. Now assume that until time $t-1$, all prescriptions are in
$\mathcal{F}(0)$. By Properties 2 and 3, $\Pi^{1}_{t}$ is $\mathrm{SU}(0)$.
Therefore, by (P2), there exists a threshold-based prescription
$\varphi_{t}\in\mathcal{F}(0)$ that is optimal. This proves the induction step
and, hence, by the principle of induction, threshold-based prescriptions of
the form (44) are optimal for all time. Translating the result back to
$\\{X_{t}\\}_{t\geq 0}$, we get that threshold-based prescriptions of the form
(43) are optimal.

Observe that Properties 2 and 3 also imply that for all $t$, $\Pi^{2}_{t}$ is
$\mathrm{SU}(0)$. Therefore, by Property 1, the optimal estimate
$\hat{E}_{t}=0$. Recall that $\hat{E}_{t}=\hat{X}_{t}-Z_{t}$. Thus,
$\hat{X}_{t}=Z_{t}$. This proves the first part of Theorem 2.

To prove that there exist optimal transmission strategies where the thresholds
do not depend on $\Pi^{1}_{t}$, we fix the estimation strategy to be of the
form (19) and consider the problem of finding the best transmission strategy
at the sensor. This is a single-agent (centralized) stochastic control problem
and the optimal solution is given by the following dynamic program:

$\displaystyle J_{T+1}(e,s)$ $\displaystyle=0$ (45) and for
$t\in\\{T,\dots,0\\}$ $\displaystyle J_{t}(e,s)$
$\displaystyle=\min\\{J^{0}_{t}(e,s),J^{1}_{t}(e,s)\\}$ (46)

where

$\displaystyle J^{0}_{t}(e,s)$
$\displaystyle=d(e)+Q_{s0}\mathds{E}_{W}[J_{t+1}(ae+W,0)]$
$\displaystyle\quad+Q_{s1}\mathds{E}_{W}[J_{t+1}(ae+W,1)],$ (47)
$\displaystyle J^{1}_{t}(e,s)$
$\displaystyle=\lambda+Q_{s0}d(e)+Q_{s0}\mathds{E}_{W}[J_{t+1}(ae+W,0)]$
$\displaystyle\quad+Q_{s1}\mathds{E}_{W}[J_{t+1}(W,1)],$ (48)

We now use the results of [22] to show that the value function even and
increasing on $\mathds{R}_{\geq 0}$ (abbreviated to EI).

The results of [22] rely on stochastic dominance. Given two probability
density functions $\xi$ and $\pi$ over $\mathds{R}_{\geq 0}$, $\xi$
_stochastically dominates_ $\pi$, which we denote by $\xi\succeq_{s}\pi$, if

$\int_{x\geq y}\xi(x)dx\geq\int_{x\geq y}\pi(x)dx,\quad\forall
y\in\mathds{R}_{\geq 0}.$

Now, we show that dynamic program (45)–(48) satisfies conditions (C1)–(C3) of
[22, Theorem 1]. In particular, we have: Condition (C1) is satisfied because
the per-step cost functions $d(e)$ and $\lambda+Q_{s0}d(e)$ are EI. Condition
(C2) is satisfied because the probability density $\mu$ of $W_{t}$ is even,
which implies that for any $e\in\mathds{R}_{\geq 0}$,

$\int_{w\in\mathds{R}}\mu(ae+w)dw=\int_{w\in\mathds{R}}\mu(-ae+w)dw.$

Now, to check condition (C3), define for $e\in\mathds{R}$ and
$y\in\mathds{R}_{\geq 0}$,

$\displaystyle M^{0}(y|e)$
$\displaystyle=\int_{y}^{\infty}\mu(ae+w)dw+\int_{-\infty}^{-y}\mu(ae+w)dw$
$\displaystyle=1-\int_{-y}^{y}\mu(ae+w)dw,$ $\displaystyle M^{1}(y|e)$
$\displaystyle=\int_{y}^{\infty}\mu(w)dw+\int_{-\infty}^{-y}\mu(w)dw.$

$M^{1}(y|e)$ does not depend on $e$ and is thus trivially even and increasing
in $e$. Since $\mu$ is even, $M^{0}(y|e)$ is even in $e$. We show that
$M^{0}(y|e)$ is increasing in $e$ for $e\in\mathds{R}_{\geq 0}$ later (see
Lemma 5).

Since conditions (C1)–(C3) of [22, Theorem 1] are satisfied, we have that for
any $s\in\\{0,1\\}$, $J_{t}(e,s)$ is even in $e$ and increasing for
$e\in\mathds{R}_{\geq 0}$. Now, observe that

$J^{0}(e,s)-J^{1}(e,s)=(1-Q_{s0})d(e)+Q_{s1}\mathds{E}_{W}[J_{t+1}(ae+W,1)]\\\
-\lambda-Q_{s1}\mathds{E}_{W}[J_{t+1}(W,1)]$

which is even in $e$ and increasing in $e\in\mathds{R}_{\geq 0}$. Therefore,
for any fixed $s\in\\{0,1\\}$, the set $A$ of $e$ in which
$J^{0}_{t}(e,s)-J^{1}_{t}(e,s)\leq 0$ is convex and symmetric around the
origin, i.e., a set of the form $[-k_{t}(s),k_{t}(s)]$. Thus, there exist a
$k_{t}(\cdot)$ such that the action $u_{t}=0$ is optimal for
$e\in[-k_{t}(s),k_{t}(s)]$. This, proves the structure of the optimal
transmission strategy.

######  Lemma 5.

For any $y\in\mathds{R}_{\geq 0}$, $M^{0}(y|e)$ is increasing in $e$,
$e\in\mathds{R}_{\geq 0}$.

######  Proof:.

To show that $M^{0}(y|e)$ is increasing in $e$ for $e\in\mathds{R}_{\geq 0}$,
it sufficies to show that $1-M^{0}(y|e)=\int_{-y}^{y}\mu(ae+w)dw$ is
decreasing in $e$ for $e\in\mathds{R}_{\geq 0}$. Consider a change of
variables $x=ae+w$. Then,

$1-M^{0}(y|e)=\int_{-y}^{y}\mu(ae+w)dw=\int_{-y-ae}^{y-ae}\mu(x)dx$ (49)

Taking derivative with respect to $e$, we get that

$\frac{\partial M^{0}(y|e)}{\partial e}=a[\mu(y-ae)-\mu(-y-ae)]$ (50)

Now consider the following cases:

  * •

If $a>0$ and $y>ae>0$, then the right hand side of (50) equals
$a[\mu(y-ae)-\mu(y+ae)]$, which is positive.

  * •

If $a>0$ and $ae>y>0$, then the right hand side of (50) equals
$a[\mu(ae-y)-\mu(ae+y)]$, which is positive.

  * •

If $a<0$ and $y>|a|e>0$, then the right hand side of (50) equals
$|a|\,[\mu(y-|a|e)-\mu(y+|a|e)]$, which is positive.

  * •

If $a<0$ and $|a|e>y>0$, then the right hand side of (50) equals
$|a|\,[\mu(|a|e-y)-\mu(|a|e+y)]$, which is positive.

Thus, in all cases, $M^{0}(y|e)$ is increasing in $e$, $e\in\mathds{R}_{\geq
0}$.

##  V Conclusion

In this paper, we studied remote estimation over a Gilbert-Elliot channel with
feedback. We assume that the channel state is observed by the receiver and fed
back to the transmitter with one unit delay. In addition, the transmitter gets
ack/nack feedback for successful/unsuccessful transmission. Using ideas from
team theory, we establish the structure of optimal transmission and estimation
strategies and identify a dynamic program to determine optimal strategies with
that structure. We then consider first-order autoregressive sources where the
noise process has unimodal and symmetric distribution. Using ideas from
majorization theory, we show that the optimal transmission strategy has a
threshold structure and the optimal estimation strategy is Kalman-like.

A natural question is how to determine the optimal thresholds. For finite
horizon setup, these can be determined using the dynamic program of (45)–(48).
For inifinite horizon setup, we expect that the optimal threshold will not
depend on time. We believe that it should be possible to evalute the
performance of a generic threshold based strategy using an argument similar to
the renewal theory based argument presented in [16] for channels without
packet drops.

## References

  * [1] J. Marschak, “Towards an economic theory of organization and information,” _Decision processes_ , vol. 3, no. 1, pp. 187–220, 1954.
  * [2] O. C. Imer and T. Basar, “Optimal estimation with limited measurements,” _Joint 44the IEEE Conference on Decision and Control and European Control Conference_ , vol. 29, pp. 1029–1034, 2005.
  * [3] M. Rabi, G. Moustakides, and J. Baras, “Adaptive sampling for linear state estimation,” _SIAM Journal on Control and Optimization_ , vol. 50, no. 2, pp. 672–702, 2012.
  * [4] Y. Xu and J. P. Hespanha, “Optimal communication logics in networked control systems,” in _Proceedings of 43rd IEEE Conference on Decision and Control_ , vol. 4, 2004, pp. 3527–3532.
  * [5] G. M. Lipsa and N. C. Martins, “Remote state estimation with communication costs for first-order LTI systems,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 9, pp. 2013–2025, 2011.
  * [6] A. Nayyar, T. Basar, D. Teneketzis, and V. V. Veeravalli, “Optimal strategies for communication and remote estimation with an energy harvesting sensor,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 9, pp. 2246–2260, 2013.
  * [7] A. Molin and S. Hirche, “An iterative algorithm for optimal event-triggered estimation,” in _4th IFAC Conference on Analysis and Design of Hybrid Systems (ADHS’12)_ , 2012, pp. 64–69.
  * [8] J. Wu, Q. S. Jia, K. H. Johansson, and L. Shi, “Event-based sensor data scheduling: Trade-off between communication rate and estimation quality,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 4, pp. 1041–1046, April 2013.
  * [9] D. Shi, L. Shi, and T. Chen, _Event-Based State Estimation: A Stochastic Perspective_. Springer, 2015, vol. 41.
  * [10] J. Chakravorty and A. Mahajan, “Remote state estimation with packet drop,” in _6th IFAC Workshop on Distributed Estimation and Control in Networked Systems_ , Sep 2016.
  * [11] R. Xiaoqiang, W. Junfeng, J. K. Henrik, S. Guodong, and S. Ling, “Infinite horizon optimal transmission power control for remote state estimation over fading channels,” _arxiv: 1604.08680v1 [cs.SY]_ , Apr 29 2016.
  * [12] H. S. Witsenhausen, “On the structure of real-time source coders,” _BSTJ_ , vol. 58, no. 6, pp. 1437–1451, July-August 1979.
  * [13] J. C. Walrand and P. Varaiya, “Optimal causal coding-decoding problems,” _IEEE Trans. Inf. Theory_ , vol. 29, no. 6, pp. 814–820, Nov. 1983.
  * [14] D. Teneketzis, “On the structure of optimal real-time encoders and decoders in noisy communication,” _IEEE Trans. Inf. Theory_ , pp. 4017–4035, Sep. 2006\.
  * [15] A. Mahajan and D. Teneketzis, “Optimal design of sequential real-time communication systems,” _IEEE Trans. Inf. Theory_ , vol. 55, no. 11, pp. 5317–5338, Nov. 2009.
  * [16] J. Chakravorty and A. Mahajan, “Fundamental limits of remote estimation of Markov processes under communication constraints,” _IEEE Transactions on Automatic Control_ , 2017 (to appear).
  * [17] E. N. Gilbert, “Capacity of a burst-noise channel,” _Bell System Technical Journal_ , vol. 39, no. 5, pp. 1253–1265, 1960.
  * [18] E. O. Elliott, “Estimates of error rates for codes on burst-noise channels,” _Bell System Technical Journal_ , vol. 42, no. 5, pp. 1977–1997, 1963.
  * [19] A. Nayyar, A. Mahajan, and D. Teneketzis, “Decentralized stochastic control with partial history sharing: A common information approach,” _IEEE Trans. Autom. Control_ , vol. 58, no. 7, pp. 1644–1658, jul 2013.
  * [20] S. Yuksel, “On optimal causal coding of partially observed Markov sources in single and multiterminal settings,” _IEEE Trans. Inf. Theory_ , vol. 59, no. 1, pp. 424–437, 2013.
  * [21] P. R. Kumar and P. Varaiya, _Stochastic Systems: Estimation, Identification and Adaptive Control_. Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1986.
  * [22] J. Chakravorty and A. Mahajan, “On evenness and monotonicity of value functions and optimal strategies in markov decision processes,” _submitted to Operations Research Letters_ , 2016.