Combinatorial Capacity Bounds for the q-ary Deletion Channel

2026/07/21 by Hassan Tavakoli, Thinh Nguyen, Bella Bose
Computer Science · Mathematics · #cs.IT #math.IT

paper · pdf

Accepted for publication at Information Theory Workshop 2026, ITW 2026

arxiv created 2026/07/30 · arxiv updated 2026/08/03

Abstract

We study the \(q\)-ary deletion channel via the pattern-count scalar \(N_n(x,y)\), the number of deletion subsets mapping \(x∈Σ_qⁿ\) to \(y∈Σ_q^k\), which factorizes the transition probability. Two sum identities on \(N_n\) certify stochastic normalization and, under uniform input, yield an exact closed-form output entropy. These give the finite-block capacity sandwich \( (1-d)log₂ q-h₂(d) ≤ C_q,n ≤ (1-d)log₂ q. \) The exact uniform-input rate is \( (1)/(n)I_U(X;Y) =(1-d)log₂ q+(1)/(n)H_Bin(n,1-d)-h₂(d)+(Δ_n(d))/(n), \) from which the simpler certified bound \( C_q,n≥ (1-d)log₂ q-h₂(d)+(Δ_n(d))/(n) \) follows. The small-\(d\) bound \(C_q(d)≥log₂ q+dlog₂ d+O(d)\) follows for all \(q≥ 2\). Numerical experiments at \(n=3,5,10\) and \(q=2,3\) confirm all bounds.

Related

• Novel Bounds on the Capacity of the Binary Deletion Channel
• New Capacity Upper Bounds For Binary Deletion Channel
• A new bound for the capacity of the deletion channel with high deletion probabilities
• A Note on the Deletion Channel Capacity
• Improved Upper and Lower Bounds on the Capacity of the Binary Deletion Channel