第 7 / 79 页
非代码面试题
显示 20 / 1576 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
480Hitting-Time Variance via a Compensated MartingaleConsider a Markov chain on \ 0, 1, 2, 3\ with transitions: from state i (0 < i < 3), the chain moves to i+1 with probability p = \tfrac 2 3 and to i-1 with probability q = \tfrac 1 3 . State 0 and state 3 are absorbing. Let T = \inf\ n \ge 0 : X n \in \ 0, 3\ \ . **(a)** Define M n = X n \wedge T - (p - q)(n \wedge T). Verify that M n is a martingale and use the Optional Stopping Theorem to find E[T \mid X 0 = 2]. **(b)** Find a second martingale of the form N n = (X n \wedge T - (p-q)(n \wedge T)) 2 - 4pq(n \wedge T) and use it to compute Var (T \mid X 0 = 2). **(c)** Verify your answer for E[T] by first-step analysis.概率困难derivation未尝试面试订阅481Hitting Time with Skip TransitionsA Markov chain on \ 0, 1, 2, 3, 4\ has the following transition rules. From state i with 1 \le i \le 3: move to i-1 with probability \tfrac 1 2 , and move to i+1 with probability \tfrac 1 2 . From state 4: jump to state 2 with probability 1. State 0 is absorbing. Compute E[T 0 \mid X 0 = 2], the expected number of steps to reach state 0 starting from state 2.概率简单数值题未尝试免费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.概率中等数值题未尝试免费487Mean Return Time on a Doubly Stochastic ChainA Markov chain on \ 0, 1, 2, 3\ has a doubly stochastic transition matrix (every row and every column sums to 1). Without knowing the specific entries of P, determine the expected number of steps to return to state 0 starting from state 0. Justify your answer.概率简单数值题未尝试免费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未尝试免费490Martingale Construction for Hitting Time on a Non-Symmetric ChainA Markov chain on \ 0, 1, 2, 3\ has transition probabilities: p(1, 0) = \tfrac 1 3 , \quad p(1, 2) = \tfrac 2 3 , \quad p(2, 1) = \tfrac 1 2 , \quad p(2, 3) = \tfrac 1 2 . State 0 is absorbing and state 3 is reflecting: p(3, 2) = 1. Let T = \inf\ n \ge 0 : X n = 0\ . **(a)** Find a function f : \ 0,1,2,3\ R and a constant c > 0 such that M n = f(X n \wedge T ) - (n \wedge T) c is a martingale. Use this to compute E[T \mid X 0 = 2]. **(b)** Find a function g : \ 0,1,2,3\ R such that N n = g(X n \wedge T ) - (n \wedge T) d is a martingale for an appropriate constant d, and use the optional stopping theorem to compute E[T 2 \mid X 0 = 2]. Hence find Var (T \mid X 0 = 2).概率困难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未尝试免费498Hitting Time with Interior Reflecting BarrierA Markov chain on \ 0, 1, 2, 3, 4\ has the following transitions: - State 0 is absorbing. - From state 1: p(1, 0) = \tfrac 1 2 , p(1, 2) = \tfrac 1 2 . - From state 2: p(2, 1) = \tfrac 1 3 , p(2, 3) = \tfrac 2 3 . - From state 3: p(3, 2) = \tfrac 1 2 , p(3, 4) = \tfrac 1 2 . - From state 4: p(4, 3) = 1 (reflecting barrier). Compute E[T 0 \mid X 0 = 3].概率中等derivation未尝试免费500Harmonic Function Method for Splitting Probability and Hitting TimeA Markov chain on \ 0, 1, 2, 3, 4, 5\ has absorbing states 0 and 5. For interior states: p(1,0) = \tfrac 1 4 , \quad p(1,2) = \tfrac 3 4 , p(2,1) = \tfrac 1 3 , \quad p(2,3) = \tfrac 2 3 , p(3,2) = \tfrac 1 2 , \quad p(3,4) = \tfrac 1 2 , p(4,3) = \tfrac 2 3 , \quad p(4,5) = \tfrac 1 3 . Let T = \inf\ n \ge 0 : X n \in \ 0, 5\ \ . **(a)** A function f on \ 0,\ldots,5\ is *harmonic* on \ 1,2,3,4\ if f(i) = \sum j p(i,j) f(j) for i \in \ 1,2,3,4\ . Find the harmonic function with f(0) = 0, f(5) = 1, and use it to compute P(X T = 5 \mid X 0 = 2). **(b)** Compute E[T \mid X 0 = 2].概率困难derivation未尝试免费503Asymmetric Step-Size Gambler's RuinA gambler starts with \3. Each round she wins \1 with probability \tfrac 2 3 or loses \2 with probability \tfrac 1 3 . She stops when her fortune first hits \0 or below (ruin) or reaches \5 or above (victory). Note that if her fortune is \1 and she loses, she goes to -\1, which counts as ruin. What is the probability that she achieves victory?概率中等数值题未尝试免费504Three-Player Elimination GameThree players A, B, C hold tokens: A has 2, B has 1, C has 1 (total 4). Each round, two players are chosen uniformly at random (from the \binom 3 2 = 3 pairs) and they play a fair game: each of the two has probability \tfrac 1 2 of winning one token from the other. A player with 0 tokens is eliminated. Play continues until one player holds all 4 tokens. What is the probability that player A (who starts with 2 tokens) ends up with all 4?概率中等数值题未尝试免费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?概率简单数值题未尝试免费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?概率中等数值题未尝试免费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未尝试面试订阅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未尝试面试订阅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)?概率中等数值题未尝试免费