# Expected values and recurrence relations

1. Jun 29, 2010

### techmologist

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

$$p_{n+2} + r p_{n+1} + s p_n = 0$$ for n = 0, 1, 2, ....; p0 and p1 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.

2. Jun 29, 2010

### 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
$$\sum_{n\geq 0}{(n+2)p_{n+2}} = E[N]-p_1-\mathbf{p_0}$$
you forgot to subtract $p_0$ and similarly for the sum
$$\sum_{n\geq 0}{(n+1)p_{n+1}} = E[N]-\mathbf{p_0}.$$

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

3. Jun 29, 2010

### techmologist

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

4. Jun 29, 2010

### 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
$$\sum_{n\geq 0}p_n = \frac{(1+r)p_0+p_1}{1+r+s}$$

If you use that the two results coincide.

5. Jun 29, 2010

### techmologist

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.

6. Jun 30, 2010

### techmologist

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!