Renewal process with geometric interarrival times

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!

-

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$.
You mean you cannot compute $E(u^{X_k})$? –  Did Mar 9 '12 at 5:51
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