1 Probabilities

In this excercise, you will prove some basic, but very important rules in probability theory.

1. For any two events E₁ and E₂, prove

p(E₁ E₂) = p(E₁) + p(E₂) p(E₁ E₂) (1)

what if E₁ and E₂ are two disjoint events?

2. (Bayes law) Given the Kolmogorov definition for conditional probabilities

(2)

derive Bayes law:

(3)

3. (Law of total probability) Let E₁, , E_n be mutually disjoint events in the probability space such that =. Then for any event B in the same space show that

) (4)

4. (Linearity of expectation) For any finite collection of discrete random variables X₁,,X_n with finite expectations, show that

n n

E[^XX_i] = ^XE[X_i] (5)

i=1 i=1

5. Let X, Y , Z be three disjoint subsets of random variables. We say X and Y are conditionally independent given Z if and only if

p_X,Y |_Z(x,y | z) = p_X|_Z(x | z)p_Y |_Z(y | z) (6)

Show that X and Y are conditionally independent given Z if and only if the joint distribution for the three subsets of random variables factors in the following form:

p_X,Y,Z(x,y,z) = h(x,z)g(y,z) (7)

(Be careful to prove both directions!)

2 Complexity analysis

Consider the three random variables X,Y,Z all of which are binary.

• How many states do you need in general to fully specify the joint distribution p(x,y,z)?
• How many states are needed if the distribution does factorize in p(x,y,z) = p(x | y)p(y | z)p(z)?
• How many states do you need, if the variables are not binary but can take values in {1,2,,N}; consider both previous cases.
• How many states do you need to specify a distribution over all 8bit grayscale images of size 1000 1000 pixels? There are random variables x₁,x₂,,x_1M with x_i {0,,255} for i = 1,M.
• Do you have an idea of how to represent the distribution more compactly?

Provide the number of states needed by your method.

3 Chest Clinic Network

The chest clinic network above concerns the diagnosis of lung disease (tuberculosis,lung cancer, or both, or neiter). In this model a visit to asia is assumed to increase the probability of lung cancer. We have the following binary variables.

xpositive X-ray dDyspnea (shortness of breath) eEither Tuberculosis or Lung Cancer tTuberculosis lLung cancer bBronchitis aVisited Asia sSmoker

1. Write down the factorization of the distribution implied by the graph.
2. Are the following independence statements implied by the graph? (And how do you conclude this?)
   • tuberculosissmoking|shortness of breath
   • tuberculosissmoking|bronchitis
   • lung cancerbronchitis|smoking
   • visit to Asiasmoking|lung cancer
   • visit to Asiasmoking|lung cancer,shortness of breath
3. Calculate by hand the values for p(d). The Conditional Probability Table (CPT) is:

and

= 0,

.