Good-Turing estimation of the number of operating sensors: a large deviations analysis

We have proposed an estimator for the number of operating sensors in a wireless sensor network based on the Good-Turing non-parametric estimator of the missing mass (Budianu and Tong, Proc. Asilomar Conf. on Sig., Systems and Computers, 2003). We now investigate the performance of this estimator using the theory of large deviations. We determine the asymptotic behavior of the large deviations exponent as the ratio n/N between the number of collected samples n and the number of operating sensors N decreases to zero. The simulations reveal that the confidence intervals obtained using the large deviations formula are upper bounds for the actual performance of the estimator. Together with the asymptotic behavior of the exponent, this suggests the surprising fact that if the scaling law n=f(N) is used for the number of samples, then reliable estimation can be done if n grows at least as fast as √N. Separately, it is shown that, if lim_N→∞(n/√N)=0, the estimator cannot be used.