机器算法验证 - 达到固定总和之前的试验次数分布 - 吾爱随笔录

达到固定总和之前的试验次数分布

机器算法验证可能性分布

2022-04-06 17:47:06

我试图找出多次试验的分布，直到满足停止条件。特别是，假设我们正在观察一个均匀分布的随机变量的样本， $X \in \{a,a+1,...,b\}$ . 我们继续观察样本，直到这些数字的总和超过某个阈值 $Z$ 然后我们停止这个过程。也就是说，我们有集合 $\{x_1, ..., x_T | \sum_{i=1}^T x_i \geq Z\}$ . 我对随机变量的分布感兴趣 $T$ （试验次数）。

这类似于多项式分布或负多项式，但不一样。

假如说 $b << Z$ ，我们可以忽略最后的小舍入误差，假设 $\sum_{i=1}^T x_i = Z$ . 然后我们可以做一些基本的观察，比如 $\frac{Z}{a} \leq T \leq \frac{Z}{b}$ . 此外，从实验看来， $\mathbb{E}[T] = \frac{Z}{\mathbb{E}[X]}$ ，但不确定方差或分布的一般形状。

编辑：这个问题可以通过观察以下来部分回答，首先表示 $Y = \sum_{i=1}^N X_i$ ，我们当然有 $Y/N \overset{d}{\to} \mathbb{E}[X]$ . 自然，对于任何大 $N$ 我们期待 $Y \approx N\mathbb{E}[X]$ . 事实上，这也可以从Hoeffding 的不等式中看出。所以，对于一个足够大的 $Z$ , 如果我们约束 $Y=Z$ ，我们有 $Z \approx T\mathbb{E}[X]$ 或者 $T \approx \frac{Z}{\mathbb{E}[X]}$ 正如我所观察到的。

3个回答

让 $X_1,X_2,\dots$ 独立同居 $\mathrm{Uniform}\{a,a+1,\dots,b\}$ . 找到分布 $S_n=\mathrm{constant} + X_1+\dots+X_n$ 使用从本文档第 285 页开始的信息。使用击中时间定理找到的分布 $T=\inf\,\{n\geq 1:S_n=0\}$ .

我的第一步是尝试一下。在编写这样的程序时，我通常会更好地了解如何进行。这是我在 Stata（和 Mata）中的写法：

clear all
set obs 10000

mata
// for 10,000 obs role a 6-sided die 24 times
x = ceil(6*runiform(10000,24))

// compute a running sum for each observation
for(i=1; i <= 10000; i++) {
    x[i,.] = runningsum(x[i,.])
}

// number of roles till running sum passes 24
T = rowsum(x :< 24)

// add that variable to the dataset
idx =st_addvar("byte","T")
st_store(.,idx,T)
end

// look at T:
spikeplot T

在此处输入图像描述

tab T
          T |      Freq.     Percent        Cum.
------------+-----------------------------------
          3 |          6        0.06        0.06
          4 |        638        6.38        6.44
          5 |      2,248       22.48       28.92
          6 |      2,976       29.76       58.68
          7 |      2,313       23.13       81.81
          8 |      1,204       12.04       93.85
          9 |        451        4.51       98.36
         10 |        123        1.23       99.59
         11 |         33        0.33       99.92
         12 |          7        0.07       99.99
         13 |          1        0.01      100.00
------------+-----------------------------------
      Total |     10,000      100.00


sum T

    Variable |       Obs        Mean    Std. Dev.       Min        Max
-------------+--------------------------------------------------------
           T |     10000      6.3238    1.344966          3         13

所以T是一个整数，它有最小值 $\lfloor Z/b\rfloor-1$ 并且最多 $\lfloor Z/a \rfloor - 1$ . 我宁愿采取一些易于管理的价值观 $a$ , $b$ 和 $Z$ 并写下 T 的每个可能值的概率并寻找模式。

得出相同答案的另一种有趣方法是引入第二个随机变量 $Y$ 这是通过以下约束定义的

Y = Z - \sum_{i = 1}^{T} X_{i} .

$Y = Z - \sum_{i=1}^T X_i .$ 直观地说，对于任何固定数量的试验，

Y

$Y$ 将弥补需要达到的总和的剩余部分

Z

$Z$ . 我们可以清楚地看到

E [Y] = Z - T E [X]

$\mathbb{E}[Y] = Z - T\mathbb{E}[X]$ 将 LHS 设置为零（无余数），并求解

T

$T$ ，我们有

T = \frac{Z}{E [X]}

$T = \frac{Z}{\mathbb{E}[X]}$ 这只给出了预期的试验次数，直到没有剩余，这很接近，但可能不完全相同......

其它你可能感兴趣的问题

上一篇不同长度字符串的汉明距离下一篇路径分析还是完整的 SEM？