8
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Dec 19, 2009 at 5:23
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 19, 2009 at 5:27
  • $\begingroup$ 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.) $\endgroup$ Dec 19, 2009 at 7:37
  • $\begingroup$ For future reference, what you're talking about then is a sequence of identically distributed random variables, not a single random variable. Since you make the analogy with coin flips, I guess they're independent, too (meaning the conditional distribution of F_n given F_m is just the unconditional distribution of F_n except when m = n). The standard jargon for this situation is "IID random variables" (for "independent, identically distributed"). $\endgroup$ Dec 19, 2009 at 11:16
  • $\begingroup$ To expand on my previous comment: I think the confusion is just that you're conflating a random variable with its distribution. It's the distribution that's staying the same, not the identity of the random variable itself. It's very important to get that straight, because in many situations (like this one), there are lots of distinct random variables with the same distribution. $\endgroup$ Dec 19, 2009 at 11:23

5 Answers 5

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
2
$\begingroup$

See the work of Viswanath on random Fibonacci sequences.

$\endgroup$
2
  • $\begingroup$ Not applicable: this involves only the one previous term, not two. (Fooled me at first, too.) $\endgroup$ Dec 19, 2009 at 11:51
  • $\begingroup$ Oh, right. I misread the recurrence. $\endgroup$
    – lhf
    Dec 19, 2009 at 18:38
1
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.