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.

35 thoughts on “Test Your Intuition (14): A Discrete Transmission Problem

  1. Greg Friedman

    Hi Gil,

    Unless I’m misunderstanding, I think you shifted notation in here somewhere: at first I think you say the entries of the vector have to be $\pm 1$, but then later you mention a vector $(0,0,\ldots, 0)$. Of course the situation is equivalent if you equate $\{-1,1\}$ with $\{0,1\}$, but it might help your readers to edit that.


    GK: Dear Greg, thanks, corrected.

  2. Gil Kalai Post author

    Dear Tom and Rodney, “Second-order” intuitions for deducing the answer to a problem, like Tom’s intuition and Rodney’s intuition are actually quite interesting. (And they are quite relevant in theoretical economics, game theory, and psychology.) Such intuitions may depend on “framing effect” e.g. the precise wording of the question. For example, would you change your intuitive answer which is based on guessing my motivation had I asked the question:

    Find a better strategy

    Of course, if we want to sharpen our mathematical intuitions in order to solve open problems it is less clear how useful such “second-order intuitions” are.

  3. D. Eppstein

    My intuition tells me that if I pick message targets uniformly at random, then w.h.p. even after I’ve picked as many as n/2 of them I won’t have seeded the message at any point much closer than n/2 steps away from (0,0,0,…). So the random strategy still takes approximately n/2 steps just to cover (0,0,0,…) let alone the whole cube. It’s difficult to distribute codewords much more evenly than that, so I suspect n/2 – o(n) is the right answer. Of course that’s far from being a rigorous solution…

  4. yanzhang

    My first intuition actually tells me that the transmission feels like I could just regard it as a chain. Thus, I’d put the thing about 2/3 down the line and get roughly n/3.

  5. Andy D

    David’s intuition looks completely correct: n/2 – o(n) rounds are necessary. (I suspect, however, that Gil wants us to think about what the right o(n) term should be…)

    To get a slightly stronger result, let’s let our cost measure C(S) of a (possibly randomized) strategy S be the expected number of rounds to hit a uniformly chosen point in the hypercube; we’ll show that C(S) > n – o(n).

    By convexity, C(S) is minimized by some deterministic S. WLOG, this S is oblivious, so let v1, v2, …, vi, … be its fixed choice-sequence, where vi is given the message at step i.

    If x is chosen uniformly from the hypercube, then for each fixed i, dist(x, vi) is distributed as a sum of i Bernoulli trials with parameter 1/2.
    So by Chernoff bounds (please check my statement), with probability greater than 1 – n^(-2), it’s within O(sqrt(log n)) standard deviations of its expectation (n/2); i.e., in this case

    |dist(x, vi) – n/2| ( n/2 – O(sqrt(n log n) ) * (1 – O(n^(-1)) ) = n/2 – O(sqrt(n log n)).

  6. Andy D

    Sorry, the last line in my first comment was mangled by html, and the end of my argument was cut off.
    Finishing up with last eqn corrected:

    …i.e., in this case

    |dist(x, vi) – n/2| is less than O(sqrt(n log n)).

    So, by a union bound, with prob. > 1 – O(n^(-1)), we have

    |dist(x, vi) – n/2| less than O(sqrt(n log n)) for i = 1, 2, …, n/2.

    Thus, C(S) is greater than

    (1 – O(n^(-1)))(n/2 – O(sqrt(n log n))) = n/2 – O(sqrt(n log n)).

  7. Paco Santos

    Going deeper into the second-order discussion, I wonder why the question was not posed in the following *almost* equivalent form: can you cover the unit n-cube with less than \lceil n/2\rceil +1 balls of (Hamming) radius less than \lceil n/2\rceil ?

    Other than that, my only bit of wisdom is that the Hadamard code shows you certainly cannot do with less than (n+1)/4+1 rounds. Remember that the Hadamard code consists of n+1 cube vertices with every pair at distance (n+1)/2 (geometrically, they are the vertices of a regular simplex inscribed in the cube). A Hadamard code is conjectured to exist whenever n+1 is a multiple of 4 and known to exist for infinitely many values of n (in particular, whenever n+1 is a power of two).

    1. Gil Kalai Post author

      There are several ways to formulate the question but I think you want to cover by Hamming Balls B_1,B_2,\dots do that the radius of Ball i is r-i and r is as small ass possible.

  8. daveagp

    My favourite Turing Machine’s intuition tells me that if there is a better strategy, then N is at least 15. I think the V.A. also gives a lower bound of N/2-O(sqrt(N)).

    GK: Am I guessing right that V. A. stands for “Volume argumets?”

  9. Joseph Malkevitch

    If one could broadcast to all the vertices of a dominating set of an n-cube at once in the next round one would have the message to all vertices. So one approach would be to broadcast to the vertices of a dominating set one after another, and one time unit after reaching all of these one would be done. My guess is that minimum dominating sets will vary in a complex way with n.

    1. Gil Kalai Post author

      Dear Joe, every vertex of the n-cube dominates n+1 vertices, so a dominating set cannot be smaller than 2^n/n+1. This is much more then needed. The point is that when you send a message to a vertex v at round i then at round i+j the message will reach all vertices of Hamming distance \le j from v. Even if you send the message to a single vertex at the first round and stop it will reach all vertices after n+1 rounds.

  10. Anonymous Rex

    Did you ever post a follow-up to “Test Your Intuition (13)”? I solved the problem game-theoretically, but I don’t know the connection to the Barca-Inter match(es).

  11. pat

    I believe there is no faster way to cover all the nodes.

    Take the case where the dimension, n, is a power of 2. Now
    consider only those vectors with exactly n/2 1’s (and therefore also
    n/2 0’s). These are the corners that are covered last by expansion of the origin. If you are to cover the cube any faster than n/2, you will have to cover these by your actions after step two. There is a subset of these that are all pairwise at least n/2 distant from each other (i’ll show the vectors for n=8 instead of defining them generally because its easier)


    notice that there are 2n-2 of them. Therefore, there are too many of them, too far from each other to cover by hand any faster than n/2. Therefore there is no better strategy than to just dit and wait.

    1. Gil Kalai Post author

      Dear Pat, impressive! GK: I realize that the argument is incomplete (see discussion below). A combinatorial proof of this kind that you cannot do better would be interesting even for special values of n

    2. daveagp

      Isn’t there something else you need to argue? Let D be this set of 2n-2 points which are mutually (n/2)-distant. You could still cover more than one point from D “quickly” by picking a point which is “between” them. For example, 11001111 is at distance 2 from two of the points in your list. Can you preclude, for example, that there is a point X which is at distance n/3 from 3 points in D?

      1. pat

        because hamming distance is a ‘taxicab’ metric, you cannot cover more than 2 of the points with any ball of diameter < n/2.

  12. pat

    just to clarify, the uncoverable corners have a nice recursive structure: the vectors for dim 2^n form the first and second halves of the vectors for dim 2^(n+1), and are matched with either another copy of themselves, or their negation. so for example, one of the corners for n=8 is:

    so for n=16 we get two vectors:
    (1100110011001100) and

    and so its easy to show there are 2n-2 of them, and that the necessary pairwise distance properties hold.

    If you include the origin (00…00) and the far corner (11..11) in this set it actually all works out a bit more simply: there are then always a set of 2n distant corners and the asymmetry of having to pick the far corner for the second move is removed.

    1. myself

      you can cover many of the points in your set by a ball of radius less than $n/2$. e.g. 11101000 is at distance 2 from three of the points in your example for $n=8$.

  13. serdar

    Well, the binary [24,12,3] Golay code is perfect, thus the radius 3 Hamming spheres around its
    2^12 codewords don’t overlap. Even in this case, you’ll take 2^12 time steps to send the message to each of the codewords and an extra 2 steps will be required for the last codeword’s 3-sphere to be filled. Thus, this code allows you to use 2+2^12 steps which is of course no joy.

  14. gowers

    My intuition also said that you couldn’t do better. Here’s why. Suppose you strengthen what you’re allowed to do as follows. At the very first go you may place t points and their antipodal points. Then you just sit back and wait. After \lceil n/2\rceil further steps, the points not reached from x and its antipode form the intersection of the cube with a hyperplane, and this intersection is pretty big. The points not reached at all form an intersection of t hyperplanes of this kind. Here’s where my intuition starts to desert me. In \mathbb{R}^n I could argue that even if t=n-1 there will be a point in the intersection (of a 1-dimensional subspace with the sphere). But if we’re restricting to the discrete cube, it’s not clear that this dimension argument remains valid. On the other hand, t is quite a bit smaller than n. But perhaps this is the whole issue. (I don’t rule out that my numbers are out by approximately 1, by the way.)

  15. Mark Bennet

    My initial intuition thought no, but now I think maybe. I’ve just been on holiday, which gets me going. And I got thinking about a tetrahedron inscribed in a cube. So with 12 co-ordinates choosing successively (0,0,0,0,0,0,0,0,0,0,0,0); (1,1,1,1,1,1,1,1,0,0,0,0); (1,1,1,1,0,0,0,0,1,1,1,1); (0,0,0,0,1,1,1,1,1,1,1,1) i.e. choosing strategic points 2/3 of the way across [rather than the whole way across] – now with this few co-ordinates you don’t beat the original, but I think you can with n=24.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s