I'm reading this paper http://eccc.hpi-web.de/report/2016/044/download/, at page 7 you can see this equation:

$$ \sum_t \mathbb{E}_{w \in W} [|p_t - p_{t|w,w}|] = 2 \sum_t \mathbb{E}_{w \in W} [\max(0,p_t - p_{t|w,w})]$$

I think what we're using here is this: $$a+b+|a-b| = 2 \max(a,b)$$

but with $a=0$ and $b=p_t-p_{t|w,w}$ we get: $$p_t - p_{t|w,w} + |p_t - p_{t|w,w}| = 2\max(0,p_t - p_{t|w,w})$$ I know it's a bit of a silly question but I just can't figure it out, maybe I'm missing some fact about probabilities?

  • $\begingroup$ Presumably, summing over $t$ of both $p_t$ and $p_{t|w,w}$ yields 1 so they cancel out. $\endgroup$ – Aryeh Aug 27 '16 at 18:00
  • $\begingroup$ using $b=p_t - p_{t|w,w}$ i need to substract from the right-hand side $p_{t|w,w}-p_t$, so we would have: $$\sum_t \mathbb{E}_{w \in W} (p_{t|w,w}-p_t)$$, i can split this in two sums, the first giving $$\sum_t \mathbb{E}_{w \in W} p_{t|w,w} = \sum_t p_t$$ and the other give the same so they cancel out, is this correct? $\endgroup$ – Marco Aug 27 '16 at 19:02
  • $\begingroup$ I didn't read the paper but if $t$ is indeed the "index" of the distribution (i.e., summing over $t$ yields 1) then that's correct. $\endgroup$ – Aryeh Aug 28 '16 at 18:13
  • $\begingroup$ I suggest closing the question. It's not research level and I believe the answer is resolved in the comments. $\endgroup$ – Aryeh Aug 29 '16 at 20:07

This uses the fact that the L1-norm between two probability distributions is equal to twice their total variation distance.

See https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures

To prove the equality you take the subset A in the definition to be the set of points where $$p_t > p_{t|w,w}.$$

| 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.