Perspectives

Abstract

Our models go considerably beyond Shannon’s transmission model and the model of identification. They will greatly enlarge the body of information theory. We substantiate here this belief by a brief discussion of how already the identification model alone had a significant impact.

Our models go considerably beyond Shannon’s transmission model and the model of identification. They will greatly enlarge the body of information theory. We substantiate here this belief by a brief discussion of how already the identification model alone had a significant impact.

Right now the most visible influences are new approximation problems (like approximation of output statistics [14] or entropy approximations based on Schur-convexity [10] etc.), a new emphasis on random number generation [1] and, above all, an understanding of the concept of common randomness [9], in identification [10, 11, 13], cryptography [7], and classical transmission problems of arbitrarily varying channels [3, 5, 12], and the paper [6], with a novel capacity formula, which could not be derived before.

It is also fascinating to discover how transmission problems and identification problems in multi-user theory show often some kind of duality. Often identification problems are mathematically more complex and in other cases we encounter the opposite: there is a rather complete capacity theory for identification via multi-way channels in case of complete feedback [10, Lecture 3], whereas for transmission with feedback we don’t even understand the multiple access channel.

We conclude with three more recently encountered directions of research.

1 Comparison of Identification Rate and Common Randomness Capacity: Identification Rate can Exceed Common Randomness Capacity and Vice Versa

One of the observations of [9] (chapter “Identification in the Presence of Feedback: A Discovery of New Capacity Formulas” ) was that random experiments, to whom the communicators have access, essentially influence the value of the identification capacity C _p olID. We introduce now common randomness capacity, which was called mystery number in [10] (chapter “On Identification via Multi-Way Channels with Feedback: Mystery Numbers” ), and has subsequently been called by us in lectures and papers by its present name.

The common randomness capacity C _p olCR is the maximal number ν such, that for a constant c > 0 and for all 𝜖 > 0, δ > 0 and for all n sufficiently large there exists a permissible pair (K, L) of RV’s for length n on a set ${{\mathcal {K}}}$ with $|{{\mathcal {K}}}|<e^{cn}$ with

$$\displaystyle \begin{aligned}\Pr\{K\ne L\} < \epsilon\qquad \text{and}\qquad \frac{H(K)}{n}>\nu-\delta.\end{aligned}$$

Actually, if sender and receiver have a common randomness capacity C _p olCR then by the so called $\sqrt {n}\text{-trick}$ of chapter “Identification in the Presence of Feedback: A Discovery of New Capacity Formulas”, that is, the transformator lemma (discussed in [4]), always

$$\displaystyle \begin{aligned} C_pol{ID}\geq C_pol{CR}\ \text{if }\ C_pol{ID}>0.{} \end{aligned} $$

(1)

For many channels (see [7, 9]), in particular for channels with feedback [9, 10], equality has been proved.

It seemed therefore plausible, that this is always the case, and that the theory of identification is basically understood, when common randomness capacities are known.

We report here a result, which shows that this expected unification is not valid in general—there remain two theories.

Example

In [15] one can find also an example with 0 < C _p olID < C _p olCR)

Example

We will now prove the existence of a sequence of channels (not a sequence of discrete memoryless channels) with C _p olID = 1, C _p olCR = 0.

We use a Gilbert type construction of error correcting codes with constant weight words. This was done for certain parameters in [8] (see chapter “Identification via Channels”, Part I). The same arguments give for parameters needed here the following auxiliary result.

Proposition 126

Let $\mathcal {Z}$ be a finite set and let λ ∈ (0, 1∕2) be given. For (2^3∕λ)⁻¹ < ε < (2^2∕λ + 1)⁻¹ a family A ₁, …, A _N of subsets of $\mathcal {Z}$ exists with the properties

$$\displaystyle \begin{aligned} |A_i|=\varepsilon|\mathcal{Z}|, \qquad |A_i\cap A_j|<\lambda\varepsilon|\mathcal{Z}|\qquad (i\neq j)\end{aligned}$$

and

$$\displaystyle \begin{aligned} N\geq|\mathcal{Z}|{}^{-1}2^{\lfloor\varepsilon|\mathcal{Z}|\rfloor}-1.\end{aligned}$$

Notice that $\lambda \log \left (\frac 1{\varepsilon }-1\right )>2$ and that for ℓ with 2^−ℓ = ε necessarily $\ell >\frac 2{\lambda }$.

