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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Streaming Algorithms for Products of Probabilities

  • Markus Lohrey,
  • Leon Rische,
  • Louisa Seelbach,
  • Julio Xochitemol

摘要

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.