Combinatorial Capacity Bounds for the $q$-ary Deletion Channel

We study the \(q\)-ary deletion channel via the pattern-count scalar \(N_n(x,y)\), the number of deletion subsets mapping \(x\in\Sigma_q^n\) to \(y\in\Sigma_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_2 q-h_2(d)\;\le\; C_{q,n}\;\le\;(1-d)\log_2 q. \) The exact uniform-input rate is \( \frac{1}{n}I_U(X;Y) =(1-d)\log_2 q+\frac{1}{n}H_{\mathrm{Bin}}(n,1-d)-h_2(d)+\frac{\Delta_n(d)}{n}, \) from which the simpler certified bound \( C_{q,n}\ge (1-d)\log_2 q-h_2(d)+\frac{\Delta_n(d)}{n} \) follows.

The small-\(d\) bound \(C_q(d)\ge\log_2 q+d\log_2 d+O(d)\) follows for all \(q\ge 2\).

Numerical experiments at \(n=3,5,10\) and \(q=2,3\) confirm all bounds.