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. In this paper, we
show that the minimum cost to transmit B bits of information asynchronously is
(B + \bar{H})k_sync, where k_sync is the synchronous minimum cost per bit and
\bar{H} is a measure of timing uncertainty equal to the entropy for most
reasonable arrival time distributions.