Let \begin{equation} Q = \sum_{i=1}^{n} \alpha_i \end{equation} be a sum that we want to estimate. Let us suppose we have an algorithm $\mathcal{A}$, outputting an estimate $\hat Q$, such that \begin{equation} \mathbb{E}[(Q - \hat Q)^{2}] = \beta, \end{equation} where the expectation is taken over the randomness of the algorithm.

Now, consider the quantity $Q^{k}$ for an integer $k$.

We run $\mathcal{A}$ to get $\hat Q$ and output $\hat Q^{k}$ as an estimate for $Q^{k}$. Can we bound the quantity \begin{equation} \mathbb{E}[(Q^{k} - \hat Q^{k})^{2}], \end{equation} in terms of $\beta$ --- where the expectation is again taken over the randomness of the algorithm?

I think it should be more than $\beta^{k}$ but I could not prove it.

For simplicity, take each $\alpha_i$ to be between $0$ and $1$.

  • 1
    $\begingroup$ For some distributions, and $k$ large enough,\begin{equation}\mathbb{E}[(Q^{k} - \hat Q^{k})^{2}],\end{equation}is infinite, so there is no hope in finding a general relation. $\endgroup$
    – Xi'an
    Oct 2, 2021 at 7:39
  • $\begingroup$ What might be an example of such a distribution? $\endgroup$
    – BlackHat18
    Oct 2, 2021 at 14:08
  • 1
    $\begingroup$ Any Student t distribution. Any Pareto distribution. $\endgroup$
    – whuber
    Oct 2, 2021 at 14:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.