Jindong Zhang
Spaces

Spaces

理解概率问题

Jindong Zhang's photo
Jindong Zhang
·Sep 8, 2022·

1 min read

这里讨论一下概率问题。概率生成器。

我们先用信息论的角度来思考这个问题。信息可以以 bit 表示,表示了要么是要么不是。 我们先假设有一个随机噪音,或者说随机数发生器 rand(1),它只会返回 0 或者 1。这就是1个bit的不确定性。 计算机的计算行为是有确定性的,要获得随机数,本质上就是从外界获取信息。我们计算机系统从外界接收一个bit,就获得一个 bit 的随机熵。也相当于我们投掷一个硬币,要么是正面,要么是反面。不可能存在比一个bit还小的信息,因此 rand(1)是最基本的、最原子的从外界获取随机性的办法。

我们说计算机调用rand(1)就获得了一个单位的不确定性。如果我们需要更多的不确定性。譬如,我们需要生成从 0 到 15 (16种可能性)的随机数,似乎可以通过重复调用rand(1)来达到目标,那具体怎么调用呢?

让我们把多个 rand(1) 组成阵列。rand(1) 具有1个随机槽位 [0],将其看成二进制,取值范围是 [0-2)。那么如果我们做 4 次 rand(1) 试验,我们的 bit 阵列,就有了四位。

[x][x][x][x]

[0][0][0][0]
[0][0][0][1]
[0][0][1][0]
[0][0][1][1]
.................
[1][1][1][1]

这足够表示从 [0-16)的全部整数,并且因为每一位出现 0和1 的概率是相当的,也就是说,在这个取值范围内,出现每一个数字的几率均相等。因此这个 rand(15)的每一种情况的出现概率均相等。是一个比较理想的随机数发生器。

由此可见, rand(1) 只要“错位”相加,就可以通过“移位”来制造多位的随机性,用 C 来表示是

int rand3(){
    return rand(1) << 1 + rand(1);
}

int rand7(){
    return rand(1) << 2  + rand(1) << 1 + rand(1);
}

int rand15(){
    return rand(1) << 3 + rand(1) << 2  + rand(1) << 1 + rand(1);
}

那么如果是rand(2) 呢?我们来看下他的数值上的可能性。

rand(2)高位低位出现概率
-0001/3
-0111/3
-1021/3

无论是高位还是低位,随机出1和0的概率,并不是1/2。出现零的概率是2/3。其实我们发现,rand(2) 不适合用二进制表示,因为如果出现3,我们会不得不进位。但如果用3进制表示,会是

rand(2)高位低位出现概率
-0001/3
-0111/3
-0221/3

那么按之前讨论二进制的规律,同样组成阵列。可以组成更高的随机性。

rand(2)*3 +rand(2)
rand(2)*9 + rand(2)*3 +rand(2)
rand(2)*27 +rand(2)*9 + rand(2)*3 +rand(2)

3 32 = 9 33 =27 3**4 = 81

 
Share this