  The monitoring of event frequencies can be used to recognize behavioral
anomalies, to identify trends, and to deduce or discard hypotheses about the
underlying system. For example, the performance of a web server may be
monitored based on the ratio of the total count of requests from the least and
most active clients. Exact frequency monitoring, however, can be prohibitively
expensive; in the above example it would require as many counters as there are
clients. In this paper, we propose the efficient probabilistic monitoring of
common frequency properties, including the mode (i.e., the most common event)
and the median of an event sequence. We define a logic to express composite
frequency properties as a combination of atomic frequency properties. Our main
contribution is an algorithm that, under suitable probabilistic assumptions,
can be used to monitor these important frequency properties with four counters,
independent of the number of different events. Our algorithm samples longer and
longer subwords of an infinite event sequence. We prove the almost-sure
convergence of our algorithm by generalizing ergodic theory from
increasing-length prefixes to increasing-length subwords of an infinite
sequence. A similar algorithm could be used to learn a connected Markov chain
of a given structure from observing its outputs, to arbitrary precision, for a
given confidence.
