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

Diskutera uppgift

  • Alex Quinn   10 augusti 2011 13:19

    Here's a problem I've been working on today:

    Given a set of finite discrete random variables A1, A2, ..., An that are mutually independent, what is the distribution of the maximum?  In other words, for some v, what is Pr(max(A1, A2, ..., An)=v)?  Compute the entire distribution in low order time, preferably O(|A1|+ |A2| + |An|).

    Previously, I had the following solution:

    Pr(max=v = Pr("all inputs ≤ v" ∩ "any input = v")
      = Pr("all inputs ≤ v")•P("any input = v")

    That assumes that "all inputs ≤ v" and "any input = v" are independent.  It seemed logical since you don't need to know one to compute the other.  Based on this test I made in Excel, I believe I was wrong—or at least my computation above didn't work out.

    Irrespective of original problem, I'm trying to understand how you would reason why those two statements are not dependent, and how you would correctly compute the conjunction of the two.

  • Tom_Chan   10 augusti 2011 16:23
    Som Svar På:   Alex Quinn   10 augusti 2011 13:19

    In the second line you have to write Pr("all inputs ≤ v") • Pr("any input = v" | "all inputs ≤ v").

    It can be seen that Pr("any input = v") changes as v changes, given the event "all inputs ≤ v":

    Consider rolling two dice, with all 36 possible outcomes tabulated.

    1,1  2,1  3,1  4,1  5,1  6,1
    1,2  2,2  3,2  4,2  5,2  6,2
    1,3  2,3  3,3  4,3  5,3  6,3
    1,4  2,4  3,4  4,4  5,4  6,4
    1,5  2,5  3,5  4,5  5,5  6,5
    1,6  2,6  3,6  4,6  5,6  6,6

    when taking the max function the cells that gives the same outcome forms a mirrored "L", and the ratio of  Pr("all inputs ≤ v")  to  Pr("any input = v")  is not constant, i.e. they are not independent.

    This diagram also suggest the solution could be to write Pr(max=v) as Pr("all inputs ≤ v") - Pr("all inputs ≤ v-1"), although this takes n times as long compared to what you preferred, if implemented naively.

  • Jessy Kate Schingler   9 augusti 2011 09:36


    hey all! how is the reading for chapter 7 going?
    i've been focusing on some problems from earlier chapters.... i'm feeling like i want to review what we did more than i want to read new material, so for my part i'll be coming with a few problems to discuss on weds. 
    where's everyone else at?
  • Angjoo Kanazawa   9 augusti 2011 19:27
    Som Svar På:   Jessy Kate Schingler   9 augusti 2011 09:36

    Hi Jessy,

    That works for me, I've been traveling around and I finally settled in last weekend so I haven't started reading the materials.

    I know this is last min but if you can let us know which problem/chapter you're looking at i'll take a look at them. Any chapter in particular?

    See you tomorrow!


  • Alex Quinn   10 augusti 2011 08:57
    Som Svar På:   Jessy Kate Schingler   9 augusti 2011 09:36

    Jessy:  I'm just getting started now.  Let me know what you've been focusing on and I'll work on that today.  It sounds like Angjoo is in the same boat as me, so I think it's fine to shake things up.

    Kotaro:  Are you back in DC?

  • Kotaro Hara   10 augusti 2011 13:13
    Som Svar På:   Alex Quinn   10 augusti 2011 08:57

    I'll come back next Monday :)))

    I've got little suvenier for you and for the group :D