4. (a) (7 marks) The mythic hero Hercules is tasked with slaying a monster, the Hydra. In a little known variant of the classic tale, it is recorded that every time Hercules chops off one of the Hydra's heads, two grow back in its place with probability 3/4, while none grows back with probability 1/4. The Hydra starts with one head. In order to slay it, Hercules must ensure that it has no heads left (or about to grow back). i. Let p denote the probability that Hercules succeeds in slaying the Hydra. Show that p solves the equation 1+ 3p? P = 4 ii. The above equation has two solutions. Find both. Which of these is the proba- bility that Hercules succeeds in slaying the Hydra? Justify your answer briefly. (b) (12 marks) Recall that a graph G = (V, E) is bipartite if there exist vertex sets X and Y such that V = XUY, X Y = 0 and E CX XY. In words, X and Y partition the vertex set, and there is no edge between two elements of X or two elements of Y. Now, consider a random bipartite graph with X = Bn, \Y= n, where each vertex in X chooses a single vertex in Y as its neighbour, independent of the choices of all other vertices in X. In other words, each vertex in X has degree 1, while the degrees of vertices in Y are random variables. Here, > 0 is a parameter of the model, and we assume that Bn is integer-valued. i. For ve Y, let Xv denote the indicator that the degree of node v is exactly two: i, deg(u) = 2, Xv = 10, otherwise. Show that E[xu] ~ men and Var(xv) ~ men, where we recall that for two sequences an and bn, we write an ~ bn if their ratio tends to 1 as n tends to infinity. ii. Let N = {vey Xy denote the total number of nodes in Y with degree exactly equal to two. For distinct nodes v, w e V, it can be shown that Cov(Xu Xw) = 0(n-4). Use this fact, together with the results from the previous part, to show that E[N] ~ B2/2 and Var(N) ~ 32/2. iii. It can be shown that, for large n, the distribution of the random variable N is very close to a Poisson distribution with mean E[N]. Use this fact to give an approximate expression for P(N = 0), the probability that there no vertices in Y with degree exactly equal to two. (c) (6 marks) The year on planet Zog has 100 days. People there are equally likely to be born on any day, and their birthdays are all mutually independent. What is the probability that, for a group of 20 randomly chosen people, there will be at least one birthday that is shared by exactly two of those people? 4. (a) (7 marks) The mythic hero Hercules is tasked with slaying a monster, the Hydra. In a little known variant of the classic tale, it is recorded that every time Hercules chops off one of the Hydra's heads, two grow back in its place with probability 3/4, while none grows back with probability 1/4. The Hydra starts with one head. In order to slay it, Hercules must ensure that it has no heads left (or about to grow back). i. Let p denote the probability that Hercules succeeds in slaying the Hydra. Show that p solves the equation 1+ 3p? P = 4 ii. The above equation has two solutions. Find both. Which of these is the proba- bility that Hercules succeeds in slaying the Hydra? Justify your answer briefly. (b) (12 marks) Recall that a graph G = (V, E) is bipartite if there exist vertex sets X and Y such that V = XUY, X Y = 0 and E CX XY. In words, X and Y partition the vertex set, and there is no edge between two elements of X or two elements of Y. Now, consider a random bipartite graph with X = Bn, \Y= n, where each vertex in X chooses a single vertex in Y as its neighbour, independent of the choices of all other vertices in X. In other words, each vertex in X has degree 1, while the degrees of vertices in Y are random variables. Here, > 0 is a parameter of the model, and we assume that Bn is integer-valued. i. For ve Y, let Xv denote the indicator that the degree of node v is exactly two: i, deg(u) = 2, Xv = 10, otherwise. Show that E[xu] ~ men and Var(xv) ~ men, where we recall that for two sequences an and bn, we write an ~ bn if their ratio tends to 1 as n tends to infinity. ii. Let N = {vey Xy denote the total number of nodes in Y with degree exactly equal to two. For distinct nodes v, w e V, it can be shown that Cov(Xu Xw) = 0(n-4). Use this fact, together with the results from the previous part, to show that E[N] ~ B2/2 and Var(N) ~ 32/2. iii. It can be shown that, for large n, the distribution of the random variable N is very close to a Poisson distribution with mean E[N]. Use this fact to give an approximate expression for P(N = 0), the probability that there no vertices in Y with degree exactly equal to two. (c) (6 marks) The year on planet Zog has 100 days. People there are equally likely to be born on any day, and their birthdays are all mutually independent. What is the probability that, for a group of 20 randomly chosen people, there will be at least one birthday that is shared by exactly two of those people