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.

About these ads
This entry was posted in Combinatorics, Test your intuition and tagged . Bookmark the permalink.

35 Responses to Test Your Intuition (14): A Discrete Transmission Problem

  1. Greg Friedman says:

    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.

    Best,
    greg

    GK: Dear Greg, thanks, corrected.

  2. Tom Ellis says:

    My intuition tells me you wouldn’t ask the question if there was known to be a better strategy.

  3. Rodney Topor says:

    My intuition tells me you wouldn’t ask the question unless there were known to be a better strategy.

  4. Gil Kalai says:

    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.

  5. D. Eppstein says:

    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…

  6. yanzhang says:

    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.

  7. Andy D says:

    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)).

  8. Andy D says:

    Fixing typo: dist(x, vi) is distributed as a sum of n Bernoulli trials (not i trials) with parameter 1/2.

  9. Andy D says:

    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)).

  10. Paco Santos says:

    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).

  11. daveagp says:

    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?”

  12. 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.

    • Gil Kalai says:

      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.

  13. Anonymous Rex says:

    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).

  14. pat says:

    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)

    (11110000)
    (00001111)
    (11001100)
    (00110011)
    (11000011)
    (00111100)
    (10101010)
    (01010101)
    (10100101)
    (01011010)
    (10010110)
    (01101001)
    (10011001)
    (01100110)

    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.

    • Gil Kalai says:

      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

    • daveagp says:

      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?

  15. pat says:

    *sit* and wait

  16. pat says:

    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:
    (11001100)

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

    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.

    • myself says:

      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$.

  17. pat says:

    yes you are correct (and i was wrong in my comment to daveagp above)

  18. serdar says:

    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.

  19. gowers says:

    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.)

  20. Mark Bennet says:

    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