Probability III:The probabilistic method & infinite probability spacesRecapRandom VariablesIt’s a floor wax and a dessert toppingDefinition: expectationThinking about expectationLinearity of ExpectationNew topic: The probabilistic methodDefinition: A cut in a graph.Another example of prob. methodFirst, a few more facts…Def: Conditional ExpectationDef: Conditional ExpectationRecap of cut argumentConditional expectation methodPictorial view (important!)Pictorial view (important!)Pictorial view (important!)Pictorial view (important!)Conditional expectation methodAn easy questionA related questionA related questionPictorial viewUse to reason about expectations tooUse to reason about expectations tooUse to reason about expectations tooInfinite Probability spacesGeneral pictureSetting that doesn’t fit our modelRandom walk on a lineRandom walk on a lineRandom walk on a lineRandom walk on a lineExpectations in infinite spacesA slightly different questionBernoulli’s St. Petersburg Paradox (1713)Similar questionUtility Theory (Bernoulli/Cramer, 1728-1738)Utility TheoryUtility TheoryGreat Theoretical Ideas In Computer ScienceAnupam Gupta CS 15-251 Spring 2005Lecture 23 April 5, 2005 Carnegie Mellon UniversityProbability III:The probabilistic method & infinite probability spacesRecapRandom VariablesRandom Variables•An event is a subset of S. •A Random Variable (RV)is a (real-valued) function on S.P( )1,1 1/ 361, 2 1 / 361, 3 1/ 361, 4 1 / 361, 5 1/ 361, 6 1 / 362,1 1/366,5 1/ 366,6 1/ 36xxMM...Example:•Event A: the first die came up 1.•Random Variable X: the valueof the first die.E.g., X(<3,5>)=3, X(<1,6>)=1.It’s a floor wax It’s a floor wax andanda dessert toppinga dessert toppingIt’s a variable with a probability distribution on its values.It’s a function on the sample space S.You should be comfortable with both views.HMUDefinition: expectationThe expectation, or expected value of a random variable X is1HT0TT1TH2HHE.g, 2 coin flips,X = # heads.What is E[X]?Thinking about expectationThinking about expectationD S¼ ---TT¼ ---TH¼ ---HT¼ ---HHDistribDistribon Xon X0 0 ------¼¼1 1 ------½½2 2 ------¼ ¼ XE[X] = ¼*0 + ¼*1 + ¼*1 + ¼*2 = 1.E[X] = ¼*0 + ½*1 + ¼*2 = 1.Linearity of ExpectationLinearity of ExpectationIf Z = X+Y, thenE[Z] = E[X] + E[Y]Even if X and Y are not independent.HMUNew topic: The probabilistic New topic: The probabilistic methodmethodUse a probabilistic argument to prove a non-probabilistic mathematical theorem.Definition: A cut in a graph.A cutis a partition of the nodes of a graph into two sets: U and V. We say that an edge crosses the cut if it goes from a node is U to a node in V. CutCutUUVVTheorem:Theorem:In any graph, there exists a cut such that at least half the edges cross the cut.Theorem:Theorem:In any graph, there exists a cut such that at least half the edges cross the cut.How are we going to prove this?Will show that if we pick a cut at randomat random, the expectedexpected number of edges crossing is ½(# edges).How does this prove the theorem?What might be is surely possible!Goal: show exists object of value at least v.Proof strategy:• Define distribution D over objects.• Define RV: X(object) = value of object.•Show E[X] ¸ v. Conclude it must be possible to have X ¸ v.Theorem:Theorem:In any graph, there exists a cut such that at least half the edges cross the cut.Proof:Proof:Pick a cut uniformly at Pick a cut uniformly at random. I.e., for each node flip random. I.e., for each node flip a fair coin to determine if it is a fair coin to determine if it is in U or V.in U or V.Let Let XXeebe the indicator RV for be the indicator RV for the event that edge the event that edge eecrosses crosses the cut.the cut.What is E[What is E[XXee]?]?Ans: ½.Theorem:Theorem:In any graph, there exists a cut such that at least half the edges cross the cut.Proof:Proof:••Pick random cut.Pick random cut.••Let Let XXee=1=1if if eecrosses, else crosses, else XXee=0=0..••Let Let XX= total #edges crossing.= total #edges crossing.••So,So,X = X = ∑∑eeXXee..••Also, E[Also, E[XXee] = ½.] = ½.••By linearity of expectation,By linearity of expectation,E[X] = ½(total #edges).E[X] = ½(total #edges).Pick a cut uniformly at random. Pick a cut uniformly at random. I.e., for each node flip a fair I.e., for each node flip a fair coin to see if it should be in U.coin to see if it should be in U.E[#of edges crossing cut]= = # of edges/2# of edges/2The sample space of all possible cuts The sample space of all possible cuts must contain at least one cut that at must contain at least one cut that at least half the edges cross: least half the edges cross: if not, if not, the average number of edges would the average number of edges would be less than half!be less than half!Another example of prob. methodWhat you did on hwk #8.•If you color nodes at random, Pr(every v has a neighbor of a different color) > 0.•So, must exist coloring where every v has a neighbor of a different color.•This then implied existence of even-length cycle.In this case you can, through a neat strategy called the conditional expectation methodBack to cuts: Can you use this argument to also find such a cut?Idea: make decisions in greedy manner to maximize expectation-to-go.HMUFirst, a few more facts…For any partition of the sample space S into disjoint events A1, A2, ..., An, and any event B,Pr(B) = ∑iPr(B \ Ai) = ∑iPr(B|Ai)Pr(Ai). BA1A2A3 . ... AnDef: Conditional ExpectationDef: Conditional ExpectationFor a random variable X and event A, the conditional expectationof X given A is defined as:E.g., roll two dice. X = sum of dice, E[X] = 7.Let A be the event that the first die is 5.E[X|A] = 8.5Def: Conditional ExpectationDef: Conditional ExpectationFor a random variable X and event A, the conditional expectationof X given A is defined as:Useful formula: for any partition of S into A1,A2,...we have: E[X] = ∑iE[X|Ai]Pr(Ai).Proof: just plug in Pr(X=k) = ∑iPr(X=k|Ai)Pr(Ai).Recap of cut argumentRecap of cut argumentPick random cut.Pick random cut.••Let Let XXee=1=1if if eecrosses, else crosses, else XXee=0=0..••Let Let XX= total #edges crossing.= total #edges crossing.••So,So,X = X = ∑∑eeXXee..••Also, E[Also, E[XXee] = ½.] = ½.••By linearity of expectation,By linearity of expectation,E[X] = ½(total #edges).E[X] = ½(total #edges).Conditional expectation
View Full Document
Unlocking...