Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Expected values and recurrence relations

  1. Jun 29, 2010 #1
    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

    [tex]p_{n+2} + r p_{n+1} + s p_n = 0[/tex] 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

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

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

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

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

    [tex](f(x) - p_0 - p_1x) + rx(f(x) - p_0) + sx^2f(x) = 0[/tex]

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

    [tex]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}[/tex]

    Evaluate this at x=1 and simplify to get

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

    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:

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

    [tex](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[/tex]

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

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

    These can't both be right. The might both be wrong. Any ideas? thanks in advance.
  2. jcsd
  3. Jun 29, 2010 #2
    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 [itex]p_0[/itex] 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.
  4. Jun 29, 2010 #3
    Well, in the sum for expected value, [tex]\sum_{n \geq 0} n p_n[/tex], p0 gets multiplied by 0, so you can leave it off. The first (generally) nonzero term is p1.
  5. Jun 29, 2010 #4
    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.
  6. Jun 29, 2010 #5
    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.
  7. Jun 30, 2010 #6

    Aha! I see it now. I misunderstood your post when I read it last night. You are using the condition [tex]f(1) = \sum_{n \geq 0}p_n[/tex], which I didn't even think about. Thanks for your help!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook