Randomize Fibonacci sequence

Question

We all know that if $a_n$ if the $n^{th}$ Fibonacci number we can say:$$\lim_{n\rightarrow\infty}\frac{a_{n+1}}{a_n}=φ$$ Now let's build another sequence like that:$b_1=b_2=1$ and $b_{n+1}=b_n+b_{n-1}$ or $b_{n+1}\in [b_n,b_{n-1}]$ randomly with chances of $75\%,25\%$ with proportion.

For the second option it's random point in $[b_n,b_{n-1}]$

What will be:$$\lim_{n\rightarrow\infty}\frac{b_{n+1}}{b_n}?$$

Answer 1

This limit will almost surely not exist, since the $b_n$ almost surely switch infinitely often between going up and going down. However, the limit

$$ \lim_{n\to\infty}\sqrt[n]{\frac{b_{n+1}}{b_1}} $$

will almost surely exist. I would expect $\lambda=\frac{b_{n+1}}{b_n}$ to converge in distribution to a limiting distribution, and the above limit would then be the geometric mean of this distribution. Each step of the form $b_{n+1}=b_n+b_{n-1}$ transforms $\lambda$ according to $\lambda\mapsto1+\frac1\lambda$, and each step of the form $b_{n+1}\sim U[b_n,b_{n-1}]$ transforms $\lambda$ according to $\lambda\mapsto\frac1\lambda+u\left(1-\frac1\lambda\right)$. This is a complicated iteration, and I don’t see much hope for finding a closed form for the limiting distribution. The first map has an attractive fixed point at the golden section $\varphi$, whereas the second one takes the reciprocal, thus inverting around $1$, and then condenses the distribution towards $1$.

Here’s Java code that simulates the process and accumulates the distribution. The geometric mean of $\lambda$ (i.e. $\mathrm e^{\langle\log\lambda\rangle}$) is approximately $1.442$, quite close to $\varphi^\frac34\approx1.435$. If we make the probability for either type of step $\frac12$, the geometric mean is approximately $1.280$, quite close to $\varphi^\frac12\approx1.272$. Here’s a diagram of the empirical distribution for probabilities $\frac12$ (click to get the image in full resolution):

The yellow lines are the distribution of $\log\lambda$. The vertical black lines are at $\log1=0$ and at $\log\varphi\approx0.4812$. The symbols in four colours show the distribution disaggregated according to the last two steps. With F denoting a Fibonacci step and R denoting a random step, the magenta plusses, green crosses, cyan asterisks and orange boxes correspond to the states after steps FF, FR, RF and RR, respectively. A Fibonacci step always results in $\lambda\gt1$, and a random step always takes $\lambda$ to the other side of $1$, so the FR component is entirely below $1$. If we were to disaggregate RR further into FRR, FRRR, etc., the components would alternatingly lie above and below $1$. Similarly, the individual peaks in the FF component correspond to RFF, RFFF, etc., with the peaks on alternating sides of $\varphi$ and each peak closer to $\varphi$ by a factor $\phi^{-2}=\frac{3-\sqrt5}2\approx0.382$.

Here’s the diagram for the probabilities $\frac34$ and $\frac14$ that you specified. It’s qualititatively similar; I made the other one because the peaks of similar height make it easier to analyze.