Zero-error stationary coding over stationary channels

Summary For a type of stationary ergodic discrete-time finite-alphabet channel more general than the stationary totally ergodic ¯d-continuous channel of Gray, Ornstein and Dobrushin, it is shown that a stationary, ergodic source with entropy less than capacity can be transmitted over the channel with zero probability of error using stationary codes for encoding and decoding. This result generalizes the result of Gray et al. [3] that Bernoulli sources can be transmitted with zero error at rates below capacity over a totally ergodic ¯d-continuous channel.Research of author supported by NSF Grant MCS-78-21335 and the Joint Services Electronics Program under Contract N00014-79-C-0424.     

Une classe de systemes pour lesquels la conjecture de Pinsker est vraie

In this paper it is proved that any factor of a dynamical system which is isomorphic to the direct product of a Bernoulli shift by a zero entropy system splits in the same way.     

A class of finitary codes

It is shown that for any two Bernoulli schemes with a finite number of states and unequal entropies, there exists a finitary homomorphism from the scheme with larger entropy to the one with smaller entropy.     

The finitary coding of two Bernoulli schemes with unequal entropies has finite expectation

It is well known that for any two Bernoulli schemes with a finite number of states and unequal entropies, there exists a finitary homomorphism from the scheme with the larger entropy to the one with smaller entropy. We prove that the average number of coordinates in the larger entropy scheme needed to determine one coordinate in the image point is finite.     

TheT, T −1-process, finitary codings and weak Bernoulli

We give an elementary proof that the second coordinate (the scenery process) of theT, T ⁻¹-process associated to any mean zero i.i.d. random walk onZ ^d is not a finitary factor of an i.i.d. process. In particular, this yields an elementary proof that the basicT, T ⁻¹-process is not finitarily isomorphic to a Bernoulli shift (the stronger fact that it is not Bernoulli was proved by Kalikow). This also provides (using past work of den Hollander and the author) an elementary example, namely theT, T ⁻¹-process in 5 dimensions, of a process which is weak Bernoulli but not a finitary factor of an i.i.d. process. An example of such a process was given earlier by del Junco and Rahe. The above holds true for arbitrary stationary recurrent random walks as well. On the other hand, if the random walk is Bernoulli and transient, theT, T ⁻¹-process associated to it is also Bernoulli. Finally, we show that finitary factors of i.i.d. processes with finite expected coding volume satisfy certain notions of weak Bernoulli in higher dimensions which have been previously introduced and studied in the literature. In particular, this yields (using past work of van den Berg and the author) the fact that the Ising model is weak Bernoulli throughout the subcritical regime.     

Surjective cellular automata with zero entropy are almost one-to-one

We show that any one-dimensional surjective cellular automata whose entropy is zero with respect to the uniform Bernoulli measure must be almost one-to-one.     

A coding theorem on generalized R-norm entropy

Recently, Hooda and Ram [7] have proposed and characterized a new generalized measure of R-norm entropy. In the present communication we have studied its application in coding theory. Various mean codeword lengths and their bounds have been defined and a coding theorem on lower and upper bounds of a generalized mean codeword length in term of the generalized R-norm entropy has been proved.     

The positive-divergence and blowing-up properties

A property of ergodic finite-alphabet processes, called the blowing-up property, is shown to imply exponential rates of convergence for frequencies and entropy, which in turn imply a positive-divergence property. Furthermore, processes with the blowing-up property-divergence property. Furthermore, processes with the blowing-up property are finitely determined and the finitely determined property plus exponential rates of convergence for frequencies and for entropy implies blowing-up. It is also shown that finitary codings of i.i.d. processes have the blowing-up property. Partially supported by Hungarian National Foundation for Scientific Research Grant OTKA 1906. Partially supported by NSF grant DMS-9024240.     

Entropy theory for sofic groupoids I: The foundations

This is the first part in a series in which sofic entropy theory is generalized to class-bijective extensions of sofic groupoids. Here we define topological and measure entropy and prove invariance. We also establish the variational principle, compute the entropy of Bernoulli shift actions and answer a question of Benjy Weiss pertaining to the isomorphism problem for non-free Bernoulli shifts. The proofs are independent of previous literature.     

The relative isomorphism theorem for Bernoulli flows

In this paper we extend the work of Thouvenot and others on Bernoulli splitting of ergodic transformations to ergodic flows of finite entropy. We prove that ifA is a factor of a flowS, whereS ₁ is ergodic andA has a Bernoulli complement inS ₁, thenA has a Bernoulli complement inS. Consequently, Bernoulli splitting for flows is stable under taking intermediate factors and certain limits. In addition it follows that the property of isomorphism with a Bernoulli × zero entropy flow is similarly stable.     

On the possible values of the entropy of undirected graphs

