If $\mathcal{D}$ is a distribution, let $\mathcal{D}^n$ denote the $n$-fold Cartesian product of $\mathcal{D}$. In other words, $\mathcal{D}^n$ is the distribution of $n$-tuples $(x_1,\dots,x_n)$ where each $x_i$ is drawn iid from $\mathcal{D}$.

If $\mathcal{D},\mathcal{D}'$ are two distributions, let $d(\mathcal{D},\mathcal{D}')$ denote a dissimilarity measure; it measures how different the two distributions are. For instance, we might use the $\ell_1$ distance measure (i.e., $||\mathcal{D}-\mathcal{D}'||_1$, aka total variation distance), the $\ell_2$ distance (i.e., $||\mathcal{D}-\mathcal{D}'||_2$), the $\ell_\infty$ distance (i.e., $||\mathcal{D}-\mathcal{D}'||_\infty$), the KL divergence ($D_\textrm{KL}(\mathcal{D} || \mathcal{D}')$), or something else entirely. Often we might expect these to be normalized so that the dissimilarity is between 0 and 1, but I suppose that's not necessary.

Let $\mathcal{D}_0,\mathcal{D}_1$ be two distributions, and $d_1,d_2$ any two dissimilarity measures (maybe the same one, maybe different). Are there any bounds, estimates, approximations, or rules of thumb that relate $d_2(\mathcal{D}_0^n,\mathcal{D}_1^n)$ to $d_1(\mathcal{D}_0,\mathcal{D}_1)$?



Your Answer

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