Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

4 Answers 4

up vote 8 down vote accepted

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.

share|improve this answer
    
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
1  
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
add comment

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
@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
show 2 more comments

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

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.