Discrepancy, The Beck-Fiala Theorem, and the Answer to “Test Your Intuition (14)”

The Question

Suppose that you want to send a message so that it will reach all vertices of the discrete n-dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round i all its neighbors will receive it at round i+1.

We will denote the vertices of the discrete n-cube by \pm 1 vectors of length n. The Hamming distance d(x,y) between two such vertices is the number of coordinates they differ and two vertices are neighbors if their Hamming distance equals 1. 

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (-1,-1,-1,…,-1). At round 2 you send the message to vertex (1,1,…,1). Then you sit and wait. With this strategy it will take \lceil n/2\rceil+1 rounds.

Test your intuition: Is there a better strategy?

The Answer: NO

The answer to the question posed in test you intuition (14) is no. There is no better strategy. The question was originated in Intel. It was posed by Joe Brandenburg and David Scott, and popularized by Vance Faber. The answer was proved by Noga Alon in the paper Transmitting in the n-dimensional cube, Discrete Applied Math. 37/38 (1992), 9-11. The result is closely related to combinatorial discrepancy theory and the proof is related to the argument in the Beck-Fiala theorem and a related lemma by Beck and Spencer. This is a good opportunity to present the Beck-Fiala Theorem.

The general form of a discrepancy problem

Let H be a hypergraph, i.e., a collection of subsets of a ground set A. A is also called the set of vertices of the hypergraphs and the subsets in H are also called edges.

The discrepancy of H, denoted by disc(H)  is the minimum over all functions f:A \to \{-1,1\} of the maximum over all  S \in H of

\sum \{f(s):s\in S\}.  

The Erdős Discrepancy Problem (EDP) asks about the following particular hypergraph: The vertices are {1,2,…,n} and the edges are sets of vertices which form arithmetic progressions of the form (r,2r,3r,…kr}. EDP was extensively discussed and studied in polymath5. Here is the link of the first post. Here are links to all polymath5 posts.  Here is the link to polymath5 wiki.

The Beck-Fiala theorem

Theorem (Beck-Fiala): If every element in A is included in at most t edges  of  H then disc(H)<2t.

Before proving this theorem we mention that it is a famous open conjecture to show that actually disc(H)=O(\sqrt t)

Proof:  Continue reading

Test Your Intuition (14): A Discrete Transmission Problem

Recall that the n-dimensional discrete cube is the set of all binary vectors (0-1 vectors) of length n. We say that two binary vectors are adjacent if they differ in precisely one coordinate. (In other words, their Hamming distance is 1.) This gives the n-dimensional discrete cube a structure of a graph, so from now on , we will refer to binary vectors as vertices.

Suppose that you want to send a message so that it will reach all vertices of the discrete n-dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round i all its neighbors will receive it at round i+1.

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (0,0,0,…,0). At round 2 you send the message to vertex (1,1,…,1). Then you wait and sit. With this strategy it will take \lceil n/2\rceil+1 rounds.

Test your intuition: Is there a better strategy?

Here is a link to previous posts in the “Test-your-intuition” series.

Test Your Intuition (13): How to Play a Biased “Matching Pennies” Game

Recall the game “matching pennies“. Player I has to chose between ‘0’ or ‘1’, player II has to chose between ‘0’ and ‘1’.No player knows what is the choice of the other player before making his choice. Player II pays to player I one dollar if the two number match and gets one dollar from player I  if they do not match.

The optimal way to play the game for each of the player is via a mixed strategy. Player I has to choose ‘0’ with probability 1/2 and ‘1’ with probability 1/2. And so is player II.

Now, suppose that the game is the same except that if the outcomes match and both player chose ‘1’ player II pays 5 dollars to player I and not one dollar. (All other payoffs remain at one dollar.)

Test your intuition: What is the probability player I should play ‘1’. (More than 1/2? less than 1/2? more than 1/3? less than 1/3? more than 2/3? less than 2/3?)

Continue reading

Test Your Intuition (12): Perturbing a Polytope

Let P be a d-dimensional convex polytope. Can we always perturb the vertices of P moving them to points with rational coordinates without changing the combinatorial structure of P?

In order words, you require that a set of vertices whose convex hull is a k-dimensional face of P will have this property after the perturbation.

Test Your Intuition (11): Is it Rational to Insure a Toaster

Here is a question from last year’s exam in the course “Basic Ideas of Mathematics”:
 
