# linear recurrence relations with random coefficients

Are there such things as recurrence equations with random variable coefficients. For example, $$W_n=W_{n-1}+F\cdot W_{n-1}$$ where $F$ is a random variable. I tried to see if I could make sense of it using the simplest possible case of $F$ being a uniform discrete random variable on 2 points but I didn't get far because even if the initial data is not random the succeeding terms in the sequence are and each term seems to live on a different space. I couldn't figure out what space $W_n$ and $W_{n-1}$ should live on. A google search turned up nothing for the obvious keywords "random recurrence equation".

Edit in response to Alekk's answer: More specifically suppose I wanted to find the probability $P(W_{200}>3000)$. Is there a way to compute the distribution of $W_{200}$ explicitly given the distribution of $F$ and some non-random initial data $W_0$?

Edit: $F$ does not depend on $n$ and to make things even more explicit lets say $F$ has the distribution $P(F=2f)=\dfrac{1}{2}, P(F=-f)=\dfrac{1}{2}$.

-
I take it F depends on n. Are the different values of F independent? It's a lot simpler if they are, but if they aren't, then they aren't. – Darsh Ranjan Dec 19 '09 at 5:23
Let me also point out that with V_n = log(W_n) and X_n = log(1+F_n), you have V_n = V_0 + (X_1 + ... + X_n). So you're really just talking about the sum of n random variables; the term "linear recurrence relation" is a red herring. – Darsh Ranjan Dec 19 '09 at 5:27
F does not depend on n. It is equal to 2f with probability 1/2 and it is equal to -f with probability 1/2. There is no dependence on n. – davidk01 Dec 19 '09 at 7:16
I don't think you understood my question. For each n, there is a different random variable "F", right? I. e., if you have W_n, to get W_{n+1}, you have to "re-evaluate" F (like flip a coin), getting a new value to substitute into the formula. (If F didn't depend on n, then you would have a constant-coefficient difference equation.) – Darsh Ranjan Dec 19 '09 at 7:37
Well, certainly. You have to re-evaluate F on each turn but the distribution of F remains constant so I don't see what you mean by it is a different random variable each time. It is exactly like you said: You flip a coin on each turn and assign the value of F based on that flip. – davidk01 Dec 19 '09 at 9:27

So this is the product of IID random variables $1+F_n$, so you could take logarithms and do the more conventional sums of IID random variables $\log(1+F_n)$. Perhaps the logarithms are complex numbers.

-

See the work of Viswanath on random Fibonacci sequences.

-
Not applicable: this involves only the one previous term, not two. (Fooled me at first, too.) – Gerald Edgar Dec 19 '09 at 11:51
Oh, right. I misread the recurrence. – lhf Dec 19 '09 at 18:38

this is a Markov chain, so a lot can be said: ergodicity, CLT, invariance principles, etc... do you have a particular example in mind ?

-
Yes, I was thinking about betting money on some game where F determines how much you bet on each turn and W_{n-1} is the money from the previous game. – davidk01 Dec 19 '09 at 1:27

If you are really interested in random linear recurrences you're in the realm of products of random matrices. There's a lot been done in that field (look it up in math reviews), but you can start with the paper of Furstenberg and Kifer:

Random matrix products and measures on projective spaces Israel Journal of Mathematics, Volume 46, Numbers 1-2 / June, 1983, pp 12-32

$T(n) = T(H(n)) + f(n)$,