Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T05:24:25.106Z Has data issue: false hasContentIssue false
  • English
  • Français

Random sequential coding by Hamming distance

Published online by Cambridge University Press:  14 July 2016

Yoshiaki Itoh  and
Herbert Solomon
Yoshiaki Itoh*
Affiliation:
Institute of Statistical Mathematics, Tokyo
Herbert Solomon*
Affiliation:
Stanford University
*
∗Postal address: The Institute of Statistical Mathematics, 4–6–7 Minami-Azabu, Minato-ku, Tokyo, Japan.
∗∗Postal address: Department of Statistics, Sequoia Hall, Stanford University, Stanford, CA 94305–2195, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

Here we introduce two simple models: simple cubic random packing and random packing by Hamming distance. Consider the packing density γ d of dimension d by cubic random packing. From computer simulations up to dimension 11, γ d+1/γ d seems to approach 1. Also, we give simulation results for random packing by Hamming distance and discuss the behavior of packing density when dimensionality is increased. For the case of Hamming distances of 2 or 3, d–α fits the simulation results of packing density where α is an empirical constant. The variance of packing density is larger when k is even and smaller when k is odd, where k represents Hamming distance.

Keywords

SEQUENTIAL RANDOM PACKINGCUBIC PACKINGCODING THEORY
Type
Research Paper
Information
Journal of Applied Probability , Volume 23 , Issue 3 , September 1986 , pp. 688 - 695
Copyright
Copyright © Applied Probability Trust 1986 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

This paper was prepared at Stanford University with the partial support of the Office of Naval Research under Contract N00014–76–C–0475.

References

Abramson, N. (1963) Information Theory and Coding. McGraw-Hill, New York.Google Scholar
Akeda, Y. and Hori, M. (1975) Numerical test of Palásti's conjecture on two-dimensional random packing density. Nature, London 254, 318–319.Google Scholar
Akeda, Y. and Hori, M. (1976) On random sequential packing in two and three dimensions. Biometrika 63, 361–366.Google Scholar
Ash, R. (1965) Information Theory. Interscience Publishers, New York.Google Scholar
Bernal, J. D. (1959) A geometrical approach to the structure of liquids. Nature, London 183, 141–147.CrossRefGoogle Scholar
Blaisdell, B. E. and Solomon, H. (1970) On random sequential packing in the plane and a conjecture of Palásti. J. Appl. Prob. 7, 667–698.Google Scholar
Blaisdell, B. E. and Solomon, H. (1982) Random sequential packing in Euclidean spaces of dimensions three and four and a conjecture of Palásti. J. Appl. Prob. 19, 382–390.Google Scholar
Dolby, J. L. and Solomon, H. (1975) Information density phenomena and random packing. J. Appl. Prob. 12, 364–370.Google Scholar
Dvoretzky, A. and Robbins, H. (1964) On the packing problem. Publ. Math. Inst. Hungar. Acad. Sci. 9, 209–224.Google Scholar
Higuti, I. (1960) A statistical study of random packing of unequal spheres. Ann. Inst. Statist. Math. 12, 257–271.Google Scholar
Itoh, Y. (1980) On the minimum of gaps generated by one-dimensional random packing. J. Appl. Prob. 17, 134–144.Google Scholar
Itoh, Y. and Hasegawa, M. (1980) Why twenty amino acids. Seibutsubutsuri 21, 21–22 (in Japanese).Google Scholar
Itoh, Y. and Ueda, S. (1983) On packing density by a discrete random sequential packing of cubes in a space of n dimension. Proc. Inst. Statist. Math. 31, 65–69 (in Japanese with English summary).Google Scholar
Liu, C. L. (1968) Introduction to Combinatorial Mathematics. McGraw-Hill, New York.Google Scholar
Palásti, I. (1960) On some random space filling problems. Publ. Math. Inst. Hungar. Acad. Sci. 5, 353–360.Google Scholar
Renyi, A. (1958) On a one dimensional problem concerning space filling. Publ. Math. Inst. Hungar. Acad. Sci. 3, 109–127.Google Scholar
Rogers, C. A. (1958) The packing of equal spheres. Proc. London Math. Soc. 3, 609–620.CrossRefGoogle Scholar
Rogers, C. A. (1964) Packing and Covering. Cambridge Tracts in Mathematics and Mathematical Physics 54, Cambridge University Press, Cambridge.Google Scholar
Shannon, C. E. (1948) A mathematical theory of communication. Bell System Tech. J. 27, 379–423, 623–656.Google Scholar
Sloane, N. J. A. (1984) The packing of spheres. Sci. Am. January, 116–125.Google Scholar
Solomon, H. (1967) Random packing density. Proc. 5th Berkeley Symp. Math. Statist. Prob. 3, 119–134.Google Scholar
Tanemura, M. (1979) On random complete packing by discs. Ann. Inst. Statist. Math. 31, 351–365.Google Scholar
Wyner, A. (1964) Improved bounds for minimum distance and error probability in discrete channels. Bell Telephone Laboratories Internal Report, Murray Hill, N.J. Google Scholar