第 7 / 79 页
非代码面试题
显示 20 / 1576 道匹配题目
答题状态：未尝试未正确已正确
ID题目领域难度题型进度权限
480通过补偿鞅求击中时间方差马尔可夫链在 \ 0,1,2,3\ 上，从 i（0<i<3）以概率 2/3 跳至 i+1，1/3 跳至 i-1。0 和 3 吸收。令 T = \inf\ n: X n \in \ 0,3\ \ 。 (a) 用鞅 M n = X n\wedge T - (p-q)(n\wedge T) 和 OST 求 E[T \mid X 0=2]。 (b) 用鞅 N n = M n 2 - 4pq(n\wedge T) 求 Var (T \mid X 0=2)。 (c) 用一步分析验证 E[T]。概率困难derivation未尝试面试订阅481带跳跃转移的击中时间马尔可夫链在 \ 0,1,2,3,4\ 上运动。状态 i（1 \le i \le 3）以概率 1/2 向左、1/2 向右。状态 4 以概率 1 跳到状态 2。状态 0 吸收。求 E[T 0 \mid X 0 = 2]。概率简单数值题未尝试免费483非对称环上的首次回归时间四状态环 \ 0,1,2,3\ ，从 i 顺时针跳到 (i+1)\bmod 4 的概率为 p i，逆时针为 1-p i，其中 p 0=3/4, p 1=1/2, p 2=1/4, p 3=1/2。求从状态 0 出发首次返回状态 0 的期望步数。概率中等数值题未尝试免费487双随机链上的平均回归时间四状态马尔可夫链的转移矩阵 P 是双随机的（每行每列之和均为 1）。不用知道 P 的具体元素，求从状态 0 出发首次返回状态 0 的期望步数。概率简单数值题未尝试免费489双目标集的分裂概率与期望击中时间五状态链 \ 0,1,2,3,4\ ，p(1,0)=1/2, p(1,2)=1/2, p(2,1)=1/3, p(2,3)=2/3, p(3,2)=1/4, p(3,4)=3/4。0,4 吸收。T=\inf\ n: X n \in \ 0,4\ \ 。(a) 求 P(X T=4|X 0=2)。(b) 求 E[T|X 0=2]。概率困难derivation未尝试免费490非对称链上的鞅构造求击中时间四状态链 \ 0,1,2,3\ ：p(1,0)=1/3, p(1,2)=2/3, p(2,1)=1/2, p(2,3)=1/2。0 吸收，3 反射（p(3,2)=1）。T=\inf\ n: X n=0\ 。(a) 构造鞅 M n=f(X n\wedge T )-(n\wedge T)c 求 E[T|X 0=2]。(b) 类似方法求 Var (T|X 0=2)。概率困难derivation未尝试免费494遍历链上访问所有状态的期望时间四状态链 \ 1,2,3,4\ ，转移矩阵 P 如题。从状态 1 出发，求首次访问所有四个状态的期望步数 E[T cover |X 0=1]。概率困难derivation未尝试免费498带内部反射壁的击中时间五状态链 \ 0,1,2,3,4\ ，0 吸收，4 反射（p(4,3)=1）。p(1,0)=p(1,2)=1/2，p(2,1)=1/3, p(2,3)=2/3，p(3,2)=p(3,4)=1/2。求 E[T 0|X 0=3]。概率中等derivation未尝试免费500调和函数法求分裂概率与击中时间六状态链 \ 0,...,5\ ，0,5 吸收。转移概率如题。(a) 求调和函数 f(0)=0,f(5)=1，计算 P(X T=5|X 0=2)。(b) 求 E[T|X 0=2]。概率困难derivation未尝试免费503非对称步长赌徒破产赌徒初始资金 \3。每轮以概率 2/3 赢 \1，以概率 1/3 输 \2。资金 \le 0 为破产，\ge 5 为胜利。求胜利概率。概率中等数值题未尝试免费504三人淘汰博弈三人 A,B,C 持有代币：A 有 2，B 有 1，C 有 1（共 4）。每轮随机选两人进行公平博弈（赢者从输者获一枚代币），代币为 0 则淘汰。求 A 最终赢得全部 4 枚代币的概率。概率中等数值题未尝试免费526完全图 K₅ 上的击中时间随机游走在完全图 K 5（5 个顶点，每对之间有边）上进行。每步等概率移动到 4 个邻居之一。从顶点 u 出发，求首次到达指定顶点 v u 的期望步数。概率简单数值题未尝试免费528三维超立方体上的击中时间随机游走在三维超立方体 Q 3 上进行：8 个顶点为长度 3 的二进制串，两顶点相邻当且仅当恰好一个坐标不同。每步等概率选一个坐标翻转。从 000 出发，求首次到达 111 的期望步数。概率中等数值题未尝试免费529完全二部图 K₃,₃ 上的击中时间考虑完全二部图 K 3,3 ，两部分为 A=\ a 1,a 2,a 3\ 和 B=\ b 1,b 2,b 3\ ，A 中每个顶点与 B 中每个顶点相连。随机游走每步以概率 1/3 移动到 3 个邻居之一。从 a 1 出发，求首次到达 b 1 的期望步数。概率中等数值题未尝试免费530超立方体 Q₃ 的等效电阻与通勤时间三维超立方体 Q 3（顶点为长度 3 二进制串，边连一位不同的串），每边电阻为 1。 (a) 利用 Q 3 的对称性，计算 000 与 111 之间的等效电阻 R eff (000,111)。 (b) 随机游走的通勤时间满足 C(u,v)=2m R eff (u,v)，其中 m 为边数。求 000 到 111 的通勤时间。概率困难derivation未尝试面试订阅532Petersen 图上的击中时间Petersen 图有 10 个顶点、15 条边，是 3-正则且距离传递的，直径为 2。每步等概率移向 3 个邻居之一。从顶点 u 出发，求首次到达与 u 不相邻的指定顶点 v 的期望步数。概率中等数值题未尝试免费535K₂,₃ 上的等效电阻与通勤时间完全二部图 K 2,3 ，部分 A=\ a 1,a 2\ （度 3）和 B=\ b 1,b 2,b 3\ （度 2），每边电阻为 1。 (a) 计算 R eff (a 1,a 2)。 (b) 用 C(u,v)=2m R eff (u,v) 求通勤时间。 (c) 用首步分析计算 h(a 1 a 2) 并验证。概率困难derivation未尝试面试订阅539完全图 K₄ 的覆盖时间随机游走在 K 4 上。(a) 求最大击中时间。(b) 用 Matthews 定理给出覆盖时间的界。(c) 精确计算覆盖时间。概率困难derivation未尝试面试订阅5404-环图上的等效电阻与通勤时间环图 C 4，顶点 \ 0,1,2,3\ ，每边电阻为 1。(a) 计算 R eff (0,2)。(b) 求通勤时间。(c) 求 h(0 2) 并验证。概率困难derivation未尝试面试订阅543梯子图（2×3 网格）上的击中时间2 3 网格图，顶点排列为两行三列。从角顶点 1（度 2）出发，求首次到达对角顶点 6（度 2）的期望步数。概率中等数值题未尝试免费