第 15 / 23 页
非代码面试题
显示 20 / 443 道匹配题目
答题状态：未尝试未正确已正确
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未尝试面试订阅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未尝试面试订阅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未尝试面试订阅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未尝试面试订阅2942Expected Gap Between Two Random Points on an IntervalIf X and Y are independent Uniform (0,1) points, compute E[|X-Y|].概率中等derivation未尝试面试订阅2945Coordinatewise Comparability in the Unit SquareTwo independent random points (X 1,Y 1) and (X 2,Y 2) are drawn uniformly from the unit square. What is the probability that one point is coordinatewise less than the other, i.e. either X 1<X 2 and Y 1<Y 2, or X 1>X 2 and Y 1>Y 2?概率中等derivation未尝试面试订阅2948Closer to Vertical Sides Than Horizontal SidesA random point is drawn uniformly from the unit square. What is the probability that its distance to the nearer vertical side is smaller than its distance to the nearer horizontal side?概率中等derivation未尝试面试订阅2949Expected Distance to the Nearest Vertical SideA random point (X,Y) is uniform on the unit square. Compute the expected distance from the point to the nearer of the two vertical sides.概率简单derivation未尝试面试订阅