  A transmitter observing a sequence of independent and identically distributed
random variables seeks to keep a receiver updated about its latest
observations. The receiver need not be apprised about each symbol seen by the
transmitter, but needs to output a symbol at each time instant $t$. If at time
$t$ the receiver outputs the symbol seen by the transmitter at time $U(t)\leq
t$, the age of information at the receiver at time $t$ is $t-U(t)$. We study
the design of lossless source codes that enable transmission with minimum
average age at the receiver. We show that the asymptotic minimum average age
can be attained up to a constant gap by the Shannon codes for a tilted version
of the original pmf generating the symbols, which can be computed easily by
solving an optimization problem. Furthermore, we exhibit an example with
alphabet $\X$ where Shannon codes for the original pmf incur an asymptotic
average age of a factor $O(\sqrt{\log |\X|})$ more than that achieved by our
codes. Underlying our prescription for optimal codes is a new variational
formula for integer moments of random variables, which may be of independent
interest. Also, we discuss possible extensions of our formulation to randomized
schemes and to the erasure channel, and include a treatment of the related
problem of source coding for minimum average queuing delay.
