Jeremy Ting edited q3.tex  almost 10 years ago

Commit id: bfff5189e3c983ec2fde2d1fafb34547f096ed4e

deletions | additions      

       

Now, $P(e_i=1)=$ the probability that the two nodes get placed into two different sets.  We take two random nodes and enumerate all their possibilities.  Node1-A, Node2-A  Node1-A, Node2-B \textbf{Node1 - A, Node2 - A}  Node1-B, Node2-A \textbf{Node1 - A, Node2 - B}  Node1-B, Node2-B \textbf{Node1 - B, Node2 - A}  \textbf{Node1 - B, Node2 - B}  This shows us that for half the time, the edge will exist and for the other half it wont.