第 2 / 41 页
非代码面试题
显示 20 / 811 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
271Finish 1-2-3 After Already Rolling 1,2A fair six-sided die is rolled repeatedly. You already know that the current observed suffix is exactly 1,2. Starting from here, what is the expected additional number of rolls until 1,2,3 first appears?概率简单数值题未尝试免费272Three Consecutive Ones on a DieA fair six-sided die is rolled repeatedly. Let T be the waiting time until three consecutive 1s first appear. Compute E[T].概率困难derivation未尝试免费273Return-and-Overlap Pattern 1-2-1 on a DieA fair six-sided die is rolled repeatedly. Find the expected waiting time until the consecutive pattern 1,2,1 first appears.概率困难derivation未尝试免费274Either 123 or 321 on a Fair DieA fair six-sided die is rolled repeatedly. Let T be the first time that either 1,2,3 or 3,2,1 appears as a consecutive length-3 block. Compute E[T].概率困难derivation未尝试免费275Waiting for HHTHA fair coin is flipped repeatedly. What is the expected number of flips until HHTH first appears?概率中等derivation未尝试免费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].概率简单数值题未尝试免费