The entropy of a digraph is a fundamental measure that relates network coding, information theory, and fixed points of finite dynamical systems. In this article, we focus on the entropy of undirected graphs. We prove any bounded interval only contains finitely many possible values of the entropy of an undirected graph. We also determine all the possible values for the entropy of an undirected graph up to the value of four.     

Finite coding factors of Markov generators

Using Thouvenot’s relativized isomorphism theory, the author develops a conditionalized version of the Friedman—Ornstein result on Markov processes. This relativized statement is used to study the way in which a factor generated by a finite length stationary coding sits in a Markov process. All such factors split off if they are maximal in entropy. Moreover, one can show that if a finite coding factor fails to split off, it is relatively finite in a larger factor which either generates or itself splits off.     

Arithmetic coding as a non-linear dynamical system

In order to perform source coding (data compression), we treat messages emitted by independent and identically distributed sources as imprecise measurements (symbolic sequence) of a chaotic, ergodic, Lebesgue measure preserving, non-linear dynamical system known as Generalized Luröth Series (GLS). GLS achieves Shannon’s entropy bound and turns out to be a generalization of arithmetic coding, a popular source coding algorithm, used in international compression standards such as JPEG2000 and H.264. We further generalize GLS to piecewise non-linear maps (Skewed-nGLS). We motivate the use of Skewed-nGLS as a framework for joint source coding and encryption.     

Combinatorial lemmas and applications to dynamics

The well-known combinatorial lemma of Karpovsky, Milman and Alon and a very recent one of Kerr and Li are extended. The obtained lemmas are applied to study the maximal pattern entropy introduced in the paper. It turns out that the maximal pattern entropy is equal to the supremum of sequence entropies over all sequences both in topological and measure-theoretical settings. Moreover, it is shown the maximal pattern entropy of any topological system is logk for some with k the maximal length of intrinsic sequence entropy tuples; and a zero-dimensional system has zero sequence entropy for any sequence if and only if the maximal pattern with respect to any open cover is of polynomial order.     

Isomorphism of random walks

We show that any two aperiodic, recurrent random walks on the integers whose jump distributions have finite seventh moment, are isomorphic as infinite measure preserving transformations. The method of proof involved uses a notion of equivalence of renewal sequences, and the “relative” isomorphism of Bernoulli shifts respecting a common state lumping with the same conditional entropy. We also prove an analogous result for random walks on the two dimensional integer lattice.     

Versik processes: First steps

A. M. Versik defined a property of finite-state stationary stochastic processes that formally is slightly weaker than D. S. Ornstein’s very weak Bernoulli (VWB) property. Versik conjectured his property was equivalent withVWB. The conjecture is false. We construct a zero entropy Versik process that is not loosely Bernoulli (LB) and, by taking a skew product of this process with the two-shift, we produce aK process that is Versik but notVWB. Our technique for constructing a non-LB process differs from the few known methods.     

A complete classification of the two-point extensions of a multidimensional bernoulli shift

A theorem is proven which gives five characterizations of a multidimensional Bernoulli shift. The two-point extensions of a multidimensional Bernoulli shift are classified completely. If such an extension is weakly mixing then it must be Bernoulli; otherwise, it is isomorphic to one of 2 ⁿ specific trivial extensions. This result is extended to multidimensional Bernoulli flows and Bernoulli shifts of infinite entropy. This work supported in part by N.S.F. Grant DMS-85-04701 and by the University of Maryland Department of Mathematics.     

带有反馈机制的单服务台排队系统的泛函重对数律

本文考虑了一个带有贝努里反馈机制的单服务台排队系统.我们将该系统的一些数量指标如队长过程,忙期过程,负荷过程的泛函重对数律的问题转化为一个反射布朗运动相关的问题,利用已有的布朗运动的重对数率的结果,刻画了队长过程,忙期过程,负荷过程的重对数律.     

Factors of Bernoulli shifts

An example is constructed of a proper factor of a Bernoulli shift, that cannot be increased without increasing its entropy, and still has no independent complement. The construction mirrors, in a sense, that of aK-automorphism that is not a Bernoulli shift.     

Generalized higher order Bernoulli number pairs and generalized Stirling number pairs

From a delta series f(t) and its compositional inverse g(t), Hsu defined the generalized Stirling number pair . In this paper, we further define from f(t) and g(t) the generalized higher order Bernoulli number pair . Making use of the Bell polynomials, the potential polynomials as well as the Lagrange inversion formula, we give some explicit expressions and recurrences of the generalized higher order Bernoulli numbers, present the relations between the generalized higher order Bernoulli numbers of both kinds and the corresponding generalized Stirling numbers of both kinds, and study the relations between any two generalized higher order Bernoulli numbers. Moreover, we apply the general results to some special number pairs and obtain series of combinatorial identities. It can be found that the introduction of generalized Bernoulli number pair and generalized Stirling number pair provides a unified approach to lots of sequences in mathematics, and as a consequence, many known results are special cases of ours.