第 1 / 2 页
非代码面试题
显示 20 / 24 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
476Hitting Time on a Four-State ChainConsider a Markov chain on states \ 0, 1, 2, 3\ with transition probabilities: p(0,1) = 1, \quad 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 , \quad p(3,3) = 1. Starting from state 0, compute the expected number of steps to reach state 3 for the first time.概率简单数值题未尝试免费477Mean Return Time and the Stationary DistributionA Markov chain on \ 1, 2, 3\ has transition matrix P = \begin pmatrix 0 & \tfrac 1 2 & \tfrac 1 2 \\ \tfrac 1 4 & \tfrac 1 2 & \tfrac 1 4 \\ \tfrac 1 3 & \tfrac 1 3 & \tfrac 1 3 \end pmatrix . **(a)** Find the stationary distribution . **(b)** Using the relationship between the stationary distribution and mean return times, compute the expected number of steps to return to state 1 starting from state 1.概率简单数值题未尝试免费478Lazy Random Walk Hitting TimeA particle moves on \ 0, 1, 2, 3, 4, 5\ . At each step from state i (0 < i < 5), it stays at i with probability \tfrac 1 3 , moves to i-1 with probability \tfrac 1 3 , and moves to i+1 with probability \tfrac 1 3 . State 0 is reflecting: from 0 the particle moves to 1 with probability \tfrac 2 3 and stays at 0 with probability \tfrac 1 3 . State 5 is absorbing. Starting from state 0, derive the expected number of steps to reach state 5.概率中等derivation未尝试免费479State-Dependent Drift and First-Passage to a BoundaryA particle moves on \ 0, 1, 2, 3, 4\ . From state i (0 < i < 4), it jumps to i+1 with probability p i = i/4 and to i-1 with probability q i = 1 - i/4. States 0 and 4 are absorbing. Starting from state 2: **(a)** Find the probability of being absorbed at state 4. **(b)** Find the expected number of steps until absorption (hitting either boundary).概率中等derivation未尝试免费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.概率简单数值题未尝试免费482First Passage Through a Randomizing StateA Markov chain on \ 0, 1, 2\ has the transition matrix P = \begin pmatrix 1 & 0 & 0 \\ \tfrac 1 4 & 0 & \tfrac 3 4 \\ \tfrac 1 2 & \tfrac 1 2 & 0 \end pmatrix . State 0 is absorbing. Starting from state 1, let T = \inf\ n \ge 1 : X n = 0\ . **(a)** Compute E[T \mid X 0 = 1]. **(b)** Compute E[T \mid X 0 = 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.概率中等数值题未尝试免费484Hitting Time on a Product of Two-State ChainsLet (X n, Y n) be a Markov chain on \ 0,1\ 2 where X n and Y n evolve independently. At each step, X n flips (i.e., X n+1 = 1 - X n) with probability \tfrac 1 3 and stays with probability \tfrac 2 3 . Similarly, Y n flips with probability \tfrac 1 2 and stays with probability \tfrac 1 2 . Starting from (X 0, Y 0) = (1, 1), compute the expected number of steps to first reach the state (0, 0).概率中等derivation未尝试免费486Three-State First Passage with Deterministic ReturnA Markov chain on \ 0, 1, 2\ has transition probabilities: p(0,1) = 1, \quad p(1,0) = \tfrac 2 5 , \quad p(1,2) = \tfrac 3 5 , \quad p(2,2) = 1. Compute E[T 2 \mid X 0 = 0], where T 2 = \inf\ n \ge 0 : X n = 2\ .概率简单数值题未尝试免费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.概率简单数值题未尝试免费488First Passage with Parity-Dependent TransitionsConsider a Markov chain on \ 0, 1, 2, 3\ where states 0 and 3 are absorbing. The transition probabilities for transient states depend on the parity of the state: - From any **odd** state i: p(i, i-1) = \tfrac 3 4 , p(i, i+1) = \tfrac 1 4 . - From any **even** transient state i (i.e., i = 2): p(i, i-1) = \tfrac 1 4 , p(i, i+1) = \tfrac 3 4 . Compute E[T \mid X 0 = 1] where T = \inf\ n \ge 0 : X n \in \ 0, 3\ \ .概率中等derivation未尝试免费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未尝试免费491Hitting Time with State-Dependent Self-LoopsA Markov chain on \ 0, 1, 2, 3\ has transition probabilities: from state i (0 \le i \le 2), the chain stays at i with probability i 4 , moves to i+1 with probability 1 - i 4 . State 3 is absorbing. Compute E[T 3 \mid X 0 = 0].概率简单数值题未尝试免费492Hitting Time on a Six-State Chain with Paired CoordinatesA Markov chain lives on S = \ 0, 1, 2\ \ 0, 1\ . The state (0, y) for any y is absorbing. From state (i, j) with i \ge 1, the transitions are: - Move to (i-1, j) with probability \tfrac 1 3 . - Move to (i, 1-j) with probability \tfrac 1 3 (flip the second coordinate). - Move to (i+1, j) with probability \tfrac 1 3 , provided i+1 \le 2; if i = 2, this probability is redistributed equally to the other two moves. Let A = \ (0, 0), (0, 1)\ and T = \inf\ n \ge 0 : X n \in A\ . Compute E[T \mid X 0 = (1, 1)].概率中等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未尝试免费495Finite Hitting Time Between Communicating ComponentsConsider a Markov chain on \ 1, 2, 3, 4, 5\ with transition matrix P = \begin pmatrix \tfrac 1 2 & \tfrac 1 2 & 0 & 0 & 0 \\ \tfrac 1 3 & 0 & \tfrac 2 3 & 0 & 0 \\ 0 & \tfrac 1 4 & 0 & \tfrac 1 2 & \tfrac 1 4 \\ 0 & 0 & 0 & \tfrac 1 2 & \tfrac 1 2 \\ 0 & 0 & 0 & \tfrac 1 3 & \tfrac 2 3 \end pmatrix . Let B = \ 4, 5\ and T B = \inf\ n \ge 0 : X n \in B\ . **(a)** Show that E[T B \mid X 0 = i] < for all i \in \ 1, 2, 3\ . **(b)** Compute E[T B \mid X 0 = 1].概率困难derivation未尝试免费496First Passage in a Three-State Chain with Self-LoopA Markov chain on \ 0, 1, 2\ has transition matrix P = \begin pmatrix 1 & 0 & 0 \\ \tfrac 1 5 & \tfrac 2 5 & \tfrac 2 5 \\ 0 & \tfrac 3 4 & \tfrac 1 4 \end pmatrix . State 0 is absorbing. Compute E[T 0 \mid X 0 = 1], where T 0 = \inf\ n \ge 1 : X n = 0\ .概率简单数值题未尝试免费