Let \(Y_n\) be the bitwise OR of \(n\) independent uniformly random \(b\)-bit integers. Starting from \(Y_0=0\), we define \(T\) as the first step at which every bit has become 1. For the actual problem \(b=32\), and we want the expected value \(\mathbb E[T]\).
1) Track one bit first.
Fix one coordinate, for example the least significant bit. In one random \(b\)-bit integer, that bit is 0 with probability \(1/2\) and 1 with probability \(1/2\).
After \(n\) independent draws, this bit is still 0 in the OR if and only if every one of those \(n\) draws had a 0 there. Therefore
$$\Pr(\text{fixed bit still 0 after }n\text{ steps})=\left(\frac12\right)^n=2^{-n}.$$
So the same bit has already become 1 with probability
$$1-2^{-n}.$$
2) Why the \(b\) bits can be multiplied.
For a single random draw, the bits are independent. Across different draws, the samples are also independent. Therefore the full \(n\times b\) table of bit values is a collection of independent Bernoulli variables.
Whether coordinate \(j\) is still 0 after \(n\) steps depends only on the \(n\) Bernoulli variables in column \(j\). Different columns use disjoint sets of independent variables, so these events are independent across coordinates.
Hence the probability that every one of the \(b\) bits has already turned into 1 is
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) Convert that into the distribution of the stopping time.
The event \(T \le n\) means exactly that after \(n\) draws, all bits are already 1. So
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b.$$
Therefore the tail probability is
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
This is the quantity summed by the program.
4) Tail-sum formula for the expectation.
For a nonnegative integer-valued random variable,
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
Substituting the tail above gives
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
This series converges very quickly because \(2^{-n}\) shrinks exponentially.
5) Optional exact closed form.
Expand with the binomial theorem:
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
Now sum over \(n\ge 0\) and use the geometric series
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}}.$$
So we also get the exact identity
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
The C++ code does not use this alternating finite sum; it uses the tail series directly, because it is simple and numerically stable for the small value \(b=32\).
6) Worked example for \(b=1\).
With one bit, the process stops when the first 1 appears. So this is just a geometric waiting time with success probability \(1/2\), and we know immediately that
$$\mathbb E[T]=2.$$
The formula above gives the same result:
$$\mathbb E[T]=\sum_{n=0}^{\infty}2^{-n}=\frac{1}{1-\frac12}=2.$$
7) Worked example for \(b=2\).
Now both bits must be collected. The probability that both bits are already 1 after \(n\) steps is
$$\left(1-2^{-n}\right)^2.$$
Hence
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
Expanding gives
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
so
$$\mathbb E[T]=2\sum_{n=0}^{\infty}2^{-n}-\sum_{n=0}^{\infty}4^{-n}=4-\frac{4}{3}=\frac{8}{3}.$$
This is exactly the second checkpoint used in the program.
1) Fix \(b\) (for the problem, \(b=32\)).
2) For \(n=0,1,2,\dots\), compute
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) Add these terms to an accumulator for \(\mathbb E[T]\).
4) Stop when the current term is below \(10^{-20}\). Because the tail is exponentially small, the neglected remainder is far below the requested decimal precision.
The number of iterations is tiny because the terms decay exponentially. In practice the runtime is effectively constant, and the memory usage is
$$O(1).$$
The C++ code checks
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
For the actual problem \(b=32\), the final value is
$$\mathbb E[T]\approx 6.3551758451.$$
Sei \(Y_n\) das bitweise OR von \(n\) unabhaengigen gleichverteilten \(b\)-Bit-Zahlen. Mit \(Y_0=0\) bezeichnen wir mit \(T\) den ersten Zeitpunkt, an dem alle Bits den Wert 1 haben. Im eigentlichen Problem ist \(b=32\), und gesucht ist \(\mathbb E[T]\).
1) Zuerst ein einzelnes Bit betrachten.
Ein festes Bit ist in einer zufaelligen \(b\)-Bit-Zahl mit Wahrscheinlichkeit \(1/2\) gleich 0. Nach \(n\) Ziehungen bleibt es im OR genau dann 0, wenn es in allen \(n\) Ziehungen 0 war. Also
$$\Pr(\text{festes Bit nach }n\text{ Schritten noch 0})=2^{-n}.$$
Folglich ist dieses Bit mit Wahrscheinlichkeit
$$1-2^{-n}$$
bereits zu 1 geworden.
2) Warum man ueber alle Bits multiplizieren darf.
Innerhalb einer Ziehung sind die Bits unabhaengig, und verschiedene Ziehungen sind ebenfalls unabhaengig. Damit besteht die gesamte \(n\times b\)-Tabelle der Bits aus unabhaengigen Bernoulli-Variablen.
Ob Spalte \(j\) nach \(n\) Schritten noch 0 ist, haengt nur von den Variablen dieser Spalte ab. Verschiedene Spalten verwenden disjunkte Mengen unabhaengiger Variablen, also sind diese Ereignisse unabhaengig.
Daher gilt
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) Verteilung der Trefferzeit.
\(T \le n\) bedeutet genau, dass nach \(n\) Ziehungen bereits alle Bits 1 sind. Also
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
und damit
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) Schwanzsummenformel fuer den Erwartungswert.
Fuer eine nichtnegative ganzzahlige Zufallsvariable gilt
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
Somit
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
Die Reihe konvergiert sehr schnell, weil \(2^{-n}\) exponentiell faellt.
5) Exakte endliche Formel.
Mit dem binomischen Lehrsatz:
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
Danach summiert man ueber \(n\) und benutzt die geometrische Reihe
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}},$$
also
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
Das Programm verwendet trotzdem die Schwanzreihe direkt, weil sie fuer \(b=32\) besonders einfach und numerisch stabil ist.
6) Beispiel \(b=1\).
Dann wartet man nur auf das erste Auftreten einer 1. Das ist eine geometrische Wartezeit mit Erfolgswahrscheinlichkeit \(1/2\), also
$$\mathbb E[T]=2.$$
7) Beispiel \(b=2\).
Hier ist
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
Ausmultiplizieren liefert
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
also
$$\mathbb E[T]=4-\frac{4}{3}=\frac{8}{3}.$$
Genau diesen Wert prueft der Code als zweiten Checkpoint.
1) Setze \(b=32\).
2) Berechne fuer \(n=0,1,2,\dots\)
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) Addiere alle Terme.
4) Stoppe bei \(\text{term}_n<10^{-20}\). Der Rest der Reihe liegt dann weit unter der geforderten Genauigkeit.
Wegen des exponentiellen Abfalls werden nur sehr wenige Terme benoetigt. Laufzeit praktisch konstant, Speicher
$$O(1).$$
Geprueft wird
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
Fuer \(b=32\) ergibt sich
$$\mathbb E[T]\approx 6.3551758451.$$
\(Y_n\), birbirinden bagimsiz ve es dagilimli \(b\)-bit rastgele tamsayilarin bitwise OR sonucunu gostersin. \(Y_0=0\) ile basliyoruz. \(T\), tum bitlerin ilk kez 1 oldugu adim olsun. Asil problemde \(b=32\) ve istenen sey \(\mathbb E[T]\) degeridir.
1) Once tek bir biti inceleyelim.
Belirli bir koordinat secelim. Tek bir rastgele \(b\)-bit sayida bu bitin 0 olma olasiligi \(1/2\)'dir. \(n\) bagimsiz cekilis sonunda OR sonucunda bu bit ancak tum cekilislerde 0 geldiyse 0 kalir. Bu yuzden
$$\Pr(\text{sabit bit }n\text{ adim sonra hala 0})=2^{-n}.$$
Dolayisiyla ayni bitin artik 1 olma olasiligi
$$1-2^{-n}$$
olur.
2) Neden tum bitler icin carpabiliyoruz?
Her cekiliste bitler birbirinden bagimsizdir; farkli cekilisler de bagimsizdir. Bu nedenle elimizdeki tum \(n\times b\) bit tablosu bagimsiz Bernoulli degiskenlerinden olusur.
\(j\). koordinatin \(n\) adim sonunda hala 0 olmasi, sadece o sutundaki \(n\) bit degiskenine baglidir. Farkli sutunlar farkli bagimsiz degiskenler kullandigi icin bu olaylar da bagimsizdir.
Bu nedenle tum bitlerin 1 olmus olma olasiligi
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) Buradan durma zamaninin dagilimina gecelim.
\(T \le n\) olayi, \(n\) cekilis sonunda tum bitlerin 1 olmus olmasi demektir. O halde
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
ve dolayisiyla
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) Kuyruk-toplam formulu.
Negatif olmayan tamsayi degerli bir rassal degisken icin
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n)$$
gecerlidir. Bu probleme uygularsak
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
Seri hizla yakinser; cunku \(2^{-n}\) ussel olarak kuculur.
5) Istersek kapali forma da gidebiliriz.
Binom acilimini kullanalim:
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
Sonra \(n\) uzerinden toplayip geometrik seri kullaniriz:
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}}.$$
Boylece
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}$$
elde edilir. Kod ise bu alternatif kapali formu degil, dogrudan kuyruk serisini toplar; \(b=32\) icin bu hem basit hem de sayisal olarak rahattir.
6) \(b=1\) ornegi.
Tek bit varsa, ilk 1'in gelmesini bekliyoruz. Bu da basari olasiligi \(1/2\) olan geometrik bekleme suresidir, yani
$$\mathbb E[T]=2.$$
7) \(b=2\) ornegi.
Bu kez iki bitin de dolmasi gerekir:
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
Icini acarsak
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
dolayisiyla
$$\mathbb E[T]=2\sum_{n=0}^{\infty}2^{-n}-\sum_{n=0}^{\infty}4^{-n}=4-\frac{4}{3}=\frac{8}{3}.$$
Kodun ikinci checkpoint'i tam olarak budur.
1) \(b=32\) al.
2) \(n=0,1,2,\dots\) icin
$$\text{term}_n=1-\left(1-2^{-n}\right)^b$$
hesapla.
3) Bu terimleri toplayarak beklentiyi olustur.
4) Guncel terim \(10^{-20}\)'den kucuk oldugunda dur. Geri kalan kuyruk artik hedeflenen ondalik hassasiyetin cok altindadir.
Terimler ussel olarak azaldigi icin gereken iterasyon sayisi cok kucuktur. Zaman pratikte sabit gibidir, ek bellek ise
$$O(1)$$
kadardir.
C++ kodu once su iki degeri dogrular:
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
Gercek problem olan \(b=32\) icin sonuc
$$\mathbb E[T]\approx 6.3551758451$$
olarak bulunur.
Sea \(Y_n\) el OR bit a bit de \(n\) enteros aleatorios independientes y uniformes de \(b\) bits. Empezamos con \(Y_0=0\). Definimos \(T\) como el primer instante en el que todos los bits valen 1. En el problema real \(b=32\), y buscamos \(\mathbb E[T]\).
1) Empecemos con un solo bit.
Fijemos una coordenada. En un entero aleatorio de \(b\) bits, ese bit vale 0 con probabilidad \(1/2\). Tras \(n\) extracciones independientes, en el OR seguira siendo 0 si y solo si fue 0 en las \(n\) extracciones. Por tanto,
$$\Pr(\text{bit fijo sigue en 0 tras }n\text{ pasos})=2^{-n}.$$
Luego ese bit ya vale 1 con probabilidad
$$1-2^{-n}.$$
2) Por que las \(b\) coordenadas son independientes.
Dentro de una extraccion, los bits son independientes, y ademas las distintas extracciones tambien lo son. Asi, la tabla completa de \(n\times b\) bits esta formada por variables de Bernoulli independientes.
Que la columna \(j\) siga en 0 tras \(n\) pasos depende solo de las variables de esa columna. Columnas distintas usan conjuntos disjuntos de variables independientes, asi que estos eventos son independientes.
En consecuencia,
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) Distribucion del tiempo de parada.
El evento \(T \le n\) significa exactamente que despues de \(n\) numeros ya tenemos todos los bits a 1. Entonces
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
y por tanto
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) Formula de suma de colas.
Para una variable aleatoria entera no negativa,
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
Aplicando la cola anterior obtenemos
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
5) Forma cerrada finita.
Con el binomio:
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
Ahora usamos
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}},$$
y queda
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
El programa no usa esta suma alternante; suma directamente la serie de colas porque para \(b=32\) es simple y estable.
6) Ejemplo con \(b=1\).
Con un solo bit esperamos al primer 1. Es una espera geometrica con probabilidad de exito \(1/2\), asi que
$$\mathbb E[T]=2.$$
7) Ejemplo con \(b=2\).
Ahora
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
Al expandir,
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
de modo que
$$\mathbb E[T]=4-\frac{4}{3}=\frac{8}{3}.$$
Ese es precisamente el segundo checkpoint del codigo.
1) Fijar \(b=32\).
2) Para \(n=0,1,2,\dots\), calcular
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) Acumular todos esos terminos.
4) Parar cuando \(\text{term}_n<10^{-20}\). La cola restante ya es insignificante frente a la precision pedida.
Como los terminos decrecen exponencialmente, hacen falta muy pocas iteraciones. El tiempo es practicamente constante y la memoria adicional es
$$O(1).$$
El codigo verifica
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
Para \(b=32\), el valor final es
$$\mathbb E[T]\approx 6.3551758451.$$
设 \(Y_n\) 是 \(n\) 个彼此独立、均匀分布的 \(b\)-bit 随机整数的按位 OR 结果，并令 \(Y_0=0\)。定义 \(T\) 为第一次所有 bit 都变成 1 的时刻。原题取 \(b=32\)，要求 \(\mathbb E[T]\)。
1) 先只看一个 bit。
固定某一位。一次随机抽样中，这一位为 0 的概率是 \(1/2\)。经过 \(n\) 次独立抽样后，这一位在 OR 里仍为 0，当且仅当这 \(n\) 次里它次次都是 0。因此
$$\Pr(\text{某固定 bit 在 }n\text{ 步后仍为 0})=2^{-n}.$$
所以该位已经变成 1 的概率是
$$1-2^{-n}.$$
2) 为什么可以对全部 \(b\) 位直接相乘。
在一次抽样内部，各 bit 彼此独立；不同抽样之间也独立。因此整个 \(n\times b\) 的 bit 表由独立 Bernoulli 变量组成。
第 \(j\) 列在 \(n\) 步后是否仍为 0，只取决于这一列里的 \(n\) 个变量。不同列使用的是互不重叠的独立变量集合，所以这些事件彼此独立。
于是所有 bit 都已经变成 1 的概率就是
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) 得到停时 \(T\) 的分布。
\(T \le n\) 恰好表示在第 \(n\) 步之后所有位都已经是 1。因此
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
从而
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) 用尾和公式求期望。
对非负整数值随机变量，有
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
代入上式可得
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
由于 \(2^{-n}\) 指数衰减，这个级数收敛非常快。
5) 还可以推出一个精确有限和。
由二项式展开：
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
再利用几何级数
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}},$$
可得
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
代码没有采用这个交错有限和，而是直接求尾和级数，因为在 \(b=32\) 时写法更简单，也足够稳定。
6) \(b=1\) 的例子。
只剩一个 bit 时，问题就是等第一次出现 1。成功概率为 \(1/2\) 的几何等待时间的期望是
$$\mathbb E[T]=2.$$
7) \(b=2\) 的例子。
这时
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
展开得到
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
所以
$$\mathbb E[T]=4-\frac{4}{3}=\frac{8}{3}.$$
这正是程序中的第二个 checkpoint。
1) 固定 \(b=32\)。
2) 对 \(n=0,1,2,\dots\) 计算
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) 将这些项累加到答案里。
4) 当当前项小于 \(10^{-20}\) 时停止。因为尾部已经远小于题目需要的小数精度。
项按指数速度衰减，所以循环次数很少。时间复杂度实际上接近常数，额外空间是
$$O(1).$$
C++ 代码先验证
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
对于原题的 \(b=32\)，最终结果为
$$\mathbb E[T]\approx 6.3551758451.$$
Пусть \(Y_n\) - результат побитового OR для \(n\) независимых равномерных случайных \(b\)-битных чисел, причём \(Y_0=0\). Обозначим через \(T\) первый момент, когда все биты впервые становятся равны 1. В задаче нужно найти \(\mathbb E[T]\) для \(b=32\).
1) Сначала рассматриваем один бит.
Зафиксируем одну координату. В одном случайном \(b\)-битном числе этот бит равен 0 с вероятностью \(1/2\). После \(n\) независимых шагов он останется 0 в OR тогда и только тогда, когда на каждом из этих шагов он был равен 0. Значит,
$$\Pr(\text{фиксированный бит остаётся 0 после }n\text{ шагов})=2^{-n}.$$
Следовательно, вероятность того, что этот бит уже стал 1, равна
$$1-2^{-n}.$$
2) Почему можно перемножить вероятности по всем битам.
Внутри одного случайного числа биты независимы, и разные числа тоже независимы. Поэтому вся таблица из \(n\times b\) битов состоит из независимых бернуллиевских переменных.
Событие "столбец \(j\) после \(n\) шагов всё ещё равен 0" зависит только от \(n\) переменных этого столбца. Для разных столбцов это непересекающиеся наборы независимых переменных, значит, такие события независимы.
Отсюда
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) Распределение времени остановки.
Событие \(T \le n\) означает, что после \(n\) шагов все биты уже стали 1. Поэтому
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
а значит
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) Формула суммы хвостов.
Для неотрицательной целочисленной случайной величины
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
Отсюда сразу получаем
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
5) Точная конечная формула.
По биному Ньютона
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
Далее используем геометрический ряд
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}},$$
и получаем
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
Однако код суммирует именно хвостовой ряд: для \(b=32\) это проще и достаточно устойчиво численно.
6) Пример при \(b=1\).
Если бит только один, мы ждём первого появления единицы. Это геометрическое ожидание с вероятностью успеха \(1/2\), поэтому
$$\mathbb E[T]=2.$$
7) Пример при \(b=2\).
Здесь
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
После раскрытия скобок
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
поэтому
$$\mathbb E[T]=4-\frac{4}{3}=\frac{8}{3}.$$
Это и есть второй checkpoint в программе.
1) Зафиксировать \(b=32\).
2) Для \(n=0,1,2,\dots\) вычислять
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) Суммировать эти члены.
4) Остановиться, когда \(\text{term}_n<10^{-20}\). Оставшийся хвост уже намного меньше требуемой точности.
Члены ряда убывают экспоненциально, поэтому итераций очень мало. Время практически постоянно, память
$$O(1).$$
Код проверяет
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
Для \(b=32\) получается
$$\mathbb E[T]\approx 6.3551758451.$$
ليكن \(Y_n\) هو الناتج من تطبيق OR بتّي على \(n\) عددًا عشوائيًا مستقلاً ومتساوي التوزيع من طول \(b\) بت، مع \(Y_0=0\). ونعرّف \(T\) بأنه أول خطوة تصبح فيها كل البتات مساوية لـ 1. في المسألة الأصلية نأخذ \(b=32\)، والمطلوب هو \(\mathbb E[T]\).
1) نبدأ ببت واحد فقط.
ثبّت موضعًا واحدًا. في عدد عشوائي واحد بطول \(b\) بت، تكون هذه البت مساوية للصفر باحتمال \(1/2\). وبعد \(n\) سحوبات مستقلة، تبقى هذه البت صفرًا في ناتج OR إذا وفقط إذا كانت صفرًا في جميع السحوبات \(n\). لذلك
$$\Pr(\text{بت ثابتة تبقى 0 بعد }n\text{ خطوة})=2^{-n}.$$
إذًا احتمال أن تكون هذه البت قد أصبحت 1 هو
$$1-2^{-n}.$$
2) لماذا يمكن ضرب الاحتمالات عبر جميع البتات.
داخل كل سحب تكون البتات مستقلة، كما أن السحوبات نفسها مستقلة عن بعضها. لذا فإن جدول البتات الكامل بحجم \(n\times b\) يتكوّن من متغيرات برنولية مستقلة.
حدث "العمود \(j\) ما زال صفرًا بعد \(n\) خطوات" يعتمد فقط على المتغيرات الموجودة في هذا العمود. والأعمدة المختلفة تستخدم مجموعات منفصلة من متغيرات مستقلة، لذلك تكون هذه الأحداث مستقلة.
ومن ثم
$$\Pr(Y_n=2^b-1)=\left(1-2^{-n}\right)^b.$$
3) توزيع زمن التوقف.
الحدث \(T \le n\) يعني بالضبط أنه بعد \(n\) أعداد أصبحت كل البتات مساوية لـ 1. إذًا
$$\Pr(T \le n)=\left(1-2^{-n}\right)^b,$$
وبالتالي
$$\Pr(T \gt n)=1-\left(1-2^{-n}\right)^b.$$
4) صيغة مجموع الذيول.
إذا كان المتغير العشوائي يأخذ قيماً صحيحة غير سالبة، فإن
$$\mathbb E[T]=\sum_{n=0}^{\infty}\Pr(T \gt n).$$
وبالتعويض نحصل على
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^b\right].$$
هذه السلسلة تتقارب بسرعة كبيرة لأن \(2^{-n}\) يتناقص أسيًا.
5) صيغة مغلقة مفيدة.
باستخدام مفكوك ثنائي الحدين:
$$1-\left(1-2^{-n}\right)^b=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}2^{-kn}.$$
ثم نجمع على \(n\) ونستخدم المتسلسلة الهندسية
$$\sum_{n=0}^{\infty}2^{-kn}=\frac{1}{1-2^{-k}},$$
فنحصل على
$$\mathbb E[T]=\sum_{k=1}^{b}(-1)^{k+1}\binom{b}{k}\frac{1}{1-2^{-k}}.$$
لكن كود ++C لا يستعمل هذه الصيغة المتناوبة؛ بل يجمع سلسلة الذيول مباشرة لأنها أبسط وأكثر ثباتًا عدديًا عندما \(b=32\).
6) مثال عند \(b=1\).
عندما يوجد بت واحد فقط فنحن ننتظر أول ظهور للقيمة 1. وهذا زمن انتظار هندسي باحتمال نجاح \(1/2\)، ولذلك
$$\mathbb E[T]=2.$$
7) مثال عند \(b=2\).
في هذه الحالة
$$\mathbb E[T]=\sum_{n=0}^{\infty}\left[1-\left(1-2^{-n}\right)^2\right].$$
وبعد التوسيع نحصل على
$$1-\left(1-2^{-n}\right)^2=2^{1-n}-2^{-2n},$$
ومن ثم
$$\mathbb E[T]=4-\frac{4}{3}=\frac{8}{3}.$$
وهذه هي نقطة الفحص الثانية الموجودة في البرنامج.
1) نثبّت \(b=32\).
2) لكل \(n=0,1,2,\dots\) نحسب
$$\text{term}_n=1-\left(1-2^{-n}\right)^b.$$
3) نجمع هذه الحدود للحصول على التوقع.
4) نتوقف عندما يصبح الحد الحالي أصغر من \(10^{-20}\)، لأن الذيل المتبقي يكون أصغر بكثير من الدقة المطلوبة.
بما أن الحدود تتناقص أسيًا، فإن عدد التكرارات صغير جدًا. الزمن عمليًا ثابت، والذاكرة الإضافية
$$O(1).$$
يفحص البرنامج القيمتين
$$\text{solve}(1)=2,\qquad \text{solve}(2)=\frac{8}{3}.$$
ولحالة \(b=32\) تكون النتيجة النهائية
$$\mathbb E[T]\approx 6.3551758451.$$