The Bug 2

[Earlier installments of The Bug]

Now that I knew about the bug, the next thing to do was tell my advisor. It had been just a few weeks since he said to a luminary visiting campus, “One of my students generalized the entropy power inequality,” to which the luminary replied, “That’s impressive!” What had led me to smile then felt embarrassing now. Had the news spread elsewhere? Would this affect my advisor’s reputation in addition to my own if we ultimately had to retract the result? Why hadn’t I noticed the issue earlier?

To reach a plausible explanation for that last question, it helps to understand how my biases played a role in checking the proof. The incorrect proof had been following a technique similar to the one in Blackman’s “The convolution inequality for entropy powers”, and while Blackman confidently swapped things like the order of derivatives and expectations, I was less confident about these steps in my proof. To justify these steps required applying some measure-theoretic results, and while I’d been exposed to these in a couple probability theory courses, this was the first time I needed to apply them in my research. As a consequence of this insecurity, I focused my attention on making sure that these parts of the argument were watertight and failed to notice that I ultimately wouldn’t be able to apply these watertight arguments to prove the result.

The actual bug came from somewhere that didn’t require any measure-theoretic sophistication. Both Blackman’s proof and mine applied Gaussian perturbations to random variables, with the difference that I had introduced an auxiliary random variable and required a Markov chain to hold. The problem for my proof was that the way I was applying the Gaussian perturbations broke the Markov structure.

I swallowed my pride, found my advisor, and explained the technical issue to him. Our discussion immediately shifted to practical matters. Could we repair the bug in time for the camera-ready deadlines of the different conferences? Part of this would depend on whether we could use the same proof technique or not. We still had a couple weeks before the first camera-ready deadline (a paper that depended on the result) and three months before the camera-ready deadline for the last one (the result itself), so the decision was to work on a patch first and retract later if necessary. We started brainstorming some attacks and looking up possible references that could help.

The Bug

As I read through “Information theoretic inequalities”, it felt like the icing on the cake: a simpler proof of a result from my Master’s thesis. The result itself wasn’t the focus of my Master’s but instead facilitated the proof of a number of other results, so following a writeup of the initial proof and a sanity check by my advisor, I had submitted the result and its many corollaries as a series of papers to a number of conferences. Between those conference submissions and finishing my Master’s thesis, I hadn’t worried about looking for an elegant proof.

By February of 2006, the thesis had been filed, and paper acceptances had started coming in, so my focus had shifted to trying to find alternate ways to show the same result, and with that I had pulled up Dembo et al.’s “Information theoretic inequalities” among other papers of interest like Amir Dembo’s “Information inequalities and uncertainty principles”; the latter came back from Stanford with notes scrawled in blue ink on its margins, likely from Dembo himself, that read, “Ignore this part.”

My eyes had fixed upon a result in the paper showing that for real numbers $a,b,c,d$ where $d > 0$, the following two statements are equivalent:

1. $\displaystyle \exp{\frac{a}{d}} \geq \exp{\frac{b}{d}} + \exp{\frac{c}{d}}$
2. For all $0 \leq \lambda \leq 1$$\displaystyle a \geq \lambda b + (1-\lambda) c - d(\lambda \ln \lambda + (1-\lambda)\ln (1-\lambda))$

The first statement falls out of the second by setting $\lambda = \frac{1}{1 + \exp \frac{c-b}{d}}$, and the second falls from the first by showing that this choice of $\lambda$ maximizes the right side of the inequality in the second statement. The equivalence above let me rewrite my claim in a way that reduced the act of computing derivatives and showing inequalities from a multipage undertaking to a few lines, and I would be able to simplify the “walking downhill” technique I was using to show the result.

I started typing up the new proof, and when I went to apply one of the lemmas I had proven to show the result, I caught myself. Because of an operation that I was performing, one of the conditions needed to apply the lemma wouldn’t hold. Then I went back to the original proof and noticed that it suffered from the same problem. I had found a bug in the proof, and if I couldn’t resolve it quickly, I would have to retract papers and withdraw from conferences. If I couldn’t resolve it at all, a lot of the results that I had proven over the past several months would no longer hold, including one of the key ones from my Master’s thesis.

