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.



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$.

  • $\begingroup$ A bit more details would be great (please see bounty description). Thanks! $\endgroup$ – icobes Mar 9 '12 at 3:03
  • $\begingroup$ You mean you cannot compute $E(u^{X_k})$? $\endgroup$ – Did Mar 9 '12 at 5:51
  • $\begingroup$ 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. $\endgroup$ – icobes Mar 9 '12 at 6:09
  • $\begingroup$ Is E(uXk) the moment generation function of a geometric? I am probably ocnfused with your notation... $\endgroup$ – icobes Mar 9 '12 at 6:13
  • $\begingroup$ Where is the confusion? Of course m(n) is "your" m(n) (what else?) and you know what is a renewal function, yes? The definition of x(n) is written in the post. And $u\mapsto E(u^{X})$ is the generating function of $X$ (as written in the post). $\endgroup$ – Did Mar 9 '12 at 6:50

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.