技術要約：挿入リスト復号容量と削除リスト復号容量の改善された境界

問題設定

本論文は、挿入および削除に焦点を当てた、敵対的な同期エラー下におけるバイナリ符号の**リスト復号容量（list-decoding capacity）**を調査している。ビット反転や消失チャネルとは異なり、これらではリスト復号容量が既知であり、対応する確率的チャネルのシャノン容量と一致するが、同期エラーにおける容量については未解明な部分が多い。

中心となる問いは、「ブロック長 $n$ に対して多項式サイズのリストサイズ $L$ を用いて、$\delta$ 分率の挿入または削除からリスト復号できるバイナリ符号の最大レート $R$ はいくらか？」という点である。

本研究以前の知識は以下のように限定的であった：

• 削除（Deletions）: 最良の既知の下限は一様ランダム符号によって達成される $1 - h(\delta)$ であった。上限は緩い $1 - 2\delta$ であった。
• 挿入（Insertions）: $\delta \leq 1/2$ の場合、下限は同様に $1 - h(\delta)$ であった。$\delta > 1/2$ の場合、極めて小さな正の下限のみが知られており、上限は $(1+\delta)(1 - h(\frac{\delta}{1+\delta}))$ であった。
• ギャップ: 特に挿入において $\delta > 1/2$ の場合、下限と上限の間に大きなギャップが存在しており、構造化されたランダム符号（例：マルコフ連鎖）が、一様ランダム符号よりも優れた性能を発揮できるかどうかは不明であった。

手法

著者らは確率的手法を用い、特にメモリを持つランダム符号（マルコフ連鎖）の性能を一様ランダム符号と比較分析している。

1. マルコフ連鎖サンプリング: ビットごとに独立して（一様にランダムに）符号語をサンプリングする代わりに、著者らは対称な 1 次マルコフ連鎖に従って符号語をサンプリングする。これにより、隣接するビット間に、パラメータ $\alpha$（$X_i = X_{i-1}$ となる確率）によって制御される相関が導入される。
2. 大偏差理論（Large Deviations Theory）: ランダムな符号語が特定の受信文字列を部分列（削除の場合）または超系列（挿入の場合）として含む確率を分析するために、著者らは**クラメールの定理（Cramér's theorem）とモーメント母関数のラグランジュ・フェンツェル変換（Lagrange-Fenchel transform）**を利用している。これにより、「悪い事象」（すなわち、受信文字列が多すぎる数の符号語の部分列であること）の確率に対する精密な漸近的境界を導出することができる。
3. 組合せ論的計数（ラン/Runs）: 削除の容量に関する上限については、符号語における「ラン」（同一記号の最大連続ブロック）の数を分析する。著者らは、鳩の巣原理を用いた議論と、削除ボールのサイズに関する境界（レビンシュタイン境界）を組み合わせ、高レートの符号は多くのランを含む符号語を必ず含み、それが結果として大きなリストサイズを持つ受信文字列の存在を強制することを示す。

主な貢献と結果

1. 挿入からのリスト復号の正確な容量

本論文は、すべての $\delta \in [0, 1]$ における挿入の正確なリスト復号容量 $C_{ins}(\delta)$ を確立する。

• 結果:
  $$C_{ins}(\delta) = (1 + \delta) \left( 1 - h\left( \frac{\delta}{1 + \delta} \right) \right)$$
• 達成可能性: この容量は、注意深く選択された遷移確率 $\alpha = \frac{1+\delta}{2}$ を持つ対称 1 次マルコフ連鎖からサンプリングされた符号によって、高確率で達成される。
• 意義: この結果は挿入に関するギャップを解消する。これは、$\delta \leq 1/2$ で有効であった従来の $1-h(\delta)$ という下限を改善し、$\delta > 1/2$ の場合の極めて小さな正の下限を上回るものである。また、以前に知られていた平均化に基づく上限と一致しており、それがタイトであることを証明している。この構成は、レートが容量を下回る場合に定数サイズのリスト $L = O(1/\epsilon)$ を保証する。

2. 削除に対するマルコフ符号の限界

著者らは、挿入におけるマルコフ連鎖の成功が削除にも拡張されるかどうかを調査している。

• 結果: 1 次マルコフ符号は、削除からのリスト復号において、一様ランダム符号を凌駕することはない。
• 定理: 任意の削除分率 $\delta \in [0, 1/2]$ および任意のレート $R > 1 - h(\delta)$ に対して、1 次マルコフ連鎖からサンプリングされた符号は、高確率で、指数関数的な数の符号語（$2^{\Omega(\epsilon n)}$）の部分列である受信文字列 $y$ を含む。
• 意義: これは挿入と削除の間の**二分性（dichotomy）**を明らかにしている。挿入の容量を達成するためにメモリ（マルコフ構造）が役立つ一方で、削除においては、一様ランダム性がリスト復号のレジームにおいて依然として最適であり、メモリの導入は利点を与えない。

3. 削除容量の改善された上限

本論文は、特に小さな $\delta$ に対して、削除のリスト復号容量 $C_{del}(\delta)$ に関する新しい、より鋭い上限を提供する。

• 結果:
  $$C_{del}(\delta) \leq 1 - \delta - (\gamma - \delta)h\left( \frac{\delta}{\gamma - \delta} \right) = 1 - h(\delta) + o(\delta)$$
  ここで $\gamma = \frac{1}{2} - \sqrt{\frac{h(\delta) \ln 2}{2}}$ である。
• 漸近的挙動: $\delta \to 0$ のとき、容量は $1 - h(\delta) + o(\delta)$ と振る舞う。
• 意義: これは、確率的削除チャネル（ビットが確率 $\delta$ で削除されるチャネル）の容量と一致する。これは、低ノイズ領域において、敵対的なリスト復号容量と確率的チャネル容量が同じ主要項の挙動を共有していることを示唆しており、敵対的なエラーモデルと確率的エラーモデルの間の深い理論的関連性を示している。

意義と主張

本論文は、同期エラー訂正の限界を理解する上で根本的な進展を遂げたと主張している：

1. 挿入問題の解決: 挿入の正確な容量を決定することで、著者らは長年の未解決問題を解決した。彼らは、「平均化境界」がタイトであり、マルコフ的なランダム符号ングによって達成可能であることを示した。
2. モデルの分離: 本研究は、挿入エラーと削除エラーの間の根本的な違いを浮き彫りにしている。挿入容量を最適化する手法（マルコフ連鎖によるメモリの導入）は、一様ランダム性が 1 次マルコフ符号のクラスの中で最適であり続ける削除においては、効果的ではない。
3. 確率的チャネルとの接続: 削除に対する改善された上限は、低ノイズ領域における敵対的なリスト復号容量を確率的削除チャネルの容量と一致させており、敵対的なモデルと確率的モデルの間のより深い理論的つながりを提供している。

著者らは、挿入に関する結果は非構成的（ランダム符号の存在に基づいている）であるが、容量が $1-h(\delta)$ よりも厳密に高いことを示す最初の証明を提供していることを強調している。削除に関しては、主に上限を洗練させ、特定のランダム符号化戦略の限界を特徴付けている。