Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 119.34001
Autor: Erdös, Pál; Rényi, Alfréd
Title: On two problems of information theory (In English)
Source: Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 229-243 (1963).
Review: Let U be the set of all 2n sequences (\epsilon1,...,\epsilonn) where \epsilonk = 0 or 1 (k = 1,...,n). Let M be an s × n matrix whose elements are 0 or 1. Let u1,...,us be the rows of M. For u = (\epsilon1,...,\epsilonn) in U and u' = (\epsilon'1,...,\epsilon'n) in U let (u,u') = sumk = 1n \epsilonk \epsilon'k and c(u,u') = n-sumk = 1n (\epsilonk-\epsilon'k)2. M is called an A-matrix [resp., a B-matrix] if every element u of U is uniquely determined by the values of (u,u1),...,(u,us) [resp., the values of c(u,u1),...,c(u,us)]. Let A(n) [resp. B(n)] denote the minimal value of s for which there exists an s × n A-matrix [resp., B-matrix]. Results on the asymptotic (with n) behavior of A(n) and B(n) are given.
Reviewer: J.Wolfowitz
Classif.: * 94A15 General topics of information theory
Index Words: probability theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag