- Question 6 15 Points Let I Be A Sample Space And N 1921 A Natural Number Given A Positive Real Number P 1 N And W 1 (96.27 KiB) Viewed 31 times
Let I be a sample space and N < 112 a natural number. Given a positive real number p < 1, N and N we build a generator G(p, N, 12) and a decider D(N,12). The decider D(N,12) is a function that takes N sample points w1,..., WN EN, and outputs True if the sample points satisfy a condition of our choice or False otherwise. We say that the decider accepts the N sample points if, and only if, it outputs True. The generator Gp, N, 12) is a function that generates N sample points such that the decider will accept them with probability p. We devise the following algorithm A to obtain N sample points that the decider D(N, 12) accepts: Input : The generator G(p, N, 12) and the decider D(N,S2). Output: N sample points {W1,..., WN}: 1 repeat 2 Use G(p, N, 12) to generate N sample points {W1, ... , WN}. 3 until Until D(N,N2) accepts {w7,...,Wn}. 4 return Last batch of sample points {w1,...,wn} computed. Algorithm 1: Algorithm A. Let X denote the random variable that registers the number of loop iterations algorithm A executes when it is run, and assume that the generator executes exactly f(N) steps each time it is run, for a given function f: N + N. a) Describe the distribution of X and compute the expected number of steps, as a function of p and N, executed in line 2 when algorithm A is run. b) Obtain a bound for the probability that algorithm A will execute k > 0 loop iterations as a function of k and p. c) Devise a Monte Carlo algorithm (either provide a written description or pseudocode) that uses algorithm A to compute N sample points {W1, ... , Wn} that the decider accepts with probability > 2/3. Remember to justify why your algorithm satisfies the requirements.