# Proving a sequence of integrals increases (iterated minimax distributions)

I am trying to show that $$\int_0^1F_n(x) dx \leq \int_0^1F_{n+1}(x) dx$$ when $$F_n(x) = (1-(1-F_{n-1}(x))^c)^c$$ and $F_0(x) = x$ and $n$ and $c$ are integers, $n\geq 1$ and $c \geq 2$

Note that $F$ performs a "minimax type opertation". Starting with the uniform distribution, it produced the cdf of the distribution of the maximum of $c$ draws from the minimum of $c$ draws from the distribution before it.

Here is a list of things I know that might be helpful:

1) $$\int_0^1 F_0(x) dx = \int_0^1 x dx < \int (1-(1-x)^c)^c dx= \int_0^1 F_1(x) dx$$

2)

The distribution $F_n$ converges to Dirac mass at the unique solution to $L= (1-(1-L)^c)^c$, and $\frac{1}{2}^c< L <\frac{1}{2}$ The integral of $F_n$ converges to $1-L$

3)

The integrals of the sequence defined by $F$ are identical to those defined by related functions. $$\int_0^1 F_n dx = \int_0^1 G_n dx = \int_0^11-F_n^{-1} dx= \int_0^1 1-G_n^{-1}dx =$$ $$\int_0^1 1-(F_n(x^c))^{\frac{1}{c}} dx= \int_0^1 (1-F_n(x^c))^c dx$$ where $G_n = (1-(1-G_{n-1}^{\frac{1}{c}})^{\frac{1}{c}}$

4)

$$\int_0^1 F_{n+1}(x)\,dx = \int_0^1F_n(x)dF^{-1}_1(x)dx$$ (and various other ways of rewriting $\int F_i$ in terms of $\int F_j$)

5)

The sequence operator $F= (1-(1-x)^c)^c$ is really two iterations of the simpler sequence operator $(1-x)^c$

6)

The derivative of $F_n$ wrt $x$ = $$f_n = \displaystyle\prod_{k=1}^{n-1}c^2\left(1-\left(1-F_k\right)^c\right)^{c-1}(1-F_k)^{c-1}$$ $$=c^2\left(1-\left(1-F_{n-1}\right)^c\right)^{c-1}(1-F_{n-1})^{c-1}f_{n-1}$$

Does anyone have any ideas?

-
Hardy-Littlewood-Polya's "Inequalities" is an excellent source for proving these types of statements. You will want to check out sections 3.4 and 3.15 on mean values of arbitrary functions. Be forewarned, the book has more theorems than pages. –  Zack Wolske Nov 4 '11 at 22:27
@Jennifer: feel free to ask for explanations about the answer, if something is not clear to you. –  Pietro Majer Nov 14 '11 at 16:32

Let $c>1$ be any fixed real exponent and let us denote, for any $x\in I:=[0,1]$, $f(x):=(1-x)^c$, and $g(x):=1-x^{\frac{1}{c}}$. So $f$ is a strictly decreasing homeomorphism of $I$ into itself, with inverse map $g$ and with the interior fixed point $0 < L< 1/2$. Also, since all even-order iterated of $f$ are strictly increasing, for any $x\in I$ and for any $n\in\mathbb{N}$, we have $$x\le L\quad\mathrm{iff}\quad f(x)\ge x\quad\mathrm{iff}\quad F_1(x)\le x \quad\mathrm{iff}\quad F_{n+1}(x)\le F_n(x)\, .$$ The sets $$A:=\{(x,y)\in I^2\, : \, F_{n+1}(x)\le y \le F_n(x)\}$$ and $$B:=\{(x,y)\in I^2\, : \, F_{n+1}(x)\ge y \ge F_n(x)\}$$ are therefore included in the squares $[0,L]^2$, respectively $[L,1]^2$, so we have $$-\int_0^L(F_{n+1}-F_n)dx=|A|$$ and $$\int_L^1(F_{n+1}-F_n)dx=|B|\, .$$ Moreover, $(x,y)\in A$, that is $F_{n+1}(x)\le y \le F_n(x)$, if and only if $$F _ {n+1}(f(x))=f(F _ {n+1}(x))\ge f(y) \ge f(F_ n(x))=F_ n(f(x))\, ,$$ that is, $(f\times f)(x,y):=(f(x), f(y))\in B$. So $A=(g\times g)(B)\, .$ The map $g\times g$ has Jacobian determinant $g'(x)g'(y)=\frac{1}{c^2}(xy)^{\frac{1}{c}-1}\, ,$ and since $x\ge L$ and $y\ge L$ in $B$ $$|A|=|(g\times g)(B)|=\int_{B} g'(x)g'(y)dxdy\le \left( \frac{L^{\frac{1}{c}-1}}{c}\right)^2|B|\, .$$

Let's prove that the factor in front of $|B|$ is less than or equal to $1$. So we wish to show that $$L^{\frac{1}{c}-1}\le c\, .$$ Recalling that $L=(1-L)^c$, that is, $c=\frac{\log L}{\log (1-L)}$, this reduces to

$$\frac{(1-L)\log(1- L)} {L\log L}\le 1$$

which is indeed true exactly for $L\le 1/2$. So we have $$\int_0^1 F_{n+1}dx -\int_0^1 F_n dx = \int_0^L(F_{n+1}-F_n)dx + \int_L^1(F_{n+1}-F_n)dx=$$ $$= -|A|+|B|\ge 0\,,$$ as required.

-
Thank you, Pietro! –  Jennifer Nov 21 '11 at 17:27

Use Jensen's inequality and induction on $n$.

Let $\phi_c(z) = (1- (1 - z)^c)^c$ , so that $\phi_c(F_i) = F_{i+1}$. As you noted, $\phi = f \circ f$, where $f(z) = (1-z)^c$. $f$ is convex for $0 \leq z \leq 1$, since $\frac{d^2f}{dz^2} = c^2(1-z)^{c-2} \geq 0$. By chain rule, $\phi$ is convex when $0 \leq z \leq 1 - \frac{1}{(c+1)^{(1/c)}}$, so the rest of this argument doesn't work.

Now apply Jensen's inequality to get $\phi(\int F_i) \leq \int F_{i+1}$ provided $0 \leq F_i(x) \leq 1$, which holds for all $0 \leq x \leq 1$. For $z > \frac{3 - \sqrt(5)}{2}$, $\phi_c(z) > z$ for every $c \geq 2$. So since $\int F_0 = \frac{1}{2}$, we have $\int F_0 \leq \phi(\int F_0)$, and the result follows by induction.

Jensen's inequality could still be used on $f$, but that doesn't seem to get any closer to a solution.

-
Note that $\phi_c$ is not convex. This follows, in part, from the fact that $f$ is decreasing. If it were increasing you could conclude that is was convex. As another example, take $f(z) = e^{-z}$, where we see that $f \circ f$ is concave for $z > 0$. –  cardinal Nov 4 '11 at 23:05
I need to revisit intro to calculus and fix my awful notation: differentiated $f^2(x)$ instead of $f(f(x))$. –  Zack Wolske Nov 4 '11 at 23:37