随机数求和, 直至加到 $1$ 停止, 结果期望为何?

Czhang271828

给定正整数 $n$, 记 $n$ 元集 $S_n=\{\frac{1}{n},\frac{2}{n},\ldots,\frac{n}{n}\}$. 考虑以下算法:
---------------------------------------
$\texttt{Sum}=0$

$\texttt{While Sum}<1$:

$\quad$ 独立且随机地选取 $ x\in S_n$

$\quad\,\,\,\texttt{Sum}=\texttt{Sum}+x$

$\texttt{Output Sum}$
---------------------------------------
求 $\texttt{Sum}$ 的期望值 $E_n$, 并证明 $\lim_{n\to +\infty} E_n=e/2$.

hbghlyj

Absorbing probabilities
By induction,
$$ P^{k}={\begin{bmatrix}Q^{k}&(1-Q^{k})NR\\\mathbf {0} &I_{r}\end{bmatrix}}. $$
The probability of eventually being absorbed in the absorbing state $j$ when starting from transient state $i$ is given by the $(i,j)$-entry of the matrix
$$ B:=NR $$
The number of columns of this matrix equals the number of absorbing states $r$.

An approximation of those probabilities can also be obtained directly from the $(i,j)$-entry of $ P^{k} $ for a large enough value of $k$, when $i$ is the index of a transient, and $j$ the index of an absorbing state. This is because
$$ \left(\lim _{k\to \infty }P^{k}\right)_{i,t+j}=B_{i,j} $$

For $n=3$
The states are $0,\frac13,\frac23,1,\frac43,\frac53$, where $0,\frac13,\frac23$ are transient states, $1,\frac43,\frac53$ are absorbing states.
$$P=\begin{pmatrix}Q&R\\\mathbf {0} &I_3\end{pmatrix}=\left(
\begin{array}{ccc|ccc}
0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 & 0 \\
0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & 0 \\
0 & 0 & 0 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\\hline
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}
\right)$$

1. Q = {
2.   {0, 1/3, 1/3},
3.   {0, 0, 1/3},
4.   {0, 0, 0}
5. };
6. R = {
7.   {1/3, 0, 0},
8.   {1/3, 1/3, 0},
9.   {1/3, 1/3, 1/3}
10. };
11. MatrixForm[Inverse[IdentityMatrix[3] - Q] . R]

Copy the Code

\begin{pmatrix}
\frac{16}{27} & \frac{7}{27} & \frac{4}{27} \\
\frac{4}{9} & \frac{4}{9} & \frac{1}{9} \\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
\end{pmatrix}读取第一行(因为start from 0)
结果为$1,\frac43,\frac53$的概率为$\frac{16}{27},\frac{7}{27},\frac{4}{27}$

相关帖子

hbghlyj

算出$E_{2000}=1.358801284661571$, 而$\frac e2=1.35914$

1. f:=Compile[{{n,_Integer}},
2. Q=Table[If[j>i,1/n,0],{i,n},{j,n}];
3. R=Table[If[j<=i,1/n,0],{i,n},{j,n}];
4. N[First[Inverse[IdentityMatrix[n]-Q].R]].Table[1+i/n,{i,0,n-1}]];
5. f[2000]

Copy the Code

Czhang271828

hbghlyj 发表于 2023-4-5 17:23
算出$E_{2000}=1.3588$, 而$\frac e2=1.35914$

这个极限提示地很明确了, 为何不关注 $n=1,2,3,4,5$ 时的具体值?

不过, 我暂不知道如何巧妙地求解该问题. 应该可以用以上描述随机过程的矩阵求出答案, 但可能需要一些处理矩阵的技巧.

hbghlyj

Czhang271828 发表于 2023-4-5 10:33
这个极限提示地很明确了, 为何不关注 $n=1,2,3,4,5$ 时的具体值?

哦原来是$E_n=\dfrac{(1 + \frac1n)^n}2$