Efficient approximate Minimum-Rényi entropy couplings

The Rényi entropy is a natural generalization of Shannon entropy which depends on a parameter $ {{\alpha}} $. Given two probability distributions $ {\mathbf{p}} $ and $ {\mathbf{q}} $, the minimum Rényi entropy coupling is joint distribution of $ {\mathbf{p}} $ and $ {\mathbf{q}} $ with minimal Rényi entropy. We show in this paper that the greedy coupling proposed in Kocaoglu and Dimakis (2017) possesses a Rényi entropy exceeding the exact minimum value at most by $ g({{\alpha}}) $ bits. Here $ g({{\alpha}}) $ decreases to $ 0 $ as $ {{\alpha}} $ tends to infinite, $ g({{\alpha}})\leq 1 $ for $ {{\alpha}}\geq 0.3644 $ and $ g({{\alpha}}) $ tends to $ \log_2 (e)/e\approx 0.53 $ as $ {{\alpha}} $ tends to $ 1 $.