My Master’s thesis had focused on a class of problems known as CEO problems, which try to characterize fundamental limits on compressing noisy data from multiple sensors when those sensors communicate to a central estimation unit via rate-constrained links. The abstract of the paper introducing the CEO problem contains a more business-focused exposition:

A firm’s Chief Executive Officer (CEO) is interested in the data sequence $\{X(t)\}_{t=1}^{\infty}$ which cannot be observed directly, perhaps because it represents tactical decisions by a competing firm. The CEO deploys a team of $L$ agents who observe independently corrupted versions of $\{X(t)\}_{t=1}^{\infty}$. Because $\{X(t)\}$ is only one among many pressing matters to which the CEO must attend, the combined data rate at which the agents may communicate information about their observations to the CEO is limited to, say, $R$ bits per second. If the agents were permitted to confer and pool their data, then in the limit as $L \rightarrow \infty$ they usually would be able to smooth out their independent observation noises entirely. … In particular, with such data pooling $D$ can be made arbitrarily small if $R$ exceeds the entropy rate $H$ of $\{X(t)\}$. Suppose, however, that the agents are not permitted to convene, Agent $i$ having to send data based solely on his own noisy observations $\{Y_i(t)\}$. We show that then there does not exist a finite value of $R$ for which even infinitely many agents can make $D$ arbitrarily small.

The inspiration for my work had started from a paper by Yasutada Oohama, who had found the sum-rate-distortion function of the quadratic Gaussian CEO Problem.

My goal had been to extend his results to non-Gaussian sources, and while I could show that his sum-rate-distortion function was an upper bound in those cases, I had struggled to find a corresponding lower bound. My hope had been to apply his techniques to derive such a lower bound, but Oohama’s work relied on a specific property regarding the geometry of Gaussian random variables to derive the bound. Specifically, his lower bound followed by tying the orthogonality principle of conditional expectation to statistical independence, which is true for Gaussian random variables, which allowed him to use the entropy power inequality to derive a lower bound.

The proof in which I had just found a bug was an attempt to generalize the entropy power inequality to get around the fact that for non-Gaussian sources, this statistical independence condition would not hold. My attempts to fix the proof or find a counterexample would take me down the rabbit hole of related results and techniques, from Young’s inequality to the Brascamp-Lieb inequality, all because I had just realized the claim I had based part of my identity on was merely a conjecture.

Invoking Authority

Over dinner recently, a friend mentioned that when he is unfamiliar with a topic, he tends to accept what he reads on that topic at face value. The remark sparked some thoughts I’ve been having about how the way in which information is presented can affect how people interpret it, so I shared one example that has been puzzling me.

Suppose I were to say, “Red is better than blue.” Alternatively, suppose I were to say, “I prefer red to blue.” In what sense are these two sentences different from one another?

Both of the statements are making a statement from my perspective, so one could argue that if I say, “Red is better than blue,” then I must prefer red to blue. On the other hand, based on the handful of people to whom I’ve posed these sentences, the first one is more likely to invite an argument; to argue the first, one might be able to appeal to some objective knowledge about the world that contradicts the statement, but to argue against the second, one has to know something about my preferences, and one could argue there is no greater authority on my preferences than I.

My friend’s intuitions appeared to match up with what others had said about that example, so I tried to construct an analogue that was related to a statement that isn’t concerned with the opinions of the speaker to see if a larger pattern might emerge.

Suppose I were to say, “The sky is blue.” Alternatively, suppose I were to say, “I read in an encyclopedia that the sky is blue.”

Again, the first sentence is more likely to invite an argument than the second. Taking this along with with the previous example, I wonder if this all comes down to authority. What makes me an authority on the color of the sky? On the other hand, it could be argued that I am an authority on my memories, and therefore to say, “I read in an encyclopedia that…” suggests that I did read the information. Furthermore, it could also be argued that the encyclopedia is a more reliable authority on the color of the sky than I am, and therefore the second sentence is more authoritative than the first.

