第 1 / 2 页
非代码面试题
显示 20 / 23 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
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未尝试面试订阅531Cover Time of the Path Graph P₃A random walk moves on the path graph P 3 with vertices \ 1, 2, 3\ and edges \ 1 - 2, 2 - 3\ . At each step, the walker moves to a uniformly random neighbor (so from vertex 2 it goes to 1 or 3 each with probability \tfrac 1 2 , and from vertex 1 or 3 it moves deterministically to 2). Starting at vertex 1, what is the expected number of steps to visit all three vertices (the cover time)?概率简单数值题未尝试免费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未尝试免费534Hitting Time from Leaf to Root on a Complete Ternary TreeConsider the complete ternary tree of depth 2: a root vertex r with 3 children, each of which has 3 children (leaves), giving 13 vertices total. A simple random walk moves at each step to a uniformly random neighbor. Starting from a leaf vertex, what is the expected number of steps to reach the root r for the first time?概率中等数值题未尝试免费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?概率简单数值题未尝试免费537Hitting Time Between Leaves on the Star Graph S₅The star graph S 5 has a central hub vertex c connected to 4 leaf vertices \ \ell 1, \ell 2, \ell 3, \ell 4\ . A simple random walk at each step moves to a uniformly random neighbor: from the hub, it goes to each leaf with probability \tfrac 1 4 ; from any leaf, it goes to c with probability 1. Starting at leaf \ell 1, what is the expected number of steps to reach leaf \ell 2 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未尝试面试订阅546Hitting Time on the Path Graph P₅A simple random walk moves on the path graph P 5 with vertices \ 0,1,2,3,4\ and edges connecting consecutive vertices. At the interior vertices (1, 2, 3), the walker moves left or right with equal probability \tfrac 1 2 . At the endpoints (0 and 4), the walker moves to the unique neighbor with probability 1. Starting at vertex 0, what is the expected number of steps to reach vertex 4 for the first time?概率简单数值题未尝试免费