掷硬币2n次恰好n次正面概率

hbghlyj

(趣味书1089 and all that, page 92)
If you toss a coin $2n$ times, where $n$ is very large, then the probability of getting exactly $n$ heads and exactly $n$ tails is approximately $\frac1{\sqrt{n\pi}}$.
证:
相当于证明$\underset{n\to \infty }{\text{lim}}\frac{\sqrt{n} (2 n)!}{2^{2 n} (n!)^2}=\frac1{\sqrt\pi}$.
由Stirling公式,$n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}$,所以$(2n)! \approx \sqrt{2\pi·2n}\, \left(\frac{2n}{e}\right)^{2n}$,所以$\underset{n\to \infty }{\text{lim}}\frac{\sqrt{n} (2 n)!}{2^{2 n} (n!)^2}=\underset{n\to \infty }{\text{lim}}\frac{\sqrt{n}\sqrt{2\pi·2n}\, \left(\frac{2n}{e}\right)^{2n}}{2^{2 n} (\sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n})^2}=\frac1{\sqrt\pi}$.

kuing

回复 1# hbghlyj

少点守夜吧，别学我啊

Czhang271828

相似问题: 数轴原点处有 $\aleph_0$ 个小球, 即可以用自然数对小球一一对应地编号. 对任意小球而言, 其在每步移动中左移一格的概率恒为 $p$, 右移一格的概率恒为 $1-p$. 今移动所有小球, 使得第 $n$ 个小球恰好随机移动 $n$ 步. 当所有小球完成移动后, 坐标 $m$ 处小球数量的期望值为 $E_m$.

当 $p=\dfrac{1}{2}$ 时, 所有 $E_m$ 均为无穷大; 当 $p\neq\dfrac{1}{2}$时, 所有 $E_m$ 均为有限值.

isee

hbghlyj  快来，终于有人不水你的楼了～～～

Czhang271828

回复 1# hbghlyj


以及二项分布在 $n$ 足够大时会近似趋向正态分布: De Moivre-Laplace theorem 定律如是说. 一般用中心极限定理证明, 当然可以这么展开(源码来源不明)

