0
$\begingroup$

The problem I'am trying to solve is as follows :

We are given a Recurrence Relation, $$ S(n,k) = (k+1)\cdot S(n-1, k) + 2 \cdot S(n-1, k-1) + (n-k-1)\cdot S(n-1,k-2) \\ \begin{aligned} for \ n \gt 2 \ , k \le n-2\end{aligned} \\S(i,k) = \begin{cases}0\ \ for\ \ k \ne 0\\2\ \ for \ \ k = 0 \end{cases} \\S(1,0) = 1 $$ Some values for $S(n,k)$ are : $$ S(4,0) = 2\ ,S(5,2) = 58\ ,S(3,2) = 0\ ,S(3,1) = 4\ ,S(5,1) = 28 $$

I have a Generating Function $$G_n(z) = \sum_{k=0}^{n-2} \frac{S(n,k)}{n!}\cdot z^k $$

The Expected Value (Mean Value) can be found by $G'_n(1)$. This comes out to be $$ G'_n(1) = \frac{2\cdot n}{3} $$ (I am yet to figure out how to come up with the right hand side of the above equation)

Now I am trying to calculate $$ X = \sum_{k=0}^{n-2}\frac{ k^2\cdot S(n,k)}{n!}\\for\ n \ge4 $$ I think this can be computed by adding the following 2 terms : $$ G'_n(1) + G''_n(1) $$

But I dont know how to compute the Generating Function $G_n(z)$ and hence trying to avoid it. Is it possible to compute it without solving for $G_n(z)$ ? If yes then how should I proceed ?

$\endgroup$
  • $\begingroup$ I think that, by hypothesis, you assume that $\displaystyle \sum_{i=0}^n a_i = 1$ and $a_i \in [0, 1] ~\forall i$. Then $\{a_i\}$ is a probability mass function. But $\{a_i^2\}$ may not be a probability mass function! $\endgroup$ – the_candyman Feb 19 '14 at 10:32
  • $\begingroup$ @the_candyman : yes it seems I have understood the question wrong $\endgroup$ – Kyuubi Feb 19 '14 at 11:49
  • 1
    $\begingroup$ try to improve your question, and then some one may help you :D $\endgroup$ – the_candyman Feb 19 '14 at 12:00
  • 1
    $\begingroup$ I think you want the mean value of the square of the random variable that takes $0$ with probability $a_0$ and $1$ with probability $a_1$, etc. Is this correct? $\endgroup$ – ShreevatsaR Feb 19 '14 at 12:18
  • $\begingroup$ @the_candyman: Edited the question. Although ShreevastsaR caught what I was looking for before I could finish my edit. $\endgroup$ – Kyuubi Feb 19 '14 at 15:06
1
$\begingroup$

I presume that in $$G(z) = a_0 + a_1 z + a_2 z^2 + \dots,$$ $a_k$ represents the probability that a certain discrete random variable (call it $X$) takes the value $k$, for each $k$.

For the mean $E[X]$ defined as $E[X] = a_0(0) + a_1(1) + a_2(2) + a_3(3) + \dots$, we can differentiate to get $$G'(z) = a_1 + 2a_2z + 3a_3z^2 + 4a_4z^3 + \dots,$$ whose value at $z = 1$ is exactly the mean we want.

For the mean $E[X^2]$ defined as $E[X^2] = a_0(0^2) + a_1(1^2) + a_2(2^2) + a_3(3^2) + \dots$ (which is not what you wrote, but what I presume you actually want), you can multiply the above $G'(z)$ by $z$, and differentiate again: $$zG'(z) = a_1z + 2a_2z^2 + 3a_3z^3 + 4a_4z^4\dots,$$ so $$(zG'(z))' = a_1 + 2^2 a_2z + 3^2 a_3z^2 + 4^2a_4z^3 + \dots.$$

The left-hand side is $G'(z) + zG''(z)$, and setting $z = 1$ in this (namely $G'(1) + G''(1)$) gives the value of $E[X^2]$.

$\endgroup$
  • $\begingroup$ Yes thats exactly where I understood the question wrong. My only problem now is, How do I compute $G_n(z),\ G_n'(z)\ and \ G_n''(z)$ . I already know $G′n(1)$. $\endgroup$ – Kyuubi Feb 19 '14 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.