第 4 / 11 页
非代码面试题
显示 20 / 215 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
455Geometric Mean of Random Gains via LLN and CLTLet X 1, X 2, \ldots be i.i.d.\ with P(X i = 1) = \tfrac 1 2 and P(X i = 0) = \tfrac 1 2 . Define the geometric-mean-like quantity Y n = (\prod i=1 n (1 + X i) ) 1/n . **(a)** Find \lim n Y n almost surely. **(b)** For n = 200, use the CLT to approximate P(Y 200 > 1.45). You may use: \ln 2 \approx 0.6931, \Phi(1.02) \approx 0.8461.概率困难derivation未尝试免费460Delta Method for Square Root of the Sample MeanLet X 1, \ldots, X n be i.i.d.\ Exp ( ) with = 4 (so E[X i] = 1/4, Var (X i) = 1/16). Define T n = X n . **(a)** Using the delta method, find the asymptotic distribution of n \,(T n - ) where = E[X i]. **(b)** For n = 256, approximate P(T 256 > 0.525). You may use \Phi(1.60) \approx 0.9452.概率困难derivation未尝试免费464Delta Method for the Log of a Gamma Sample MeanLet X 1, \ldots, X n be i.i.d.\ Gamma (2, 1) (shape 2, rate 1), so E[X i] = 2 and Var (X i) = 2. Define W n = \ln( X n). **(a)** Using the delta method, determine the asymptotic distribution of n (W n - \ln 2). **(b)** For n = 200, approximate P(W n < 0.6). You may use \ln 2 \approx 0.6931 and \Phi(-1.86) \approx 0.0314.概率困难derivation未尝试免费465Berry-Esseen Bound for a Sum of Uniform Random VariablesLet U 1, \ldots, U n be i.i.d.\ Uniform (0,1) and S n = \sum i=1 n U i. The Berry-Esseen theorem states \sup x |P\! ( S n - n/2 n \le x ) - \Phi(x) | \le C\, 3 n , where 2 = Var (U i), = E[|U i - 1/2| 3], and C \le 0.4748. **(a)** Compute = E[|U i - 1/2| 3] exactly. **(b)** Evaluate the Berry-Esseen bound for n = 50. **(c)** How large must n be for the bound to guarantee the CLT error is below 0.01?概率困难derivation未尝试免费469Geometric Mean of Random Multipliers via LLN and CLTAn investment grows by a random factor each year: in year i, the portfolio is multiplied by X i, where X i are i.i.d.\ with P(X i = 2) = P(X i = 4) = 1/2. After n years, the annualized growth factor is the geometric mean G n = (\prod i=1 n X i ) 1/n . **(a)** Find \lim n G n almost surely. **(b)** For n = 100, use the CLT to approximate P(G 100 > 3). You may use \ln 2 \approx 0.6931, \ln 3 \approx 1.0986, and \Phi(1.70) \approx 0.9554.概率困难derivation未尝试免费470Asymptotic Distribution of the Sample MedianLet X 1, \ldots, X n be i.i.d.\ Uniform (0,1) and let M n denote the sample median (the middle order statistic for odd n, or the average of the two middle values for even n). The asymptotic theory of order statistics gives n \,(M n - m) \xrightarrow d N\! (0, 1 4[f(m)] 2 ), where m is the population median and f is the density at m. **(a)** For Uniform (0,1), identify m and f(m), and state the asymptotic variance of n \,M n. **(b)** For n = 400, approximate P(M 400 > 0.54). You may use \Phi(1.60) \approx 0.9452.概率困难derivation未尝试免费474Sample Size for a Tail Probability GuaranteeLet X 1, X 2, \ldots be i.i.d.\ Exp (1) (mean 1, variance 1). A system designer requires that the sample mean X n exceeds 1.1 with probability less than 1\%. Using the CLT, find the smallest n satisfying P( X n > 1.1) < 0.01. You may use \Phi(2.33) \approx 0.9901.概率中等数值题未尝试免费475CLT with Estimated Variance via Slutsky's TheoremLet X 1, \ldots, X n be i.i.d.\ with mean and finite variance 2 > 0. Define the sample variance S n 2 = 1 n-1 \sum i=1 n (X i - X n) 2 and the studentized statistic T n = n \,( X n - ) S n . **(a)** Using the LLN and Slutsky's theorem, show that T n \xrightarrow d N(0,1). **(b)** In a study with n = 100 observations, you find X 100 = 12.5 and S 100 = 3.0. Assuming the true mean is \mu 0 = 12, approximate P( X 100 > 12.5) using T n. You may use \Phi(1.67) \approx 0.9525.概率困难derivation未尝试免费483First Return to the Origin on an Asymmetric CycleConsider a Markov chain on \ 0, 1, 2, 3\ arranged in a cycle. From state i, the chain moves clockwise to state (i+1) \bmod 4 with probability p i and counterclockwise to state (i-1) \bmod 4 with probability 1 - p i, where p 0 = \tfrac 3 4 , \quad p 1 = \tfrac 1 2 , \quad p 2 = \tfrac 1 4 , \quad p 3 = \tfrac 1 2 . Compute the expected number of steps to return to state 0 for the first time, starting from state 0. *Recall:* The mean return time to state i in an irreducible chain equals 1/\pi i.概率中等数值题未尝试免费489Splitting Probability and Expected Hitting Time with Two TargetsConsider a Markov chain on \ 0, 1, 2, 3, 4\ with transition probabilities for interior states: p(1,0) = \tfrac 1 2 , \quad p(1,2) = \tfrac 1 2 , \quad p(2,1) = \tfrac 1 3 , \quad p(2,3) = \tfrac 2 3 , \quad p(3,2) = \tfrac 1 4 , \quad p(3,4) = \tfrac 3 4 . States 0 and 4 are absorbing. Let T = \inf\ n \ge 0 : X n \in \ 0, 4\ \ . **(a)** Starting from state 2, compute P(X T = 4 \mid X 0 = 2). **(b)** Compute E[T \mid X 0 = 2].概率困难derivation未尝试免费493Expected Absorption Time with Increasing DriftA Markov chain on \ 0, 1, 2, 3, 4\ has absorbing states 0 and 4. The transition probabilities for transient states are: p(1,0) = \tfrac 1 5 , \quad p(1,2) = \tfrac 4 5 , \quad p(2,1) = \tfrac 2 5 , \quad p(2,3) = \tfrac 3 5 , \quad p(3,2) = \tfrac 3 5 , \quad p(3,4) = \tfrac 2 5 . Compute E[T \mid X 0 = 1] and E[T \mid X 0 = 3], where T = \inf\ n \ge 0 : X n \in \ 0, 4\ \ .概率中等derivation未尝试免费494Expected Time to Visit All States in an Ergodic ChainA Markov chain on \ 1, 2, 3, 4\ has transition matrix P = \begin pmatrix 0 & 1 & 0 & 0 \\ \tfrac 1 3 & 0 & \tfrac 2 3 & 0 \\ 0 & \tfrac 1 2 & 0 & \tfrac 1 2 \\ 0 & 0 & \tfrac 1 2 & \tfrac 1 2 \end pmatrix . Starting from state 1, let T cover = \inf\ n \ge 0 : \ 1,2,3,4\ \subseteq \ X 0, X 1, \ldots, X n\ \ be the first time all four states have been visited. Compute E[T cover \mid X 0 = 1]. *Hint:* Decompose the cover time by tracking which states remain unvisited. Since the chain starts at state 1 and must go to 2, then eventually reach 3 and 4, compute the expected time to reach each new state sequentially.概率困难derivation未尝试免费499First Passage with Periodically Varying DriftA Markov chain on \ 0, 1, 2, 3, 4, 5, 6\ has absorbing state 0 and reflecting state 6 (i.e., p(6, 5) = 1). For transient states 1 \le i \le 5, the transition probabilities depend on i \bmod 3: - If i \equiv 0 \pmod 3 (i.e., i = 3): p(i, i-1) = \tfrac 2 3 , p(i, i+1) = \tfrac 1 3 . - If i \equiv 1 \pmod 3 (i.e., i \in \ 1, 4\ ): p(i, i-1) = \tfrac 1 2 , p(i, i+1) = \tfrac 1 2 . - If i \equiv 2 \pmod 3 (i.e., i \in \ 2, 5\ ): p(i, i-1) = \tfrac 1 3 , p(i, i+1) = \tfrac 2 3 . Compute E[T 0 \mid X 0 = 3].概率中等derivation未尝试免费505Gambler's Ruin with a Partially Reflecting BarrierConsider a Markov chain on \ 0, 1, 2, \ldots\ with absorbing state 0. From state k \ge 1, the chain moves to k+1 with probability p and to k-1 with probability q = 1 - p, where 0 < p < 1. However, there is a **reflecting barrier** at state N: from state N, the chain moves to N-1 with probability 1 (it is always pushed back). Starting from state k with 1 \le k \le N: **(a)** Find the probability r k of eventual absorption at 0. **(b)** For p = q = \tfrac 1 2 and N = 4, compute r 2 and the expected absorption time E[T \mid X 0 = 2].概率困难derivation未尝试免费530Effective Resistance and Commute Time on the Hypercube Q₃Consider the 3-dimensional hypercube graph Q 3 (vertices are binary strings of length 3; edges connect strings differing in exactly one bit). Each edge has unit resistance. (a) Using the symmetry of Q 3, compute the effective resistance R eff (000, 111) between the two antipodal vertices. (b) The commute time C(u, v) of a random walk between vertices u and v on a graph satisfies C(u, v) = 2m R eff (u, v), where m is the number of edges. Use this to find the commute time between 000 and 111.概率困难derivation未尝试面试订阅533Spectral Gap and Mixing Time of the Lazy Walk on a CycleConsider the lazy random walk on the cycle graph C n: at each step, the walker stays put with probability \tfrac 1 2 , and moves to each of the two neighbors with probability \tfrac 1 4 . The transition matrix has eigenvalues \lambda k = \tfrac 1 2 (1 + \cos(2 k / n)) for k = 0, 1, \ldots, n-1. (a) Find the spectral gap = 1 - \lambda 1 in terms of n. (b) Using the relation t mix \asymp 1 (up to logarithmic factors), determine the order of the mixing time for the lazy walk on C n as n .概率中等derivation未尝试免费535Effective Resistance and Commute Time on K₂,₃Consider the complete bipartite graph K 2,3 with parts A = \ a 1, a 2\ (each of degree 3) and B = \ b 1, b 2, b 3\ (each of degree 2). Each edge has unit resistance. (a) Compute the effective resistance R eff (a 1, a 2) between the two vertices of part A. (b) Use the commute-time identity C(u,v) = 2m R eff (u,v) to find the expected commute time between a 1 and a 2, where m is the number of edges. (c) By first-step analysis, compute h(a 1 a 2) and verify that h(a 1 a 2) + h(a 2 a 1) = C(a 1, a 2).概率困难derivation未尝试面试订阅540Effective Resistance and Commute Time on the 4-CycleConsider the cycle graph C 4 with vertices \ 0,1,2,3\ arranged in a square, and each edge having unit resistance. (a) Compute the effective resistance R eff (0, 2) between the two diagonally opposite vertices. (b) Using the commute-time identity C(u,v) = 2m R eff (u,v), find the commute time C(0,2). (c) By exploiting the symmetry 0 \leftrightarrow 2 of C 4, determine h(0 2) and verify consistency with the commute time.概率困难derivation未尝试面试订阅545Mixing Time of the Lazy Random Walk on KₙConsider the lazy random walk on the complete graph K n: at each step, the walker stays put with probability \tfrac 1 2 and moves to a uniformly random neighbor with probability \tfrac 1 2 . (a) Show that the transition matrix has two distinct eigenvalues: \lambda 0 = 1 (with multiplicity 1) and \lambda 1 = \tfrac 1 2 \bigl(1 - 1 n-1 \bigr) = n-2 2(n-1) (with multiplicity n-1). (b) Find the spectral gap = 1 - \lambda 1 and determine the mixing time t mix up to leading order in n.概率困难derivation未尝试面试订阅590Weighted Offer Stop Rule 5You may inspect up to 3 independent offers. Each offer takes values 0 with probability 1/4, 4 with probability 1/4, 7 with probability 1/4, 12 with probability 1/4. Rejecting an offer and continuing costs 1 point(s), and if you reach the last draw you must accept it. What first-round acceptance threshold is optimal, and what is the resulting expected net payoff?概率困难derivation未尝试免费