Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

Question

Given an $n$-bit integer, I am interested in performing an increment operation using as few bit reads as possible. The standard binary code (standard binary representation of numbers), requires $n$ bit reads and writes in the worst case, though only $2 - 2^{1-n}$ bit reads on average (i.e $2$ bit reads on average asymptotically). On the other hand, there are codes like the Binary Reflected Gray Code that only require $1$ bit write in the worst case (since all integers in the sequence have hamming distance one). However, the BRGC requires $n$ bit reads in the worst and average case. In addition, there are other codes, such as the Recursive Partition Gray Code, which improve the average number of reads down to $O(\log n)$.

I would like the know if there is a code that can outperform the standard binary code with regards to the average number of reads. I have, however, no restrictions on the number of bit writes or the number of reads in the worst case. I feel like there should be a lower bound that says you cannot do better on average than $2 - 2^{1-n}$, but haven't been able to find a reference.

Edit: I know there is a lower bound of $\log n + 1$ reads in the worst case due to Fredman in 1978, but I am not aware of a lower bound for average case.

Answer 1

There's a trivial lower bound showing that the average number of bits read needs to be strictly greater than $1$. This shows that it's not possible to improve on the standard binary code by more than a factor of 2. Probably not what you were hoping for, but it's something.

---

Proof:

In particular, what would it mean to perform an increment operation using 1 bit read on average? That would mean there is a deterministic "increment" function $f:\{0,1\}^m \to \{0,1\}^m$ and an injective function $\varphi : \{0,1\}^n \to \{0,1\}^m$ such that:

1. The average number of bits read by $f$ is 1. In other words, if we let $X$ be a random variable distributed uniformly on $\{0,1\}^n$ and $Y$ be the number of bits that $f$ reads, on input $\varphi(X)$, then we require $\mathbb{E}[Y]=1$.

2. Let $R$ denote the range of $\varphi$, i.e., $R = \{\varphi(x) : x \in \{0,1\}^n\}$. Then when projecting to $R$, $f:R \to R$ is bijective and its permutation structure consists of a single cycle.

Let's prove that no such pair $(f,\varphi)$ can exist, if $n>1$. In condition 1, note that if $n>1$, $f$ must always read at least one bit of its input, so we always have $Y \ge 1$. From the fact that $Y \ge 1$ always and $\mathbb{E}[Y]=1$, we conclude that $Y=1$ always holds. In other words, it follows that $f$ always reads exactly one bit of its input. Since $f$ is deterministic, the first bit it reads must be independent of the input, so say the first bit $f$ reads is bit position $i$. But since $Y=1$, this is the only bit of its input that $f$ reads. Thus, $f$ only depends on a single bit of the input (bit position $i$). It is easy to see that no such function can meet condition 2, i.e., can be a valid increment function, if $n>1$.

Answer 2

We can prove a tight lower bound of $2 - 2^{1-n}$ as follows. Informally speaking, we will argue inductively that whenever a bit is read during the increment procedure, that one of the two possible outcomes (a $0$ or a $1$ can be read) will cause the algorithm to stop reading additional bits. This will show that if we require the average number of reads to be strictly smaller than $2$, then we required a code isomorphic to the standard binary code.

Suppose that the first bit read by the increment algorithm is bit $i_1 \in [n]$. Now we have three cases to consider. In the first case (A), the algorithm will stop reading additional bits regardless of the value of $i_1$. This means that after reading $i_1$, the algorithm must decide which bits must be flipped right away, and clearly this will not yield a valid increment algorithm for $n > 1$. In the second case (B), the algorithm will adaptively read another bit, regardless of the value of $i_1$. We note that the algorithm may choose to read a different bit depending on the value of $i_1$. In this case, however, we are already reading at least $2$ bits no matter what, so the average number of bits read will exceed $2-2^{1-n}$. Finally, in the third case (C), the algorithm will only read another bit for a single value of $i_1$ (say $1$ for convenience). That is, when $i_1$ is $0$, the algorithm will determine which bits need to be flipped, and when $i_1$ is $1$, the algorithm will probe a second bit. In such a case, the expected number of bit reads is at least $1/2 \cdot 1 + 1/2 \cdot 2 = 3/2$. This is the only case where we can hope to beat the standard binary code.

Now we can apply this argument inductively. Suppose now that the algorithm is adaptively reading bit $i_k$, with $k \leq n-1$. Then in case (A), at most $n-1$ of the bits are ever read by the algorithm. This means that there is a bit that is never read and thus never written to, so the increment algorithm cannot be correct. Here we assume that the only bits that can be flipped are the ones read during that particular increment operation. In case (B), we can verify that the expected number of reads is at least $$\sum_{j=1}^{k-1} j/2^j + 2^{1-k}\cdot(k+1) = 2$$ which is again too many. In case (C), however, the expected number of reads can be verified to be at least $$\sum_{j=1}^{k-1} j/2^j + 2^{-k}\cdot k + 2^{-k} \cdot (k+1) = 2 - 2^{-k}\cdot(2k+3)$$ which is again the only case which might lead us to a better performance than the standard binary code.

When performing the $n$-th bit read, there are no other bits that the algorithm can read (since the other $n-1$ bits have already been read), so only case (A) becomes valid. Computing the expected number of reads then gives exactly $2 - 2^{1-n}$, as required.

---

I find that it helps to view this as a binary decision tree, where the internal nodes are labelled by the bit read, and the leaves are labelled by the bits that are flipped. So you begin by reading the bit labelled at the root of the tree (in our case $i_1$), then you go left if you've read a $0$ and right if you've read a $1$. With this picture in mind, it becomes clear that there are only three cases to consider at each step of the proof.