Law of large numbers for moving mean Consider the following process:
For $n = 1,\ldots$


*

*$U_n \sim U[0, 1]$, that is, uniformly distributed on $[0, 1]$,

*$X_n = U_n 1_{U_n > q_n}$, where

*$q_n = \frac{1}{n-1} \sum_{i=1}^{n-1} X_i$, and $q_1 \in [0, 1]$. Hence, $q_n$ is the average of the first $X_i$s.
That is, we observe $U_n$ if $U_n$ is bigger than the current running average, and zero otherwise.
I want to show that $q_n \to q^*$ (don't really care what mode of convergence), where $q^* = \sqrt{2} - 1$.
Why $\sqrt{2} - 1$? If we define $\mu(q) = E(X_n \mid q_n = q)$ (for arbitrary fixed $n$), then it seems clear that $q^*$ must be a fixed point of $\mu$. But $\mu(q) = 0.5(1-q^2)$ which has unique fixed point $\sqrt{2} - 1$ in $[0,1]$.
However, what is a nice way to show that the process actually converges to $q^*$? My hunch is that there is a martingale argument for this, but I haven't been able to find it. 
Another observation is that $q_{n} = q_{n-1} + \frac{1}{n} (x_n - q_{n-1})$ which is a gradient step of minimizing $y$ in $\|y - X_n\|^2_2$ from $q_{n-1}$ with step size $\frac{1}{2n}$. Perhaps there is a nice relation with convergence results on stochastic gradient descent.
Any pointers are much appreciated!
 A: Here is a proof that $\lim_{n\rightarrow\infty} q_n = \sqrt{2} -1$ with probability 1: 
Let $\liminf q_n$ and $\limsup q_n$ represent the random variables $\liminf_{n\rightarrow\infty} q_n$ and $\limsup_{n\rightarrow\infty} q_n$, respectively. Let $\{a_k\}_{k=0}^{\infty}$ be the deterministic sequence that satisfies $a_0=1/2$ and: 
$$a_{k+1} = \frac{1}{2}-\frac{a_k^2}{2} $$
It can be shown that $a_k>0$ for all $k$, and $\lim_{k\rightarrow\infty} a_k= \sqrt{2}-1$.  We now show that, with prob 1, $\lim_{n\rightarrow\infty} q_n = \lim_{k\rightarrow\infty} a_k$. To show this, it suffices to show that, with prob 1: 
\begin{align*}
\limsup q_n &\leq \limsup_{k\rightarrow\infty} a_{2k} = \sqrt{2}-1\\
\liminf q_n &\geq \liminf_{k\rightarrow\infty} a_{2k+1}= \sqrt{2}-1
\end{align*}
Step 0: We know $X_n \leq U_n$ for all $n$ and so with prob 1: 
$$\limsup_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i \leq \limsup_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n U_i = \frac{1}{2}$$ 
where the last equality is from the law of large Numbers (LLN). It follows that $\limsup q_n \leq 1/2 = a_0$ with prob 1. 
Step 1: Now fix $\epsilon \in (0, 1/2)$. We know from step 0 that $q_n \leq 1/2 + \epsilon$ for all sufficiently large $n$. So  $X_n \geq U_n 1\{U_n>1/2+\epsilon\}$ for all sufficiently large $n$, so with prob 1: 
$$\liminf_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i \geq \liminf_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n U_i1\{U_i>1/2+\epsilon\} =  \frac{1}{2}(1-(1/2+\epsilon)^2)$$
This holds for arbitrarily small $\epsilon>0$ and so $\liminf q_n \geq \frac{1}{2}(1-(1/2)^2)=a_1$. 
And now the induction...(for integers $k \in \{1, 2, 3, ...\}$)
Step $2k$: Fix $\epsilon>0$ sufficiently small. Suppose we know that, with prob 1, $\liminf q_n\geq a_{2k-1}$ (this holds for $k=1$ by step 1).  Then $q_n> a_{2k-1}-\epsilon$ for all sufficiently large $n$, so  $X_n \leq U_n 1\{U_n>a_{2k-1}-\epsilon\}$ for all sufficiently large $n$ and with prob 1: 
$$ \limsup_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i \leq E[U_11\{U_1>a_{2k-1}-\epsilon\}] = \frac{1}{2}(1-(a_{2k-1}-\epsilon)^2) $$
This holds for arbitrarily small $\epsilon>0$ and so $\limsup q_n \leq \frac{1}{2}(1-a_{2k-1}^2)=a_{2k}$. 
Step $2k+1$: Fix $\epsilon>0$ sufficiently small. We know from step $2k$ that with prob 1 we have  $\limsup q_n \leq a_{2k}$.  So for sufficiently large $n$ we have $X_n \geq U_n 1\{U_n > a_{2k}+\epsilon\}$, and with prob 1: 
$$ \liminf_{n\rightarrow\infty} \frac{1}{n}\sum_{i=1}^n X_i \geq E[U_1 1\{U_1>a_{2k}+\epsilon\}] = \frac{1}{2}(1-(a_{2k}+\epsilon)^2) $$
This holds for arbitrarily small $\epsilon>0$ and so $\liminf q_n \geq a_{2k+1}$. $\Box$
