Department of Mathematical Sciences, Stevens Institute of Technology_ MA 540 Introduction to Probability Theory Homework 6

Department of Mathematical Sciences, Stevens Institute of Technology MA 540 Introduction to Probability Theory Homework 6 Exercise 1 (Application of concentration inequalities) Imagine we have an algorithm for solving some decision problem. Suppose that the algorithm makes a decision at random and returns the correct answer with probability 1=2 + δ, for some δ 0, so just a bit better than a random guess. To improve the performance, we run the algorithm N times and take the majority vote. Show that, for any " 2 (0; 1), the answer is correct with probability 1 - ", as long as Hint: Use the following theorem. Theorem (Hoeffding’s inequality for general bounded random variables). Let X1; : : : ; XN be independent random variables. Assume that Xi 2 [mi; Mi] for every i. Then, for any t 0, we have N Exercise 2 (Randomized Numerical Linear Algebra) Show that the random sketch produced by Algorithm 1 from [1] is an unbiased estimator for the original matrix A in the sense that elementwise the expectation of the obtained random sketch equals the original matrix A. Exercise 3 (Application of Markov chains: SIR model) Many models used in epidemiology for characterizing a disease outbreak split a population at a given time t into disjoint subsets called compartments. These models are called compartmental models. One of the simplest of such models is the SIR model: the three compartments are Susceptible, Infectious, and Recovered (the latter including deceased). The population can be seen as a dynamic system with the compartments seen as states in which any individual can be at any time. Thus the SIR model can be written as a Markov chain with graph as depicted in Fig. 1, where the (typically time-dependent) transition probabilities are estimated by proportions based on random sampling.