Exact Minimum Number of Bits to Stabilize a Linear System

Abstract

We consider an unstable scalar linear stochastic system, $X_{n+1}=a X_n + Z_n - U_n$, where $a geq 1$ is the system gain, $Z_n$'s are independent random variables with bounded $alpha$-th moments, and $U_n$'s are the control actions that are chosen by a controller who receives a single element of a finite set ${1, ldots, M}$ as its only information about system state $X_i$. We show that $M = lfloor arfloor + 1 $ is necessary and sufficient for $beta$-moment stability, for any $beta < alpha$. Our achievable scheme is a uniform quantizer of the zoom-in / zoom-out type. We analyze its performance using probabilistic arguments. We prove a matching converse using information-theoretic techniques. Our results generalize to vector systems, to systems with dependent Gaussian noise, and to the scenario in which a small fraction of transmitted messages is lost.