Homework Assignment #8

To gain experience with probability theory and some recurrence relations review.

Show all work. i.e., justify your answers.

For both problems: all dice are six-sided.

Probability Theory:

Let's define a simple experiment as follows: Roll two dice. Each sample (outcome) is an ordered pair of die faces.

• How many samples are in the sample space?

Now define a random variable $X$which assigns to each sample the total number of dots on the faces of the two dice. Also, assume a uniform distribution over samples.

• What is the probability $p(X=7)$ with these fair dice?
• What is the probability of rolling the outcome “snake eyes” (two ones) with these fair dice?
• What is the expected value of our random variable $X$ with respect to this fair distribution?

Probability Theory:

Let's define another simple experiment involving rolling two dice as follows: again, each sample (outcome) is an ordered pair of die faces, and we define a random variable $X$which assigns to each sample the total number of dots on the faces of the two dice. This time assume that the dice are “loaded” (in other words, not fair) and that for each die the probability of rolling a 1 is 1/4, while the other outcomes for each die share the remaining 3/4 probability mass equally.

• What is the probability $p(X=7)$ with these loaded dice?
• What is the probability of rolling the outcome “snake eyes” (two ones) with these loaded dice?
• What is the expected value of our random variable $X$ with respect to this unfair distribution?

Recurrence Relations:

Suppose an algorithm has running time described by the following recurrence relation: $T(n) = 3 T(n/4) + n^2$. Use the theory of recurrence relations to solve this recurrence relation. Come up with the general solution and then place it in an asymptotic order of growth.