In A Mathematical Theory of Communication, Shannon states
If $N(t)$ represents the number of sequences of duration $t$ we have
$$N(t) = N(t-t_1) + N(t-t_2) + \dots + N(t-t_n).$$
The total number is equal to the sum of the numbers of sequences ending in $S_1,S_2,\dots,S_n$ and these are $N(t-t_1),N(t-t_2),\dots,N(t-t_n)$, respectively. According to a well-known result in finite differences, $N(t)$ is then asymptotic for large $t$ to $AX_0^t$ where $A$ is constant and $X_0$ is the largest real solution of the characteristic equation:
$$X^{-t_1}+X^{-t_2}+\cdots+X^{-t_n}=1$$
Where can I find a reference for this well-known result?
Best Answer
To begin with, assume the numbers $t_i$ are integers, with $t_i<t_{i+1}$; and assume $t$ is also integer; then we have a linear difference equation for $N(t)$, which is homogenous and linear with constant coefficients:
$$N(t) - N(t-t_1)- N(t-t_2)-\cdots N(t-t_n)=0 \tag 1$$
The theory of this is quite elementary. One postulates a solution in the form
$$ N(t)= a^t \tag 2$$ for some (in general complex) number $a$. Replacing in $(1)$ one gets
$$ 1 - a^{-t_1} - a^{-t_2} - \cdots - a^{-t_n}= a^{t_n} - a^{t_n-t_1} - a^{t_n-t_2} - \cdots -1 = 0 \tag{3}$$
This is a polynomial on $a$ of degree $t_n$ (the "characteristic polynomial), so in general it has $t_n$ roots, let them be $a_i$. Then the general solution is
$$N(t) = \sum c_i a_i^t$$
If only real solutions make sense, we stick to the real roots. And the dominant term will correspond to the largest $a_i$, i.e., the largest real root of the polynomial.
What if the numbers $t_i$ are not integer? Well, if they are rational (or at least conmensurable, i.e, they can be expressed as rational multiples of the smallest term) the derivation basically stands. If they are not conmensurable, things are more complex (that's where the answer at MO apply), but we are dealing with engineering here, not pure math, hence this scenario is rather unimportant.