language: en

The Common Randomness Capacity of a Pair of Independent Discrete Memoryless Channels

S. Venkatesan V. Anantharam zx
13 August 1995

Abstract We study the following problem: two agents Alice and Bob are connected to each other by independent discrete memoryless channels. They wish to generate common randomness by communicating interactively over the two channels. Assuming that Alice and Bob are allowed access to independent external random sources at rates (in bits per step of communication) of H A and H B , respectively, we show that they can generate common randomness at a rate of max f min [H A + H(W jQ); I(P ; V )] + min [H B + H(V jP ); I(Q; W )] g bits per step. Here, V is the channel from Alice to Bob, and W is the channel from Bob to Alice. The maximum is over all probability distributions P and Q on the input alphabets of V and W respectively. We also prove a strong converse which establishes the above rate as the highest attainable in this situation.

Keywords: Common randomness capacity, generating randomness from noise, interactive communication.

[Research supported by NSF IRI 9005849, IRI 9310670, NCR 9422513, and the AT&T Foundation.]

Cornell University and U.C. Berkeley. Univ. of California, Berkeley.

[x Address all correspondence to the second author:]

570 Cory Hall, Dept. of EECS, U.C. Berkeley, Berkeley, CA 94720.