Shannon's communication paper and finite differences

Question

In Shannon's 1948 paper "A Mathematical Theory of Communication", early on he derives the equation $$N(t)=N(t-t_1)+N(t-t_2)+\ldots+N(t-t_n).$$

He then says "according to a well-known result in finite differences, $N(t)$ is then asymptotic to $X_0^t$ where $X_0$ is the largest solution to the equation $X_0^{-t_1}+\ldots X_0^{-t_n}=1$."

He does not cite a reference. Obviously if the $t_i$ are commensurable, this reduces to a standard constant coefficient recurrence relation, but Shannon does not explicitly make this assumption (in his examples all the $t_i$ are rational).

The result seems to be true in the case of general positive $t_i$ also if you assume some kind of regularity of $N(t)$, but here is my question:

Can anyone suggest a reference that treats this? (the books on finite differences I've seen seem to deal with the commensurable case).

Answer 1

When the $t_i$ are incommensurable in the sense that they generate a dense subgroup, $N(t)=CX_0^t+o(X_0^t)$ for a given constant $C$. This is a consequence of the standard renewal theorem and needs no hypothesis on the monotonicity of the function $t\mapsto N(t)$.

To see this, let $(\xi_k)$ denote some i.i.d. random variables such that $P[\xi_k=t_i]=X_0^{-t_i}$ for every $k$ and $i$. Introduce $M(t)=N(t)/X_0^t$. Then $$ M(t)=E[M(t-\xi_1)]. $$ Fix $t_0$ such that $t_0\ge t_i$ for every $i$. For every positive $k$, let $S_k=\xi_1+\cdots+\xi_k$. For every $t > t_0$, consider the first time $T(t)$ such that $S_{T(t)}\ge t-t_0$. Since $T(t)$ is a stopping time, the martingale property yields $$ M(t)=E[M(t-S_{T(t)})]. $$ Reversing the time axis, $t_0-(t-S_{T(t)})$ becomes the overshoot over $t-t_0$ for the renewal process based on the sequence $(\xi_k)$ and starting from $0$. In the non lattice case, the renewal theorem asserts that $t_0-(t-S_{T(t)})$ converges in distribution to a random variable $\xi_0$ when $t\to+\infty$. Being lattice means that there exists a nonzero $a$ such that the random variables $a\xi_k$ are almost surely integer valued, hence the non lattice case corresponds to non commensurate parameters $t_i$.

Thus, when the $t_i$ are non commensurate, $N(t)/X_0^t=M(t)\to C$ wih $$ C=E[M(t_0-\xi_0)]=X_0^{-t_0}E[N(t_0-\xi_0)X_0^{\xi_0}]. $$ Finally, $\xi_0$ is distributed like $u\xi'$ where $u$ and $\xi'$ are independent, $u$ is uniform on $[0,1]$ and the distribution of $\xi'$ is the size-biased distribution of the distribution of $\xi_k$, given by $P[\xi'=t_i]=t_iX_0^{-t_i}/E[\xi_k]$. Hence one can write $C$ as an explicit integral of the function $N$ over $[0,t_0]$.

A reference is Applied Probability and Queues by Søren Asmussen.

Answer 2

Even if the $t_i$ are not commensurate, the principle of superposition applies to this linear homogeneous recurrence relation. We can therefore find a basis for (the vector space of) all solutions.

The solution is asymptotic to some multiple of $X^t_0$ only if the initial conditions provide some component in that basis element. One might argue this happens with probability 1.

So the question comes down to whether the equation $X^{-t_1} + ... X^{-t_n} = 1$ has a unique solution of largest absolute value, but if we assume that the reasoning seems not to matter whether the $t_i$ are commensurate.

Answer 3

I am pretty sure Shannon assumes the $t_i$ to be commensurable (not "commensurate"), and actually positive integers. He wants $N$ to be a sequence, not a function.

If not, then we've got two possible interpretations of the situation:

1st interpretation: $N(t)$ denotes the number of all transmissions containing only the symbols, with NO pauses inbetween. Then $N(t)$ is a very discontinuous function, being zero at all points which cannot be written as sums of some $t_i$'s, and the asymptotics is toast.

2nd interpretation: $N(t)$ denotes the number of all transmissions containing symbols and pauses, where pauses are ignored on decryption. This makes $N(t)$ not a continuous, but at least a monotonically increasing function. However, in this case the formula $N(t)=N(t-t_1)+N(t-t_2)+...+N(t-t_n)$ should be replaced by something more complicated, and the asymptotic is wrong as well (check $n=1,\ t_1=1$, in which case $N(t)$ should be the floor function of $t$, which is hardly asymptotic to $1^t$).

Answer 4

Shannon might be a bit loose on the definition of asymptotic to here but he is basically right, of course.

To see why, assume there exists two finite constants $A$ and $B$ such that $AX_0^t\le N(t)\le BX_0^t$ for every $t$ in an interval of length at least $\max t_i$. Then, if $\min t_i$ is positive, the same double inequality holds for every $t$ to the right of this interval. Thus, Shannon's statement holds in the sense that $N(t)=\Theta(X_0^t)$.

More strict interpretations of asymptotic to such as equivalent to a multiple of cannot hold in full generality as simple examples based on periodic functions show.