I’d be curious to find out to what extent these types of sentences have been studied and whether the thoughts others have in any way line up with the intuitions I’ve detailed.

Posted in Uncategorized | 1 Comment

Propagating Errors

Jim mentioned Puzzled Pint a few months ago, but it conflicted with an improv rehearsal. However, this month, we decided to make Puzzled Pint our troupe’s social outing.

The first step in Puzzled Pint is to figure out where the event will be held. To do this, one solves a location puzzle. In our case, we needed to traverse a maze, and the puzzle was sensitive in the sense that early mistakes propagate to steps later on. It took a while to realize that we had missed a clue, but once it was resolved, we found ourselves on our way.

What’s interesting about a puzzle with this type of propagating error is that it becomes fairly simple to detect that an error was made since the solution is typically an English word or phrase, but not necessarily obvious what the error was, akin to losing an inter frame in video and seeing an error propagate across subsequent frames until the start of the next GOP. The difference between the puzzle and video coding is that given a codec, there is a well understood way to decode the video frames, whereas in the puzzle, the decoding mechanism is intentionally obfuscated and to be deduced along with the solution.

This makes a mistake in a puzzle all the more challenging to debug. For instance, in an early attempt at the February location puzzle, I decoded ROTATERETAMETOYONE, so I was confident that my method was on the right track because the prefix ROTATE is a word, but it wasn’t necessarily clear whether I was applying a correct method and had simply overlooked a piece in the process, or whether the method I was applying was too simplistic to solve the puzzle, and there was something more complex occurring that needed to be applied before moving to the next word.

Ultimately, someone figured out what was missing, and we had a mechanism to validate that the solution we had arrived at was correct. That leads to a second difference between video coding and puzzle solving; namely, it’s sometimes possible to arrive at and validate a solution by sidestepping the expected method the puzzle wants one to apply. For instance, if one gets enough clues that the entropy of the solution is sufficiently low, taking advantage of one’s knowledge of English can provide an alternate mechanism to arrive at the solution instead of figuring out the intended method. In fact, in some cases, one might reverse-engineer the remaining pieces of the method after discovering the solution.

Apples and Oranges

While waiting to do an improv set, Chrysteena told me that she and Jim had three cartons: one with apples, one with oranges, and a third with apples and oranges. Unfortunately, each carton was mislabeled, and they wanted to move the labels to the correct cartons. What is the minimum number of pieces of fruit one would one need to take out of the cartons to correct the labels, and what would be the strategy?

The thing I like about this puzzle is that there’s information encoded in the wording of the problem, and changing one sentence changes the puzzle significantly. “Each carton was mislabeled” indicates that no box contains the correct label, which eliminates 4 out of 6 permutations of labels. If we replace the phrase “each carton was” with “some cartons were” in that sentence, the sentence only eliminates 1 out of 6, and it uncovers a potential ambiguity in how the final sentence of the puzzle is worded, but regardless of how one interprets that sentence, its solution is different from the “each carton was” case. If “each carton was” changes to “the cartons may have been” then the sentence doesn’t eliminate any of the permutations, and depending on how one interprets the wording of the final sentence of the puzzle, it may or may not have the same solution as the “some cartons were” case.

Jigsaw Puzzle Procrastination

During a workshop about academic careers at Allerton in 2008, Roy Yates responded to the above question in one of my favorite responses to a question of this type: “It was the most socially acceptable way to procrastinate what I wanted to do with the rest of my life.”

Recently, a friend posted on Facebook that she decided to spend time working on a jigsaw puzzle with her daughter when the ISIT 2015 submission deadline was extended. Roy responded to the thread:

I’ve been trying to understand why a puzzle with several hundred pieces is easier to put together than an ISIT paper with a few simple ideas. Each puzzle piece has several possible rotations. The ordering of the pieces would seem to explode combinatorially. You can argue that the picture provides a lot of clues, but I suspect you could do that same 200 piece puzzle upside down, without looking at the picture in a maybe one extra hour. I suppose google could tell me why, but I’d rather tag Lalitha Sankar, Chris Rose, Anand Sarwate, Krish Eswaran and Bobak Nazer.

