The capacity per unit cost, or equivalently minimum cost to transmit one bit,
is a well-studied quantity. It has been studied under the assumption of full
synchrony between the transmitter and the receiver. In many applications, such
as sensor networks, transmissions are very bursty, with small amounts of bits
arriving infrequently at random times. In such scenarios, the cost of acquiring
synchronization is significant and one is interested in the fundamental limits
on communication without assuming a priori synchronization.
Given two dependent stochastic processes X and Y, and a stopping time S on X,
the tracking stopping time problem consists in finding a stopping time T on Y
that best tracks S, e.g., so as to minimize the mean absolute deviation E|T-S|.
This problem formulation applies in several areas including control,
communication, and finance. However, the problem is in general hard to solve
analytically as it generalizes the well-known (Bayesian) change-point detection
problem for which solutions have been reported only for specific settings.
We consider asynchronous point-to-point communication. Building on a recently
developed model, we show that training based schemes, i.e., communication
strategies that separate synchronization from information transmission, perform
suboptimally at high rate.