Problem 2-1. WageRank [45 points] After another successful year of Googol, Parry Lage prepares to negotiate his salary with the board of Counting Numbers Inc. As the co- developer of the WageRank algorithm, Parry believes himself capable of modeling the behavior of the board members and predicting his salary even before the meeting. The procedure, as he understands it, is that each of the 100 board members has drawn an optimal salary uniformly at random from the range (0, 1000000) in dollars, not necessarily independently. Parry can propose any salary he desires, and each board member has one vote, which will be cast in favor of the proposal if the proposed value is no greater than this board member's optimal salary and will be cast against the proposal otherwise. If at least 51 of the 100 board members cast votes in favor of Parry's proposed salary, then this salary will be approved. Otherwise, Parry risks being fired! Parry wonders how likely it is that he can secure a proposal of at least $200000, an extremely modest salary given all of his hard work (a) [8 points] Use Markov's Inequality to provide a bound on the probability that Parry will fail in his proposal of a salary of $200000. In addition, solve for the highest salary that Parry can propose while keeping his probability of failure at most (b) 17 points] Now, one of Parry's most trusted advisors has come to Parry and shared an important piece of information. Specifically, she informs Parry that the board members have chosen the salaries pairwise independently. Use Chebyshev's Inequality to provide a tighter bound on the probability that Parry will fail in his proposal of a salary of $200000. Hint: Recall that two random variables X and Y are pairwise independent if, and only if, Pr( X = 2, Y = y) = Pr(X = x). Pr(Y = y). (c) [5 points] Now, Parry, having co-developed WageRank, insists that he can make an even stronger assumption about the board members-namely, that they all select the salaries mutually independently. With this new assumption, use the Chernoff Bound to provide a yet tighter bound on the probability that Parry will fail in his proposal of a salary of $200000. (d) (25 points) Just as Parry believes that he's begun to work out the right salary to propose, he is informed by one of his advisors that the format of the board meeting is not what he believed. The board size is not fixed at 100 but rather includes n board members, and Parry can only propose one salary to the board, so he needs to choose very wisely. Additionally, the power dynam- ics on the board have shifted, and some board members have more votes than others. Specifically, suppose the board members x1, 12...In each have W1, W2, ..., votes respectively. You may assume the total number of votes, W, is odd. Parry, understanding the intricacies of WageRank, has held a private meeting with every board member to ask the board member what a reasonable CEO salary is. He knows that board member thinks s, is the ideal salary for Parry. A board member will use all their votes to vote against Parry's pro- posed salary if it is higher than their wishes, and the board member will use all their votes in favor of the proposed salary if the proposal is less than or equal to their wishes. You may assume the s, are distinct. Devise an algorithm to determine the highest salary Parry can propose. For full credit, your algorithm should run in O(n). Partial credit will be given to an O(n log n) solution. Problem 2-1. WageRank [45 points] After another successful year of Googol, Parry Lage prepares to negotiate his salary with the board of Counting Numbers Inc. As the co- developer of the WageRank algorithm, Parry believes himself capable of modeling the behavior of the board members and predicting his salary even before the meeting. The procedure, as he understands it, is that each of the 100 board members has drawn an optimal salary uniformly at random from the range (0, 1000000) in dollars, not necessarily independently. Parry can propose any salary he desires, and each board member has one vote, which will be cast in favor of the proposal if the proposed value is no greater than this board member's optimal salary and will be cast against the proposal otherwise. If at least 51 of the 100 board members cast votes in favor of Parry's proposed salary, then this salary will be approved. Otherwise, Parry risks being fired! Parry wonders how likely it is that he can secure a proposal of at least $200000, an extremely modest salary given all of his hard work (a) [8 points] Use Markov's Inequality to provide a bound on the probability that Parry will fail in his proposal of a salary of $200000. In addition, solve for the highest salary that Parry can propose while keeping his probability of failure at most (b) 17 points] Now, one of Parry's most trusted advisors has come to Parry and shared an important piece of information. Specifically, she informs Parry that the board members have chosen the salaries pairwise independently. Use Chebyshev's Inequality to provide a tighter bound on the probability that Parry will fail in his proposal of a salary of $200000. Hint: Recall that two random variables X and Y are pairwise independent if, and only if, Pr( X = 2, Y = y) = Pr(X = x). Pr(Y = y). (c) [5 points] Now, Parry, having co-developed WageRank, insists that he can make an even stronger assumption about the board members-namely, that they all select the salaries mutually independently. With this new assumption, use the Chernoff Bound to provide a yet tighter bound on the probability that Parry will fail in his proposal of a salary of $200000. (d) (25 points) Just as Parry believes that he's begun to work out the right salary to propose, he is informed by one of his advisors that the format of the board meeting is not what he believed. The board size is not fixed at 100 but rather includes n board members, and Parry can only propose one salary to the board, so he needs to choose very wisely. Additionally, the power dynam- ics on the board have shifted, and some board members have more votes than others. Specifically, suppose the board members x1, 12...In each have W1, W2, ..., votes respectively. You may assume the total number of votes, W, is odd. Parry, understanding the intricacies of WageRank, has held a private meeting with every board member to ask the board member what a reasonable CEO salary is. He knows that board member thinks s, is the ideal salary for Parry. A board member will use all their votes to vote against Parry's pro- posed salary if it is higher than their wishes, and the board member will use all their votes in favor of the proposed salary if the proposal is less than or equal to their wishes. You may assume the s, are distinct. Devise an algorithm to determine the highest salary Parry can propose. For full credit, your algorithm should run in O(n). Partial credit will be given to an O(n log n) solution