Choose now $\mathcal {Z}=\{0,1\}^n$, ε = 2^−ℓ and A _i’s as in the Proposition. Thus |A _i| = 2^n−ℓ, $N(n,\lambda )=2^{-n} 2^{2^{n-\ell }}-1$ and |A _i ∩ A _j| < λ2^n−ℓ.

Consider now a discrete channel $(W^n)^{\infty }_{n=1}$, where the input alphabets $\mathcal {X}_t=\{1,2,\dots ,N(t,\lambda )\}$ are increasing, $\mathcal {X}^n=\prod \limits _{t=1}^n\mathcal {X}_t$ are the input words of length n, $\mathcal {Y}^n=\{0,1\}^n$ are the output words and $W^n:\mathcal {X}^n\rightsquigarrow \mathcal {Y}^n$ is defined by

$$\displaystyle \begin{aligned} W^n(\cdot|i_1i_2\dots i_n)=W^n(\cdot|i_n)\end{aligned}$$

and W ⁿ(⋅|i) is the uniform distribution on A _i for 1 ≤ i ≤ N(n, λ).

By Proposition 126 and 3∕λ > ℓ > 2∕λ

$$\displaystyle \begin{aligned} N(n,\lambda)\geq2^{-n}2^{2^{n-3/\lambda}}\end{aligned}$$

and

$$\displaystyle \begin{aligned} C_pol{ID}\geq\liminf_{n\to\infty}\frac 1n\log\log N(n,\lambda)\geq1.\end{aligned}$$

However, for transmission every decoding set is contained in some A _i and for error probability λ must have cardinality (1 − λ)|A _i| = (1 − λ)2^n−ℓ.

Therefore $M(n,\lambda )\leq \frac {2^n}{(1-\lambda )2^{n-\ell }}\leq 2^{\ell +1}$, if λ < 1∕2, and $\frac 1n\log M(n,\lambda )\leq \frac {\ell +1}n\leq \frac {3/\lambda +1}n\to 0 (n\to \infty )$. The transmission capacity is 0. Consequently also C _p olCR = 0. $\blacktriangle$

Remark

The case of bounded input alphabets remains to be analyzed. What are “natural” candidates for equality of C _p olID and C _p olCR?

Remark

For infinite alphabets one should work out conditions for finiteness of the identification capacity.

2 Robustness, Common Randomness and Identification

It is understood now [6, 7] how the theory of AV-channels is intimately related to the concept of robust common randomness. A key tool is the balanced hypergraph coloring [2]. We sketch now another direction concerning robustness and identification.

For more robust channel models, for instance in jamming situations, where the jammer knows the word to be sent (c.f. AV-channels with maximal error criterion), the communicators are forced to use the maximal error concept. In case of identification this makes the randomization in the encoding (see [8, Lecture 1]) superfluous. Now, for a DMC W it was mentioned in chapter “Identification via Channels” that in the absence of randomization the identification capacity, say $C^*_I(W)$, equals the logarithm of the number of different row-vectors in W. This is easy to show, however, a formidable problem arises if the DMC W is replaced by the AVC $\mathcal {W}$. In fact, for 0-1-matrices only in $\mathcal {W}$ we are—exactly as for transmission—led to the equivalent Shannon-zero-capacity problem. But for general $\mathcal {W}$ the identification problem is quite different from the transmission problem.

In so far there is a lower bound on $C^*_I(\mathcal {W})$, which implies for

$$\displaystyle \begin{aligned}\mathcal{W}= \left\{\left(\begin{array}{cc}1&0\\0&1\end{array}\right), \left(\begin{array}{cc}1&0\\ \delta&1-\delta \end{array}\right)\right\}, \qquad \delta\in(0,1)\end{aligned}$$

that $C^*_I(\mathcal {W})=1$, which is obviously tight. It exceeds the known capacity for transmission. The capacity for

$$\displaystyle \begin{aligned}\mathcal{W}=\left\{ \left(\begin{array}{cc}1&0\\0&1\end{array}\right), \left(\begin{array}{cc}1-\delta&\delta\\ \delta&1-\delta \end{array}\right)\right\}\end{aligned}$$

is unknown.

3 Beyond Information Theory: Identification as a New Concept of Solution for Probabilistic Algorithms

Finally we mention as the perhaps most promising direction the study of probabilistic algorithms with identification as concept of solution. (For example: for any i, is there a root of a polynomial in interval i or not?)

The algorithm should be fast and have small error probabilities. Every algorithmic problem can be thus considered. This goes far beyond information theory. Of course, like in general information transfer also here a more general set of questions can be considered. As usual in complexity theory one may try to classify problems.

What rich treasures do we have in the much wider areas of information transfer?!