第 1 / 6 页
非代码面试题
显示 20 / 102 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
257Overlap Penalty for HTHTA fair coin is flipped repeatedly. Let T be the waiting time until HTHT first appears. Compute E[T].概率困难derivation未尝试免费263First Hit of ABA or BAAAn iid stream over \ A,B,C\ is uniform. Let T be the first time that either ABA or BAA appears. Compute E[T].概率中等derivation未尝试免费265Nonuniform Stream Waiting for AABAAn iid source emits A,B,C with probabilities rac 1 2 , rac 1 3 , rac 1 6 respectively. Find the expected waiting time until AABA first appears.概率中等derivation未尝试免费266Nonuniform Stream Waiting for ABBAAn iid source emits A,B,C with probabilities rac 1 2 , rac 1 3 , rac 1 6 respectively. What is the expected number of emitted symbols until ABBA first appears?概率中等derivation未尝试免费270Rolls Until 1-2-3 AppearsA fair six-sided die is rolled repeatedly. What is the expected number of rolls until the consecutive pattern 1,2,3 first appears?概率中等derivation未尝试免费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未尝试免费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未尝试面试订阅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未尝试免费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未尝试免费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?概率中等数值题未尝试免费505Gambler's Ruin with a Partially Reflecting BarrierConsider a Markov chain on \ 0, 1, 2, \ldots\ with absorbing state 0. From state k \ge 1, the chain moves to k+1 with probability p and to k-1 with probability q = 1 - p, where 0 < p < 1. However, there is a **reflecting barrier** at state N: from state N, the chain moves to N-1 with probability 1 (it is always pushed back). Starting from state k with 1 \le k \le N: **(a)** Find the probability r k of eventual absorption at 0. **(b)** For p = q = \tfrac 1 2 and N = 4, compute r 2 and the expected absorption time E[T \mid X 0 = 2].概率困难derivation未尝试免费506Martingale Approach to Biased Ruin ProbabilityA gambler starts with \4 and repeatedly bets \1 on a biased coin that lands heads with probability p = 0.55. She gains \1 on heads and loses \1 on tails. The game ends when her fortune reaches \0 or \10. Using the martingale (q/p) X n and the optional stopping theorem, find the exact probability that she reaches \10 before going broke.概率中等数值题未尝试免费515Ruin Probability Under a Martingale Betting StrategyA gambler uses a doubling strategy (Martingale system): she bets \1 on a fair coin, and after each loss she doubles her bet, resetting to \1 after any win. Her initial capital is \31 and the table maximum bet is \16 (so she can lose at most 4 consecutive times before hitting the cap, since 1 + 2 + 4 + 8 + 16 = 31). If the bet would exceed \16, she bets her remaining capital instead. Her target is \42 (a net gain of \11). What is the probability she reaches \42 before going broke?概率困难数值题未尝试面试订阅525Expected Ruin Time via Martingale MethodA biased random walk on \ 0, 1, \ldots, 10\ with absorbing barriers at 0 and 10 moves +1 with probability p = 0.6 and -1 with probability q = 0.4. Starting from state 3, use the martingale M n = X n - n (where = p - q) and the optional stopping theorem to find the expected absorption time E[\tau].概率中等数值题未尝试免费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未尝试面试订阅630Weighted Centered Sum 5Let X 1, X 2, ... be iid Bernoulli(3/5) random variables, and let F n = sigma(X 1,...,X n). Define M n = sum (k=1) n 3k*(X k-3/5). Is (M n) a martingale with respect to (F n)?概率困难derivation未尝试免费635Terminal-Variable Projection 5Let X 1, X 2, X 3, X 4 be iid symmetric ±1 variables with natural filtration F n. Define Y = (X 1+X 2+X 3) 2 and M n = E[Y | F n]. Is (M n) a martingale?概率困难derivation未尝试面试订阅642Martingale Diagnosis Counterexample 2M n = X (n+1)-p for iid Bernoulli(p) variables with natural filtration F n. Is (M n) a martingale?概率中等derivation未尝试免费