A. Pelc, Coding with bounded error fraction,
Ars Combinatoria 24 (1987), pp. 17-22.
A. Pelc, Coding with bounded error fraction,
Ars Combinatoria 24 (1987), pp. 17-22.
Abstract:
We discuss the existence and efficiency of error correcting codes under assumption that only a given fraction of code bits may be altered. The results are compared to the classical setting of binary symmetric noisy channel with given cross-over probability.
A. Pelc, Invariant measures on abelian metric groups,
Colloquium Mathematicum 54 (1987), pp. 95-101.
Abstract:
We consider complete countably additive sigma-finite measures which vanish on singletons and are non-identically zero. A measure m defined on a sigma-algebra M of subsets of a group (G, +) is called invariant iff g+A belongs to M and m(g+A)=m(A) for any g in G and A in M. If d is a metric on (G, +), then d is called invariant iff d(x,y) = d(g+x, g+y) for any g, x, y in G. Given a metric d on (G, +), a measure m is called d-invariant iff the following condition holds: for any subsets A, B of G, whenever there exists a funcion f from A onto B such that d(x,y) = d(f(x), f(y)) for any x, y in A, and the set A is m-measurable, then B is also m-measurable and m(A) = m(B). Since left translations are isometries for any invariant metric, a measure invariant with respect to an invariant metric is clearly invariant. The converse turns out to be sometimes true as well. Bandt proved that every left Haar measure on a locally compact metric group is invariant with respect to every invariant metric. The aim of this paper is to show that this is a rather specific feature of Haar measures in the sense that many other invariant measures on groups do not enjoy it. Our main result is the following: Let (G, +) be an abelian group without elements of order 2. Then every invariant measure on G can be extended to an invariant measure which is not invariant with respect to any invariant metric.
A. Pelc, Solution of Ulam's problem on searching with a lie,
Journal of Combinatorial Theory, Series A, 44 (1987), pp. 129-140.
Abstract:
S.M. Ulam, (`` Adventures of a Mathematician, '' Scribner's, 1976.) stated the following problem: what is the minimal number of yes-no queries needed to find an integer between one and one million, if one lie is allowed among the answers. In Rivest et al. (J. Comput. System Sci 20, 396-404 (1980)) and Spencer, (Math. Mag. 57, 105-108 (1984)) partial solutions were given by establishing bounds for the minimal number of queries necessary to find a number in the set {1, ..., n}. Applied to the original question both solutions yield two possibilities: 25 or 26. We give an exact solution of Ulam's problem in the general case. For n=1000000 the answer turns out to be 25. We also give an algorithm to perform the search using the minimal number of queries.