Homework Assignment #9

To gain more experience with probability theory, to gain experience with convolution, and to practice working with recurrence relations.

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

Probability Theory:

Let's define a simple experiment as follows: permute the numbers $(1,2,3,4)$. Each sample (outcome) is such a permutation. Now define a random variable $X$which assigns to each sample the number of elements that are not in their correct (sorted) position. For example, for the following samples, $X$ assigns the indicated values:

• $X(\{(1, 2, 3, 4)\}) = 0$
• $X(\{(1, 3, 2, 4)\}) = 2$
• $X(\{(4, 3, 2, 1)\}) = 4$
• $X(\{(4, 1, 2, 3)\}) = 4$

Also, assume a uniform distribution over samples. (Each question scored individually.)

1. How many samples are in the sample space?
2. What is the probability $p(X=2)$?
3. What is the probability $p(X\geq 2)$?
4. What is the expected value of our random variable $X$ with respect to this uniform distribution?

Convolution:

Convolve these two sequences (signals) A and B to produce a new third sequence (signal) C:

• A: (0, 1, 2, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0)
• B: (0, 1, 1, 0)

Recurrence Relations:

Suppose an algorithm has running time described by the following recurrence relation: $T(n) = 4 T(n/3) + n^3$. Use the theory of recurrence relations to solve this recurrence relation.

• Come up with the general solution.
• Assume that the smallest instance of the problem solved by this algorithm has size $n=3$ and that the running time on that instance is 1 (i.e., $T(3)=1$). Find the specific solution to the recurrence given this initial condition.