Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
A bit more details would be great (please see bounty description). Thanks! – icobes Mar 9 '12 at 3:03
You mean you cannot compute $E(u^{X_k})$? – Did Mar 9 '12 at 5:51
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. – icobes Mar 9 '12 at 6:09
Is E(uXk) the moment generation function of a geometric? I am probably ocnfused with your notation... – icobes Mar 9 '12 at 6:13
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). – Did Mar 9 '12 at 6:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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