\begin{aligned}{n \choose k}p^{k}q^{n-k}&\simeq {\frac {1}{\sqrt {2\pi npq}}}\exp \left\{\ln \left(\left({\frac {np}{k}}\right)^{k}\right)+\ln \left(\left({\frac {nq}{n-k}}\right)^{n-k}\right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-k\ln \left({\frac {k}{np}}\right)+(k-n)\ln \left({\frac {n-k}{nq}}\right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-k\ln \left({\frac {np+x{\sqrt {npq}}}{np}}\right)+(k-n)\ln \left({\frac {n-np-x{\sqrt {npq}}}{nq}}\right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-k\ln \left({1+x{\sqrt {\frac {q}{np}}}}\right)+(k-n)\ln \left({1-x{\sqrt {\frac {p}{nq}}}}\right)\right\}\qquad p+q=1\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-k\left({x{\sqrt {\frac {q}{np}}}}-{\frac {x^{2}q}{2np}}+\cdots \right)+(k-n)\left({-x{\sqrt {\frac {p}{nq}}}-{\frac {x^{2}p}{2nq}}}-\cdots \right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{\left(-np-x{\sqrt {npq}}\right)\left({x{\sqrt {\frac {q}{np}}}}-{\frac {x^{2}q}{2np}}+\cdots \right)+\left(np+x{\sqrt {npq}}-n\right)\left(-x{\sqrt {\frac {p}{nq}}}-{\frac {x^{2}p}{2nq}}-\cdots \right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{\left(-np-x{\sqrt {npq}}\right)\left(x{\sqrt {\frac {q}{np}}}-{\frac {x^{2}q}{2np}}+\cdots \right)-\left(nq-x{\sqrt {npq}}\right)\left(-x{\sqrt {\frac {p}{nq}}}-{\frac {x^{2}p}{2nq}}-\cdots \right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{\left(-x{\sqrt {npq}}+{\frac {1}{2}}x^{2}q-x^{2}q+\cdots \right)+\left(x{\sqrt {npq}}+{\frac {1}{2}}x^{2}p-x^{2}p-\cdots \right)\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-{\frac {1}{2}}x^{2}q-{\frac {1}{2}}x^{2}p-\cdots \right\}\\&={\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-{\frac {1}{2}}x^{2}(p+q)-\cdots \right\}\\&\simeq {\frac {1}{\sqrt {2\pi npq}}}\exp \left\{-{\frac {1}{2}}x^{2}\right\}\\&={\frac {1}{\sqrt {2\pi npq}}}e^{\frac {-(k-np)^{2}}{2npq}}\\\end{aligned}

Czhang271828

回复 3# Czhang271828

小球的问题想了一下, 为方便起见, 设第 $n$ 个小球移动 $2n$ 次.

考虑特殊情况, 原点处小球数量的期望值为 $\sum_{k=0}^\infty\binom{2k}{k}(pq)^k$​, 即加和所有小球回到原点的概率. 而
$$
\begin{align*}
\sum_{k=0}^\infty\binom{2k}{k}x^k=&\sum_{k=0}^\infty\dfrac{2^k\cdot1\cdot3\cdot5\cdots(2k-1)}{k!}x^k\\
=&\sum_{k=0}^\infty\dfrac{(-1/2)\cdot(-3/2)\cdots(-n+1/2)}{k!}\cdot(-4x)^k\\
=&\sum_{k=0}^\infty\binom{-1/2}{n}(-4x)^n\\
=&(1-4x)^{-1/2}
\end{align*}
$$
从而原点处小球数量期望为 $(1-4(p-p^2))^{-1/2}=\dfrac{1}{|1-2p|}$​. 记
$$
\theta:=\arcsin (2 \sqrt{x}) \in[0, \pi / 2].
$$
从而可以发现(后两个未验证)
$$
\left\{
\begin{align*}
&\sum_{n=0}^{\infty}\binom{2n}{n} x^{n}=\frac{1}{\sqrt{1-4 x}}=\frac{1}{\cos \theta} \\
&\sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} x^{n}=\frac{1-\sqrt{1-4 x}}{2 x}=\frac{1}{\cos ^{2}(\theta / 2)} \\
&\sum_{n=0}^{\infty}\binom{2n+k}{n} x^{n}=\frac{1}{\sin \theta \cdot \cos ^{2 k} \theta / 2} \\
&\sum_{n=0}^{\infty} \frac{k}{2 n+k}\binom{2n+k}{n} x^{n}=\frac{1}{\cos ^{2 k} \theta / 2}
\end{align*}
\right.
$$
坐标 $2m$ 处小球数量为 $\sum_{k=0}^\infty\binom{2k}{m+k}p^{k-m}q^{k+m}$, 从而:

1. 右侧: $P(X=2m)=((1-|p-q|)/2p)^{-2m}\cdot\dfrac{1}{|p-q|}$,

2. 左侧: $P(X=2m)\sim((1-|p-q|)/2q)^{-2m}\cdot \dfrac{1}{|p-q|}$.

hbghlyj

Czhang271828 发表于 2022-1-15 13:45
以及二项分布在$n$足够大时会近似趋向正态分布: De Moivre-Laplace theorem 如是说. 一般用中心极限定理证明, 当然可以这么展开(源码来源不明)

问一下:  Wikipedia说  Poisson distribution is an alternative approximation of the binomial distribution for large values of $n$.
那么, 二项分布趋于正态分布, 难道它也趋于Poisson分布吗

hbghlyj

hbghlyj 发表于 2022-11-2 21:48
问一下:  Wikipedia说  Poisson distribution is an alternative approximation of the binomial distrib ...

找到一个相关帖子: stats.stackexchange.com/a/34486
A $\mathrm{Poisson}(\lambda)$ pmf is the limiting pmf of a $\mathrm{Binomial}(n,p_n)$ with $p_n = \lambda / n$.

One rather lengthy development can be found on this blog.

But, we can prove this economically here as well. If $X_n \sim \mathrm{Binomial}(n,\lambda/n)$ then for fixed $k$
\begin{align*}
\mathbb P(X_n = k) &= \frac{n!}{k!(n-k)!} \left(\frac{\lambda}{n}\right)^k \left(1-\frac{\lambda}{n}\right)^{n-k} \\ &= \underbrace{\frac{n! n^{-k}}{(n-k)!}}_{\to 1} \frac{\lambda^k}{k!}\underbrace{(1-\lambda/n)^n}_{\to e^{-\lambda}} \cdot \underbrace{(1-\lambda/n)^{-k}}_{\to 1} \>.
\end{align*}The first and last terms are easily seen to converge to 1 as $n \to \infty$ (recalling that $k$ is fixed). So,
$$
\mathbb P(X_n = k) \to \frac{e^{-\lambda} \lambda^k}{k!} \,,
$$
as $n \to \infty$ since $(1-\lambda/n)^n \to e^{-\lambda}$.

In addition one has the normal approximation to the Binomial, i.e., $\mathrm{Binomial}(n,p)\approxeq^d \mathcal N(np, np(1-p))$. The approximation improves as $n \rightarrow \infty$ and $p$ stays away from 0 and 1. Obviously for the Poisson regime this is not the case (since there $p_n = \lambda / n \rightarrow 0$) but the larger $\lambda$ is the larger $n$ can be and still have a reasonable normal approximation.

hbghlyj

Czhang271828 发表于 2022-1-15 14:00
回复 3# Czhang271828

小球的问题想了一下, 为方便起见, 设第 $n$ 个小球移动 $2n$ 次.

Example 6.10 (One-dimensional random walk). Consider again the familiar example of a one-dimensional random walk. Let $I=\{0,1,2, \ldots\}$ and let
\[
\begin{aligned}
p_{i, i+1} &=p \text { for } i \geq 0, \\
p_{i, i-1} &=q=1-p \text { for } i \geq 1, \\
p_{00} &=q .
\end{aligned}
\]
If $p>q$, we found previously that the walk is transient, so no stationary distribution will exist.

If $p=q$, the walk is recurrent, but the mean return time is infinite, so again there is no stationary distribution.

If $p<q$, the walk is positive recurrent. For stationarity, we need $\pi_i=\pi_{i-1} p+\pi_{i+1} q$ for $i \geq 1$. This is (not coincidentally) reminiscent of the hitting probability equation we previously found for the model (except the values of $p$ and $q$ are reversed). It has general solution $\pi_i=A+B(p / q)^i$.
We need $\sum \pi_i=1$, which forces $A=0$ and $B=(1-p / q)$, giving
\[
\pi_i=\left(1-\frac{p}{q}\right)\left(\frac{p}{q}\right)^i .
\]
That is, the stationary distribution of the walk is geometric with parameter $1-\frac{p}{q}$.

hbghlyj

“掷硬币2n次恰好n次正面概率”就是$\mathbb Z^1$上的simple symmetric random walk 时刻$2n$回到起点0的概率.
5.9.1 d=1
We need to show that $\sum_{n=0}^{\infty} p_{00}^{(n)}=\infty$. We will use Stirling's formula, which tells us that $n ! \sim \sqrt{2 \pi} n^{n+1 / 2} e^{-n}$ as $n \rightarrow \infty$.
(The constant $\sqrt{2 \pi}$ will not be important.)
Suppose $X_0=0$. If $n$ is odd, then $\mathbb{P}_0\left(X_n=0\right)=0$, since the chain has period 2. For $X_{2 m}=0$ we need $m$ "ups" and $m$ "downs" in the first $2 m$ steps. Applying Stirling's formula to the binomial probability we obtain
$$
\begin{aligned}
p_{00}^{(2 m)} & =\left(\begin{array}{c}
2 m \\
m
\end{array}\right)\left(\frac{1}{2}\right)^{2 m} \\
& =\frac{(2 m) !}{m ! m !}\left(\frac{1}{2}\right)^{2 m} \\
& \sim \frac{1}{\sqrt{\pi}} \frac{1}{m^{1 / 2}}
\end{aligned}
$$
Since $\sum m^{-1 / 2}=\infty$, we have $\sum p_{00}^{(n)}=\infty$ and the chain is recurrent.
Exercise. Use Stirling's formula to show that if $p \neq q$, then the chain is transient. (We could also deduce this from the hitting probability analysis after (5.7).)

hbghlyj

hbghlyj 发表于 2023-3-29 12:24
Exercise. Use Stirling's formula to show that if $p \neq q$, then the chain is transient.

\begin{align*}p_{00}^{(2m)}&=\binom{2m}m(pq)^{2m}\\&\sim\frac1{\sqrt\pi}\frac1{\sqrt m}(\underbrace{4pq}_{<1})^m\end{align*}
Since $\sum_{m=1}^\infty\frac1{\sqrt m}x^m<\infty$ for any $x\in(-1,1),$ we have $\sum_{n=0}^\infty p_{00}^{(n)}=\sum_{m=0}^\infty p_{00}^{(2m)}<\infty$
By Theorem 5.8, the state $0$ is transient, since this Markov chain is irreducible, by Proposition 5.9, this Markov chain is transient.

hbghlyj

hbghlyj 发表于 2023-3-29 12:24
...(We could also deduce this from the hitting probability analysis after (5.7).)

参看这个讲义第51页的$p>q$情况:

Hence $h_i=\left(\frac{q}{p}\right)^i$. The chain has a positive probability of "escaping to infinity".

So the chain is transient.

hbghlyj

Section 11 Long-term behaviour of Markov chains

Example 11.3 The simple random walk is null recurrent for \(p = \frac12\) and transient otherwise. Either way, we have \(\mathbb P(X_n = i) \to 0\) for all states \(i\), and there is no equilibrium distribution.