The question immediately reminded me of a paper I’d encountered during my summer at Xerox PARC back in 2002: David Goldberg, Christopher Malon, and Marshall Bern’s “A Global Approach to Automatic Solution of Jigsaw Puzzles”. The algorithm is for the apictorial case, which corresponds to flipping over all the jigsaw pieces face-down so that the picture doesn’t help.

If one tailors an algorithm based on the picture, the discrepancy between the face-up and face-down cases could be quite severe when compared with the abstraction of Goldberg, Malon, and Bern. For instance, imagine a picture whose pixels follow an even gradient that goes from light to dark vertically and from green to red horizontally. Then by splitting the puzzle pieces by greenness and luminance, one could subdivide the initial set of puzzle pieces into four groups of one fourth the size. In fact, one could continue this subdivision until the number of pieces are small, solve them brute force, creating larger puzzle pieces that can then be solved one level above, similar to a divide-and-conquer approach like the merge sort algorithm, taking roughly $O(N \log N)$ steps for $N$-piece puzzles.

The problem with the tailor-made algorithm above is that it doesn’t necessarily generalize to all pictures. One could have a picture that is symmetric, and then any sort of division would result in smaller groups that don’t necessarily merge into a single piece. Similar problems may occur if the puzzle is of a painting by Ad Reinhardt, which effectively reduces the problem to the apictorial case.

While allowances could be made, it’s worth noting that any divide-and-conquer approach cannot automatically take advantage of an algorithm like the one in Goldberg, Malon, and Bern, which attempts to solve the corners first. On the other hand and as noted in the paper, solving the corners, if abstracted in the way that the authors suggest, turns out to be equivalent to a traveling salesman problem and is NP-hard.

It’s unclear to me, however, that the traveling salesman problem is the most useful abstraction. For instance, if one assumes that puzzle pieces only fit together if they fit together in the solution, and there is a unique way in which they do, in the apictorial case, for $N$-piece puzzles, one could test all pieces against each other pairwise in $O(N^2)$ steps to create a graph based on connecting pieces (vertices) that fit together. After that, one could prune the resulting graph one vertex at a time by combining vertices that share an edge at each step, terminating in $N$ steps, thereby solving the puzzle. I suspect there is an even more efficient algorithm one could employ in this case, but this is more to illustrate how an alternate abstraction could make the problem simpler.

Ultimately, it appears there is both a sensitivity to how the jigsaw puzzle problem is abstracted as well as how useful the image is. As to whether a jigsaw puzzle is easier to solve than an ISIT paper is to write, it might be worth revisiting that in a week.

The Doors

It was the first evening of the 2008 School of Information Theory, and Paul Cuff, then a grad student at Stanford, had just shared a probability puzzle about doors (not the Monty Hall problem). I don’t remember exactly how we started on puzzles, but I am pretty sure people had grown tired of my Ali G impersonation. At some point, I had shared a puzzle about dice that has a solution in the spirit of Paul’s puzzle, which may have been the inspiration.

We found a strategy that would work, but calculating the probability seemed a little tricky. When I asked Paul, he mentioned that the probability was about 1/3 but that he hadn’t gleaned any special insights from it. Thoughts about the puzzle were quickly replaced with the more common preoccupations of a final-year graduate student: finishing a dissertation and finding a job. The “about 1/3” result entered my head as a folk theorem.

Recently, I posed the puzzle to Jim and Chrysteena, two friends in the San Francisco improv community. Jim designs puzzles and seemed dissatisfied when he evaluated the probability for the candidate solution purported to be the best. I quoted the folk theorem, but I was dissatisfied, as well, and I thought it was time to revisit the puzzle.

100 Doors Puzzle

There are 100 people and a room with 100 doors. Behind each door is the name of exactly one of the 100 people such that every name is behind exactly one door. The location of the names are unknown to the 100 people. The 100 people are then asked to play the following game:

