Convert the following problem to a linear program in standard form. [20pts] max x∈R4 2×1 − x3 + x4 s.t. x1 + x2 ≥ 5 x1 − x3 ≤ 2 4×2 + 3×3 − x4 ≤ 10 x1 ≥ 0 (1)Use the two-phase simplex procedure to solve the following problem. [40pts] min x∈R4 − 3×1 + x2 + 3×3 − x4 s.t. x1 + 2×2 − x3 + x4 = 0 2×1 − 2×2 + 3×3 + 3×4 = 9 x1 − x2 + 2×3 − x4 = 6 x1, x2, x3, x4 ≥ 0 (2)3.1 Q1 Prove that the extreme points of the following two sets are in one-to-one correspondence. [20pts] S1 = {x ∈ R n : Ax ≤ b, x ≥ 0} S2 = {(x, y) ∈ R n × R m : Ax + y = b, x ≥ 0, y ≥ 0} (3) , where A ∈ R m×n, b ∈ R m. 1 3.2 Q2 Does the set P = {x ∈ R 2 : 0 ≤ x1 ≤ 1} have extreme points? What is its standard form? Does it have extreme points in its standard form? If so, give a extreme point and explain why it is a extreme point. [20pts]
Problem 1. f is a positive definite quadratic function f(x) = 1 2 x TAx + b Tx, A ∈ S n ++, b ∈ R n , x k is the current iteration point, d k is the descent direction. Derive the step size of exact linear search [20pts] α k = arg min α>0 f(x k + αdk ).Problem 2. Prove that f : R n → R is affine if and only if f is both convex and concave. [20pts]Problem 3. Solve the optimal solution of the Rosenbrock function f(x, y) = (1 − x) 2 + 100(y − x 2 ) 2 , using MATLAB programming to implement three algorithms (each 20pts): gradient descent (GD) method, Newton’s method, and Quasi-Newton methods (either rank-1, DFP or BFGS).You are required to print iteration information of last 10 steps: including objective, step size, residual of gradient. Technical implementation: explain how to choose the step size, how to set the termination criteria, how to choose the initial point, the value of the required parameters, converge or not and convergence rate. (paste the code in the pdf to submit it, no need to submit the source code) [60pts]
Problem 1. Prove the dual of the dual of a linear programming (standard form) is itself.[25pts]Problem 2. Prove the dual objective increases after a pivot of the dual simplex method.[25pts]Problem 3. Let L(x,λ) be the Lagrangian of a linear programming problem, and (x ∗ ,λ ∗ ) be the optimal primaldual solution. Prove that L(x,λ ∗ ) ≥ L(x ∗ ,λ ∗ ) ≥ L(x ∗ ,λ), for any primal feasible x and dual feasible λ.[25pts]Problem 4. Construct a linear programming problem for which both the primal and the dual problem has no feasible solution.[25pts]
Problem i. Write the gradient and Heissan matrix of the following formula. [10pts] x TAx + b Tx + c (A ∈ Rn∗n , b ∈ Rn , c ∈ R)Problem ii. Write the gradient and Heissan matrix of the following formula. [10pts] ∥Ax − b∥ 2 2 (A ∈ Rm∗n , b ∈ Rm)Problem iii. Convert the following problem to linear programming. [10pts] min x∈Rn ∥Ax − b∥1 + ∥x∥∞ (A ∈ Rm∗n , b ∈ Rm)Problem vi. Proof the convergence rates of the following point sequences. [30pts] x k = 1 k x k = 1 k! x k = 1 2 2 k (Hint: Given two iterates x k+1 and x k , and its limit point x ∗ , there exists real number q > 0, satisfies lim k→∞x k+1 − x ∗∥xk − x∗∥ = q if 0 < q < 1, then the point sequence Q-linear convergence; if q = 1, then the point sequence Q-sublinear convergence; if q = 0, then the point sequence Q-superlinear convergence)Problem v. Select the Haverly Pool Problem or the Horse Racing Problem in the courseware, compile the program using AMPL model language and submit it to https://neos-server. org/neos/solvers/index.html.(Hint: both AMPL solver and NEOS solver can be used, please indicate the type of solver used in the submitted job, show the solution results (eg: screenshots attached to the PDF file), and submit the source code together with the submitted job, please package as .zip file, including your PDF and source code.) [40pts]
1. A DNA sequence can be represented as a sequence of letters, where the “alphabet” has 4 letters: A,C,T,G. Suppose such a sequence is generated randomly, where the letters are independent and the probabilities of A,C,T,G are p1, p2, p3, p4, respectively.(a) In a DNA sequence of length 115, what is the expected number of occurrences of the expression “CATCAT” (in terms of the pj )? (Note that, for example, the expression “CATCATCAT” counts as 2 occurrences.)(b) For this part, assume that the pj are unknown. Suppose we treat p2 as a Unif(0, 1) r.v. before observing any data, and that then the first 3 letters observed are “CAT”. Given this information, what is the probability that the next letter is C?2. Let X1, . . . , Xn be i.i.d. r.v.s with mean µ and variance σ2, and n ≥ 2. A bootstrap sample of X1, . . . , Xn is a sample of n r.v.s X∗ 1 , . . . , X∗ n formed from the Xj , ∀j ∈ {1, . . . , n} by sampling with replacement with equal probabilities. Let X¯ ∗ denote the sample mean of the bootstrap sample: X¯ ∗ = 1 n (X∗ 1 + · · · + X∗ n). (a) Calculate E(X∗ j ) and Var(X∗ j ) for each j ∈ {1, . . . , n}.(b) Calculate E(X¯ ∗|X1, . . . , Xn) and Var(X¯ ∗|X1, . . . , Xn). Hint: Conditional on X1, . . . , Xn, the X∗ j , ∀j ∈ {1, . . . , n} are independent, with a PMF that puts probability 1/n at each of the points X1, . . . , Xn. As a check, your answers should be random variables that are functions of X1, . . . , Xn.(c) Calculate E(X¯ ∗) and Var(X¯ ∗). (d) Explain intuitively why Var(X¯) < Var(X¯ ∗).3. A coin with probability p of Heads is flipped repeatedly. For (a) and (b), suppose that p is a known constant, with 0 < p < 1. (a) What is the expected number of flips until the pattern HT is observed? What about the pattern HH? Solve the problems using conditional expectation.(b) Now suppose that p is unknown, and that we use a Beta(a, b) prior to reflect our uncertainty about p (where a and b are known constants and are greater than 2). In terms of a and b, find the corresponding answers to (a) and (b) in this setting.4. A fair 6-sided die is rolled repeatedly. (a) Find the expected number of rolls needed to get a 1 followed right away by a 2. (b) Find the expected number of rolls needed to get two consecutive 1’s.(c) Let an be the expected number of rolls needed to get the same value n times in a row (i.e., to obtain a streak of n consecutive j’s for some not-specified-in-advance value of j). Find a recursive formula for an+1 in terms of an. (d) Find a simple, explicit formula for an for all n ≥ 1. What is a7 (numerically)?5. Let X be the height of a randomly chosen adult man, and Y be his father’s height, where X and Y have been standardized to have mean 0 and standard deviation 1. Suppose that (X, Y ) is Bivariate Normal, with X, Y ∼ N (0, 1) and Corr(X, Y ) = ρ.(a) Let y = ax + b be the equation of the best line for predicting Y from X (in the sense of minimizing the mean squared error), e.g., if we were to observe X = 1.3 then we would predict that Y is 1.3a + b. Now suppose that we want to use Y to predict X, rather than using X to predict Y . Give and explain an intuitive guess for what the slope is of the best line for predicting X from Y .(b) Find a constant c (in terms of ρ) and an r.v. V such that Y = cX + V , with V independent of X. (c) Find a constant d (in terms of ρ) and an r.v. W such that X = dY + W, with W independent of Y . (d) Find E(Y |X) and E(X|Y ). (e) Reconcile (a) and (d), giving a clear and correct intuitive explanation.
1. Let X1, X2, . . . be i.i.d. Expo(1). (a) Let N = min{n : Xn ≥ 1} be the index of the first Xj to exceed 1. Find the distribution of N − 1 (give the name and parameters), and hence find E(N).(b) Let M = min{n : X1 + X2 + · · · + Xn ≥ 10} be the number of Xj ’s we observe until their sum exceeds 10 for the first time. Find the distribution of M − 1 (give the name and parameters), and hence find E(M).(c) Let X¯n = (X1 + · · · + Xn)/n. Find the exact distribution of X¯n (give the name and parameters), as well as the approximate distribution of X¯n for n large (give the name and parameters).2. Let the random variables X1, X2, . . . , Xn be independent with E(Xi) = µ, a ≤ Xi ≤ b for each i = 1, . . . , n, where a, b are constants. Then for any ! ≥ 0, show the Hoeffding Bound holds: P !” ” ” 1 n #n i=1 Xi − µ ” ” ” ≥ ! $ ≤ 2 exp % − 2n!2 (b − a)2 & . Hint: Hoeffding Lemma + Chernoff Inequality.3. Given a random variable X with expectation µ and variance σ2. For any a ≥ 0, show the following inequality holds: P (X − µ ≥ a) ≤ σ2 σ2 + a2 .4. We observe a collection X = (X1, . . . , Xn) of random variables, with an unknown common mean whose value we wish to infer. We assume that given the value of the common mean, the Xi are normal and independent, with known variances σ2 1, . . . , σ2 n.We model the common mean as a random variable Θ, with a given normal prior (known mean x0 and known variance σ2 0). Find the posterior PDF of Θ.5. (a) We wish to estimate the parameter for an exponential distribution, denoted by θ, based on the observations of n independent random variables X1, . . . , Xn, where Xi ∼ Expo(θ). Find the MLE of θ.(b) We wish to estimate the mean µ and variance ν of a normal distribution using n independent observations X1, . . . , Xn, where Xi ∼ N (µ, ν). Find the MLE of the parameter vector θ = (µ, ν).
1. Let X and Y be i.i.d. N (0, 1), and let S be a random sign (1 or −1, with equal probabilities) independent of (X, Y ). (a) Determine whether or not (X, Y, X + Y ) is MVN. (b) Determine whether or not (X, Y, SX + SY ) is MVN. (c) Determine whether or not (SX, SY ) is MVN.2. Let X and Y be i.i.d. N (0, 1) r.v.s, T = X +Y , and W = X −Y . Show that T and W are independent using two methods: 1) properties of MVN and 2) change of variables.3. Let (X, Y ) denote a random point in the plane, and assume that the rectangular coordinates X and Y are i.i.d. N (0, 1) r.v.s. Find the joint distribution of R and Θ (shown in the following figure). Are R and Θ independent?4. (a) Let X and Y be i.i.d. Expo(λ), and transform them to T = X + Y , W = X/Y . Find the marginal PDFs of T and W, and the joint PDF of T and W. (b) Let X, Y, Z be i.i.d. Unif(0, 1), and W = X + Y + Z. Find the PDF of W using convolution. (c) Let X and Y be i.i.d. Expo(λ) r.v.s and M = max(X, Y ). Show that M has the same distribution as X + 1 2Y using two methods: 1) properties of the Exponential and 2) convolution.5. Programming Assignment:(a) Use the Box-Muller Method to obtain the samples from the standard normal distribution N (0, 1). You need to plot the pictures of both histogram and the theoretical PDF.(b) Based on (a), generate samples from the standard bivariate Normal distribution, where the correlation is ρ ∈ (−1, 1), and the marginal PDFs are both N (0, 1).(c) According to the following picture format, plot the joint PDFs and the corresponding contours of standard bivariate Normal distribution with correlation ρ = 0, 0.3, 0.5, 0.7, 0.9. ⇢ = 0.8 ⇢ = 0.4 ⇢ = 0 ⇢ = 0.4 ⇢ = 0.8 fX,Y (x, y) x y (a) (b) (c) (d) (e) fX,Y (x, y) fX,Y (x, y) fX,Y (x, y) fX,Y (x, y) x x x x y y y y
1. Laplace’s law of succession says that if X1, X2, . . . , Xn+1 are conditionally independent Bern(p) r.v.s given p, but p is given a Unif(0, 1) prior to reflect ignorance about its value, then P (Xn+1 = 1 | X1 + · · · + Xn = k) = k + 1 n + 2As an example, Laplace discussed the problem of predicting whether the sun will rise tomorrow, given that the sun did rise every time for all n days of recorded history; the above formula then gives (n+1)/(n+2) as the probability of the sun rising tomorrow.(a) Find the posterior distribution of p given X1 = x1, X2 = x2, . . . , Xn = xn, and show that it only depends on the sum of the xj (so we only need the one-dimensional quantity x1 +x2 +· · ·+xn to obtain the posterior distribution, rather than needing all n data points).(b) Prove Laplace’s law of succession, using a form of LOTP to find P (Xn+1 = 1 | X1 + · · · + Xn = k) by conditioning on p.(c) Reinterpret the Laplace’s law of succession from the perspective of Beta-Binomial Conjugacy.2. (a) Let p ∼ Beta(a, b), where a and b are positive real numbers. Find E(p2(1 − p)2), fully simplified (Γ should not appear in your final answer).Two teams, A and B, have an upcoming match. They will play five games and the winner will be declared to be the team that wins the majority of games. Given p, the outcomes of games are independent, with probability p of team A winning and (1 − p) of team B winning. But you don’t know p, so you decide to model it as an r.v., with p ∼ Unif(0, 1) a priori (before you have observed any data).To learn more about p, you look through the historical records of previous games between these two teams, and find that the previous outcomes were, in chronological order, AAABBAABAB. (Assume that the true value of p has not been changing over time and will be the same for the match, though your beliefs about p may change over time.)(b) Does your posterior distribution for p, given the historical record of games between A and B, depend on the specific order of outcomes or only on the fact that A won exactly 6 of the 10 games on record? Explain.(c) Find the posterior distribution for p, given the historical data. The posterior distribution for p from (c) becomes your new prior distribution, and the match is about to begin!(d) Conditional on p, is the indicator of A winning the first game of the match positively correlated with, uncorrelated with, or negatively correlated with the indicator of A winning the second game of the match? What about if we only condition on the historical data?(e) Given the historical data, what is the expected value for the probability that the match is not yet decided when going into the fifth game (viewing this probability as an r.v. rather than a number, to reflect our uncertainty about it)?3. Let U1, . . . , Un be i.i.d. Unif(0, 1). Let U(j) be the corresponding jth order statistic, where 1 ≤ j ≤ n. (a) Find the joint PDF of U(1), . . . , U(n). (b) Find the joint PDF of U(j) and U(k), where 1 ≤ j < k ≤ n. (c) Let X ∼ Bin(n, p) and B ∼ Beta(j, n − j + 1), where n is a positive integer and j is a positive integer with j ≤ n. Show using a story about order statistics that P(X ≥ j) = P(B ≤ p).This shows that the CDF of the continuous r.v. B is closely related to the CDF of the discrete r.v. X, and is another connection between the Beta and Binomial.(d) Show that ! x 0 n! (j − 1)!(n − j)! t j−1 (1 − t) n−j dt = “n k=j #n k $ xk(1 − x) n−k, without using calculus, for all x ∈ [0, 1] and j, n positive integers with j ≤ n.4. If X ∼ Pois(λ), Z ∼ Gamma(k + 1, 1), where k is a nonnegative integer. Show the Poisson-Gamma Duality holds: P(X ≤ k) = P(Z > λ). Hint: Two possible methods, where one is based on the identity in 3(d), the other is based on the model of Poisson process.5. Programming Assignment: (a) Use the Acceptance-Rejection Method to obtain the samples from distribution Beta(2, 4). You need to plot the pictures of both histogram and the theoretical PDF.(b) Use the Acceptance-Rejection Method to obtain the samples from the standard Normal distribution N (0, 1). You are required to show the correctness of your algorithm in theory.(c) Both the Acceptance-Rejection Method and Box-Mulller Method can obtain the samples from the standard Normal distribution N (0, 1). Discuss the pros and cons of such two methods.(d) Use the importance sampling method to evaluate the probability of rare event c = P(Y > 8), where Y ∼ N(0, 1).
1. Show the proof of general LOTP (four cases). 2. The bus company from Blissville decides to start service in Blotchville, sensing a promising business opportunity. Meanwhile, Fred has moved back to Blotchville. Now when Fred arrives at the bus stop, either of two independent bus lines may come by (both of which take him home).The Blissville company’s bus arrival times are exactly 15 minutes apart, whereas the time from one Blotchville company bus to the next is Expo( 1 15 ). Fred arrives at a uniformly random time on a certain day.(a) What is the probability that the Blotchville company bus arrives first? (b) What is the CDF of Fred’s waiting time for a bus?3. A chicken lays a Pois(λ) number N of eggs. Each egg hatches a chick with probability p, independently. Let X be the number which hatch, and Y be the number which do NOT hatch.(a) Find the joint PMF of N, X, Y . Are they independent? (b) Find the joint PMF of N, X. Are they independent? (c) Find the joint PMF of X, Y . Are they independent?(d) Find the correlation between N and X. Your final answer should work out to a simple function of p and the λ should cancel out.4. A scientist makes two measurements, considered to be independent standard Normal random variables. Find the correlation between the larger and smaller of the values.5. This problem explores a visual interpretation of covariance. Data are collected for n ≥ 2 individuals, where for each individual two variables are measured (e.g., height and weight). Assume independence across individuals (e.g., person l’s variables gives no information about the other people), but not within individuals (e.g., a person’s height and weight may be correlated).Let (x1, y1), . . . ,(xn, yn) be the n data points. The data are considered here as fixed, known numbers-they are the observed values after performing an experiment. Imagine plotting all the points (xi, yi) in the plane, and drawing the rectangle determined by each pair of points. For example, the points (1, 3) and (4, 6) determine the rectangle with vertices (1, 3),(1, 6),(4, 6),(4, 3).The signed area contributed by (xi, yi) and (xj , yj ) is the area of the rectangle they determine if the slope of the line between them is positive, and is the negative of the area of the rectangle they determine if the slope of the line between them is negative.(Define the signed area to be 0 if xi = xj or yi = yj , since then the rectangle is degenerate.) So the signed area is positive if a higher x value goes with a higher y value for the pair of points, and negative otherwise. Assume that the xi are all distinct and the yi are all distinct.(a) The sample covariance of the data is defined to be r = 1 n �n i=1 (xi − x¯)(yi − y¯) where x¯ = 1 n �n i=1 xi and y¯ = 1 n �n i=1 yi are the sample means. (There are differing conventions about whether to divide by n − 1 or n in the definition of sample covariance, but that need not concern us for this problem.)Let (X, Y ) be one of the (xi, yi) pairs, chosen uniformly at random. Determine precisely how Cov(X, Y ) is related to the sample covariance.(b) Let (X, Y ) be as in (a), and (X˜, Y˜ ) be an independent draw from the same distribution. That is, (X, Y ) and (X¯, Y˜ ) are randomly chosen from the n points, independently (so it is possible for the same point to be chosen twice).Express the total signed area of the rectangles as a constant times E((X −X¯)(Y − Y˜ )). Then show that the sample covariance of the data is a constant times the total signed area of the rectangles.Hint: Consider E((X − X˜)(Y − Y˜ )) in two ways: as the average signed area of the random rectangle formed by (X, Y ) and (X¯, Y¯ ), and using properties of expectation to relate it to Cov(X, Y ). For the former, consider the n2 possibilities for which point (X, Y ) is and which point (X˜, Y¯ ); note that n such choices result in degenerate rectangles.(c) Based on the interpretation from (b), give intuitive explanations of why for any r.v.s W1, W2, W3 and constants a1, a2, covariance has the following properties: (i) Cov (W1, W2) = Cov (W2, W1); (ii) Cov (a1W1, a2W2) = a1a2 Cov (W1, W2); (iii) Cov (W1 + a1, W2 + a2) = Cov (W1, W2); (iv) Cov (W1, W2 + W3) = Cov (W1, W2) + Cov (W1, W3).
1. Show the proof of general Bayes’ Rule (four cases). 2. Let X and Y be i.i.d. Geom(p), and N = X + Y . (a) Find the joint PMF of X, Y, N. (b) Find the joint PMF of X and N. (c) Find the conditional PMF of X given N = n, and give a simple description in words of what the result says.3. Let X ∼ Expo(λ), and let c be a positive constant. (a) If you remember the memoryless property, you already know that the conditional distribution of X given X > c is the same as the distribution of c + X (think of waiting c minutes for a “success” and then having a fresh Expo(λ) additional waiting time). Derive this in another way, by finding the conditional CDF of X given X > c and the conditional PDF of X given X > c. (b) Find the conditional CDF and conditional PDF of X given X < c.4. Let U1, U2, U3 be i.i.d. Unif(0, 1), and let L = min(U1, U2, U3), M = max(U1, U2, U3). (a) Find the marginal CDF and marginal PDF of M, and the joint CDF and joint PDF of L, M. (b) Find the conditional PDF of M given L.5. Let X and Y be i.i.d. Geom(p), L = min(X, Y ), and M = max(X, Y ). (a) Find the joint PMF of L and M. Are they independent?(b) Find the marginal distribution of L in two ways: using the joint PMF, and using a story.(c) Find E[M].(d) Find the joint PMF of L and M − L. Are they independent?
1. Use the method of inverse transform sampling (or called the method of inverse CDF) to obtain samples from each of the following continuous distributions: (a) Logistic distribution with CDF F(x) = 1 1+e−x , ∀x ∈ R. (b) Rayleigh distribution with CDF F(x) = 1 − e−x2/2, ∀x > 0. (c) Exponential distribution with CDF F(x) = 1 − e−x, x > 0.2. Develop algorithms to obtain samples from each of the following discrete distributions: (a) Bernoulli distribution Bern(0.5). (b) Binomial distribution Bin(20, 0.5). (c) Geometric distribution Geom(0.5). (d) Negative Binomial distribution NBin(10, 0.5).3. Let Ui ∼ Unif(0, 1), i ≥ 1 be i.i.d. random variables. Define N as follows: N = max � n : �n i=1 Ui ≥ e−1 · � (a) Estimate E(N) by generating 5000 values of N and then use the sample mean. (b) Estimate Var(N). (c) Estimate P(N = i), for i = 0, 1, 2, 3. (d) Can you find the exact distribution of N4. (a) In the classical three-door Monty Hall problem, a contestant chooses one of three closed doors, two of which have a goat behind them and one of which has a car. Monty, who knows where the car is, then opens one of the two remaining doors.The door he opens always has a goat behind it (he never reveals the car). If he has a choice, then he picks a door at random with equal probabilities. Monty then offers the contestant the option of switching to the other unopened door. If the contestants goal is to get the car, should she switch doors? Please use simulation to compare the strategy of never-switching and the strategy of switching.(b) Now we consider the progressive Monty Hall problem. This time we assume there are n identical doors, where n is an integer satisfying n ≥ 3. One door conceals a car, the other n − 1 doors conceal goats.You choose one of the doors at random but do not open it. Monty then opens a door he knows to conceal a goat, always choosing randomly among the available doors. At this point he gives you the option either of sticking with your original door or switching to one of the remaining doors.You make your decision. Monty now eliminates another goat-concealing door (at random) and once more gives you the choice either of sticking or switching. This process continues until only two doors remain in play.What strategy should you follow to maximize your chances of winning? We consider three strategies: i. Select a door at random and stick with it throughout. ii. Select a door at random, then switch doors at every opportunity, choosing your door randomly at each step. iii. Select a door at random, stick with your first choice until only two doors remain, and then switch. When n = 4 and n = 100, please use simulation to compare such three strategies.5. Estimate the value of the percolation threshold via Monte Carlo simulation. (a) Percolation. Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations.(b) The model. We model a percolation system using an n-by-n grid of sites. Each site is either open or blocked, where open means the water or other materials can flow through such site. Open sites can be further classified into two categories: full open sites and empty open sites. A full open site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites.An empty open site is an open site that is NOT full. We say the system percolates if there is a full open site in the bottom row. In other words, a system percolates if we could find a path of open sites from the top row to the bottom row. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)Figure 1: The blocked sites are displayed in black. The full open sites are displayed in cyan. The empty open sites are displayed in white. (c) The problem. In a famous scientific problem, researchers are interested in the following question: given an n-by-n random grid, if sites are independently set to be open with probability p (and therefore blocked with probability 1 − p), what is the probability that the system percolates? When p = 0, the system does not percolate; when p = 1, the system percolates. The plots below show the site vacancy probability p versus the percolation probability for 20-by-20 random grid (left) and 100-by-100 random grid (right).When n is sufficiently large, there is a threshold value p∗ such that when p < p∗ a random n-by-n grid almost never percolates, and when p > p∗, a random n-byn grid almost always percolates. No mathematical solution for determining the percolation threshold p∗ has yet been derived. Your task is to write a computer program to estimate p∗.(d) Monte Carlo simulation. To estimate the percolation threshold, consider the following computational experiment:• Initialize all sites to be blocked and black. • Repeat the following until the system percolates: – Choose a site uniformly at random among all blocked sites. – Open the site. • The fraction of sites that are opened when the system percolates provides an estimate of the percolation threshold.For example, if sites are opened in a 20-by-20 lattice according to the snapshots below, then our estimate of the percolation threshold is 204/400 = 0.51 because the system percolates when the 204th site is opened.By repeating this computation experiment T times and averaging the results, we obtain a more accurate estimate of the percolation threshold. Let xt be the fraction of open sites in computational experiment t. The sample mean x¯ provides an estimate of the percolation threshold: x¯ = x1 + x2 + · · · + xT T .(e) The task. Estimate the percolation threshold for 20-by-20 grid, 50-by-50 grid, and 100-by-100 grid via Monte Carlo simulation.
1. Let F(x) = 2 π sin−1 ( √x), for 0 < x < 1, and let F(x) = 0 for x ≤ 0 and F(x) = 1 for x ≥ 1. (a) Check that F is a valid CDF, and find the corresponding PDF f.(b) Explain how it is possible for f to be a valid PDF even though f(x) goes to ∞ as x approaches 0 and as x approaches 1.2. Let F be a CDF which is continuous and strictly increasing. Let µ be the mean of the distribution. The quantile function, F −1, has many applications in statistics and econometrics. Show that the area under the curve of the quantile function from 0 to 1 is µ.3. Let U1, . . . , Un be i.i.d. Unif(0, 1), and X = max(U1, …, Un). What is the PDF of X? What is E(X)?4. A stick of length 1 is broken at a uniformly random point, yielding two pieces. Let X and Y be the lengths of the shorter and longer pieces, respectively, and let R = X/Y be the ratio of the lengths X and Y .(a) Find the CDF and PDF of R. (b) Find the expected value of R (if it exists). (c) Find the expected value of 1/R (if it exists).5. The Exponential is the analog of the Geometric in continuous time. This problem explores the connection between Exponential and Geometric in more detail, asking what happens to a Geometric in a limit where the Bernoulli trials are performed faster and faster but with smaller and smaller success probabilities.Suppose that Bernoulli trials are being performed in continuous time; rather than only thinking about first trial, second trial, etc., imagine that the trials take place at points on a timeline.Assume that the trials are at regularly spaced times 0, ∆t, 2∆t, . . . , where ∆t is a small positive number. Let the probability of success of each trial be λ∆t, where λ is a positive constant. Let G be the number of failures before the first success (in discrete time), and T be the time of the first success (in continuous time).(a) Find a simple equation relating G to T. (b) Find the CDF of T. (c) Show that as ∆t → 0, the CDF of T converges to the Expo(λ) CDF, evaluating all the CDFs at a fixed t ≥ 0.6. Let Z ∼ N (0, 1), and c be a nonnegative constant. Find E(max(Z − c, 0)), in terms of the standard Normal CDF Φ and PDF ϕ.
1. Suppose there are n types of toys, which you are collecting one by one. Each time you collect a toy, it is equally likely to be any of the n types. What is the expected number of distinct toy types that you have after you have collected t toys? (Assume that you will definitely collect t toys, whether or not you obtain a complete set before then.)2. A coin with probability p of Heads is flipped n times. The sequence of outcomes can be divided into runs (blocks of H’s or blocks of T’s), e.g., HHHTTHTTTH becomes HHH TT H TTT H , which has 5 runs. Find the expected number of runs.3. Elk dwell in a certain forest. There are N elk, of which a simple random sample of size n is captured and tagged (so all �N n � sets of n elk are equally likely). The captured elk are returned to the population, and then a new sample is drawn. This is an important method that is widely used in ecology, known as capture-recapture. If the new sample is also a simple random sample, with some fixed size, then the number of tagged elk in the new sample is Hypergeometric.For this problem, assume that instead of having a fixed sample size, elk are sampled one by one without replacement until m tagged elk have been recaptured, where m is specified in advance (of course, assume that 1 ≤ m ≤ n ≤ N). An advantage of this sampling method is that it can be used to avoid ending up with a very small number of tagged elk (maybe even zero), which would be problematic in many applications of capture-recapture. A disadvantage is not knowing how large the sample will be.(a) Find the PMFs of the number of untagged elk in the new sample (call this X) and of the total number of elk in the new sample (call this Y ). (b) Find the expected sample size E[Y ] using symmetry, linearity, and indicator r.v.s.(c) Suppose that m, n, N are such that E[Y ] is an integer. If the sampling is done with a fixed sample size equal to E[Y ] rather than sampling until exactly m tagged elk are obtained, find the expected number of tagged elk in the sample. Is it less than m, equal to m, or greater than m (for n < N)?4. People are arriving at a party one at a time. While waiting for more people to arrive they entertain themselves by comparing their birthdays. Let X be the number of people needed to obtain a birthday match, i.e., before person X arrives there are no two people with the same birthday, but when person X arrives there is a match. 1 Assume for this problem that there are 365 days in a year all equally likely. By the result of the birthday problem form Chapter 1, for 23 people there is a 50.7% chance of a birthday match (and for 22 people there is a less than 50% chance). But this has to do with the median of X; we also want to know the mean of X, and in this problem we will find it, and see how it compares with 23.(a) A median of a random variable Y is a value m for which P(Y ≤ m) ≥ 1/2 and P(Y ≥ m) ≥ 1/2. Every distribution has a median, but for some distributions it is not unique. Show that 23 is the unique median of X.(b) Show that X = I1 + I2 + · · · + I366, where Ij is the indicator random variable for the event X ≥ j. Then find E(X) in terms of pj ’s defined by p1 = p2 = 1 and for 3 ≤ j ≤ 366, pj = � 1 − 1 365 � � 1 − 2 365 � · · · � 1 − j − 2 365 � . (c) Compute E(X) numerically (do NOT submit the code if used). (d) Find the variance of X, both in terms of the pj ’s and numerically (do NOT submit the code if used).5. Suppose there are 5 boxes (with tags 1, 2, 3, 4, 5) and we are going to put 14 balls into these boxes. It is known that one can at most put 6 balls in a box. How many different ways can you distribute these balls?
1. A treasure is randomly placed in one of the nine realms (numbered from 1 to 9) attached to the Yggdrasill. Kratos searches for the treasure by asking Mimir yes-no questions. Find the expected number of questions until Kratos is sure about the location of the treasure, under each of the following strategies.(a) An enumeration strategy: Kratos asks questions of the form “is it in realm k?”. (b) A bisection strategy: Kratos eliminates as close to half of the remaining realms as possible by asking questions of the form “is it in a realm numbered less than or equal to k?”.2. A particular Youtuber is known for his arbitrary steak-eating habit during live streaming. In each live streaming day, he orders a steak with doneness as one of well done, medium well, medium, medium rare, and rare (with equal probability, independent of other live streaming days). How many days of live streaming do you expect to watch before you see him eating steaks with each possible doneness at least once (suppose you are a big fan who watches his every live streaming)?3. Mario and Zelda are independently performing independent Bernoulli trials. For concreteness, assume that Mario is flipping a nickel with probability p1 of Heads and Zelda is flipping a penny with probability p2 of Heads. Let X1, X2, · · · be Mario’s results and Y1, Y2, · · · be Zelda’s results, with Xi ∼ Bern(p1) and Yj ∼ Bern(p2).(a) Find the distribution and expected value of the first time at which they are simultaneously successful, i.e., the smallest n such that Xn = Yn = 1. (b) Find the expected time until at least one has a success (including the success).(c) For p1 = p2, find the probability that their first successes are simultaneous, and use this to find the probability that Mario’s first success precedes Zelda’s.4. Let X and Y be independent geometric random variables, where X has parameter p and Y has parameter q. (a) What is the probability that X = Y ? (b) What is E[max(X, Y )]? (c) What is P(min(X, Y ) = k)? (d) What is E[X|X ≤ Y ]?5. You plan to eat m meals at a certain restaurant, where you have never eaten before. Each time, you will order one dish (without replacement).The restaurant has n dishes on the menu, with n ≥ m. Assume that if you had tried all the dishes, you would have a definite ranking of them from 1 (your least favorite) to n (your favorite). If you knew which your favorite was, you would be happy to order it always (you never get tired of it).Before you’ve eaten at the restaurant, this ranking is completely unknown to you. After you’ve tried some dishes, you can rank those dishes amongst themselves, but don’t know how they compare with the dishes you haven’t yet tried. There is thus an exploration-exploitation trade-off : should you try new dishes, or should you order your favorite among the dishes you have tried before?A natural strategy is to have two phases in your series of visits to the restaurant: an exploration phase, where you try different dishes each time, and an exploitation phase, where you always order the best dish you obtained in the exploration phase. Let k be the length of the exploration phase (so m − k is the length of the exploitation phase).Your goal is to maximize the expected sum of the ranks of the dishes you eat there (the rank of a dish is the true rank from 1 to n that you would give that dish if you could try all the dishes). Show that the optimal choice is k = �2(m + 1) − 1 or this rounded up or down to an integer if needed.Do this in the following steps: (a) Let X be the rank of the best dish that you find in the exploration phase. Find the expected sum of the ranks of the dishes you eat, in terms of E[X]. (b) Find the PMF of X, as a simple expression in terms of binomial coefficients. (c) Show that E[X] = k(n + 1) k + 1 . (d) Use calculus to find the optimal value of k.
1. Consider the original Monty Hall problem, except that Monty enjoys opening door 2 more than he enjoys opening door 3, and if he has a choice between opening these two doors, he opens door 2 with probability p, where 1 2 ≤ p ≤ 1.To recap: there are three doors, behind one of which there is a car (which you want), and behind the others there are goats (which you don’t want). Initially, all possibilities are equally likely for where the car is. You choose a door, which for concreteness we assume is door 1. Monty (knows which door has the car) then opens a door to reveal a goat, and offers you the option of switching.(a) Find the unconditional probability that the strategy of always switching succeeds (unconditional in the sense that we do not condition on which of doors 2 or 3 Monty opens).(b) Find the probability that the strategy of always switching succeeds, given that Monty opens door 2 (assume we always choose door 1 first). (c) Find the probability that the strategy of always switching succeeds, given that Monty opens door 3 (assume we always choose door 1 first).2. (a) Is there a discrete distribution with support {1, 2, 3, . . . }, such that the value of the PMF at n is proportional to 1/n? (b) Is there a discrete distribution with support {1, 2, 3, . . . }, such that the value of the PMF at n is proportional to 1/n2?3. Let X be a random day of the week, coded so that Monday is 1, Tuesday is 2, etc. (so X takes values 1, 2, . . . , 7 with equal probabilities). Let Y be the next day after X. Do X and Y have the same distribution? What is P(X < Y )?4. There are two coins, one with probability p1 of Heads and the other with probability p2 of Heads. One of the coins is randomly chosen (with equal probabilities for the two coins). It is then flipped n ≥ 2 times. Let X be the number of times it lands Heads.(a) Find the PMF of X. (b) What is the distribution of X if p1 = p2? (c) Give an intuitive explanation of why X is not Binomial for p1 ∕= p2.5. For x and y binary digits (0 or 1), let x �y be 0 if x = y and 1 if x ∕= y (this operation is called exclusive or (often abbreviated to XOR), or addition mod 2).(a) Let X ∼ Bern(p) and Y ∼ Bern(1/2), independently. What is the distribution of X �Y ?(b) With notation as in sub-problem (a), is X �Y independent of X? Is X �Y independent of Y ? Be sure to consider both the case p = 1/2 and the case p ∕= 1/2.(c) Let X1, . . . , Xn be i.i.d. (i.e., independent and identically distributed) Bern(1/2) R.V.s. For each nonempty subset J of {1, 2, . . . , n}, let YJ = � j∈J Xj .Show that YJ ∼ Bern(1/2) and that these 2n − 1 R.V.s are pairwise independent, but not independent.
1. A system composed of 5 homogeneous devices is shown in the following figure. It is said to be functional when there exists at least one end-to-end path that devices on such path are all functional. For such a system, if each device, which is independent of all other devices, functions with probability p, then what is the probability that the system functions? Such a probability is also called the system reliability. Figure 1: An illustration of the system composed of 5 homogeneous devices.2. (a) Suppose that in the population of gamers, being good at Genshin Impact is independent of being good at Apex (with respect to some measure of “good”). A certain school club has a simple admission procedure: admit an applicant if and only if the applicant is good at Genshin Impact or is good at Apex.Intuitive explain why it makes sense that among gamers that the club admits, being good at Apex is negatively associated with being good at Genshin Impact, i.e., conditioning on being good at Apex decreases the chance of being good at Genshin Impact.(b) (Berkson’s paradox) Show that if A and B are independent and C = A ∪ B, then A and B are conditionally dependent given C (as long as P(A ∩ B) > 0 and P(A ∪ B) < 1), with P(A | B ∩ C) < P(A | C).3. A fair die is rolled repeatedly, and a running total is kept (which is, at each time, the total of all the rolls up until that time). Let pn be the probability that the running total is ever exactly n (assume the die will always be rolled enough times so that the running total will eventually exceed n, but it may or may not ever equal n).(a) Write down a recursive equation for pn. Your equation should be true for all positive integers n, so give a definition of p0 and pk for k < 0 so that the recursive equation is true for small values of n.(b) Find p7. (c) Give an intuitive explanation for the fact that pn → 1/3.5 = 2/7 as n → ∞.4. There are n types of toys, which you are collecting one by one. Each time you buy a toy, it is randomly determined which type it has, with equal probabilities. Let pi,j be the probability that just after you have bought your ith toy, you have exactly j toy types in your collection, for i ≥ 1 and 0 ≤ j ≤ n.(a) Find a recursive equation expressing pi,j in terms of pi−1,j and pi−1,j−1, for i ≥ 2 and 1 ≤ j ≤ n. (b) Describe how the recursion from (a) can be used to calculate pi,j .5. Link is an immortal drunk man who wanders around randomly on the integers. He starts at the origin, and at each step he moves 1 unit to the right or 1 unit to the left, with probabilities p and q = 1 − p respectively, independently of all his previous steps. Let Sn be his position after n steps.(a) Let pk be the probability that the drunk ever reaches the value k, for all k ≥ 0. Write down a recursive equation for pk (you do not need to solve it for this part). (b) Find pk, fully simplified; be sure to consider all 3 cases: p < 1/2, p = 1/2, and p > 1/2.
1. Given n ≥ 2 numbers (a1, a2, . . . , an) with no repetitions, a bootstrap sample is a sequence (x1, x2, . . . , xn) formed from the aj ’s by sampling with replacement with equal probabilities. Bootstrap samples arise in a widely used statistical method known as the bootstrap. For example, if n = 2 and (a1, a2) = (3, 1), then the possible bootstrap samples are (3, 3),(3, 1),(1, 3), and (1, 1).(a) How many possible bootstrap samples are there for (a1, . . . , an)? (b) How many possible bootstrap samples are there for (a1, . . . , an), if order does not matter (in the sense that it only matters how many times each aj was chosen, not the order in which they were chosen)?(c) One random bootstrap sample is chosen (by sampling from a1, . . . , an with replacement, as described above). Show that not all unordered bootstrap samples (in the sense of (b)) are equally likely.Find an unordered bootstrap sample b1 that is as likely as possible, and an unordered bootstrap sample b2 that is as unlikely as possible. Let p1 be the probability of getting b1 and p2 be the probability of getting b2 (so pi is the probability of getting the specific unordered bootstrap sample bi). What is p1/p2? What is the ratio of the probability of getting an unordered bootstrap sample whose probability is p1 to the probability of getting an unordered sample whose probability is p2?2. If each box of the broad noodle of chili oil flavor contains a coupon, and there are 108 different types of coupons. Given n ≥ 200, what is the probability that buying n boxes can collect all 108 types of coupons? You need to plot a figure (you do NOT need to submit the code, if used, this time) to show how such probability changes with the increasing value of n. When such probability is no less than 95%, what is the minimum number of n?3. A batch of one hundred garage kits is inspected by testing four randomly selected ones. If one of the four is defective, the batch is rejected. What is the probability that the batch is accepted if it contains five defectives?4. There are three boxes: a. A box containing two gold coins; b. A box containing two silver coins;c. A box containing one gold coin and a silver coin. After choosing a box randomly and withdrawing one coin randomly, if that happens to be a gold coin, find the probability of the next coin drawn from the same box also being a gold coin.5. Mirana is about to play a two-game Starcraft match with an opponent, and wants to find the strategy that maximizes his winning chances. Each game ends with either a win by one of the players, or a draw. If the score is tied at the end of the two games, the match goes into a sudden-death mode, and the players continue to play until the first time one of them wins a game (and the match).Mirana has two playing styles, i.e., timid and bold, and she can choose one of the two at will in each game, no matter what style she chose in previous games. With timid play, she draws with probability pd > 0, and she loses with probability (1 − pd). With bold play, she wins with probability pw, and she loses with probability (1 − pw). Mirana will always play bold during sudden death, but may switch style between games 1 and 2.Find the probability that Mirana wins the match for each of the following strategies: (a) Play bold in both games 1 and 2. (b) Play timid in both games 1 and 2. (c) Play timid whenever she is ahead in the score, and play bold otherwise.(d) Assume that pw < 1/2, so Mirana is the worse player, regardless of the playing style she adopts. Show that with the strategy in (c) above, and depending on the values of pw and pd, Mirana may have a better than a 50-50 chance to win the match. Intuitively, how do you explain this advantage?
1. Define � n k � as the number of ways to partition {1, 2, . . . , n} into k non-empty subsets, or the number of ways to have n students split up into k groups such that each group has at least one student. For example, � 4 2 � = 7 because: •{1}, {2, 3, 4}, • {1, 2}, {3, 4}, •{2}, {1, 3, 4}, • {1, 3}, {2, 4}, •{3}, {1, 2, 4}, • {1, 4}, {2, 3}, •{4}, {1, 2, 3}. Prove the following identities: (a) � n + 1 k � = � n k − 1 � + k � n k � . (b) �n j=k � n j � � j k � = � n + 1 k + 1 � .2. A norepeatword is a sequence of at least one (and possibly all) of the usual 26 letters a, b, c, . . . , z, with repetitions not allowed. For example, “course” is a norepeatword, but “statistics” is not. Order matters, e.g., “course” is not the same as “source”. A norepeatword is chosen randomly, with all norepeatwords equally likely. Show that the probability that it uses all 26 letters is very close to 1/e.3. An academic department offers 8 lower level courses: {L1, L2, . . . , L8} and 10 higher level courses: {H1, H2, . . . , H10}. A valid curriculum consists of 4 lower level courses and 3 higher level courses. (a) How many different curricula are possible? (b) Suppose that {H1, . . . , H5} have L1 as a prerequisite, and {H6, . . . , H10} have L2 and L3 as prerequisites, i.e., any curricula which involve, say, one of {H1, . . . , H5} must also include L1. How many different curricula are there?4. In the birthday problem, we assumed that all 365 days of the year are equally likely (and excluded February 29). In reality, some days are slightly more likely as birthdays than others.For example, scientists have long struggled to understand why more babies are born 9 months after a holiday. Let p = (p1, p2, . . . , p365) be the vector of birthday probabilities, with pj the probability of being born on the jth day of the year (February 29 is still excluded, with no offense intended to Leap Dayers). The kth elementary symmetric polynomial in the variables x1, . . . , xn is defined by ek(x1, . . . , xn) = � 1≤j1
