New answers tagged probability-theory
1
Algorithm 1, which I refer to in the question, produces a strategy that minimizes cumulative counterfactual regret.
The motivation is to get a strategy which minimizes overall regret (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy.
In other words, cumulative counterfactual regret was designed to be:
...
1
Hint:
2
Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{...
1
You need $\Omega(2^n)$ samples in order to accomplish your task.
Consider an algorithm that gets $m$ samples from $D$ and then another sample, either from $D$ or from $U$, and has to guess which it is. Its input thus consists of $m+1$ samples $X_1,\ldots,X_m,Y$.
We will generate the distribution $D$ at random by choosing a random set $V \subseteq \{0,1\}^n$ ...
0
You can't. Your intuition is wrong. I will give an explicit counter-example. Actually, I'll give you two: two for the price of one.
Suppose $n=1$, the distribution $D$ always outputs 1, and $U$ is uniform on $\{0,1\}$. The following algorithm is an optimal distinguisher:
Never use the black box. If the input $z$ is 0, guess that it came from $U$, ...
1
Total variation distance, which is exactly half of your notion of distance, is equal to
$$
d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|.
$$
You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute....
1
The notation $\|x_n - \mu\|^2$ stands for the squared $L_2$ norm of the vector $x_n - \mu$.
The squared $L_2$ norm of the $d$-dimensional vector $v = \begin{pmatrix} v_1 & \cdots & v_d \end{pmatrix}$ is $$\|v\|^2 = v_1^2 + \cdots + v_d^2. $$
In particular, when $d = 1$, we have $\|v\|^2 = v_1^2$.
The formula you state works for the Gaussian ...
2
Here is the key. Let $A \otimes B$ be the distribution corresponding to a sample from $A$ and an independent sample from $B$, and denote total variation distance by $d_{TV}$. Then
$$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$
We can see this using the $L_1$ formula for $d_{TV}$:
\begin{align}
d_{TV}(A_1\otimes A_2,B_1\...
Top 50 recent answers are included
