Nit*_*arg 5 algorithm graph probability stochastic-process
一头牛正站在无限的篱笆前.另一边是草.奶牛想要去这草.沿着这个栅栏的某个地方是一个洞,母牛可以通过这个洞到达另一侧.从母牛到洞的距离d具有与其相关的概率分布f(d),即孔距离母牛k步的概率由f(k)给出.请注意,我们认为所有距离都是离散的,即它们总是根据母牛所采取的步骤来测量.母牛可以采取负整数步骤以及正整数步骤,即分别向左和向右步进k步.此外,我们知道Σ(k =-∞)^∞| k |⋅f(k)<∞.我们想要描述一种能够找到概率为1的洞的算法.
问题1算法能够以概率1找到孔的充分条件是什么？问题2描述这样的算法.
在我看来，正如所述，你的问题有一个简单的解决方案：
这次步行将以概率 1 访问所有相对整数。当然，您真正想要的是优化奶牛必须采取的平均步数，这称为搜索游戏问题。解是一维指数“螺旋”；您只需将上面的 1-2-3-4-5 算术数列替换为几何数列，每次乘以 2 即可。那是：
谷歌搜索“The Cow-Path Problem”，这是你对 N 路十字路口的概括（你只有两个，“左”和“右”）