# Limit of a nested probability function?

Let $F_0(x) =x$.

Then, let $F_i(x) = (1-(1-F_{i-1})^2)^2$ where $i>0$.

Is there a way I can calculate $F_{\infty}(x)$? (Terminology-wise, would I say that is a limit of $F_i(x)$ as $i \to \infty$ ?)

And/or, since in this case $F_i(x)$ is a cdf, can I say what any of the central moments (e.g. mean, skewness) of the $X_i$ represented by $F_i(x)$ approach as $i \to \infty$ ?

-
solving $l=(1-(1-l)^2)^2$ may help. – timhortons Aug 15 '11 at 18:10
To simplify the "algebra," let $S_j(x)=1-F_j(x)$. – André Nicolas Aug 15 '11 at 18:32
An answer has been given by @sasha. There is a limiting distribution, with all the weight at $(3-\sqrt{5})/2$. The golden ratio strikes again. – André Nicolas Aug 15 '11 at 19:02
JandR: Sorry to bring bad news but it seems difficult to completely buy @Sasha's argument about the limit of $F_i$, inter alia because this argument uses nowhere the properties of the specific initial point $F_0$ you are interested in. See my answer for more details. The good news is that Sasha's result itself holds. – Did Aug 15 '11 at 20:14
@JandR: Let $p=(3-\sqrt{5})/2$, $q=1-p$. Then $q/p$ is the golden ratio. – André Nicolas Aug 18 '11 at 1:07

Let $u^*=\frac12(3-\sqrt5)$. As already noted by others, for every fixed $x$, $(F_i(x))$ converges to a limit which depends on $F_0(x)$: the limit is $0$ if $F_0(x)< u^*$, $u^*$ if $F_0(x)=u^*$, and $1$ if $F_0(x)>u^*$.

From here, the asymptotics depends on the starting point $F_0$. The OP is interested in the case when $F_0(x)=x$ for every $x$ in $[0,1]$. In this case, $F_i\to G$ pointwise, where $G(x)$ is $0$ if $x<u^*$, $u^*$ if $x=u^*$, and $1$ if $x>u^*$.

This function $G$ is not a CDF but there exists a CDF $H$ such that $F_i(x)\to H(x)$ for every $x$ such that $H$ is continuous at $x$, namely the function $H=\mathbf{1}_{[u^*,+\infty)}$. Since $H$ is the CDF of a random variable $X$, a well known theorem asserts that this is enough to guarantee that $X_i\to X$ in distribution. Since $0\le X_i\le 1$ almost surely for every $i$, $X_i\to X$ in every $L^p$ as well. Of course, $P(X=u^*)=1$ hence $X_i\to u^*$ in distribution and in every $L^p$.

Note that for other starting points $F_0$, the limit can be different. For example, if there exists $w$ such that $F_0$ is the cdf of a random variable $X_0$ such that $P(X_0=w)=1$, then $F_i=F_0$ for every $i$, hence $F_i\to F_0$ for any $w$.

Likewise, if there exists $v<w$ and $p$ in $(0,1)$ such that $F_0$ is the cdf of a random variable $X_0$ such that $P(X_0=v)=p$ and $P(X_0=w)=1-p$, then one of three asymptotics occurs:

• either $p>u^*$, and then $X_i\to v$,
• or $p<u^*$, and then $X_i\to w$,
• or $p=u^*$, and then $F_i=F_0$ for every $i$, hence $F_i\to F_0$.

A pathwise representation of the transformation of interest may help to get some intuition about the asymptotics described above and is as follows. Assume that the random variables $X_i^{(n)}$ are i.i.d. with CDF $F_i$. Then $F_{i+1}$ is the CDF of the random variable $X_{i+1}$ defined by $$X_{i+1}=\max\{\min\{X_i^{(1)},X_i^{(2)}\},\min\{X_i^{(3)},X_i^{(4)}\}\}.$$

-
Your analysis is much more careful. +1. – Sasha Aug 15 '11 at 20:15
@Sasha: Thanks. – Did Aug 15 '11 at 22:28
@Didier: I get it now! Even tried plotting in Mathematica and seeing all sorts of different limits. This is great. I don't know what to do about the official answer though. This one is more correct and detailed , but I wouldn't know how to understand it w/o Sasha's first (since you did an excellent job of not being redundant). Wish I could have a Part 1 and Part2. – OctaviaQ Aug 18 '11 at 0:47
JandR, thanks for the kind words. I re-read @Sasha's post and I think there is a subtle but fatal flaw in the analysis, which is to confuse the argument of the CDF and their value (that is, for a CDF $F$, $x$ vs $F(x)$). To explain this, write $h(t)=(1-(1-t)^2)^2$. The point $u^*$ is relevant, not because $u^*=h(u^*)$ (Sasha's post) but because $F_0(u^*)=h(F_0(u^*))$... Of course, for the CDF $F_0$ you are interested in, the two conditions coincide but the two-points examples I included in my post show this is just that: a coincidence (since none of them .../... – Did Aug 18 '11 at 7:38
.../... concentrates on a Dirac mass at $u^*$ except when $u^*\in\{v,w\}$). These examples also show that the analysis of the fixed points of $h$ and their un/stability cannot be enough to conclude. Anyway, thanks to you for this nice problem, this is fun once one begins to understand what is really going on. – Did Aug 18 '11 at 7:39

There are only 3 roots in the unit interval to the steady state equation $F_\infty = (1-(1-F_\infty)^2)^2$, which are $F_\infty = 0$, $F_\infty = 1$ and $F_\infty = \frac{3-\sqrt{5}}{2}$, thus $F_\infty(x)$ can only assume one of these values.

The point $x=\frac{1}{2}( 3 - \sqrt{5})$ is unstable, resulting that for all $x$ you would $F_\infty(x)$ is either 0 or 1. The limiting distribution is therefore degenerate, with all the probability concentrated at $x=\frac{1}{2}( 3 - \sqrt{5})$.

-
@Sasha: Not sure I completely buy your argument about the limit of $F_i$, inter alia because it uses nowhere the properties of the specific initial point $F_0$ the OP is interested in. See my answer for more details. – Did Aug 15 '11 at 20:08
@Sasha: Thanks again! Despite not using $F_0$, this answer really helped me get the general idea and to think about the solution. Very clear and easy to read -- the graph helped! – OctaviaQ Aug 18 '11 at 0:22
Although this was very helpful for me and I appreciate it, I switched the "accepted" answer to the one below. – OctaviaQ Aug 18 '11 at 23:05