Dr. I. Csiszar

Dr. I. Csiszar

Budapest, Hungary

September 12, 1995

Common Randomness in Information Theory

Abstract -
It is often desirable that distant terminals have access to common randomness/CR, i.e., to the outcome of the same random experiment. In information theory, the role of CR is basic for identification via chan- nels, for transmission using random codes, e.g., for arbitrarily varying channels, and for secure communication, where CR secret from the eaves- dropper is needed.

In this talk, two-terminal models will be considered that involve a block-length parameter n. One example is when the resources for genera- ting CR consist in the terminals' access to /correlated/ side informa- tion represented by the first resp. second components of n independent repetitions of a pair of random variables (X,Y), and to a noiseless channel over which nR bits may be transmitted, where R>0 is fixed. For models of this kind, the growth rate as n goes to infinity of the maximum amount of CR that can be generated for block-length n, is called the CR capacity, or the key-capacity if secrecy is also required.

Some exact results as well as bounds on such capacities will be given. E.g., the key-capacity of the above model equals the mutual information of X and Y, providing R is sufficiently large. Here the eavesdropper is assumed to "see" the communication between the terminals, hence the secrecy of CR means its stochastic independence from that communication. Models whose statistics depend on unknown parameters will also be considered, requiring CR of nearly uniform distribution no matter what the unknown parameters are.

return to Prior CSPL Seminars homepage