1. Each person is given a chance to go into the room and open 50 doors.
2. After a person opens 50 doors, the room is reset to the state it was in before entry, and the person who entered may not communicate with any of the other people for the remainder of the game.
3. The game ends in victory if and only if each of the 100 people opens the door with his or her name. In other words, if any one person fails, everyone loses.

If the location of the names behind the doors is chosen at random, find a strategy that maximizes the probability of victory.

Candidate Solution

It helps to look at cases with a smaller number of doors to build intuition. Let’s first consider two doors and two people, in which each person is allowed to open one door. Note that if both people open the same door, then they are guaranteed to lose since we require that they both find their names. Thus, the best strategy is for them to choose separate doors, at which point the probability of them winning is $\frac{1}{2}$. Note that this matches the probability that one of them finds his or her name, so it is optimal.

Now let’s move to four doors, four people, in which each person is allowed to open two doors. After some thought, one strategy that would generalize to 100 doors is to arrange the names in alphabetical order and assign a number to each name based on where it is in the ordering, e.g. the first name in alphabetical order is assigned the number 1, and the last is assigned 100. Then, each person starts by opening the door with the number corresponding to his or her name. Upon opening the door, that person will see a new name, which has its own number associated with it in the alphabetical ordering, and will then proceed to open the door associated with this new number. The process repeats until all tries are exhausted.

If one follows this approach, the cases leading to victory are those in which the process of going through the subsequent doors will cycle through to each person’s name within 50 tries in the case of 100 doors, or within 2 tries in the case of 4 doors. For instance, with 4 doors, victory occurs in a case like the following:

Door 1 (Bob), Door 2 (Alice), Door 3 (Dennis), Door 4 (Cindy)

Bob would start at door 2, see Alice’s name and then go to door 1, where he would find his name. Following the approach for the others results in something similar. On the other hand, we fail if we have a case like this:

Door 1 (Bob), Door 2 (Cindy), Door 3 (Alice), Door 4 (Dennis)

Again, Bob would start at door 2, which would give him Cindy’s name and lead him to door 3, which would give him Alice’s name, by which point he has exhausted his two tries without finding his name. Since one person failed, everyone loses.

It turns out that for four doors, there are 10 cases among the 24 permutations that have these smaller cyles, resulting in a victory with probability $\frac{5}{12}$, which is close to $\frac{1}{2}$. For 100 doors, there’s the folk theorem.

Probability of Victory

One thing that has bothered me in the formulation of the puzzle is that the focus is to maximize the probability, but it’s unclear to me whether the candidate strategy above does this. If “about 1/3” continues to hold as the probability of victory as the number of doors increases say even beyond 100, then at least there is a sense that this is a scaleable strategy if not the best since no strategy can exceed 1/2. On the other hand, if the probability decays to 0, it raises a new question to understand why that’s the case, if all strategies decay to a victory probability of 0 as the number of doors increase, or if there exists a strategy that is within some bound $\Delta < \frac{1}{2}$ of $\frac{1}{2}$.

We can start asking these questions if we have an expression for the probability of victory. Let’s consider $n = 2k$ doors, where $k$ represents the number of tries, and $n = 100$ in the original problem. We have characterized the victory cases as those in which the permutation of doors can be represented as cycles of at most $k$. To calculate the probability, we can use the cycle index of the symmetric group $S_n$ as

$Z(S_n) = \sum_{j_1+2 j_2 + 3 j_3 + \cdots + n j_n = n} \frac{1}{\prod_{i=1}^n i^{j_i} j_i!} \prod_{i=1}^n a_i^{j_i}$,

where $a_i$ denotes cycles of length $i$.

It turns out the cycle index of the symmetric group can be expressed as the recurrence

$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l})$

Let’s define $F_n(a_1, \ldots, a_n) = Z(S_n)$ to highlight the dependence on the cycles. Thus, we can rewrite the above equation as

$F_n(a_1, \ldots, a_n) = \frac{1}{n} \sum_{l=1}^n a_l F_{n-l}(a_1, \ldots, a_{n-l})$.

