# Shannon's communication paper and finite differences

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

-

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.

-
This is very nice. I still think that there are counterexamples of non-measurable $N(t)$: let $T$ be the countable subgroup of $\mathbb R$ generated by the $t_i$ and pick representative elements of each coset of $T$ in $\mathbb R$. You can then find a solution that looks like a different multiple of $X_0^t$ on each coset (maybe some positive and some negative). – Anthony Quas Jan 21 '11 at 4:28
Sure, if $t\mapsto N$ is not (Lebesgue) measurable at some small values of $t$, this "pathology" could propagate to larger values of $t$ by the recursion equation. (Was that your original question?) To ensure the asymptotics $N(t)=(C+o(1))X_0^t$, one could assume that $t\mapsto N(t)$ is measurable and (say) bounded "at the beginning", i.e. on $[0,t_0]$. (So regular as measurable is needed but regular as monotone is not.) – Did Jan 21 '11 at 6:45

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.

-
Thanks for the answer. I agree the space of solutions is a vector space, but not one of finite dimension. Any basis for the v.s. should be truly horrible. I think the uniqueness of $X$ is fairly straightforward. What I really would like though is a reference (if any exists) that treats non-commensurate differences – Anthony Quas Jan 20 '11 at 19:14

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

-
@darij When $n=1$ and $t_1=1$, $N$ is any $1$-periodic function (and not the floor function) hence $N$ is bounded as soon as it is bounded on any interval of length $1$. – Did Jan 20 '11 at 20:17
I interpret $N(t)$ as the number of sequences that can be transmitted in time $t$ or less. Thanks for the commensurate -> commensurable. I fixed this in the question. I don't see any evidence that Shannon wants the $t_i$'s to be integers. Indeed when he introduces them he says "Each of the symbols $S_i$ is assumed to have a duration in time $t_i$ seconds (not necessarily the same for different $S_i$, for example the dots and dashes in telegraphy)." – Anthony Quas Jan 20 '11 at 20:21
"Not necessarily the same" doesn't mean "not necessarily commensurable". So you are going with the 2nd interpretation. Just read what I wrote about it: If you had just one symbol with length $1$, then your $N(t)$ would be the floor of $t$, contradicting the asymptotics. – darij grinberg Jan 20 '11 at 20:48
Is it obvious in Morse code that the length of a dash is an exact integer (or rational) multiple of the length of a dot? – Anthony Quas Jan 21 '11 at 4:30
@darij Bis repetita: if $n=1$, then $N$ is not the floor function. – Did Jan 21 '11 at 6:48

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.

-
A nice simple argument. I think though that as long as the $t_i$ are incommensurable and you assume some regularity of the $N(t)$ (such as being monotonic) I think you do get more strict versions of asymptotic. – Anthony Quas Jan 20 '11 at 20:27