You buy a toaster for 200 NIS ($50) and you are offered one year of insurance for 24 NIS ($6).
 
a) Is it worth it if the probability that damage covered by the insurance will occur during the first year is 10%? (We assume that without insurance, such damage makes the toaster a “total loss”.)
 
b) Is it worth it if the probability that the toaster will be damaged is unknown?
 
As an additional test of your imagination, can you think of reasons why buying the toaster insurance would be rational?

Test Your Intuition (10): How Does “Random Noise” Look

This is a bit unusual post in the “test your intuition” corner as the problem is not entirely formal.  

How does random noise in the digital world typically look?

Suppose you have a memory of n bits, or a memory based on a larger r-letters alphabet, and suppose that a “random noise” hits the memory in such a way that the probability of each bit being affected is t.

What will be the typical behavior of such a random digital noise? Part of the question is to define “random noise” in the best way possible, and then answer it for this definition.

In particular, Will the “random noise” typically behave in a way which is close to be independent on the different bits? or will it be highly correlated? or pehaps the answer depends on the size of the alphabet and the value of t?

The source of this question is an easy fact about quantum memory which asserts that if you consider a random noise operation acting on a quantum memory with n qubits, and if the probability that every qubit is damaged is a tiny real number t, then typically the noise  has the following form: with large probability nothing happens and with tiny probability (a constant times t) a large fraction of qubits are harmed.

 I made one try for the digital (binary) question but I am not sure at all that it is the “correct” definition for what “random noise” is.

(Maybe I should try to ask the problem also on “math overflow“. See also here, here and here for what math overflow is.)

Update:  over “mathoverflow” Greg Kuperberg made an appealing argument that for the correct notion of random noise the behavior in the classical case is similar to that of the quantum case.

Test Your Intuition #9 (answer to #9),  #8  (answer),   #7,   #6,  #5,  #4 (answer), #3 (answer), #2#1.

Answer to Test Your Intuition (9)

Two experimental results of 10/100 and 15/100 are not equivalent to one experiment with outcomes 3/200.

(Here is a link to the original post.)

One way to see it is to think about 100 experiments. The outcomes under the null hypothesis will be 100 numbers (more or less) uniformly distributed in [0,1]. So the product is extremely tiny.

What we have to compute is the probability that the product of two random numbers uniformly distributed in [0,1] is smaller or equal 0.015. This probability is much larger than 0.015.

Here is a useful approximation (I thank Brendan McKay for reminding me): if we have n independent values in U(0,1)  then the prob of product < X is

X \sum_{i=0}^{n-1} ( (-1)^i (log X)^i/i!.

In this case  0.015 * ( 1 – log(0.015) ) = 0.078

So the outcomes of the two experiments do not show a significant support for the theory.

The theory of hypothesis testing in statistics is quite fascinating, and of course, it became a principal tool in science and  led to major scientific revolutions. One interesting aspect is the similarity between the notion of statistical proof which is important all over science and the notion of interactive proof in computer science. Unlike mathematical proofs, statistical proof are based on following certain protocols and standing alone if you cannot guarantee that the protocol was followed the proof has little value.

Buffon’s Needle and the Perimeter of Planar Sets of Constant Width

Here is an answer to “Test your intuition (8)”. (Essentially the answer posed by David Eppstein.)

BuffonNeedle_700

(From Wolfram Mathworld)

Buffon’s needle problem asks to find the probability that a needle of length \ell will land on a line, given a floor with equally spaced parallel lines at distance one apart. The problem was posed by Georges-Louis Leclerc, Comte de Buffon (1707 – 1788).

There is a familiar computation showing that when \ell \le 1 the probability is 2\ell/\pi. A computation-free proof can be found in these pages on geometric probability written mostly by Molly McGinty. (They were pointed to me by Sergiu Hart.)

Briefly the computation-free argument goes as follows:

1) Consider the expected number of crossings of a needle with the lines rather than the probability of crossing.

2) Allow also polygonal needles.

3) Show, based on linearity of expectation, that for a polygonal needle the expected number of crossings is a linear function c\ell of the length \ell of the needle.

4) Consider now a circular needle of radius 1/2. Note that with probability one it has two crossings with the lines. Deduce that c=2/\pi.

This gives a proof for Buffon’s needle problem. But now consider any closed planar curve with constant width one. Again with probability one it will have two crossings with the parallel lines. Therefore, it has the same perimeter as the circle.

Update: The argument above Continue reading