Let’s define the cumulative distribution function (CDF) $F_{n}^{(i)}$ as $F_n(a_1, \ldots, a_n)$ evaluated at $a_l = 1, l \leq i$ and $a_l = 0, l > i$. In words, $F_{n}^{(i)}$ is the probability that all cycles are of length $i$ or less.

Thus, if we can find an expression for $F_{n}^{(k)}$, we can evaluate it at $F_{100}^{(50)}$ to get our result. The results are contained in Propositions 1 and 2 below, where Proposition 2 is reminiscent of our folk theorem, which yields a probability of $0.306$, which is slightly less than 1/3. Furthermore, Corollary 1.1 indicates that we decrease monotonically to this probability, so regardless of the number of doors, this strategy is within $0.2$ of $\frac{1}{2}$, the upper bound on how well one could possibly do.

Proposition 1. $F_{2k}^{(k)} = F_{n}^{(k)} = 1 - \sum_{m=k+1}^n \frac{1}{m}$.
Proof: The first equality is by definition, so we simply need to show the second equality. For $i \leq j$, we can evaluate the probabilities as

$F_{2j}^{(i)} = \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(i)}$

$F_{2j}^{(2j-i)} = \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(2j-i)} +\frac{1}{2j}\sum_{m=i+1}^{2j-i} F_{2j-m}^{(2j-m)} = \frac{2j-2i}{2j}+ \frac{1}{2j} \sum_{l=1}^i F_{2j-l}^{(2j-i)}$

$F_{2j+1}^{(i)} = \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(i)}$

$F_{2j+1}^{(2j+1-i)} = \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(2j+1-i)} + \frac{1}{2j+1} \sum_{l=i+1}^{2j+1-i} F_{2j+1-l}^{(2j+1-l)} = \frac{2j+1-2i}{2j+1} + \frac{1}{2j+1} \sum_{l=1}^i F_{2j+1-l}^{(2j+1-i)}$.

Note that if $i \leq j$, then $i - 1 \leq j$, so we can apply the same result to get that

$F_{2j}^{(2j+1-i)} = \frac{2j-2(i-1)}{2j}+ \frac{1}{2j} \sum_{l=1}^{i-1} F_{2j-l}^{(2j+1-i)}$

and substituting this into our expression for $F_{2j+1}^{(2j+1-i)}$ yields

$F_{2j+1}^{(2j+1-i)} = \frac{2j}{2j+1} (F_{2j}^{(2j+1-i)} - \frac{2j-2(i-1)}{2j}) = F_{2j}^{(2j+1-i)} - \frac{1}{2j+1}$.

Likewise, one can similarly derive

$F_{2j}^{(2j+1-i)} = F_{2j-1}^{(2j+1-i)} - \frac{1}{2j}$.

Starting with the base case that $F_{2k}^{(k)} = F_{n}^{(k)} = F_{n-1}^{(k)} - \frac{1}{n}$ and the above inductive steps, one can conclude that

$F_{n}^{(k)} = F_{k}^{(k)} - \sum_{m=k+1}^{2k} \frac{1}{m}$.

However, $F_{k}^{(k)} = 1$, so we have our result.

Corollary 1.1. $F_{n+2}^{(k+1)} = F_{n}^{(k)} - \frac{1}{(n+2)(n+1)}$.

Proposition 2. $\lim_{k \rightarrow \infty} F_{2k}^{(k)} = 1 - \ln 2 \approx 0.306$
Proof: From Proposition 1, we can write

$F_{2k}^{(k)} = 1 - \sum_{m=k+1}^{2k} \frac{1}{m}$. Note that we can rewrite the summation

$\sum_{m=k+1}^{2k} \frac{1}{m} = \sum_{i=1}^{k} \frac{1}{k+i} = \sum_{i=1}^{k} \frac{1}{1+i/k} \frac{1}{k}$.

The key is to observe that this is simply a Riemann sum approximating the integral

$\int_{0}^1 \frac{1}{1+x} dx = \ln 2$,

which converges as we let $k \rightarrow \infty$.

Posted in Probability, Puzzle | 8 Comments