Q: There are two numerical sequence $X_n$ and $Y_n $. $X_n$ takes random integer from one to six for a given n. $Y_1=X_1$, and $$Y_n=X_n+\dfrac{1}{Y_{n-1}}$$. Find the probability $P$ that $$\dfrac{1+\sqrt3}{2}\leq Y_n \leq 1+ \sqrt3$$ when n is very large.
I can calculate the limit if $X_n$ is constant. But have no idea how to deal with the random number.
Thanks in advance.
On
Here's a sketch that gets sketchier at the end, but the idea should be right:
Let's just start out by trying to say as much as we can about the probability of $Y_n$ lying in certain ranges for large $n$.
The first somewhat interesting observation we can make is: $\Pr[1 \le Y_n < 2] = \Pr[2 \le Y_n < 3] = \dots = \Pr[6 \le Y_n \le 7] = \frac{1}{6}$ for all $n \ge 1$. And $\Pr[Y_n < 1] = \Pr[Y_n > 7] = 0$.
It's impossible for $Y_n$ to be an integer for $n \ge 3$, so we can in fact say that for large enough $n$ (i.e. $\ge 3$) we have a $\frac{1}{6}$ chance that $Y_n$ is in each of the ranges $[1,2], [2,3], \dots, [6,7]$; (this is so we don't need to get too hung up on endpoints latter).
So now if we wanted $Pr[3 \le Y_n \le 5]$ we'd be done already.
But we want something trickier, so let's see what else we can say:
Basically, we can "recurse" this fact to get more equalities.
For a large $n$: the probability $X_n$ is 1 is $\frac{1}{6}$.
Now we also know that $Y_{n-1}$ has $\frac{1}{6}$ probability of being in the ranges $[1,2], [2,3], \dots [6,7]$. So then $X_n$ has probability $\frac{1}{6^2}$ of being in any one of the ranges $[1 + \frac{1}{7}, 1 + \frac{1}{6}], [1 + \frac{1}{6}, 1 + \frac{1}{5}], \dots [1 + \frac{1}{2}, 1 + \frac{1}{1}]$. And prob 0 of being in the range $[1, 1+ \frac{1}{7}]$.
Similarly, $X_n$ has probability $\frac{1}{6^2}$ of being in any one of the ranges $[2 + \frac{1}{7}, 2 + \frac{1}{6}], [2 + \frac{1}{6}, 2 + \frac{1}{5}], \dots [2 + \frac{1}{2}, 2 + \frac{1}{1}]$.
Recursing one step further, we'll get 216 disjoint ranges in which the probability that $Y_n$ is in that range is $\frac{1}{6^3}$. One such is $[2 + \frac{1}{4 + \frac{1}{2}}, 2 + \frac{1}{4 + \frac{1}{3}}]$.
Knowing the notion of continued fractions helps to see/organize what's going on here now - https://en.wikipedia.org/wiki/Continued_fraction.
Using the usual notation for continued fractions (which is a bit confusing since we're using square brackets above for intervals; I'll use parentheses for the intervals below), we can write our above equalities as follows:
Iteration 1: ranges bounded by $([1], [2])$ $([2], [3])$, $\dots$, $([6], [7])$ have probability $\frac{1}{6}$ of containing $Y_n$.
Iteration 2: ranges bounded by $([1,7], [1,6])$, $([1,6], [1,5])$, $\dots$, $([6,2], [6,1])$ have probability $\frac{1}{6^2}$.
Iteration 3: ranges bounded by $([1,6,1], [1,6,2]), \dots ([6,1,6], [6,1,7])$ all have probability $\frac{1}{6^3}$.
With some work we can then derive the following:
If $y$ is a finite continued fraction all of whose terms are $\le 6$, i.e. $y = [y_1, y_2, \dots, y_k]$ where $1 \le y_i \le 6$ for all $i \le k$, then:
for large $n$, if $k$ is odd then $$\Pr[Y_n \le y] = \frac{y_1-1}{6} + \frac{6-y_2}{6^2} + \frac{y_3-1}{6^3} + \frac{6-y_4}{6^4} \dots + \frac{y_k-1}{6^k}.$$ And if $k$ is even then $\Pr[Y_n \le y] = \frac{y_1-1}{6} + \frac{6-y_2}{6^2} + \frac{y_3-1}{6^3} + \frac{6-y_4}{6^4} \dots + \frac{6-y_k}{6^k} + \frac{1}{6^k}$ (note the extra $+\frac{1}{6^k}$).
Now $1+\sqrt{3}$ is the repeating continued fraction $[2,1,2,1,2,1, \dots]$. And $\frac{1+\sqrt{3}}{2}$ is the repeating continued fraction $[1,2,1,2,1,2, \dots]$.
So to get $\Pr[Y_n \le 1+\sqrt{3}]$ we'll just have to sum the corresponding infinite series (can use some inequalities and limits to justify this more rigorously I think -- have not done this).
For $1+\sqrt{3}$ it's $\frac{1}{6} + \frac{5}{6^2} + \frac{1}{6^3} + \dots$. And for $\frac{1+\sqrt{3}}{2}$ it's $\frac{0}{6} + \frac{4}{6^2} + \frac{0}{6^3} + \dots$.
We want the difference which is $\frac{1}{6} + \frac{1}{6^2} + \frac{1}{6^3} + \dots = \boxed{\frac{1}{5}}$.
The details were a bit messy; as the range is a little larger than width 1, this passes one sanity check.
Let $Q(x)$ be the probability that $1/Y_n\leq x$ for large $n$. Then, since $n$ is large, $Q(x)$ is also the probability that $1/Y_{n+1}\leq x$ for large $n$, i.e. $Q(x) = P(1/Y_{n+1}\leq x)=P(X_n+1/Y_n\geq 1/x)$. Taking cases on $X_n$,
$$ Q(x) = \frac{1}{6}\left(P\left(1/Y_n\geq \frac{1}{x}-1\right)+P\left(1/Y_n\geq \frac{1}{x}-2\right)+\dots+P\left(1/Y_n\geq \frac{1}{x}-6\right)\right)\\ =\frac{1}{6}\left(1-Q\left(\frac{1}{x}-1\right)+1-Q\left(\frac{1}{x}-2\right)+\dots+1-Q\left(\frac{1}{x}-6\right)\right)$$
Simplifying, $Q(x)+\sum_{i=1}^6 Q(1/x-i)=1$. Note that $Q(x)=0$ when $x\leq 0$ and $Q(x)=1$ when $x\geq 1$ so the only part of the sum that matters is when $i\leq\left\lfloor 1/x\right\rfloor$. We want to know the probability of $$\frac{(1+\sqrt{3})}{2}\leq Y_n\leq 1+\sqrt{3}\iff \frac{\sqrt{3}-1}{2}\leq \frac{1}{Y_n}\leq \sqrt{3}-1$$.
Let $a=(\sqrt{3}-1)/2$ and $b=\sqrt{3}-1$. Using the equation on $Q(a)$ and $Q(b)$, we get
$$ Q(a)+\frac{1}{6}+\frac{1}{6}Q(b)=1\\ Q(b)+\frac{1}{6}Q(a)=1$$
(This is so nice because coincidentally $1/a-2=b$ and $1/b-1=a$). Solving this system of equations yields $Q(a)=24/35$ and $Q(b)=31/35$. Hence, the solution is $Q(b)-Q(a)=\boxed{1/5}$.