1
$\begingroup$

How would I go about determining the renewal function, $m(n)$, for a general $n$, if the interarrival times, $X_i$ are geometrically distributed with $P(X_i = k) = p \cdot (1-p)^{k-1}$.

I believe I may have to use induction to do this. But if you could get me started off on this, or give me an idea of how the final expression will look like, then that will greatly help.

Thanks!

1 Answers 1

2

Let $S_k=X_1+X_2+\cdots+X_k$ for every $k\geqslant1$, then $x(n)=m(n)-m(n-1)$ is the probability that $S_k=n$ for at least one (hence exactly one) index $k\geqslant1$. Hence your goal is to compute, for each $n\geqslant1$, $$ x(n)=\sum_{k\geqslant1}\mathrm P(S_k=n). $$ Here is a further hint: each $x(n)$ is the coefficient of $u^n$ in the series $$ t(u)=\sum_{k\geqslant1}\mathrm E(u^{S_k}). $$ Now, you should be able to compute the generating functions $u\mapsto\mathrm E(u^{X_k})$ and $u\mapsto\mathrm E(u^{S_k})$, to deduce from these an expression of $t(u)$, and finally that $x(n)=p$ for every $n\geqslant1$.

Edit For every $u$ in $(0,1)$ and every $k\geqslant1$, $\mathrm E(u^{S_k})=\sum\limits_{n\geqslant1}\mathrm P(S_k=n)u^n$ by definition of the generating function. Summing this over $k$ and using the fact that every term is nonnegative hence the order of the summations does not change the result, one gets $$ t(u)=\sum_{k\geqslant1}\sum_{n\geqslant1}\mathrm P(S_k=n)u^n=\sum_{n\geqslant1}u^n\sum_{k\geqslant1}\mathrm P(S_k=n)=\sum_{n\geqslant1}x(n)u^n. $$ Hence, each $x(n)$ is the coefficient of $u^n$ in the series expansion of $t(u)$.

Now, here is an elementary computation: for every $X$ distributed like the random variables $X_k$, $\mathrm E(u^X)=g(u)$ with $$ g(u)=\sum_{k\geqslant1}p(1-p)^{k-1}u^k=pu\sum_{k\geqslant0}((1-p)u)^k=\frac{pu}{1-(1-p)u}. $$ Since $S_k$ is the sum of $k$ independent copies of $X$, $\mathrm E(u^{S_k})=g(u)^k$ for every $k\geqslant1$. Summing this over $k$, one gets $$ t(u)=\sum_{k\geqslant1}g(u)^k=\frac{g(u)}{1-g(u)}. $$ An elementary computation yields $\frac{g(u)}{1-g(u)}=\frac{pu}{1-u}$ hence $t(u)=\sum\limits_{n\geqslant1}pu^n. $ By identification, $x(n)=p$ for every $n\geqslant1$.

  • 0
    A bit more details would be great (please see bounty description). Thanks!2012-03-09
  • 0
    You mean you cannot compute $E(u^{X_k})$?2012-03-09
  • 0
    Yes, I am also confused with your notation. What does x(n) and m(n) represents and how do they differ from my m(n) which is E[N(t)] where N(t) is the number of events that occurred by time t.2012-03-09
  • 0
    Is E(uXk) the moment generation function of a geometric? I am probably ocnfused with your notation...2012-03-09
  • 0
    Where is the confusion? Of course m(n) is "your" m(n) (what else?) and you know what is a [renewal function](http://en.wikipedia.org/wiki/Renewal_theory#The_elementary_renewal_theorem), yes? The definition of x(n) is written in the post. And $u\mapsto E(u^{X})$ is the [generating function](http://en.wikipedia.org/wiki/Probability-generating_function) of $X$ (as written in the post).2012-03-09
  • 0
    What would be the final solution for m(n) so I can verify if what I have gotten is correct?2012-03-09
  • 0
    I also don't seem to follow your assertions about t(u) and how it i s related to this problem.2012-03-09
  • 0
    About $m(n)$: this is written in the post... About $t(u)$: the $u^n$ coefficient of $E(u^Y)$ is $P(Y=n)$, for every nonnegative integer random variable $Y$, this implies the result. // May I suggest that you reread slowly my answer, every sentence is there for a purpose and the total is supposed to let you reach the solution (but, for that, you need to read carefully).2012-03-09
  • 0
    I have worked through it and compared the moment generating function of a geometric r.v. with the mgf of the sum of geometric r.vs. They only differ by a power of k. Is this how you get x(n) to equal p?2012-03-09
  • 0
    As written in the post, one gets $x(n)=p$ by computing (1) $E(u^{X_k})$, (2) $E(u^{S_k})$, (3) $t(u)$, (4) the $u^n$ coefficient in the expansion of $t(u)$. This is the path I suggest to follow, so: which step on this path is a problem?2012-03-09
  • 0
    I believe this is incorrect. I worked it out using the Elementary Renewal Theorem (through induction) and the answer is np.2012-03-16
  • 0
    As written in the post (bis), $x(n)=p$ hence $m(n)=np$. You probably computed $m(n)$...2012-03-16