Suppose we have two different probability distributions $p, q$ defined on input $x \in [0,1]$. We know that for any value of $x$ in the domain, we have $\exp^{-a} \leq \frac{p(x)}{q(x)} \leq \exp^{a} $, here $a$ is a fixed number. In other words, $p$ and $q$ are quite similar. Is there any way that can relate between the expected value $E_p[x] $ and $E_q[x]$. For example, there might be exists two numbers $l, u \geq 0$ s.t: $$ l \leq \frac{E_p[x]}{E_q[x]} \leq u $$.

Also, $l, u$ depends on the value $a$ above.

  • $\begingroup$ Hi, that notation came from the definition of differential privacy. Basically, a randomize mechanism $\mathcal{M}$ is called differentially private iff for two neighboring datasets $D, D'$,that differ in one entry, i.e we remove one individual from $D$ to obtain $D'$, and for all output $o$ we have: $ \frac{ Pr(\mathcal{M}(D) = o) } {Pr(\mathcal{M}(D') = o) } \leq exp^{a}$. a is called the privacy loss. $\endgroup$ – Kieu Anh Dang Aug 3 at 1:13
  • $\begingroup$ Look like that comment was not finnished? $\endgroup$ – kjetil b halvorsen Aug 3 at 1:15
  • $\begingroup$ I just revised that. Thanks for your comment. The notation is from differential privacy. I would like to know the similarity between two means, if I know their distributions are quite similar at any place. $\endgroup$ – Kieu Anh Dang Aug 3 at 1:17

Not an exact proof but a good intuition:

  • I imagine that you get the most extreme difference in expectation values when the weight is concentrated on the outside (you need some nonzero density everywhere in order for the ratio of densities to make sense but you can take the limit of this density to zero, make it as small as you want).

  • Say you can use some variable like:

    $$f(x \vert b,\epsilon) = \begin{cases} c \cdot b & \quad & \text{if }x \in [0,\epsilon] \\ \epsilon & \quad & \text{if }x \in (\epsilon,1-\epsilon) \\ c / b & \quad & \text{if }x \in [1-\epsilon,1] \\ 0 & \quad & \text{otherwise} \end{cases}$$

    where (in order have $\int f(x) dx = 1$) the constant $c$ must be $$c = \frac{1-\epsilon (1-2\epsilon)}{b+1/b}$$ and consider the limits of $\epsilon \to 0$ such it basically becomes a Bernoulli variable.

  • Now you can choose two such variables with $b_p = \sqrt{d}$ and $b_q = 1/\sqrt{d}$, such that $$\frac{p(0)}{q(0)} = d$$ and similarly $$\frac{p(1)}{q(1)} = 1/d $$ also $$\lim_{\epsilon \to 0} \frac{E_p(x)}{E_q(x)} = \frac{p(1)}{q(1)} = 1/d $$

Using this idea you could get the limits

$$e^{-a} < \frac{E_p[x]}{E_q[x]} < e^a$$

You could get this equality if you allow $\epsilon = 0$, ie discrete distributions that do not have nonzero mass everywhere.

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.