Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $f, \hat{f}, g,$ and $\hat{g}$ be continuous probability densities. Define probability densities $p \propto fg$ and $\hat{p} \propto \hat{f}\hat{g}$. Is it true that \begin{align*} ||p - \hat{p}||_{1} \le || f - \hat{f}|| _{1} + ||g - \hat{g}||_1 \end{align*}

share|improve this question
    
Why would this inequality imply something of interest, if true? In short, what are your motivations for asking this? –  Did Oct 29 '11 at 7:13
add comment

1 Answer 1

up vote 1 down vote accepted

Here is a real counterexample, as verified by mathematica: so we take the same discrete two point space as below, and let $f=(u_1,u_2), \hat{f} = (v_1,v_2), g = (a_1,a_2), \hat{g}=(b_1,b_2)$, with the relation that $x_1 + x_2 = 1$ where $x \in \{u,v,a,b\}$. So your claim becomes in this special case

$$ |\frac{u_1 a_1}{u_1 p_1 + u_2 a_2} - \frac{v_1 b_1}{v_1 b_1 + v_2 b_2}| + | \frac{u_2 a_2}{u_1 a_1 + u_2 a_2} - \frac{v_2 b_2}{v_1 b_1 + v_2 b_2}|$$ $$\le |u_1 - v_1| + |u_2 - v_2| + |a_1 - b_1| + |a_2 - b_2|$$

Now using the relation that if $x + y = 1$ and $w + z = 1$, then $|x - w| + |y - z| = 2 |x -w|$, we can simplify the above inequality to

$$ |\frac{u_1 a_1}{u_1 a_1 + u_2 a_2} - \frac{v_1 b_1}{v_1 b_1 + v_2 b_2}| \le |u_1 - v_1| + |a_1 - b_1| $$.

What I then did is to subtract the square of the right hand side from the square of the left hand side, and call the resulting function $h(u,v,a,b)$, where $x := x_1$ for $x \in \{u,v,a,b\}$. Then I did some brute force search of maximum and found the following point:

$$u=v =0.456239, a = 1/5, b = 1/2$$ If you plug it in to $h$ you should get $0.000652285 > 0$. So that means the left hand side is not always $\le$ the right hand side. Here are the mathematica code so that you can help me verify:

q[u1_, u2_, a1_, a2_, v1_, v2_, b1_, b2_] := (u1 a1/(u1 a1 + u2 a2) - v1 b1/(v1 b1 + v2 b2))^2 - ( (u1 - v1)^2 + (a1 - b1)^2 + 2 Abs[(u1 - v1) (a1 - b1)]);

h[u_, v_, a_, b_] := q[u, 1 - u, a, 1 - a, v, 1 - v, b, 1 - b];

h[0.456239, 0.456239, 2/3, 2/5]

= 0.000652285

Edit: below was my earlier false counterexample.

I believe it's false. Here is an argument. It suffices to consider discrete probability space, say the two point space $\Omega = \{ 0,1 \} $. Now let $f =(u_1,1-u_1)$ be the probability mass function, so that means $f(0) = u_1$ and $f(1) = 1-u_1$. and similarly $\hat{f} = (u_2,1-u_2)$. Also I will let $g = \hat{g} = (p, 1-p)$. Then $\|g - \hat{g}\|_1 = 0$, so your inequality amounts to

$ |\frac{p u_1}{p u_1 + (1-p)(1-u_1)} - \frac{p u_2}{pu_2 + (1-p)(1-u_2)}| \le |u_1 - u_2|$.

Now take $u_1 = 2/3$ and $u_2 = 1/3$, and let $ 1-p >> p$. Then you get a contradiction.

share|improve this answer
2  
I don't think this counter example is true. The left hand side should be |P_1 - \hat{P}_1| + |P_2 - \hat{P}_2|, (P \propto fg not to confuse with your p) currently you are only considering the term |P_1 - \hat{P}_1|. Also the left hand side is 2|u_1 - u_2|. Moreover, when g is highly biased (p \to 0 in your example) then the right hand side of my inequality (||P - \hat{P}||_1) goes to zero so it's true. –  Nima Oct 29 '11 at 3:42
    
Thanks for the counter example. I appreciate it. Do you think some inequality like that might be true perhaps with some prefactor? I want to somehow bound the tv distance of the product of some probability densities in terms of the individual tv distances –  Nima Oct 29 '11 at 5:57
    
That's a good question. I have no intuitions whatsoever, just pure luck. Can you state the original problem you are trying to solve? My first impression was that the inequality does not scale appropriately on the two sides, which led to my disbelief. –  John Jiang Oct 29 '11 at 6:01
    
I was trying to prove convergence of a low-complexity variant of belief propagation algorithm which we call it stochastic belief propagation. Belief propagation has various applications in signal and image processing, computer vision, etc. This statement or something like that would be helpful. Thanks anyway –  Nima Oct 29 '11 at 21:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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