Expected values and recurrence relations

[techmologist]

I'm really puzzled about this one. Say you have a discrete, nonnegative random variable N where the probability p_n = P{N=n} satisfies the recurrence relation

p_{n+2} + r p_{n+1} + s p_n = 0 for n = 0, 1, 2, ...; p₀ and p₁ are given.

How do you find the expectation E[N] without solving the recurrence? One way I did it was to find the generating function f for this sequence, and evaluate its derivative at x=1:

Define f(x) as

f(x) = \sum_{n \geq 0}p_n x^n and therefore

f'(1) = \sum_{n \geq 0}np_n1^{n-1} = E[N]

To find f(x), multiply the recurrence relation through by x^{n+2} and sum over nonnegative n:

\sum_{n \geq 0}p_{n+2}x^{n+2} + r p_{n+1}x^{n+2} + s p_n x^{n+2} = 0

(f(x) - p_0 - p_1x) + rx(f(x) - p_0) + sx^2f(x) = 0

f(x) = \frac{p_0 + (p_1 + rp_0)x}{1+rx+sx^2}

f'(x) = \frac{p_1 + rp_0}{1+rx+sx^2} - \frac{[p_0 + (p_1 + rp_0)x](r+2sx)}{(1+rx+sx^2)^2}

Evaluate this at x=1 and simplify to get

E[N] = f'(1) = \frac{(1-s)p_1 - s(2+r)p_0}{(1+r+s)^2}

That looked pretty good to me ... until I tried to do it another way. It seems like you should be able to get E[N] directly from the recurrence without having to bother with the generating function. Just multiply through by n+2, rearrange a little, and sum:

\sum_{n \geq 0}(n+2)p_{n+2} + r [(n+1)p_{n+1} + p_{n+1}] + s (np_n + 2p_n) = 0

(E[N] - p_1) + r(E[N] + \sum_{n \geq 0} p_{n+1}) + s(E[N] + 2 \sum_{n \geq 0} p_n) = 0

(E[N] - p_1) + r(E[N] + 1-p_0 ) + s(E[N] + 2) = 0 which gives

E[N] = \frac{p_1 - r(1-p_0) - 2s}{1 + r + s}

These can't both be right. The might both be wrong. Any ideas? thanks in advance.

 

[Pere Callahan]

I agree that both methods are conceptually correct and should give the same result.

One thing I noticed is that in the second approach in the sum
<br /> \sum_{n\geq 0}{(n+2)p_{n+2}} = E[N]-p_1-\mathbf{p_0}<br />
you forgot to subtract p_0 and similarly for the sum
<br /> \sum_{n\geq 0}{(n+1)p_{n+1}} = E[N]-\mathbf{p_0}.<br />

Maybe if you correct this you get an answer compatible with the first approach.

 

[techmologist]

Well, in the sum for expected value, \sum_{n \geq 0} n p_n, p₀ gets multiplied by 0, so you can leave it off. The first (generally) nonzero term is p₁.

 

[Pere Callahan]

True enough. Another point is that you assumed the sum of the p_n to be one. Of course they should sum to unity but they might actually not, depending on the initial values...as it turns out
<br /> \sum_{n\geq 0}p_n = \frac{(1+r)p_0+p_1}{1+r+s}<br />

If you use that the two results coincide.

 

[techmologist]

True enough. Another point is that you assumed the sum of the p_n to be one. Of course they should sum to unity but they might actually not, depending on the initial values...as it turns out
<br /> \sum_{n\geq 0}p_n = \frac{(1+r)p_0+p_1}{1+r+s}<br />

If you use that the two results coincide.

OK, I'll have to think about that. It may be that this is a necessary restriction on p_0, p_1, and the coefficients r and s. Thanks.

 

[techmologist]

True enough. Another point is that you assumed the sum of the p_n to be one. Of course they should sum to unity but they might actually not, depending on the initial values...as it turns out
<br /> \sum_{n\geq 0}p_n = \frac{(1+r)p_0+p_1}{1+r+s}<br />

If you use that the two results coincide.

Aha! I see it now. I misunderstood your post when I read it last night. You are using the condition f(1) = \sum_{n \geq 0}p_n, which I didn't even think about. Thanks for your help!