Probability Questions

Let 0 <𝛼 <.5 be some constant (independent of the input array length 𝑛). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is ≥𝛼 times the size of the original array?

• 1 −2 ∗𝛼
• 𝛼
• 1 −𝛼
• 2 −2 ∗𝛼

ANSWER: If the picked pivot is one of the smallest 𝑛⁢𝛼 elements in the array, then the left partition’s size will be less than 𝑛⁢𝛼. Similarly, if the picked pivot is one of the largest 𝑛⁢𝛼 elements in the array, the right partition’s size will be less than 𝑛⁢𝛼. Hence, there are 𝑛 −2 ∗𝑛⁢𝛼 elements that we can pick such that both partitions have size greater than or equal to 𝑛⁢𝛼. Since the algorithm picks a pivot randomly, all elements have an equal probability of getting picked as the pivot, i.e. 1𝑛. Therefore, 𝑃⁢𝑟 =1𝑛⁢(𝑛 −2⁢𝑛⁢𝛼) =1 −2⁢𝛼. Option 1 is correct.

Now assume that you achieve the approximately balanced splits above in every recursive call — that is, assume that whenever a recursive call is given an array of length 𝑘, then each of its two recursive calls is passed a subarray with length between 𝑘⁢𝛼 and 𝑘⁢(1 −𝛼) (where 𝛼 is a fixed constant strictly between 0 and .5). How many recursive calls can occur before you hit the base case? Equivalently, which levels of the recursion tree can contain leaves? Express your answer as a range of possible numbers 𝑑, from the minimum to the maximum number of recursive calls that might be needed.

• −log⁡𝑛log⁡𝛼 ≤𝑑 ≤−log⁡𝑛log⁡(1−𝛼)
• 0 ≤𝑑 ≤−log⁡𝑛log⁡𝛼
• −log⁡𝑛log⁡(1−𝛼) ≤𝑑 ≤−log⁡𝑛log⁡𝛼
• −log⁡𝑛log⁡(1−2⁢𝛼) ≤𝑑 ≤−log⁡𝑛log⁡(1−𝛼)

ANSWER: If 𝛼 <12, then 1 −𝛼 >𝛼, thus the branch with subarray length 𝑛⁢(1 −𝛼) will have greater recursion depth.

If 𝑑 is the height of the recursion tree, 𝑛⁢(1−𝛼)𝑑 =1
Taking 𝑙⁢𝑜⁢𝑔1−𝛼 on both sides 𝑙⁢𝑜⁢𝑔1−𝛼⁡𝑛 =−𝑑
By log rule 𝑑 =−log⁡𝑛log⁡(1−𝛼)

The best case is −log⁡𝑛log⁡𝛼. Since both 𝛼 and (1 −𝛼) are less than 1, so, their logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth. Therefore, option 1 is correct.

Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case — equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the minimum-possible and maximum-possible recursion depth of QuickSort, respectively?

• 𝑀⁢𝑖⁢𝑛⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(log⁡𝑛);𝑀⁢𝑎⁢𝑥⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(𝑛)
• 𝑀⁢𝑖⁢𝑛⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(log⁡𝑛);𝑀⁢𝑎⁢𝑥⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(𝑛⁢log⁡𝑛)
• 𝑀⁢𝑖⁢𝑛⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(1);𝑀⁢𝑎⁢𝑥⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(𝑛)
• 𝑀⁢𝑖⁢𝑛⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(√𝑛);𝑀⁢𝑎⁢𝑥⁢𝑖⁢𝑚⁢𝑢⁢𝑚 :Θ⁡(𝑛)

ANSWER: Option 1 is correct.

Consider a group of k people. Assume that each person’s birthday is drawn uniformly at random from the 365 possibilities. (And ignore leap years.) What is the smallest value of k such that the expected number of pairs of distinct people with the same birthday is at least one?

[Hint: define an indicator random variable for each ordered pair of people. Use linearity of expectation.]

• 27
• 28
• 366
• 20
• 23

