Andy's Math/CS page

Sunday, September 09, 2007

Correlation Reversal

In an earlier post, we discussed Kleitman's Theorem, which tells us that monotone events are nonnegatively correlated. So, for example, if we generate a random graph G, including each edge with probability 1/2, and we condition on the event that G is nonplanar, that can only make it more likely that G is Hamiltonian, not less.

There's a further wrinkle we could add to make things more interesting. By a witness for the event f(x) = 1 on a particular bitstring x, we mean a subset of the bits of x that force f(x) = 1. (This event could have multiple, overlapping or disjoint, witnesses.)

Let f, g be monotone Boolean functions, and consider the event we'll call f^^g, the event (over uniformly chosen x)that f(x), g(x) are both 1 and that, moreover, we can find disjoint witnesses for these two conditions.

Problem: Is P(f^^g) greater or less than P(f = 1)*P(g = 1)?

On the one hand, f and g `help each other' to be 1, by Kleitman's Theorem. On the other hand, the disjoint-witness requirement seems to undercut their ability to positively influence each other. Which tendency wins out?

I'll tell you: P(f^^g) <= P(f = 1)*P(g = 1). The latter tendency prevails, although ironically enough, Kleitman's Theorem can actually be used to show this! It's a not-too-hard exercise in conditioning, which I recommend to the interested reader.

Here's the kicker, though: the inequality above is actually true for arbitrary f, g, not just monotone ones! This result, however, took a decade of work to prove; it was conjectured by van den Berg and Kesten, and proved by Reimer in 1994; see this article. Reimer's Inequality appears fruitful in probabilistic analysis, including in theoretical CS, see this article (which I have yet to read).



  • Hey Andy!

    It's Peggy Yang :)

    I don't understand all the math theory that's on your blog, but it seems interesting :)

    How are you doing?

    I don't know if you check your Facebook recently, I'm just wondering if you still play go once in a while anymore :) I remember you were shodan... way back when?

    Take care!

    By Anonymous Anonymous, at 2:25 AM  

  • Hi Peggy! Great to hear from you...
    I don't play Go anywhere near as often as I'd like (and would make a pretty dubious shodan at this point), but I still do the occasional tsumego puzzle and look at pro games. It's definitely still close to my heart, and has also I think largely inspired my choice of focus (complexity theory) within math/CS.

    How about you? Doing well for yourself?

    By Blogger Andy D, at 10:54 AM  

  • Your link to the second article is broken.

    By Anonymous Anonymous, at 12:35 PM  

  • Thanks. Can't fix right now, my computer is off-kilter, but link is

    ' A Dual Version of Reimer’s Inequality and a Proof of Rudich’s Conjecture'

    By Anonymous Anonymous, at 12:44 PM  

  • Hey Andy! :)

    Aww, I'm sure you're still a strong shodan. That's good that you still look at some tsumego puzzles and pro games once in a while. Maybe I should start looking at them as well, but I am usually clueless to what goes on. Yes! I remember how you mentioned to me about how you and Herb thought you were going to be a mathematician? :) It was a while ago and I probably don't have my facts down right. You seem very interested in what you're doing though. Oh, congrats on the MIT visit you're doing? It sounds like you are really doing something you have a passion for.

    I'm doing okay. I inherited Kevin's go club at UCI and I'm trying to start it up. It's a little frustrating and confusing though. I don't know if I can keep members here because I'm a very weak player still, after all these years. It's a bit embarrassing. I wish I could make it as well as James/Herb's go club when I was there. That was great.

    I thought about you because I was doing this business. If you hadn't introduced Kevin to the go club, I wouldn't have the chance to be here playing go either. Thank you very much :)

    Take care,

    By Anonymous Anonymous, at 5:17 AM  

  • eydqz5 Your blog is great. Articles is interesting!

    By Anonymous Anonymous, at 5:39 AM  

  • lG3O7O Nice Article.

    By Anonymous Anonymous, at 2:07 PM  

  • Nice Article.

    By Anonymous Anonymous, at 3:45 PM  

  • Please write anything else!

    By Anonymous Anonymous, at 3:21 PM  

Post a Comment

<< Home