Mutual Information Upper Bounds for Uniform Inputs Through the Deletion Channel
Francisco Pernice, Berivan Isik, Tsachy Weissman · IEEE Transactions on Information Theory · 2024
We consider the mutual information between a uniformly-random input and the corresponding output through the deletion channel. We prove an upper bound that’s within approximately 0.1 of the best-known lower bounds for all values of the deletion probabilityd, and much closer for small and larged. We give simulation results which suggest that our upper bound is within 0.05 of the exact value for alld, and within 0.01 ford> 0.75. Despite our upper bounds, based on simulations, we conjecture that the mutual information is positive for all deletion probabilities less than 1. Our results imply impossibility results for the (equivalent) problem of compression of i.i.d. sources correlated via the deletion channel, a relevant model for DNA storage.