scientific article; zbMATH DE number 3166608

The aim of this paper is to give a mathematical proof of the fundamental Shannon's theorem under sufficiently large conditions, according to the interpretation of \textit{A. N. Kolmogorov} [Trans. Inf. Theory 2, 102--108 (1956)]. A study of the fundamental properties of the information concept as defined in the abstract case is also given. Let \((\xi^1, \eta^1), \ldots, (\xi^t, \eta^t), \ldots\) be a sequence of pairs of (generalized) random variables, where the \((\xi^t, \eta^t)\) are defined on a probability space \((\Omega^t, B^t, P^t)\) and take their values in the measurable spaces \((X^t, S^t_X)\) and \((Y^t, S^t_Y)\), respectively. For the simplicity of the exposé will be all the attributes relative to the pair \((\xi^t, \eta^t)\) indexed by \(t\) with only one time using this index in any individual expression. As it is well known, the information relative to the pair of random variables \((\xi^t, \eta^t)\) is given, in case that it is finite, by \[ I^t(\xi, \eta) = \int_{X^t\times Y^t} \log f^t_{\xi\eta}(x, y) p^t_{\xi\eta}\,(dx, dy) \tag{1} \] where \(p^t_{\xi\eta}\) is the joint probability distribution of the pair \((\xi^t, \eta^t)\) induced by \(P^t\) and \(f^t_{\xi\eta}\) is the Radon-Nikodym density of \(p^t_{\xi\eta}\) with respect to the product measure \(p^t_\xi \times p^t_\eta\), of the corresponding marginal measures. This density always exists in case that the information is finite because in this case \(p^t_{\xi\eta}\) is absolutely continuous with respect to \(p^t_\xi \times p^t_\eta\). The \(\log f^t_{\xi\eta}\) is the so-called information density, noted by \(i^t_{\xi\eta}\). By restricting us in the practically important case of finite information, we shall say that the sequence of pairs of random variables \((\xi^t, \eta^t)\) is information stable if for all sufficiently large \(t\) the information \(0 < I^t(\xi, \eta)< \infty\) and the sequence of random variables \[ (i^t(\xi,\eta)/I^t (\xi,\eta) \to 1\quad\text{for } t\to\infty \tag {2} \] in the sense of convergence in measure. Thus the information stability is a version of what we call the generalized \(E\) (equipartition) property. The definition of the message concept is as follows: let \((X, S_X)\) and \((\tilde X, S_{\tilde X})\) be two given measurable spaces, the one of the messages at the input and the other of the messages at the output. In most applications these two spaces coincide. Let, further, \(W\) be a given set of distributions \(p_{\xi\tilde \xi}(C)\), \(C\in S_X\times S_{\tilde X}\), on the cartesian product \(X\times \tilde X\) such that the corresponding marginal distributions \(p_\xi(A)\) of the component \(\xi\), \(p_\xi(A) = p_{\xi\tilde \xi}(A \times \tilde X)\), coincide for all distributions of \(W\). This set will be called the message \(\{W\}\). The distribution \(p_\xi(\cdot)\) will be called the distribution of the message at the input, and for any pair of random variables \(\xi\) and \(\tilde\xi\) the simultaneous distribution of which belongs to \(W\), it will be said that this pair satisfies the conditions of reproduction \(W\). In the sequel only the special case is considered, where we assume as given a certain number \(M\) of real functions \(\rho_i(x,\tilde x)\), \(i = 1, \ldots, M\), measurable with respect to the \(\sigma\)-algebra \(S_X \times S_{\tilde X}\), and an \(M\)-dimensional set \(\overline W\). The set of distributions \(W\) consists of all distributions \(p_{\xi\tilde \xi}\) for which the \(M\)-dimensional vector of averages \[ \left(\mathbf M\rho_1(\xi,\tilde \xi), \mathbf M\rho_2(\xi, \tilde \xi), \ldots \mathbf M\rho_M(\xi, \tilde \xi)\right) \in \overline W \tag{3} \] and \(\xi\) has the given distribution \(p_\xi\). Message entropy with accuracy of reproduction \(W\) is called the number \[ H(W) =\inf_W I(\xi,\tilde \xi). \tag{4} \] The sequence of messages \(\{W^t\}\) will be called information stable if there exists an information stable sequence of pairs of random variables \(\xi^t,\tilde{\xi^t}\) such that the \(t\)-th pair satisfies the conditions of reproduction \(W^t\) and \[ \lim_{t\to\infty} \frac{I^t(\xi,\tilde \xi)}{H^t(W)} = 1. \tag{5} \] Besides a number of known cases, the author gives an other important example of an information stable sequence of messages, the so-called message with independent components. The problem to obtain general sufficient conditions for information stability of sequences of messages is tightly connected with the problem to obtain sufficiently general conditions for information stability of a sequence of pairs of random variables. The concept of communication channel is in this paper replaced by a slightly modified concept, the so-called transmitter. Let \((Y, S_Y)\) and \((\tilde Y, S_{\tilde Y})\) be two measurable spaces, called, respectively, the space of signals at the input and the space of signals at the output of the transmitter. Let further \(Q(y, \tilde A)\), \(y\in Y\), \(\tilde A\in S_{\tilde Y}\), be a transition function such that 1. for fixed \(y\in Y\), the function \(Q(y, \cdot)\) is a probability measure on \(S_{\tilde Y}\); 2. for fixed \(\tilde A\in S_{\tilde Y}\) the function \(Q(\cdot, \tilde A)\) is measurable with respect to the \(\sigma\)-algebra \(S_Y\). Let, further, \(V\) be a given subset of the set of probability distributions on the cartesian product \((Y \times \tilde Y, S_Y \times S_{\times Y})\)). The system of \(Y, \tilde Y\), of the function \(Q(\cdot, \cdot)\) and of the set \(V\) is called transmitter and noted by \(\{Q, V\}\). We shall say that two random variables \(\eta\) and \(\tilde \eta\) taking their values in the spaces \(Y\) and \(\tilde Y\), respectively, are connected by the transmitter \(\{Q, V\}\) if the joint probability distribution of the pair \((\eta,\tilde \eta)\) belongs to the set \(V\) and for any \(\tilde A\in S_{\tilde Y}\) the conditional probability \(P\{\tilde \eta\in \tilde A\mid \eta\} = Q(\eta, \tilde A)\) almost everywhere. As in the case of messages, in the sequel it is considered by the author only the case, when the limitation \(V\) is given by giving \(N\) real-valued measurable functions \(\pi_i(y, \tilde y)\), \(i =1, \ldots, N\), in the space \(Y \times \tilde Y\), and an \(N\)-dimensional set \(V\). The set \(V\) of distributions consists of such distributions of the pair \((\eta,\tilde\eta)\) that the \(N\)-dimensional vector of averages \((\mathbf M \pi_i(\eta,\tilde\eta), \ldots, \mathbf M \pi_N(\eta,\tilde\eta))\in\overline V\). Particularly important for the applications is the special case when the functions \(\pi_i\) depend only on \(y\), so that the limitation is imposed on the distribution of the input signal. Capacity of the transmitter \(\{Q, V\}\) is called the number \[ C(Q, V) = \sup_V I(\eta,\tilde\eta). \tag{6} \] The sequence of transmitters \(\{Q^t, V^t\}\) is called information stable if there exists an information stable sequence of pairs of random variables \((\eta^t, \tilde{\eta^t})\) such that the \(t\)-th pair is connected by the transmitter \(\{Q^t, V^t\}\) and that \[ \lim_{t\to\infty} \frac{I^t(\eta,\tilde\eta)}{C^t(Q,V)} = 1. \tag{7} \] All the results are related only to the case of information stable sequences of transmitters. Besides the well-known cases of ergodic channels in the discrete theory of information, the author gives an important special class of information stable sequences of transmitters, the so-called transmitters without memory. It is said that the message \(\{W\}\) is transmissible by means of the transmitter \(\{Q, V\}\) if there exist four random variables \(\xi\), \(\eta\), \(\tilde\xi\), \(\tilde\eta\) such that: 1. the sequence of four random variables \(\xi\), \(\eta\), \(\tilde\xi\), \(\tilde\eta\) constitutes a Markov chain; 2. the pair \((\xi, \tilde\xi)\) satisfies the conditions of accuracy of reproduction \(W\); 3. the pair \((\eta, \tilde\eta)\) is connected by the transmitter \(\{Q, V\}\). The conditional probability distribution \(P\{\eta\in A\mid \xi = \tilde x\}\) can be interpreted as the conditional probability distribution of the signal at the input to which the message \(x\) is converted as a result of the coding operation (randomized coding). Analogously, \(P\{\tilde\xi\in \tilde A\mid \tilde \eta = \tilde y\}\) can be interpreted as the conditional probability distribution of the message at the output to which the received signal is converted \(\tilde y\) as a result of the decoding operation (randomized decoding). In the above cited paper of Kolmogorov it is proved that if the message \(\{W\}\) is transmissible by means of the transmitter \(\{Q, V\}\), then \[ H(W) \le C(Q,V). \tag{8} \] The fundamental Shannon's Theorem in the interpretation of Kolmogorov states that, in a certain asymptotic sense and under certain regularity conditions, the inequality (8) is not only necessary but also sufficient for the message transmissibility by means of the transmitter. The proof of some statements of such a type is the aim of the paper. Let so \(\{W^t\}\) be a given sequence of messages and \(\{Q^t, V^t\}\) a given sequence of transmitters. Let \(U\in\mathbb R^n\), where \(\mathbb R^n\) is the \(n\)-dimensional Euclidean space. We shall take as a distance \(r(\overline x', \overline x")\) between two points \(\overline x' = (x_1', \ldots, x_n')\) and \(\overline x = (x_1, \ldots, x_n)\) of \(\mathbb R^n\) the number \(r(\overline x', \overline x") = \max_{i=1,\ldots,n}\vert x_i' - x_i\vert\). Let \([U]_\varepsilon\), \(\varepsilon > 0\), be the set of points \(\overline x\in \mathbb R^n\) such that, for some \(\overline{\overline x}\in U\), \(r(\overline x,\overline{\overline x}) \le \varepsilon\). We shall call message \(\{W_\varepsilon\}\) a message given by the relation (3), but where the set \(\overline W\) is replaced by the set \([\overline W]_\varepsilon\). In an analogous manner we shall call transmitter \(\{Q,V_\varepsilon\}\) a transmitter for which in the corresponding relation the set \(\overline V\) is replaced by the set \([\overline V]_\varepsilon\). We shall say that the message \(\{W\}\) is transmissible by means of the transmitter \(\{Q, V\}\) within an event of probability \(\varepsilon\), if there exist four random variables \(\xi\), \(\eta\), \(\tilde\xi\), \(\tilde\eta\), and a fifth random variable \(\tilde\xi'\), taking its values together with \(\tilde \xi\) in the space \((\tilde X, S_{\tilde X})\), such that: 1. the sequence \(\xi\), \(\eta\), \(\tilde\xi\), \(\tilde\eta\) constitutes a Markov chain; 2. the pair \((\xi, \tilde\xi')\) satisfies the conditions of accuracy of reproduction \(W\); 3. the pair \((\eta, \tilde\eta')\) is connected by the transmitter \(\{Q, V\}\); 4. the probability \(P\{\tilde\xi\ne\tilde\xi'\} \le \varepsilon\). The main theorem states: Let \(\{W^t\}\) be a given sequence of messages and \(\{Q^t, V^t\}\) a given sequence of transmitters, such that \[ \text{I}. \quad \lim_{t\to\infty} H^t(W) = \infty;\qquad \text{II}. \quad \lim_{t\to\infty} \frac{H^t(W)}{C^t(Q,V)} < 1; \] III. the number \(M^t\) of functions \(\rho_i^t(x,\tilde x)\) in the definition of the message and the number \(N^t\) of functions \(\pi_i^t(y, \tilde y)\) in the definition of the transmitter are such that, for every \(a > 0\), \(M^t= o\left(2^{aH^t(W)}\right)\) and \(N^t = o\left(2^{aC^t(Q,V)}\right)\); IV. the sequence \(\{Q^t, V^t\}\) is information stable, so that there exists an information stable sequence of pairs of random variables \((\eta^t ,\tilde\eta^t)\) connected by the transmitter \(\{Q^t, V^t\}\) and satisfying the condition \[ \lim_{t\to\infty} \frac{I^t(\eta,\tilde\eta)}{C^t(Q,V)} = 1 \tag{9} \] and such that for some \(\bar b> 0\) and \[ \bar c^t = \max_{k=1,\ldots, M^t} \mathbf M \left\{\left\vert\pi_k^t(\eta,\tilde\eta) - \mathbf M \pi_k^t(\eta,\tilde\eta)\right\vert^{1+ \bar b}\right\} \] \( \bar c^t= o(2^{aC^t(Q,V)})\), for every \(a > 0\); V. the sequence \(\{W^t\}\) is information stable, so that there exists an information stable sequence of pairs of random variables \(\{\xi^t,\tilde\xi^t\}\) satisfying the conditions of accuracy of reproduction \(\{W^t\}\), the condition \[ \lim_{t\to\infty} \frac{I^t(\xi,\tilde\xi)}{H^t(W)} = 1, \tag{10} \] and such that for some \(b > 0\) and \[ c^t = \max_{k=1,\ldots,M^t} \mathbf M \left\{\left\vert\rho_k^t(\xi,\tilde\xi) - \mathbf M \rho_k^t(\xi,\tilde\xi)\right\vert^{1+ b}\right\}\] \(c^t = o(2^{aH^t(W)})\) for every \(a > 0\). Then for every \(\varepsilon > 0\), it is possible to find a large \(T\), such that for all \(t \ge T\) the message \(\{W_\varepsilon^t\}\) is transmissible by means of the transmitter \(\{Q^t, V_\varepsilon^t\}\) within an event of probability \(\varepsilon\). Under some supplementary conditions it is possible to suppress the last restriction, that the transmissibility takes place ``within an event of probability \(\varepsilon\). For illustration we give a very important special case (Theorem 4): Let be given the information stable sequences of messages \(\{W^t\}\) and of transmitter \(\{Q^t, V^t\}\) such that: \[ 1. \quad \lim_{t\to\infty} H^t(W) = \infty;\qquad 2. \quad \limsup_{t\to\infty} \frac{H^t(W)}{C^t(Q,V)} < 1. \] Let, further, for some constants \(\overline M\), \(\overline N\), \(C\), and for all \(k\) and \(t\), \[ M^t \le \overline M,\quad N^t\le \overline N,\quad \vert\rho_k^t(x, \tilde x)\vert \le C,\quad \vert\pi_k^t(y, \tilde y)\vert \le C. \] Then for every \(\varepsilon > 0\), there exists a large \(T\), such that for all \(t\ge T\) the message \(\{W_\varepsilon^t\}\) is transmissible by means of the transmitter \(\{Q^t, V_\varepsilon^t\}\)

Recommendations

Cited in

(25)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3284980)