News and Comments

on “Testing Error Correcting Codes by Multicanonical Sampling of Rare Events”
J. Phys. Soc. Jpn. 77 (2008) 103801


Measuring Very Rare Events

by Hidetoshi Nishimori (Department of Physics, Tokyo Institute of Technology)
Published October 10, 2008


Do you expect to be hit by a meteorite on your way back home today? No one probably does. Let us see how rare such an event could be. The age of the universe is about 13.7 billion years, or 1.2 × 1014 hours. An extreme underestimate would be that a meteorite hit the earth only once during this time span. Then the probability that such a disaster would happen in a given hour is the inverse of the above number, about 8.3 × 10-15. This rather sloppy calculation provides a rough idea of how small the probability 10-15 is. Iba and Hukushima recently succeeded in generating rare events with probabilities as small as 10-60 on a computer [1]. This was done to evaluate the performance of error-correcting codes, a standard technique to remove errors in digital communication (Fig.1).

Fig. 1: The probability of errors in an error-correcting code at the tail of the distribution.

In error-correcting codes, a sequence of bits (the original message) is first expanded to a longer sequence (encoding) that is more robust to noise in the transmission channel. Then the receiver retrieves the original message (decoding) from the noisy output of the channel, making use of the redundancy in the encoded message (Fig. 2). This whole process can be formally mapped to a problem of spin-glass physics and has been the focus of considerable research activity for a decade or more [2]. What Iba and Hukushima did is, in the terminology of spin-glass physics, to estimate the probability distribution of overlap between the original and decoded messages at the tail of the distribution, i.e., very rare events, for a disordered spin system on a quasi-one-dimensional lattice.

Fig. 2: Schematic illustration of the structure of error-correcting codes.

The key is to generate configurations of random interactions that create very rare values of overlap using Monte Carlo samplings. In standard Monte Carlo simulations, dynamical variables such as spins are updated, but Iba and Hukushima stochastically sampled randomness as well, not just the conventional dynamical variables. Configurations of randomness that tend to generate rarer events (extreme values of overlap) were ingeniously chosen with higher probabilities by exchanging the numerator and denominator of the transition probability such that one puts a larger emphasis on rarer events. This way, they could observe extremely rare events using moderate computational resources.

Such a concept was already proposed several years ago in a different context. The notable contribution of Iba and Hukushima is its successful application to the problem of error-correcting codes, paving the way for the prediction of rare but critical error patterns that can hinder reliable digital communication. This adds another prominent instance to the list of applications of physics to the more abstract world of information [2].


References

  • [1] Y. Iba and K. Hukushima: J. Phys. Soc. Jpn. 77 (2008) 103801.
  • [2] H. Nishimori: Statistical Physics of Spin Glasses and Information Processing: An Introduction (Oxford University Press, Oxford, U.K. 2001).

Note The above article should be referred as “H. Nishimori: JPSJ Online—News and Comments [October 10, 2008]” when citing.

Copyright © 2008 The Physical Society of Japan.