ANSWER: For each pair of 𝑘 people in the room, let 𝑋 be an indicator random variable such that: 𝑋 ={1if the pair has the same birthday0otherwise⁢𝐸⁡[𝑋]=𝑘−1∑𝑖=1𝑘∑𝑗=𝑖+1𝑋𝑖⁢𝑗⁢𝑃⁢𝑟⁡[i and j have the same birthday]𝑃⁢𝑟⁡[i and j have unique birthdays] =365/365 ∗364/365 (𝑖 may have been born on any of the 365 days, and 𝑗 on any of the remaining 364 days). ∴𝑃⁢𝑟⁡[i and j have the same birthday] =1 −364365 =1365 𝐸⁡[𝑋]=1365∗𝑘−1∑𝑖=1𝑘∑𝑗=𝑖+1𝑋𝑖⁢𝑗=1365∗𝑘−1∑𝑖=1(𝑘−𝑖−1+1)=1365∗𝑘−1∑𝑖=1(𝑘−𝑖)=1365∗(𝑘−1∑𝑖=1𝑘−𝑘−1∑𝑖=1⁡𝑖)=1365∗(𝑘⁢(𝑘−1)−(1+2+...+𝑘−1))=1365∗(𝑘⁢(𝑘−1)−𝑘⁢(𝑘−1)2)=𝑘⁢(𝑘−1)(365∗2)

If 𝐸⁡[𝑋] =1,𝑘 ∗(𝑘 −1) =365 ∗2
Rewriting as a general quadratic equation 𝑎⁢𝑥2 +𝑏⁢𝑥 +𝑐 =0, for which 𝑥 is given by −𝑏±√𝑏2−4⁢𝑎⁢𝑐2⁢𝑎
𝑘2 −𝑘 −730 =0,𝑎 =1,𝑏 =−1,𝑐 =−730 𝑘=1±√1+29202=1±54.052=1±27.02

Since the number of people cannot be negative, 𝑘 ≈28. Option 2 is correct.

Let 𝑋⁢1,𝑋⁢2,𝑋⁢3 denote the outcomes of three rolls of a six-sided die. (i.e., each 𝑋⁢𝑖 is uniformly distributed among 1,2,3,4,5,6, and by assumption they are independent.) Let 𝑌 denote the product of 𝑋⁢1 and 𝑋⁢2 and 𝑍 the product of 𝑋⁢1 and 𝑋⁢3. Which of the following statements is correct?

• Y and Z are independent, but 𝐸⁡[𝑌⁢𝑍] ≠𝐸⁡[𝑌] ∗𝐸⁡[𝑍]
• Y and Z are not independent, but 𝐸⁡[𝑌⁢𝑍] =𝐸⁡[𝑌] ∗𝐸⁡[𝑍]
• Y and Z are not independent, but 𝐸⁡[𝑌⁢𝑍] ≠𝐸⁡[𝑌] ∗𝐸⁡[𝑍]
• Y and Z are independent, but 𝐸⁡[𝑌⁢𝑍] ≠𝐸⁡[𝑌] ∗𝐸⁡[𝑍]

ANSWER: For 𝑌 and 𝑍 to be independent, by definition, the two events [𝑌 =𝑥⁢1] and [𝑍 =𝑥⁢2] must be independent ∀ x1, x2. If we choose 𝑥⁢1 =𝑥⁢2 =1, then 𝑃⁢𝑟⁡[𝑌 =1 AND 𝑍 =1] is the probability that the outcome of all three rolls was one. Since each roll is independent, this is equal to 163. 𝑃⁢𝑟⁡[𝑌 =1]⁢𝑃⁢𝑟⁡[𝑍 =1] =136 ∗136 =164

Clearly, 𝑃⁢𝑟⁡[𝑌 =1 AND 𝑍 =1] ≠𝑃⁢𝑟⁡[𝑌 =1] ∗𝑃⁢𝑟⁡[𝑍 =1], therefore, 𝑌 and 𝑍 are not independent.

Covariance reference: Expectations on the product of two dependent random variables

Clearly, 𝐸⁡[𝑍] is the same.

𝐶⁢𝑜⁢𝑣⁡(𝑌,𝑍) =∑6𝑖=1(𝑦𝑖 −𝐸⁡(𝑌))⁢(𝑧𝑖 −𝐸⁡(𝑍))
𝑦⁢𝑖 ∈{1 ∗1,1 ∗2,...,6 ∗1,...,6 ∗6} and clearly ≠𝐸⁡(𝑌). Similarly, 𝑧𝑖 ≠𝐸⁡(𝑍). Therefore, 𝐶⁢𝑜⁢𝑣⁡(𝑌,𝑍) ≠0, and from expression ( ∗),𝐸⁡[𝑌⁢𝑍] ≠𝐸⁡[𝑌]⁢𝐸⁡[𝑍]. Option 3 is correct.