Streaming algorithms for products of probabilities

Abstract

We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of $1-\hat{I}\mu$. It is shown that every randomized streaming algorithm for this problem needs space $\hat{I}\text{c◯}(\log n+\log b-\log \hat{I}\mu )-\mathcal{O}(1)$, where $n$ is length of the input stream and $b$ is the bit length of the input numbers. This matches an upper bound from Alur et al.~up to a constant multiplicative factor. Moreover, we consider the threshold problem, where it is asked whether the product of the input probabilities is below a given threshold. It is shown that every randomized streaming algorithm for this problem needs space $\hat{I}\text{c◯}(n\cdot b)$.