1

I was trying to solve a statistics problem on expected values when the following recurrence relation came up. Quite frankly I'm stumped on how to solve it ... even to the point that I'm starting to believe that it has no possible solutions.
$X_{n}=\frac{1}{2}*(1+X_{n-1}^2)$ for $X_{0} = 0.5$ (tends to 1)

(I've already taken a look at How to solve quadratic recurrence relation which would only prove helpful if my recurrence has no closed form solutions in which case I would appreciate a proof)

If you run the following code in MATLAB, the random sampling and the original function do not completely match (at each step you run max(H(i-1), rand(0,1)):

G = 0.5; for t=2:100; G(t) = 0.5+0.5*G(t-1)^2; end;
H = rand(1,100000); for i=2:100; H(i,1:100000)=max(H(i-1,1:100000),rand(1,100000)); endfor; plot(mean(H')); hold on; plot(G,'g'); hold off
David
  • 25

1 Answers1

1

A closed form for $X_n$ is unlikely, but to rigorously show that $$ \lim_{n\to\infty}X_n=1 $$ we can argue as follows . . .

It's clear that $X_n > 0$ for all $n$.

Also we have $X_0 < 1$, and if $X_{n-1} < 1$ then $$ X_n = \frac {1+X_{n-1}^2}{2} < \frac {1+1^2}{2} = 1 $$ so $X_n < 1$ for all $n$.

Then we get \begin{align*} X_n-X_{n-1} &= \frac {1+X_{n-1}^2}{2} - X_{n-1} \\[4pt] &= \frac {1-2X_{n-1}+X_{n-1}^2}{2} \\[4pt] &= \frac {(1-X_{n-1})^2}{2} \\[4pt] & > 0 \\[4pt] \end{align*} so the sequence $X_0,X_1,X_2,...$ is monotonically increasing, hence, since the sequence is bounded above, it follows that it approaches a limit, $L$ say, as $n$ approaches infinity.

Then from the recursion $$ X_n = \frac {1+X_{n-1}^2}{2} $$ we get \begin{align*} & L = \frac {1+L^2}{2} \\[4pt] \implies\;& 1-2L+L^2=0 \\[4pt] \implies\;& (1-L)^2=0 \\[4pt] \implies\;& L=1 \\[4pt] \end{align*}

quasi
  • 58,772
  • That's another way to do it. If you reverse engineer my thought process you get the same result. The equation came from getting the expected value of a function that samples from a uniform distribution. xn+1= max(xn, rand(0,1)). Of course this has to tend to 1. My recursive function takes the expected value at every time step – David Mar 16 '24 at 01:26
  • I'm looking for two things either a solution to the RR or a proof that no solution exists and a reason why the two curves from the script don't match. – David Mar 16 '24 at 01:29