第 5 / 23 页
非代码面试题
显示 20 / 443 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
467Symmetric Random Walk Displacement via CLTA particle performs a symmetric random walk: at each step i, it moves X i = +1 or X i = -1, each with probability 1/2, independently. After n = 400 steps, the position is S 400 = \sum i=1 400 X i. **(a)** What does the LLN say about S n / n as n ? **(b)** Using the CLT, approximate P(S 400 > 10). You may use \Phi(0.50) \approx 0.6915.概率中等数值题未尝试免费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未尝试免费473Probability of Negative Portfolio Return via CLTA portfolio consists of n = 50 stocks with equal weight 1/n. The annual returns R 1, \ldots, R 50 are independent, each with mean = 0.08 (i.e., 8\%) and standard deviation = 0.20. The portfolio return is R = 1 50 \sum i=1 50 R i. **(a)** State what the LLN implies about R as n . **(b)** Using the CLT, approximate P( R < 0). You may use \Phi(2.83) \approx 0.9977.概率中等数值题未尝试免费526Hitting Time on the Complete Graph K₅A random walk moves on the complete graph K 5 (five vertices, every pair connected). At each step, the walker moves to one of the 4 neighbors chosen uniformly at random. Starting from vertex u, what is the expected number of steps to reach a specified vertex v u for the first time?概率简单数值题未尝试免费527Hitting Time to the Antipodal Vertex on a CycleA simple random walk moves on the cycle graph C 8 (vertices 0, 1, \ldots, 7 arranged in a circle). At each step, the walker moves clockwise or counterclockwise with equal probability \tfrac 1 2 . Starting at vertex 0, what is the expected number of steps to reach the antipodal vertex 4 for the first time?概率简单数值题未尝试免费528Hitting Time on the 3-Dimensional HypercubeA random walk moves on the 3-dimensional hypercube graph Q 3: the 8 vertices are binary strings of length 3, and two vertices are adjacent if they differ in exactly one coordinate. At each step, the walker picks one of the 3 coordinates uniformly at random and flips it. Starting at vertex 000, what is the expected number of steps to reach vertex 111 for the first time?概率中等数值题未尝试免费529Hitting Time on the Complete Bipartite Graph K₃,₃Consider the complete bipartite graph K 3,3 with parts A = \ a 1, a 2, a 3\ and B = \ b 1, b 2, b 3\ , where every vertex in A is connected to every vertex in B and vice versa (no edges within a part). A random walk at any vertex moves to each of its 3 neighbors with equal probability \tfrac 1 3 . Starting from vertex a 1, what is the expected number of steps to reach vertex b 1 for the first time?概率中等数值题未尝试免费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未尝试面试订阅532Hitting Time on the Petersen GraphThe Petersen graph has 10 vertices and 15 edges; it is 3-regular, vertex-transitive, and has diameter 2 (every pair of non-adjacent vertices has exactly one common neighbor, and the graph has girth 5). A random walk at each step moves to one of the 3 neighbors uniformly at random. Starting from a vertex u, what is the expected number of steps to reach a specified non-adjacent vertex v for the first time?概率中等数值题未尝试免费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未尝试面试订阅536Expected Return Time on the Complete Graph K₄A simple random walk moves on the complete graph K 4 (four vertices, every pair connected). At each step, the walker moves to one of the 3 neighbors chosen uniformly at random. Starting at a vertex v, what is the expected number of steps to return to v for the first time?概率简单数值题未尝试免费539Cover Time of the Complete Graph K₄A simple random walk moves on the complete graph K 4. At each step, the walker moves to one of the 3 neighbors uniformly at random. (a) Compute the maximum hitting time t hit = \max u,v h(u v). (b) Using Matthews' theorem, which gives t hit H n-1 \ge E[\tau cov ] \ge t hit H n-1 n-1 n , where n = 4 and H k = \sum i=1 k 1/i, bound the expected cover time. (c) Compute E[\tau cov ] exactly by decomposing into phases: after visiting k distinct vertices, find the expected time to discover the (k+1)-th.概率困难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未尝试面试订阅541Stationary Distribution and Return Times on a Small GraphConsider the graph G on four vertices \ A, B, C, D\ with edges \ A - B,\, A - C,\, A - D,\, B - C\ , so the degree sequence is d(A)=3, d(B)=2, d(C)=2, d(D)=1. A simple random walk moves at each step to a uniformly random neighbor. (a) Find the stationary distribution . (b) Compute the expected return time E v[T v +] for each vertex v.概率简单数值题未尝试免费542Hitting Time on the Wheel Graph W₆The wheel graph W 6 consists of a central hub h connected to all 5 vertices of a cycle C 5 (so h has degree 5 and each rim vertex has degree 3: two cycle neighbors and the hub). A simple random walk moves at each step to a uniformly random neighbor. Starting from a rim vertex v, what is the expected number of steps to reach the hub h?概率中等数值题未尝试免费543Hitting Time on the Ladder Graph (2×3 Grid)Consider the 2 3 grid graph (ladder graph) with vertices arranged as: \begin matrix 1 & - & 2 & - & 3 \\ | & & | & & | \\ 4 & - & 5 & - & 6 \end matrix Edges connect horizontal and vertical neighbors. A simple random walk moves at each step to a uniformly random neighbor. Starting at corner vertex 1 (degree 2), what is the expected number of steps to reach the opposite corner vertex 6 (degree 2)?概率中等数值题未尝试免费544Hitting Time on the Diamond GraphTake the complete graph K 4 on vertices \ A, B, C, D\ and remove edge A - D, leaving 5 edges (the "diamond" or "kite" graph). The resulting degrees are d(A) = d(D) = 2 and d(B) = d(C) = 3. A simple random walk moves at each step to a uniformly random neighbor. (a) Starting from vertex A, find the expected hitting time h(A D). (b) Starting from vertex D, find h(D A). (c) Compute the commute time C(A, D) and verify it using the effective-resistance formula.概率困难数值题未尝试面试订阅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未尝试面试订阅547Hitting Time on K₄ Minus One EdgeTake the complete graph K 4 on vertices \ 1,2,3,4\ and remove edge \ 1,4\ . The resulting graph has 5 edges, with d(1)=d(4)=2 and d(2)=d(3)=3. A simple random walk moves at each step to a uniformly random neighbor. Starting from vertex 2, what is the expected number of steps to reach vertex 4?概率简单数值题未尝试免费