Motivation of this question:

This question is related to the expected stopping time of a stochastic process under two hypotheses. Especially, it answers the question "how many more samples are required such that a sequential test stops when there is a model missmatch compared to the case when there is no missmatch". I found that the ratio is ${D(f_0,f_1)}/{D(g_0,g_1)}$ if the null hypothesis is correct and ${D(f_1,f_0)}/{D(g_1,g_0)}$ if the alternative hypothesis is correct. I know that both should be greater than $1$ because $g_0$ and $g_1$ are gradually getting closer to each other when we increase the degree of missmatch which indicates that their distance is also getting smaller and smaller. However, I was not able to show it analytically.

My question is as follows:

Given $4$ distinct densities $f_0,f_1$ and $g_0,g_1$ on $\mathbb{R}$ with their cumulative distribution functions $F_0,F_1$ and $G_0,G_1$ satisfying

$$F_0(y)>G_0(y)>G_1(y)>F_1(y),\quad \forall y$$

Show that



Note that the equation above is based on the distance


In addition to this, I wonder if it is possible to generalize the result for any distance measure $D$ between two densities? for example

$$D^2(h_0,h_1)=\frac{1}{2}\int \left(\sqrt{h_0(y)}-\sqrt{h_1(y)}\right)^2 \mathrm{d}y$$


$$D(h_0,h_1)=\frac{1}{2}\int |h_0(y)-h_1(y)| \mathrm{d}y$$

For the first question I tried to separate the integrals to $(-\infty,y]$ and $[y,\infty)$ but then I was stuck and couldnt continue with the solution.

EDIT: here is an example for Gaussian densities

It can be seen that $g_0,g_1$ are between $f_0,f_1$ and closer to each other and $D$ is getting smaller.

Thanks for reading this post and any possible help.

  • $\begingroup$ This cannot be as the $(g_0=g_1,f_0\ne f_1)$ case shows. $\endgroup$
    – Did
    Jun 29 '13 at 10:09
  • $\begingroup$ @Did $g_1\neq g_0$ and $f_1\neq f_0$ $\endgroup$ Jun 29 '13 at 10:11
  • $\begingroup$ @Did okay I think there is one more $c.d.f.$ condition which is necessary $c.d.f.(f_0)>c.d.f.(f_1)$. I will update the question. $\endgroup$ Jun 29 '13 at 10:26
  • $\begingroup$ To assume the $g_i$ are distinct does not save the day since one can choose the $g_i$ very close (but distinct) and, by continuity, still get a counterexample. (I thought this was obvious from my first comment and, frankly, was a bit surprised by the I-do-not-want-to-hear-bad-news style reaction.) Note that the $g_0\approx g_1$ case fits the new set of conditions as well. $\endgroup$
    – Did
    Jun 29 '13 at 10:50
  • $\begingroup$ @Did bad news are welcomed. I do want to hear both bad and good news and would like to thank for any of your comment. It was me, who couldnt make the question clear. Now I put a picture. The idea of the question is that: $g_0$ and $g_1$ are moving to each other starting from $f_0, f_1$. They move as long as they do not fully overlap. This means their distance should get smaller and smaller. I was angry to myself since the question is simple and still I am forgetting the necessary information. $\endgroup$ Jun 29 '13 at 10:57

Here is a hint leading to the conclusion that the inequality between relative entropies that you suggest cannot hold in general. Call $\gamma_t$ the gaussian density with mean $t$ and variance $1$ and consider the densities $$ f^{(t)}_0=\tfrac12(\gamma_0+\gamma_{2t}),\qquad g_0^{(t)}=\tfrac12(\gamma_1+\gamma_{2t}),\qquad g_1^{(t)}=\tfrac12(\gamma_t+\gamma_{2t}),\qquad f_1^{(t)}=\gamma_{2t}. $$ Then $F_1^{(t)}\lt G_1^{(t)}\lt G_0^{(t)}\lt F_0^{(t)}$ for every $t\gt1$, as desired, and I am fairly confident that the relative entropies are such that $D(f_1^{(t)},f_0^{(t)})\lt D(g_1^{(t)},g_0^{(t)})$, at least for $t$ large enough, for the following reason.

Renormalizing when $t\to+\infty$, the distributions of respective densities $f_0^{(t)}$, $g_0^{(t)}$, $g_1^{(t)}$ and $f_1^{(t)}$ converge to the measures $$ \mu_0=\tfrac12(\delta_0+\delta_2),\qquad\nu_0=\tfrac12(\delta_0+\delta_2),\qquad\nu_1=\tfrac12(\delta_1+\delta_2),\qquad\mu_1=\delta_2, $$ respectively, and $D(\mu_1,\mu_0)=\log2$ while $D(\nu_1,\nu_0)=+\infty$. Since $D(f_1^{(t)},f_0^{(t)})\to D(\mu_1,\mu_0)$ and $D(g_1^{(t)},g_0^{(t)})\to D(\nu_1,\nu_0)$ when $t\to+\infty$, the conclusion follows.

  • 1
    $\begingroup$ sounds very interesting, though bad news) lemme read and understand $\endgroup$ Jun 30 '13 at 14:41
  • $\begingroup$ Did thanks alot for the counterexample. First of all I checked it quickly (according to my time), and it works perfectly for the conditions in the question. There is at most one more condition and this condition is not satisfied by this counterexample. It is $f_1/f_0$ is increasing and $g_1/g_0$ is non-decreasing, the second fails. I will accept the answer and I hope you could comment on the case with this new constraint. $\endgroup$ Jun 30 '13 at 15:52
  • $\begingroup$ I will write a newer and fresh question with the monotonicity constraint. $\endgroup$ Jul 1 '13 at 9:23

My work with the constraint when $f_1/f_0$ and $g_1/g_0$ are increasing:

enter image description here

I tried to come up with some densities. First, I thought perhaps I could consider Lagrangian type of optimization for the given inequality


I would minimize the left hand side and maximize the right hand side jointly. Since this would be the worst case, and if in this case no such density would exist then I would be done. BUT, relative entropy is convex and maximizing the right hand side therefore makes no sense. Then, I decided to make some conclusions. You can see them below as well.

$f_0$ and $f_1$ should be as close as possible to each other while $g_0$ and $g_1$ should be as far as possible.

Based on this idea, the $\arg \max g_0$ should be greater than $\arg \max f_0$. There are two ways to do this. In the first case $\max g_0>\max f_0$ or $\max g_0<\max f_0$.

Then I decided to plot them. You can see the plot above. The higher variance $g_0$ and $g_1$ need to have asymmetric tails to satisfy the constraints. Whenever I consider lower variance pairs $g_0,g_1$, namely when $\max g_0>\max f_0$ is true, then the areas $A,B,C,D$ should satisfy the given criteria. This case might have the potential to be a counterexample but I dont know such asymmetric densities on the Real numbers. For example on $[0,\infty]$ there is Rayleigh distribution but on reals?


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.