Part 4: The Time Required for a Collision Suppose you start out with N hash values and assign them to individuals one by one at random with replacement as we have assumed throughout. Let M1 be the number of individuals who are assigned hash values until the first time the value assigned has been assigned before. For example, if the sequence of assigned values starts out as 212, 41, 7, 90, 41, then M1 = 5. Important Note: In this course "until" will mean "up to and including" as you can see in the example above. The random variable M1 is called the time of the rst match. In this part of the lab you will find its probability distribution. 4a) When you are trying to identify a distribution, always start with the possible values. In terms of N, what are the possible values of M1? M1 includes {2,3, 4,..., N+1} 4b) [On Paper] Suppose there are in individuals in all. As in Part 1a let D" be the event that all n individuals are assigned different values. In Part 1 you have the algebraic formula for P(D,,) as well as numerical values when the total number of hash values is N = 365. Fill in the blank with one of the symbols 2, >, Z, 1, the event D\" is the same as the event {M 1 n}. 4c) [On Paper] Forn Z 1 define the event G\" = {M1 > n}. Fill in the blanks. . The first blank should be filled in with set operations (such as union, intersection, difference, complement, etc) performed on some or all of the events G1 ' GZ Q v v - - o The second blank should be filled in with arithmetic operations performed on some or all of P(G1), P(G2 ), For a possible value 11 in the range identified in Part a above, the event {M 1 = n} is the same as the event , and hence P(M1 = n) = Be sure to show that your answer is correct for the values of n that are at the edges of your answer to Part a