Problem 3 Probabilities of Non-Collisions The cryptographic relevance of this question will become clear when we cover hash functions in class. In each question below, provide a brief explanation and a formula for your answer. In addition, for parts (d) and (f), provide a numerical value that is an integer. Let k, n be positive integers with k n. Consider an experiment involving a group of k participants, where we assign each participant a number that is randomly chosen from the set {1, 2, . . . , n} (so all these assignments are independent events). Now pick your favourite number N between 1 and n.

(a) What is the probability that a given participant is assigned your favourite number N?

(b) What is the probability that a given participant is not assigned the number N?

(c) What is the probability that none of the k participants is assigned the number N?

(d) Intuitively, the more people participate, the likelier the chance that one of them is assigned the number N. In other words, higher values of k decrease the probability that no one gets assigned N. Suppose n = 10. What is the maximal number k of participants in this experiment to ensure at least a 50% chance that none of then is assigned the number N?

(e) Going back to k participants and n numbers, what is the probability that all k participants are assigned different numbers?

(f) Intuitively, the more people participate, the likelier the chance that two of them are assigned the same number (this is called a collision; hence the title of this problem). In other words, higher values of k decrease the probability that all participants are assigned different numbers. Suppose n = 10. What is the maximal number k of participants in this experiment to ensure at least a 50% chance that they are all assigned different numbers?

(g) Let P be the quantity of part (e). Prove that P exp(k ²/2n) when k is large but is very small compared to n. You may use without proof the following two approximations: exp(x) 1 x when x > 0 is very small. This comes from the Taylor series exp(x) = 1 x + x ²/ 2! x ³ /3! + x ⁴ /4! + , where the terms from x ²/2 onwards are so small that they are negligible compared to 1 x.

k(k 1) k ² (since k k 1 when k is large).

(h) ( Generalizing part (f) from n = 10 to any n, suppose we want to enlist sufficiently many participants to ensure a roughly 50% chance that they are all assigned different numbers. Use the result of part (g) to prove that the number k of required participants is approximately 1.177 n.(note:youcan solve(h) even if you didn't do part (f) and (g)

Note : Please do (f), (g), (h) only. if possible do (e) . DO NOT DO (a), (b), (c), (d).