{"id":"arxiv/2607.04192","url":"https://arxiv.org/abs/2607.04192","tags":["cs.IT","math.PR"],"score":0,"title":"A Gallager-Type Redundancy Bound for Binary Shannon-Fano Coding","domain":"cs.IT","source":"arxiv","authors":["Kamila Szewczyk"],"reviews":0,"subject":"cs.IT","summary":"Krajči, Liu, Mikeš, and Moser proved in 2015 that the redundancy of binary Shannon-Fano coding is always below one bit. We sharpen this to a bound depending on the largest source probability $p_1$: an explicit seven-piece envelope $R<f(p_1)$. The envelope equals the exact supremum of $R$ given $p_1$ for every $p_1\\ge\\tfrac12$ and on a subinterval below $\\tfrac13$, and gives the cap $R<\\tfrac52-\\tfrac56\\log_2 5=0.5651$ for $p_1<\\tfrac12$. It is the first $p_1$-dependent redundancy bound for Fano codes. The method is more sophisticated than the approach typical for Huffman codes: Fano trees…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-05","reactions":{}}