Streaming Algorithms for Products of Probabilities
摘要
We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of \(1-\epsilon \) . It is shown that every randomized streaming algorithm for this problem needs space \(\varOmega (\log n + \log b - \log \epsilon - \varTheta (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 \(\varOmega (n \cdot b)\) . Finally, also the sliding window variant of the approximation problem for a product of input probabilities is considered.