Zero-error target tracking through limited querying of binary sensors

We consider the problem of tracking a target that moves according to a Markov chain. An estimator queries a set of sensors to obtain tracking information. We are interested in finding the minimum number of queries per time step such that a target is trackable. Three scenarios are analyzed. First we investigate the case where the estimator is required to know the exact location of the target at each time step. We then relax our requirements and explore the case where the estimator may lose track of the target at a given time step, but it is able to "catchup," regaining up-To-date information about the target's track. Finally, we consider the case where tracking information is only known after a delay of d time steps. We provide necessary and sufficient conditions on the number of queries per time step to track in the above three scenarios. These conditions are stated in terms of the entropy rate of the target's Markov chain.