Formal Reasoning in Computer Science

This course will become read-only in the near future. Tell us at community.p2pu.org if that is a problem.

Task Navigation 

Meeting 13 - August 17

Review week! 

We decided at the last meeting to focus our review on questions from chapter 6. In particular, if you'd like to be able to compare with others, then focus on every 5th problem... so 1, 6, 11, 16... . 

Of course you can do other problems that interest you too. if you work on other problems, then please try to post the problem numbers to this page so that others can use them as suggestions for problems to work on too. Doing the same problems makes the arguments more fun :)

Meeting will be on weds in AVW grad lounge as usual. 

Task Discussion


  • Alex Quinn   Aug. 17, 2011, 2:42 p.m.

    Here is the solution to the MAX problem I wrote about last week.

    Question:

    Let A={a1, a2, ..., an}, a set of discrete, finite random variables that are mutually independent.

    What is the distribution of max(A)? In other words, for some v, what is Pr(max(A)=v), for all possible values of v? Calculate the entire distribution efficiently.

    Answer:

    Pr(max(A)=v) = Pr(all ai ≤ v) - Pr(all ai < v)
    v ∈ {all vals of ai between greatest min and greatest max}

    This seems super-simple when you write it like this, but it took me a long, long, long time to get there. I worked at this for 16 hours last week, in addition to probably 30 hours prior to that. I tried several other perfectly reasonable approaches that didn't work. When it finally reduced to this clean, compact expression, I was astonished... astonished and then furious with myself for not seeing it sooner. I have since calculated results by hand, in Excel, and in Python code. The answers all match.

  • Alex Quinn   Aug. 17, 2011, 2:19 p.m.

    Here's a general question I was grappling with last week.

    Suppose:
    • A and B are independent
    • B and C are independent
    • A and C are not necessarily independent

    Q1: Under what conditions could (A∩B) and C be independent?
    Q2: Under what conditions could (A∪B) and C be independent?

    An easy example of when it does not hold is this:

    Flip a nickel and a quarter.
    A={nickel is heads}
    B={quarter is heads}
    C={nickel and quarter are same}

    Nevertheless, I suspect there are conditions in which at least (A∩B) and C are independent. If so, then you could simplify Pr(A|B∩C) as...

    Pr(A|B∩C) = Pr(A∩B∩C)
    Pr(B∩C)
      = Pr(A∩B)Pr(C)
    Pr(B)Pr(C)
      = Pr(A∩B)
    Pr(B)
      = Pr(A|B)

    I worked on this for a long time and never came to a resolution. In the end, I gave up and assumed pretended that (A∩B) and C were independent for purposes of my larger problem (the one about MAX that I wrote up last week). The final answer came out very obviously correct so I have to assume there are some conditions, maybe relating to joint probabilities or conditional independence, in which at least (A∩B) and C are independent.