  We consider the canonical {\em shared link network} formed by a source node,
hosting a library of $m$ information messages (files), connected via a
noiseless common link to $n$ destination nodes (users), each with a cache of
size M files. Users request files at random and independently, according to a
given a-priori demand distribution $\qv$. A coding scheme for this network
consists of a caching placement (i.e., a mapping of the library files into the
user caches) and delivery scheme (i.e., a mapping for the library files and
user demands into a common multicast codeword) such that, after the codeword
transmission, all users can retrieve their requested file. The rate of the
scheme is defined as the {\em average} codeword length normalized with respect
to the length of one file, where expectation is taken over the random user
demands. For the same shared link network, in the case of deterministic
demands, the optimal min-max rate has been characterized within a uniform
bound, independent of the network parameters. In particular, fractional caching
(i.e., storing file segments) and using linear network coding has been shown to
provide a min-max rate reduction proportional to 1/M with respect to standard
schemes such as unicasting or "naive" uncoded multicasting. The case of random
demands was previously considered by applying the same order-optimal min-max
scheme separately within groups of files requested with similar probability.
However, no order-optimal guarantee was provided for random demands under the
average rate performance criterion. In this paper, we consider the random
demand setting and provide general achievability and converse results. In
particular, we consider a family of schemes that combine random fractional
caching according to a probability distribution $\pv$ that depends on the
demand distribution $\qv$, with a linear coded delivery scheme based on ...
