Exact Channel Simulation under Exponential Cost

Hill, Spencer; Alajaji, Fady; Linder, Tamás

Permalink

https://hdl.handle.net/2142/130271 Copy

Description

Title

Exact Channel Simulation under Exponential Cost

Author(s)

• Hill, Spencer
• Alajaji, Fady
• Linder, Tamás

Issue Date

2025-09-17

Keyword(s)

• Channel simulation
• Rényi entropy
• Rényi divergence
• α-mutual information
• Poisson functional representation
• Common randomness
• Variable-length codes
• Exponential cost

Abstract

In this work, we generalize results in exact channel simulation to an exponential communication cost, specifically to Campbell’s average codeword length L(t) of order t [1], and to Rényi’s entropy. In exact channel simulation, given a source of shared randomness, a sender wishes to communicate a message to the receiver so they can generate a sample from the conditional distribution PY |X. We lower bound the Campbell cost of channel simulation using any sampling algorithm, showing that it grows approximately as It+1(X; Y), where Iα is an appropriately defined α-mutual information of order α. Using the Poisson functional representation of Li and El Gamal [2], we prove an upper bound on L(t) whose leading α-mutual information term has order within ϵ of the lower bound. Our results reduce to the bounds of Harsha et al. [3] as t → 0. We also provide numerical examples for the additive white Gaussian noise channel, demonstrating that the upper and lower bounds are typically within 5-10 bits of each other.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130271&&

Copyright and License Information

Copyright 2025 owned by the authors.

Owning Collections