Bit propagation over a noisy grid | Jason Fantl<br>Jason Fantl<br>A computer science blog
HOME CATEGORIES ARCHIVES ABOUT SUBSCRIBE
Home Bit propagation over a noisy grid Post<br>Cancel
Bit propagation over a noisy grid<br>Posted Jun 6, 2026 Updated Jun 8, 2026<br>By Jason Fantl 9 min read
Below is an open problem, an approachable problem, one perhaps you will be the one to solve!<br>We send a bit over a noisy grid, starting from the origin and propagating out as a wave. Can we recover the original bit when looking at just the wavefront?<br>This is easy to solve for 1D, mostly solved in 2D, and still open in 3D and above.<br>Here is the lecture that introduced the problem to me, as well as the paper proving that no single function works in 2D.<br>The problem<br>1D<br>We start with a bit at the root node, in this case the bit is a 1. That node then sends the bit to the next node, indicated with an arrow. This repeats forever. There is a small probability, which we call the temperature, that the bit will flip during each transmission.
The question is, can you determine the original bit by only looking at the last bit in a long chain?<br>You cannot. Your chances of guessing correctly decay exponentially with every hop, down to 50%, at which point you are guessing at random. There’s a good chance the bit is flipped multiple times between the origin and the node you are looking at, so there’s a roughly equal chance it’s a 1 or 0 regardless of what it started out as.<br>There was no way to preserve the original information in 1D. Perhaps we can in 2D?<br>2D<br>Now the information of the original bit gets replicated at each layer, so perhaps there is a better chance we can recover the bit?<br>In order to attempt to recover the bit, we are allowed to look at all the nodes in the wavefront. We will guess that the original bit was a 1 if the majority of bits in the wavefront are 1s, and then likewise for 0s. For the full open problem you are free to use any calculation on the final bits, but we will restrict ourselves to just the majority calculation today. We say the bit is recoverable if the expected percent of correct bits in the wavefront is strictly > 50% as we look at the layers in their limit (again, just for this restricted version of the problem, in general you should be looking to prove that there exists a decoder with error bounded away from 0.5 in the limit).<br>We also need to decide how each node in our 2D grid should handle receiving two different inputs. If both inputs match, then we pass that value forward, as that is likely the value of the original bit. If they are different, we will just pass forward a random value, as both are equally likely.
In this single example, we see how between the 6th and 7th layers the information about the original bit was lost, as it was no longer the majority of the wavefront.<br>Note that the full problem looks at assigning functions to each node, where each node can decide for itself how to handle two inputs. Perhaps some clever combination of functions arranged on the grid will allow more information to be preserved, similar in spirit to Toom’s rule. But for a homogeneous assignment of any function, it has been proved that information is not preserved, at least for 2D. For today, we will use just one function: pass forward the majority bit, or pick at random in a tie.<br>3D<br>The open question, can we recover the bit from the 3D wavefront?
The majority function makes natural sense here, as most nodes have 3 inputs and can erase a bad bit. This means if a single bit gets flipped, there is a good chance it gets immediately fixed due to the surrounding bits being correct and the majority function overwriting the error. Is this enough to maintain the original bit at the wavefront? Let’s explore!<br>Exploring<br>Simulations<br>The first and easiest thing to do is to just simulate a bunch of random 3D grids and see if the percent of correct bits along the wavefront tends to go to 50% or not, sampled across different temperature values.<br>Because this is probabilistic, let’s run 100 simulations at each of 10 temperature values, with grids out to 300 layers. It is likely that the temperature only starts to matter at small values, so let’s sample those logarithmically.
At high temperature, the percent of correct bits drops to 50% very quickly, meaning the original bit is irrecoverable. As we decrease the temperature, the percent of correct bits stays high for longer, but still eventually reaches 50%. At very low temperatures, starting around $2^{-6}$, it is hard to tell when or if the original bit will stay as the majority. Perhaps if we simulate more layers we will see the percent eventually drop, or perhaps at such low temperatures the correct bit will always stay the majority. We don’t know. If there is a phase change from information-eroding to information-preserving anywhere, which we do not know, these empirical simulations suggest we start looking around $2^{-5}$.<br>To get a more intuitive idea for the problem, here is an...