Channel and question
- Input
- A binary input string.
- Output
- The concatenation of each transmitted bit and, independently with probability \(p\), one fair inserted bit.
- Law
- Random insertions occur after transmitted bits; transmitted bits are never deleted or replaced.
- Quantity
- Random-insertion capacity \(C_{\mathrm{ins}}(p)\), measured in bits per transmitted input bit.
Criterion. Vanishing average decoding error under the fixed iid insertion law.
- Inserted bits are independent Bernoulli one-half symbols.
- The decoder observes only the resulting variable-length output string.
- This is not the Gallager replacement-by-two-bits model.
Parameters
- \(p\)
- Probability that one fair bit is inserted after a transmitted bit. Range: \(0\le p\le1\).
Current status
\[0\le C_{\mathrm{ins}}(p)\le1\]
Small-insertion asymptotics are known, but no exact all-p formula is known.
| Result | Relation | Method | Year |
|---|---|---|---|
| Upper | \(C_{\mathrm{ins}}(p)\le1\) | Binary input entropy bound. | 2025 |
| Lower | \(C_{\mathrm{ins}}(p)\ge0\) | One-message code. | 2025 |
Open question
Determine capacity or sharper finite-p bounds for this random-after-each-bit insertion model.
Random output length and synchronization ambiguity create memory in the induced channel.
Extend rigorous small-p expansions and finite-block certificates.
Formal verification
Lean coverageDefinitions only
Lean declarations (1)
CapacityAtlas.Channel.randomBinaryInsertionStepdefinition
lean/CapacityAtlas/Channels/Insertion.lean — Concrete one-step random binary insertion law.
References
- Busra Tegin and Tolga M. Duman (2025). Capacity Approximations for Insertion Channels with Small Insertion Probabilities. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2025.3644665.