从 1000 滚落到 1 的随机概率

Question

如果我在 1 和 1000 之间滚动一个随机数，然后使用这个随机数作为 1 和新数字的新范围，例如，如果它滚动 500，则新范围将是 1 到 500。什么是意思试图降到 1？

Answer 1

均值尝试将“数字”降为一？所以像 E[len((1,1000), …, (1,1))]?

可能是

from random import randint
from statistics import mean

i = 100

trials = list()
while len(trials) < i:
    value, attempts = 1000, 0
    while value != 1:
        value = randint(1, value)
        attempts += 1
    trials.append(attempts)
print(mean(trials))

与许多 Monte-Carlo 方法一样，可能需要 i 非常大。

Answer 2

我用这段代码找到了 ~8.5:

import random

def f():
    i = 0
    n = 0
    r = 1000
    while n != 1:
        n = random.randint(1, r)
        i += 1
        r = n
    return i

N = 10000
l = [f() for _ in range(N)]
print(sum(l) / len(l))

输出：

8.5206

Answer 3

我的答案是 8.48。逻辑如下：让 f(n) 表示下降到 1 的平均圈数。那么，f满足以下递归：

f(1) = 1
f(n) = 1/n + (n-1)/n * (1 + sum(f(i) for i in range(2, n+1)) / (n - 1))

对于一般 n，本回合有 1/n 机会获得 n 一个，本回合后有 (n-1)/n 机会获得一个。在后一种情况下，预期的圈数是 1 加上加权平均值。重新排列项给出以下公式：

from functools import lru_cache

@lru_cache(None)
def f(n):
  if n == 1:
    return 1
  return n / (n - 1) + 1 / (n - 1) * sum(f(i) for i in range(2, n))

您也可以使用 fractions 模块来准确计算答案，尽管结果分数相当大。

经过一些摆弄，似乎 Mathematica 可以根据 polygamma function 和

找到一个“封闭形式”的解决方案

f[n_] := 1 + EulerGamma + PolyGamma[0, n]

一种推导方法是 re-express 根据 y(n) = sum(f(k) for k in range(1, n)) 的递归。这也表明 f(n) 是渐进的 O(log(n))。

Answer 4

均值满足以下循环：如果 f(n) 表示从 n 到 1 的平均步数，则 f(1) = 0 并且对于 n>1，

f(n) = 1 + (f(1) + ... + f(n-1) + f(n))/n -->
f(n) = n/(n-1) + [f(1) + ... + f(n-1)]/(n-1).

我们可以用下面的脚本找到f(1000):

import numpy as np

means = [0]
for n in range(2,1001):
    means.append(n/(n-1)+np.average(means))
print(means[-1])

结果是8.484470860550345。我不确定 f(n) 是否有任何好的封闭形式。

Answer 5

我们弄明白了，我忘记在while循环中为我的randrange中的数字添加+1，我现在得到的值是8.48......用下面的代码，谢谢大家帮助回答了这个问题:).

import random
import math
random.seed(13)
import statistics

tries = []
for i in range(1000000):
  number = random.randrange(1, 1001)
  attempts = 1
  while number != 1:
    number = random.randrange(1, number+1)
    attempts += 1
  tries.append(attempts)

print(statistics.mean(tries))

Answer 6

前 100 位数字：

8.4844708605503449126565182043339001765216791697088036657736267499576993491652024440959934437411845081

精确分数：

60484649691685213005704263395601539057400162783408267244512899237619438652990632145483065609746993406733894830753023779634909455921438397706516749459866848443713860300689848494770432824401693665503983189312845928714471628150308917599333411703457439105339322525040288258228358123705825959020674166771023657949375130672985808604458424810309577532641272807764258202248144159846532965261433911670727905231051075533636840438428488803438997
/
7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000

得出与 Ben 相同的公式，但使用 fractions 模块得到准确的结果：

from fractions import Fraction

attempts = [None, 0]
for hi in range(2, 1001):
    attempts.append(Fraction(hi + sum(attempts[1:]), hi-1))

# Print the first 100 digits
a = attempts[-1]
print(a.numerator * 10**99 // a.denominator)

# Print the fraction
print(a)

Try it online!

从 1000 滚落到 1 的随机概率

Random proababilty of rolling down to 1 from 1000

python

statistics