  We derive Concentration of Measure (CoM) inequalities for randomized Toeplitz
matrices. These inequalities show that the norm of a high-dimensional signal
mapped by a Toeplitz matrix to a low-dimensional space concentrates around its
mean with a tail probability bound that decays exponentially in the dimension
of the range space divided by a quantity which is a function of the signal. For
the class of sparse signals, the introduced quantity is bounded by the sparsity
level of the signal. However, we observe that this bound is highly pessimistic
for most sparse signals and we show that if a random distribution is imposed on
the non-zero entries of the signal, the typical value of the quantity is
bounded by a term that scales logarithmically in the ambient dimension. As an
application of the CoM inequalities, we consider Compressive Binary Detection
(CBD).
