第 29 / 41 页
非代码面试题
显示 20 / 814 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
2896Complete Bipartite Graph K_{2,3}A simple random walk runs on the complete bipartite graph K 2,3 . What is the stationary probability of each vertex, and what total stationary mass sits on each side of the bipartition?概率中等derivation未尝试面试订阅2897Triangle with a Pendant NodeConsider a simple random walk on the graph with vertices A,B,C,D, where A,B,C form a triangle and D is connected only to A. Find the stationary distribution.概率中等derivation未尝试面试订阅2898Directed Cycle with Clockwise DriftOn the directed cycle with states \ 0,1,\dots,n-1\ , from each state the chain moves clockwise with probability p and counterclockwise with probability 1-p. Show that the stationary distribution is uniform.概率中等derivation未尝试面试订阅2899Reflecting Simple Walk on 0 to mConsider the chain on \ 0,1,\dots,m\ . From an interior state it moves left or right with probability 1/2 each. From 0 it stays put with probability 1/2 and moves to 1 with probability 1/2; from m it stays put with probability 1/2 and moves to m-1 with probability 1/2. Find the stationary distribution.概率中等derivation未尝试面试订阅2900Truncated Birth-Death ChainA chain runs on states \ 0,1,\dots,m\ . From interior state i it moves to i+1 with probability p, to i-1 with probability q, and stays put with probability 1-p-q. At 0 the left move is replaced by staying put; at m the right move is replaced by staying put. Assume p,q>0. Find the stationary distribution.概率中等derivation未尝试面试订阅2901A Tiny Queue with Capacity TwoA queue length process lives on \ 0,1,2\ . From state 0 it stays at 0 with probability 1-a and moves to 1 with probability a. From state 1 it moves to 2 with probability a, to 0 with probability b, and stays with probability 1-a-b. From state 2 it moves to 1 with probability b and stays at 2 with probability 1-b. Find the stationary distribution.概率中等derivation未尝试面试订阅2902Laziness Does Not Change StationaritySuppose is stationary for a Markov chain with transition matrix P. Fix \in(0,1) and define a lazy version \[ P'= I+(1- )P. \] Show that is also stationary for P'.概率简单derivation未尝试面试订阅2903Weighted Random Walk with ConductancesOn an undirected graph, each edge \ u,v\ has a positive conductance c uv =c vu . The chain moves from u to v with probability \[ P(u,v)= c uv \sum w c uw . \] Find the stationary distribution.概率中等derivation未尝试面试订阅2904Metropolis Chain for Target Weights 1,2,5On the line graph 1\leftrightarrow 2\leftrightarrow 3, propose moving to a neighboring state uniformly, and accept proposals using the Metropolis rule targeting weights proportional to (1,2,5). What is the stationary distribution?概率中等derivation未尝试面试订阅2905Ehrenfest Urn StationarityIn the Ehrenfest urn model with N balls, state i means exactly i balls are red. Each step, choose one ball uniformly at random and flip its color. Find the stationary distribution of the chain on \ 0,1,\dots,N\ .概率困难derivation未尝试面试订阅2906Uniform Teleportation on Top of a Doubly Stochastic BaseLet Q be a finite doubly stochastic matrix, and let U be the matrix whose every row is uniform over all states. For \[ P= U+(1- )Q,\qquad 0< <1, \] find the stationary distribution of P.概率中等derivation未尝试面试订阅2907Long-Run Occupancy on a 3x3 GridA simple random walk moves on the 3 3 grid graph. What is the stationary probability of the center, of a non-corner edge vertex, and of a corner vertex? What total stationary mass lies on the corners?概率中等derivation未尝试面试订阅2908How Often Is a Given Edge Crossed?A simple random walk on a connected undirected graph is started in stationarity. What is the long-run probability that the next step traverses a particular undirected edge \ u,v\ , regardless of direction?概率困难derivation未尝试面试订阅2909A Four-State Ring with Resets to ZeroConsider states \ 0,1,2,3\ . From state i, the chain moves to i+1 \pmod 4 with probability 1/2 and resets to 0 with probability 1/2. Find the stationary distribution.概率困难derivation未尝试面试订阅2910Simple Walk on a Three-State PathConsider the path graph 1\leftrightarrow 2\leftrightarrow 3. A simple random walk moves to a uniformly chosen neighbor. Find the stationary distribution.概率简单derivation未尝试面试订阅2911Custom Three-State Reversible ChainConsider a chain on states \ 1,2,3\ with transition matrix \[ P=\begin pmatrix 0.6 & 0.4 & 0\\ 0.2 & 0.5 & 0.3\\ 0 & 0.6 & 0.4 \end pmatrix . \] Find the stationary distribution.概率中等derivation未尝试面试订阅2913Half the Mass on Each Side of K_{m,n}A simple random walk runs on the complete bipartite graph K m,n . Show that although the two sides have different numbers of vertices, each side carries stationary mass 1/2.概率中等derivation未尝试面试订阅2914A Concrete Weighted TriangleA weighted random walk runs on vertices \ 1,2,3\ with symmetric conductances \[ c 12 =1,\qquad c 23 =2,\qquad c 13 =3. \] From a vertex, the chain picks the next vertex proportionally to the conductance of the connecting edge. Find the stationary distribution.概率中等derivation未尝试面试订阅2915Random Walk on the HypercubeConsider the chain on \ 0,1\ d that chooses one coordinate uniformly at random at each step and flips that bit. Find the stationary distribution.概率中等derivation未尝试面试订阅2916Mean Generation Size from One FounderA Galton-Watson process starts from one ancestor, and each individual has offspring mean m. What is E[Z n]?概率简单derivation未尝试面试订阅