递归循环

Question

问题是 return 如果您从 10,000 开始，需要达到 20,000，并且您每次下注 1,000（在达到 0 之前达到 20,000 的概率）。您有 50-50 的输赢变化。

public static double roulette( double start, double end, double bet) {

    if (start >= end) return 1;
    if (start <= 0) return 0;

        return .5*roulette(start+2*bet,end,bet) + .5*roulette(start-bet,end,bet);
}

但它陷入了无限循环，因为一些递归调用将再次开始。就好像我打了一个开始 = 11,000 的电话，它会回到 10,000 并创建一个循环。我该如何防止这种情况？

Answer 1

这是一个建议的迭代解决方案（我将实施留给您）：

为了缩短它，让我们找到 roulette(10,20,1)（相当于您的 roulette(10000,20000,1000)）。让我们用 r(10).

表示 roulette(10,20,1)

现在，让我们计算 r(i)，其中 i 从 0 变为 20。

r(0) = 0 - 即如果您没钱就没有机会赢。
r(20) = 1 - 因为这意味着你赢了。

现在让我们计算其他 r(i)s:

r(1) = 0.5 * r(2) + 0.5 * r(0) = 0.5 * r(2) + 0 = 1/2 * r(2)
r(2) = 0.5 * r(3) + 0.5 * r(1) = 0.5 * r(3) + 0.5 * (0.5 * r(2))

这意味着

r(2) = 2/3 * r(3)

如果你继续这些计算，你会发现

r(3) = 3/4 * r(4)
r(4) = 4/5 * r(5)

...

r(18) = 18/19 * r(19)
r(19) = 19/20 * r(20) = 19/20 * 1 = 19/20

既然我们找到了r(19)，我们可以找到r(18):

r(18) = 18/19 * 19/20 = 18/20
r(17) = 17/18 * r(18) = 17/18 * 18/20 = 17/20

...

r(10) = 10/20 = 0.5

因此，如果您从 10000 开始，需要达到 20000，并且每次下注 1000，那么您有 50% 的机会达到 20000。

Answer 2

正如我在评论中提到的，概率是所有以 start >= end 或 left < 0 结束的概率的总和。

static double roulette(double start, double end, double bet, int left) {
    if (start >= end && left >= 0)
        return 1; // you definitely win.
    if (start < bet || left < 0)
        return 0; // you cannot win.
    double win = 0.5 * roulette(start + bet, end, bet, left - 1);
    double lose = 0.5 * roulette(start - bet, end, bet, left - 1);
    return win + lose; // you get a 0.5-0.5 to win or lose.
}

例如，假设 start 是 100，end 是 200，bet 是 50。如果总数为2，则只有一种方式：100->150->200，即0.25的概率。但如果总数为4，则可以有以下几种中奖方式：100->150->200、100->150->100->150->200、100->50->100->150-> 200。获胜的概率是 0.375.

Answer 3

关于 "probability of reaching 20,000 before you get to 0" 的特定查询，这可以作为 Random Walk over a one dimensional graph 解决，如解释的那样：

"If a and b are positive integers, then the expected number of steps until a one-dimensional simple random walk starting at 0 first hits b or −a is ab. The probability that this walk will hit b before −a is b/(a+b), which can be derived from the fact that simple random walk is a martingale."

给定，行走原点 = 10000，a=10000（距 0 的距离），b=10000（距 20000 的距离），& 步长 =1000：在 -a = 10000/(10000 + 10000) = 1/2 之前到达 b 的概率。

不确定这是否是您想要实现的全部内容，这将是一行 return 语句。

另一方面，给定的实现最终将探索整个 space 可能的解决方案（即达到 0 或 20000 的所有可能方式）。请参阅 RandomWalk.pdf 中的概率和帕斯卡三角形部分，了解此时间及其长运行时间的增长模式。您的实施已开始沿着帕斯卡三角形最右边的分支/对角线探索，并继续探索所有可能的分支。

相反，另一种方法是尝试实现一种方法，该方法计算第一次达到 20000（或 0）的概率（并非以所有可能的方式）然后中断。选择向右（赢）还是向左（输）分支 at random。在几个运行秒内对数字进行平均，这应该非常接近概率，如上计算的 ~1/2。

有趣的是，n 步后随机游走的预期距离 = sqrt(n)。这可用于估计正确实现的算法达到 20000 或 0 所需的迭代次数或递归调用次数（复杂性）。在这种情况下，距离 n = ((20000-10000)/1000) = 10，平均需要大约 n*n = 100 步/迭代。

递归循环

Recursive loops

java

recursion

probability

infinite-loop