第 4 / 9 页
非代码面试题
显示 20 / 164 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
517Two-Player Ruin with Unequal Bet SizesAlice and Bob play a sequence of fair-coin games. In each round, Alice wagers \1 and Bob wagers \2. If heads, Alice gains \1 from Bob (and Bob loses \1); if tails, Bob gains \2 from Alice (and Alice loses \2). Alice starts with \4 and Bob starts with \6. The game ends when either player is ruined (reaches \0). Note that the total wealth is not conserved — the net transfer is asymmetric. What is the probability that Alice is ruined?概率中等数值题未尝试免费518Gambler's Ruin with Killing (Absorption in the Interior)A particle moves on \ 0, 1, 2, 3, 4, 5\ . States 0 and 5 are absorbing barriers. At each step from a transient state k (1 \le k \le 4), the particle is "killed" (absorbed into a cemetery state \Delta) with probability c = 1/5. With the remaining probability 4/5, it moves +1 or -1 each with probability 1/2. Starting from state 2, find the probability that the particle reaches state 5 (without being killed or hitting 0).概率中等数值题未尝试免费519Ruin Probability via Probability Generating FunctionsConsider a random walk on \ 0, 1, 2, \ldots, N\ with absorbing barriers at 0 and N. At each step, the walker moves +1 with probability p and -1 with probability q = 1 - p. Let G k(s) = E[s \tau \mid X 0 = k] be the probability generating function of the absorption time \tau, for 0 < k < N. (a) Derive a recurrence relation for G k(s). (b) For N = 4, k = 2, and p = q = 1/2, find G 2(s) explicitly and use it to compute E[\tau] and Var (\tau).概率困难derivation未尝试面试订阅522Gambler's Ruin with Stochastic ResettingA gambler plays on \ 0, 1, 2, 3, 4, 5\ with absorbing barriers at 0 and 5. At each step from transient state k, with probability r = 1/4 the gambler is "reset" to state 3 (regardless of current position), and with probability 3/4 she takes a fair step (+1 or -1 each with probability 3/8). Starting from state 2, find the probability of reaching 5 before 0.概率中等数值题未尝试免费523Gambler's Ruin with Momentum (Correlated Steps)A gambler on \ 0, 1, \ldots, 8\ has absorbing barriers at 0 and 8. Her step probabilities depend on the previous outcome: after a win (+1), she wins again with probability 2/3 (momentum); after a loss (-1), she wins with probability 1/3. The first step is a win with probability 1/2. Starting from state 4, what is the probability of ruin (reaching 0)?概率困难数值题未尝试面试订阅524Absorption with a Long-Range JumpA particle moves on \ 0, 1, 2, 3, 4, 5\ with absorbing states 0 and 5. The transitions from transient states are: - From 1: to 0 w.p. 1/2, to 2 w.p. 1/2. - From 2: to 1 w.p. 1/3, to 3 w.p. 1/3, to 4 w.p. 1/3 (a long-range jump). - From 3: to 2 w.p. 1/2, to 4 w.p. 1/2. - From 4: to 3 w.p. 1/2, to 5 w.p. 1/2. Starting from state 2, what is the probability of being absorbed at 5?概率简单数值题未尝试免费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].概率中等数值题未尝试免费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?概率简单数值题未尝试免费527Hitting Time to the Antipodal Vertex on a CycleA simple random walk moves on the cycle graph C 8 (vertices 0, 1, \ldots, 7 arranged in a circle). At each step, the walker moves clockwise or counterclockwise with equal probability \tfrac 1 2 . Starting at vertex 0, what is the expected number of steps to reach the antipodal vertex 4 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未尝试面试订阅531Cover Time of the Path Graph P₃A random walk moves on the path graph P 3 with vertices \ 1, 2, 3\ and edges \ 1 - 2, 2 - 3\ . At each step, the walker moves to a uniformly random neighbor (so from vertex 2 it goes to 1 or 3 each with probability \tfrac 1 2 , and from vertex 1 or 3 it moves deterministically to 2). Starting at vertex 1, what is the expected number of steps to visit all three vertices (the cover time)?概率简单数值题未尝试免费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?概率中等数值题未尝试免费533Spectral Gap and Mixing Time of the Lazy Walk on a CycleConsider the lazy random walk on the cycle graph C n: at each step, the walker stays put with probability \tfrac 1 2 , and moves to each of the two neighbors with probability \tfrac 1 4 . The transition matrix has eigenvalues \lambda k = \tfrac 1 2 (1 + \cos(2 k / n)) for k = 0, 1, \ldots, n-1. (a) Find the spectral gap = 1 - \lambda 1 in terms of n. (b) Using the relation t mix \asymp 1 (up to logarithmic factors), determine the order of the mixing time for the lazy walk on C n as n .概率中等derivation未尝试免费534Hitting Time from Leaf to Root on a Complete Ternary TreeConsider the complete ternary tree of depth 2: a root vertex r with 3 children, each of which has 3 children (leaves), giving 13 vertices total. A simple random walk moves at each step to a uniformly random neighbor. Starting from a leaf vertex, what is the expected number of steps to reach the root r 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未尝试面试订阅536Expected Return Time on the Complete Graph K₄A simple random walk moves on the complete graph K 4 (four vertices, every pair connected). At each step, the walker moves to one of the 3 neighbors chosen uniformly at random. Starting at a vertex v, what is the expected number of steps to return to v for the first time?概率简单数值题未尝试免费537Hitting Time Between Leaves on the Star Graph S₅The star graph S 5 has a central hub vertex c connected to 4 leaf vertices \ \ell 1, \ell 2, \ell 3, \ell 4\ . A simple random walk at each step moves to a uniformly random neighbor: from the hub, it goes to each leaf with probability \tfrac 1 4 ; from any leaf, it goes to c with probability 1. Starting at leaf \ell 1, what is the expected number of steps to reach leaf \ell 2 for the first time?概率简单数值题未尝试免费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未尝试面试订阅