Problem Proposal: Flipping Bits in A String

Problem Proposal: Flipping Bits in a String
David Altizio
October 3, 2018
1 Problem
Let n be a positive integer. Given a random n-element sequence s of zeroes and ones, we perform the following
operation repeatedly: if the sequence s has exactly k ones, then the k th element of s is toggled from a 0 to a 1
or vice versa. For example, if n = 3 and the original sequence is (0, 1, 0), then this operation results in the list of
strings
(0, 1, 0) → (1, 1, 0) → (1, 0, 0) → (0, 0, 0).
We see that it takes three steps for this process to reach the sequence consisting of all zeroes.
1. Prove that this process will eventually terminate regardless of what the initial string is. (Here we make the
convention that the string of all zeroes terminates after zero steps.)
2. Determine, with proof, the average number of steps a random n-bit string will take for this process to stop.
1
2 Solution
As stated before, this solution is not 100% airtight, but I’m pretty certain it works. It also happens to be a bit
clunky though, so if there’s an easier solution I’d be happy to see it :)
We will solve both parts of this problem by the following observation. Consider a more substantial example,
namely n = 5 and starting with the string 10111. Below is the sequence of moves, where the flipped bit after each
step is in red.
10101 11110
10001 11100
11001 11000
11101 10000
11111 00000
Notice that this sequence consists of three phases: a downward phase of two zeroes, an upward phase of three
ones, and a downward phase of five zeroes. The key idea is, using this, to assign this binary integer the subset
{2, 3, 5}.
Define Φ : P([n]) → {0, 1}n as follows. Given a subset S = {a1 , . . . , ak } ⊆ [n] with a1 < a2 < · · · < ak , start
with the binary string 00 . . . 0 and perform the following operations.
• Flip the bits in positions 1 through ak to 1s;
• flip the bits in positions ak − ak−1 through ak − 1 to 0s;
• flip the bits in positions ak − ak−1 + 1 through ak − ak−1 + ak−2 to 1s;
• ···
This process eventually stops because our sequence is finite; call the result Φ(s).
Lemma 1. After step t we have the bit sequence that comes from the subset {ak−t+1 , . . . , ak }.
Proof. We proceed by induction on t. Our base case of t = 0 is vacuously true: at step zero our string 00 . . . 0 has
zero ones, and so there is nothing to do.
For the induction step, assume the result holds true for t − 1, where t ≥ 1 is an integer. Remark that after t
steps, we have precisely S := ak − ak−1 + ak−2 − · · · + (−1)t+1 ak−t+1 ones in our string; thus, at the beginning of
this process we will flip the S th bit of the string. Now we perform casework.
• Suppose first that t is odd, so that on the tth step we add 1s to our string. Note that by the way we defined
Φ(s), the S th bit of this string is a 1; thus, the algorithm will change the 1 to a 0. This decreases the number
of ones in our string by 1. As a result, the algorithm will continue down the row of 1s and change each one to
a zero. At the end, we have precisely the string obtained after t − 1 steps, and so we may apply the inductive
hypothesis to finish.
• Suppose next that t is even, so that on the tth step we add 0s to our string. Note that by the way we defined
Φ(s), the S th bit of this string is a 0; thus, the algorithm will change the 0 to a 1. This increases the number
of ones in our string by 1. As a result, the algorithm will continue up the row of 0s and change each one to
a 1. At the end, we have precisely the string obtained after t − 1 steps, and so we may apply the inductive
hypothesis to finish.
We have exhausted all possible cases, and so by induction we are done.
Lemma 2. In fact Φ is a bijection.
Proof. It suffices to prove injectivity, as then the claim follows by the fact that both sets have an equal number of
members.
We’ll show this by induction on the length n of the bit-string. The base case of n = 1 is easy, as the sets ∅
and {1} yield the sequences 0 and 1 respectively. Now suppose that this transformation is injective on strings with
n bits, and consider this function acting on strings with n + 1 bits. Denote by A and B the subsets of P([n + 1])
consisting of all subsets without and with n+1 respectively. We know by the induction hypothesis Φ when restricted
to A is bijective and, in particular, the (n + 1)st bit of any output string is a zero. Now suppose our subset S is in
B. Remark that Φ(S) necessarily contains a 1 in the (n + 1)st bit, since after toggling all the bits to 1s on the first
step we never touch the 1 again; thus, Φ[A] ∩ Φ[B] = ∅, and so it suffices to show that the restriction of Φ to B is
injective. Consider the following two operations on strings of bits on n digits:
2
• reversing the order of the digits, so that e.g. 1011 turns into 1101;
• flipping each bit from a 0 to a 1, so that e.g. 1101 turns into 0010.
Both of these transformations are bijective, so their composition is also bijective; denote the result of this trans-
formation on a string s by s̄. I claim that by the way we defined the transformation, if applying this process to
{a1 , . . . , ak−1 , n} yields the string s1, then applying this process to {a1 , . . . , ak−1 } yields the string s̄. Indeed, by
reversing the order of the indexes in the process given above and swapping all zeroes for ones and vice versa, we
obtain the same process as before:
• flip the bits in positions 1 through ak−1 to 1s;
• flip the bits in positions ak−1 − ak−2 through ak−2 − 1 to 0s;
• ···
Thus injectivity of Φ on all subsets of [n + 1] containing n + 1 is equivalent to injectivity of Φ on all subsets of [n],
which we know is true by the inductive hypothesis.
We can now solve both parts. Part (a) follows from surjectivity of Φ and the fact that every string in the image
of Φ terminates under this algorithm. For (b) remark that the number of steps required for a string s to terminate
is the sum of the elements of the set Φ(s); thus, the answer is the expected sum of elements of a random n-element
n(n+1)
subset of [n], which is 21 (1 + 2 + · · · + n) = 4 . Yay.

Problem Proposal: Flipping Bits in A String

Uploaded by

Copyright:

Available Formats

Problem Proposal: Flipping Bits in A String

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Problem Proposal: Flipping Bits in A String

Uploaded by

Copyright:

Available Formats

Problem Proposal: Flipping Bits in a String

You might also like