第 5 / 9 页
非代码面试题
显示 20 / 164 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
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?概率简单数值题未尝试免费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?概率简单数值题未尝试免费548Commute Time Between Endpoints of a PathConsider the path graph P n with vertices \ 0, 1, \ldots, n-1\ and n-1 edges (each of unit resistance), where the walk at interior vertices moves left or right with equal probability, and at the endpoints moves to the unique neighbor. (a) Compute the effective resistance R eff (0, n-1) between the two endpoints. (b) Using C(u,v) = 2m R eff (u,v), find the commute time between the two endpoints. (c) Verify for n = 4 by computing h(0 3) and h(3 0) directly.概率中等derivation未尝试免费550Expected Cover Time of the Cycle C₆A simple random walk moves on the cycle graph C 6 (vertices 0, 1, \ldots, 5). At each step, the walker moves clockwise or counterclockwise with equal probability. Starting at vertex 0, what is the expected number of steps to visit all 6 vertices (the expected cover time)?概率困难derivation未尝试面试订阅551Expected Occupied Labels 110 independent packets are hashed uniformly into 8 labels. What is the expected number of labels hit at least once?概率简单数值题未尝试免费556Expected Singleton Labels 18 independent arrivals are assigned uniformly to 10 labels. What is the expected number of labels that receive exactly one arrival?概率简单数值题未尝试免费561Tagged Label Survives Unseen 1A particular tag is one of 9 equally likely outcomes on each of 11 independent draws. What is the probability that this tag is never drawn?概率简单数值题未尝试免费566Time to Reach 3 Distinct Types 1Coupons arrive uniformly from 7 types. What is the expected number of draws needed to see 3 distinct types for the first time?概率简单数值题未尝试免费571All Labels Seen by Draw 5 1Draw 5 coupons independently and uniformly from 3 types. What is the probability that all 3 types have appeared at least once by time 5?概率简单数值题未尝试免费2891Two-State Regime SwitchingA market regime is either Calm or Volatile. From Calm, the chain moves to Volatile with probability ; from Volatile, it moves to Calm with probability . Find the stationary distribution.概率简单derivation未尝试面试订阅2892A Three-State Birth-Death Regime ChainConsider states Bull, Neutral, and Bear with transition matrix \[ P= \begin pmatrix 0.8 & 0.2 & 0\\ 0.3 & 0.4 & 0.3\\ 0 & 0.2 & 0.8 \end pmatrix . \] Find the stationary distribution.概率中等derivation未尝试面试订阅2893Uniform Stationarity for a Doubly Stochastic ChainSuppose a finite Markov chain has transition matrix P whose rows and columns both sum to 1. Show that the uniform distribution is stationary.概率简单derivation未尝试面试订阅2894Random Walk on an Undirected GraphA simple random walk moves on a connected undirected graph G=(V,E) by choosing a uniformly random neighbor at each step. Show that the stationary distribution is proportional to degree.概率简单derivation未尝试面试订阅2895Star Graph Long-Run OccupancyA simple random walk runs on a star graph with one hub and m leaves. What fraction of time is spent at the hub in stationarity, and what fraction at each leaf?概率简单derivation未尝试面试订阅