2
$\begingroup$

Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$. That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a query to $p$ or $q$.

What is the fastest randomized algorithm for estimating the trace distance between $p$ and $q$? Formally, I would like to know the fastest algorithm in literature to estimate $\widetilde{T}$ such that $|T-\widetilde{T}|<\epsilon$ with probability $1-\delta$ where $T$ is:

$$T = \frac{1}{2}\sum_{x \in X} |p(x) -q(x)| $$

I am looking for all the type of cases: average time, worst time.. I would ready any paper that is relevat to this question, so to understand when it's important to estimate trace distances.

$\endgroup$
4
  • 1
    $\begingroup$ How do you measure "fastest"? Worst-case running time? Average-case? If so, what distribution on distributions do you have in mind? Something else? $\endgroup$
    – D.W.
    Dec 12, 2021 at 4:06
  • $\begingroup$ Good question. I think any setting is relevant, as I am trying to learn more about where trace distance is used in practice. $\endgroup$
    – asdf
    Dec 12, 2021 at 15:03
  • $\begingroup$ Are $p$ and $q$ the probability mass functions? Then you can't do faster than $O(n)$ (unless you allow very high error probability): consider two distributions where $p_i = 1$ for some $i$ and $q_j =1$ for some $j$. You need to check whether $i=j$, and for that you need to find at least one of them. There is no way to do this faster than $O(n)$. $\endgroup$
    – Dmitry
    Dec 12, 2021 at 22:31
  • $\begingroup$ "I want to know for all types of cases..." doesn't help. This site is intended for focused, specific question. Each one of those cases has some issues; by trying to tackle them all, it makes it hard to provide a useful answer. I'm trying to get you to focus on just one for now so that I can highlight the issues associated with that. I already indicated that if you want average-case, you need to specify a distribution on distributions; I don't see that you have addressed that. Dmitry is highlighting an issue for worst-case running time. Please pick one notion of running time. $\endgroup$
    – D.W.
    Dec 13, 2021 at 4:50

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.