  We study security games in which a defender commits to a mixed strategy for
protecting a finite set of targets of different values. An attacker, knowing
the defender's strategy, chooses which target to attack and for how long. If
the attacker spends time $t$ at a target $i$ of value $\alpha_i$, and if he
leaves before the defender visits the target, his utility is $t \cdot \alpha_i
$; if the defender visits before he leaves, his utility is 0. The defender's
goal is to minimize the attacker's utility. The defender's strategy consists of
a schedule for visiting the targets; it takes her unit time to switch between
targets. Such games are a simplified model of a number of real-world scenarios
such as protecting computer networks from intruders, crops from thieves, etc.
  We show that optimal defender play for this continuous time security games
reduces to the solution of a combinatorial question regarding the existence of
infinite sequences over a finite alphabet, with the following properties for
each symbol $i$: (1) $i$ constitutes a prescribed fraction $p_i$ of the
sequence. (2) The occurrences of $i$ are spread apart close to evenly, in that
the ratio of the longest to shortest interval between consecutive occurrences
is bounded by a parameter $K$. We call such sequences $K$-quasi-regular.
  We show that, surprisingly, $2$-quasi-regular sequences suffice for optimal
defender play. What is more, even randomized $2$-quasi-regular sequences
suffice for optimality. We show that such sequences always exist, and can be
calculated efficiently.
  The question of the least $K$ for which deterministic $K$-quasi-regular
sequences exist is fascinating. Using an ergodic theoretical approach, we show
that deterministic $3$-quasi-regular sequences always exist. For $2 \leq K < 3$
we do not know whether deterministic $K$-quasi-regular sequences always exist.

Computer Science and Game Theory;Discrete Mathematics;Data Structures and Algorithms