  We consider a node-monitor pair, where updates are generated stochastically
(according to a known distribution) at the node that it wishes to send to the
monitor. The node is assumed to incur a fixed cost for each transmission, and
the objective of the node is to find the update instants so as to minimize a
linear combination of AoI of information and average transmission cost. First,
we consider the Poisson arrivals case, where updates have an exponential
inter-arrival time for which we derive an explicit optimal online policy. Next,
for arbitrary distributions of inter-arrival time of updates, we propose a
simple randomized algorithm that transmits any newly arrived update with a
fixed probability (that depends on the distribution) or never transmits that
update. The competitive ratio of the proposed algorithm is shown to be a
function of the variance and the mean of the inter-arrival time distribution.
For some of the commonly considered distributions such as exponential, uniform,
and Rayleigh, the competitive ratio bound is shown to be 2.
