Computation of Growth Rates of Random Sequences with Multi-step Memory

摘要

We extend the generating function approach to the computation of growth rate of random Fibonacci sequences with long memory. Functional iteration equations are obtained and its general form is conjectured and proved, based on which an asymptotic representation of the growth rate is obtained. The validity of both the derived and the conjectured formula are verified upon comparison with Monte Carlo simulation. A numerical scheme of the functional iteration is designed and implemented successfully.