August 4 - 10: Alice Ch. 7

Task Discussion

• 
  Alex Quinn   Aug. 10, 2011, 1:19 p.m.

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

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

  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   Aug. 10, 2011, 4:23 p.m.
  In Reply To:   Alex Quinn   Aug. 10, 2011, 1:19 p.m.

  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   Aug. 9, 2011, 9:36 a.m.

   

  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   Aug. 9, 2011, 7:27 p.m.
  In Reply To:   Jessy Kate Schingler   Aug. 9, 2011, 9:36 a.m.

  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!

  aj

• 
  Alex Quinn   Aug. 10, 2011, 8:57 a.m.
  In Reply To:   Jessy Kate Schingler   Aug. 9, 2011, 9:36 a.m.

  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   Aug. 10, 2011, 1:13 p.m.
  In Reply To:   Alex Quinn   Aug. 10, 2011, 8:57 a.m.

  I'll come back next Monday :)))

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