Order Out of Chaos: Sending Information on Channels With Pre-Encoding Loss

Introduction

I first started wondering about this set of problems when I learned that some CDs are not rewritable. I wondered about whether there are any good ways of storing information on already-used CDs: assuming that I am given a CD whose bits are roughly evenly distributed between 1s and 0s, and the only operations I am allowed to perform are to transform 0s into 1s, but not vice versa, can I encode information effectively? At some point, I realized that this problem and related ones can be more generally described, and have some interesting properties that I have discovered, yet all of my work on this topic has left more questions than answers. Please do not treat this post as a completed work; rather, it is a place for me to share my notes on this topic so I and others can reference it.

The textbook Information, Physics, and Computation (Part A) by Mezard and Montanari provides the following figure for a standard flow of information across a lossy channel:

However, I am interested in what happens when the order is switched: what if the loss of the channel occurs prior to the sender encoding their information? How much information is a sender able to convey, working within the limitations of such a system?

TODO: Insert my own little flowchart here

I will explore several concrete problems of this variety below. These are by no means an exhaustive list of them and I would be interested in hearing about other related problems.

Asymmetric Channel Noise

In this problem, the sender is trying to communicate a message to a receiver over a binary channel. The sender can send one bit on each time step, but there is sometimes noise in the channel that causes the channel to convey a 1 bit, instead of whatever the sender sends. Right before the sender sends each bit, they can already tell whether there will be noise 1