  The problem of optimal real-time transmission of a Markov source under
constraints on the expected number of transmissions is considered, both for the
discounted and long term average cases. This setup is motivated by applications
where transmission is sporadic and the cost of switching on the radio and
transmitting is significantly more important than the size of the transmitted
data packet. For this model, we characterize the distortion-transmission
function, i.e., the minimum expected distortion that can be achieved when the
expected number of transmissions is less than or equal to a particular value.
In particular, we show that the distortion-transmission function is a piecewise
linear, convex, and decreasing function. We also give an explicit
characterization of each vertex of the piecewise linear function.
  To prove the results, the optimization problem is cast as a decentralized
constrained stochastic control problem. We first consider the Lagrange
relaxation of the constrained problem and identify the structure of optimal
transmission and estimation strategies. In particular, we show that the optimal
transmission is of a threshold type. Using these structural results, we obtain
dynamic programs for the Lagrange relaxations. We identify the performance of
an arbitrary threshold-type transmission strategy and use the idea of
calibration from multi-armed bandits to determine the optimal transmission
strategy for the Lagrange relaxation. Finally, we show that the optimal
strategy for the constrained setup is a randomized strategy that randomizes
between two deterministic strategies that differ only at one state. By
evaluating the performance of these strategies, we determine the shape of the
distortion-transmission function. These results are illustrated using an
example of transmitting a birth-death Markov source.
