Take the 2-minute tour ×

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}$.

share|improve this question
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

5 Answers 5

up vote 2 down vote accepted

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.

share|improve this answer

See the work of Viswanath on random Fibonacci sequences.

share|improve this answer
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 ?

share|improve this answer
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


share|improve this answer

There are such things as probabilistic recurrence relations that come up in the analysis of randomized algorithms. The recurrence form is slightly different to the way you phrase it: rather than the coefficients of the recurrence being random, it's the "jump" itself that can be random. For example, a protoptypical example would be

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

where H(n) is a random function of n (i.e a random variable that takes n as input and returns some random number less than n), and f(n) is some (deterministic) function.

Richard Karp first studied these recurrences in a classic paper, and there was later followup work by Chaudhari and Dubhashi.

share|improve this answer

Your Answer


