抛硬币出现连续正面的概率

shangwen_ren

whoops... i just did something silly... fortunately the posted comment can be edited...

mathe

你这个是个不同的问题,很简单.连续出现t次正面的概率为$1/{2^t}$,所以出现一次的概率最大,为1/2

zhangjianquan

高手,我想问一个问题,如果此个题100次趋于无穷大,请求出多大次数的连续正面的概率为最大?

mathe

Now we could summarize how the formula of t-step Fibonacci sequence is got.
In 9#, we got the characteristic polynomial of
the Linear recurrence equation of the t-step Fibonacci sequence: ${x^{t+1}-2x^t+1}/{x-1}$.
According to link solutions of equation $x^m=2-x^{-n}$, we could use Rouché's Theorem to prove that there's
only one root of polynomial $x^{t+1}-2x^t+1$ whose norm is greater than 1 and t-1 roots whose norms are less than 1. And obviously, the root with greatest norm is a real root greater than 1.
Let's assuming that the real root greater than 1 is r, and besides from $1/{z_0}=1$ and $1/{z_1}=r$, there're another t-1 roots of polynomial $x^{t+1}-2x^t+1$. Let's assuming they're $1/{z_2},1/{z_3},...,1/{z_t}$. And it is obvious there're no multiple roots.
So that we could write the n'th item of the t-step Fibonacii sequence in the form: $u_1z_1^{-n}+u_2z_2^{-n}+...+u_{t}z_t^{-n}$, and we got that $u_s={z_s-1}/{2t-(t+1)z_s^{-1}}$
Now let's assuming $e_n = F_n^{(t)} - u_1 z_1^{-n} = u_2z_2^{-n}+...+u_{t}z_t^{-n}$, so we know that the characteristic polynomial of $e(n)$ is ${x^{t+1}-2x^t+1}/{(x-1)(x-r)}$.
In 30#, a probability modeling is used to prove that $|e(n)|<1/2$.
Let's assuming a man is randomly walking in an axis. He starts from a positive integer location in the axis and each time he random walks towards the positive direction by 1 or towards the negative direction by t with equivalent probability.
And he will stop when he reached a point whose coordinate is no more than 1. We will give a score $e(x)$ to him when he finally stops at coordinate x.
We know the probablity that he will finally stop is 1 when t is no less than 1. It is interesting that we could find that the expected score is $e_n$ when he starts from point whose coordinate is n.
In 29# it is proved that the absolute values of all those final scores ($e(-t+2)$ to $e(1)$) are less than $1/2$, so we proved that $|e_n|<1/2$ for all $n>=-t+2$
So we know now that $F_n^{(t)}$ could be represented by $"round"(u_1 z_1^{-n})$, or $F_n^{(t)}="round"({r-1}/{(t+1)r-2t}r^{n-1})$ for any $n>=-t+2$, where r is t-bonacci constant.

mathe

由此我们可以得到
$b(n)="round"({r^{-1}(r-1)}/{(t+1)r-2t}r^n)$
而抛硬币n次出现连续t次正面的概率为
$p(n)=1-{"round"({r-1}/{(t+1)r-2t}r^{n+1})}/{2^n}; r>1&&r^{t+1}-2r^t+1=0$

mathe

我们现在定义一个模型，有一个人在实数轴的整点上行走（开始坐标大于1），他每次分别以均等的概率随机后退t格或前进1格，知道到达坐标位置$[-t+2,1]$之间停止；如果他最后停留在坐标x,那么我们说他最终的得分为$e(x)$,那么请问如果他的起始坐标为x,那么他最终得分的期望值是多少呢？(容易证明他最终会停止下来的概率为1)
非常有意思，对于任何一个位置n,他最终得分的期望值为$e(n)$,由于每个最终得分都在$-1/2$和$1/2$之间，我们可以知道所有的$e(n)$也必然只能在$-1/2$和$1/2$之间。也就是这种方法可以证明上面的猜想。

这个是因为假设开始在位置n的得分为$f(n)$,我们知道对于任意$n>=2$有$f(n)={f(n+1)+f(n-t)}/2$或者说$f(n+1)=2f(n)-f(n-t)$,而且对于$n<=1$有边界条件$f(n)=e(n)$
根据$f(n)$的递推公式我们知道它对应的特征方程为$x^{t+1}-2x^t+1$,这个方程有一个根的绝对值大于1，还有一个根为1，其余t-1个根绝对值小于1，根据
http://bbs.emath.ac.cn/thread-354-1-1.html 中的结论，由于数列$f(n)$有界，那么绝对值大于1的根所对应的项的系数必然为0。也就是$f(n)$的通项公式可以由其余t个特征根决定，也就是前t项已经唯一决定了数列$f(n)$,而由于$e(n)$也满足同样递推式，必然得出$f(n)=e(n)$

mathe

现在我们定义序列$e(n)=b(n)-{r^{-1}(1-r)}/{2t-(t+1)r}r^n$也就是这个误差，其中对于所有的$n>=-t+2$全部定义。
而其中$b(n)$在$n<=0$时定义为$b(-t+2)=b(-t+3)=...=b(0)=0$(这样所有这些项都可以用同一个递推公式推导了)
显然$e(n)$也满足递推公式$e(n+t)=e(n+t-1)+e(n+t-2)+...+e(n)$,这个递推式对于所有的$n>=-t+2$都成立。
而且我们知道$e(0)=b(0)-{r^{-1}(1-r)}/{2t-(t+1)r}=-{r^{-1}(1-r)}/{2t-(t+1)r}$,所以$-1/2<e(0)<0$
同样，我们知道$-1/2<e(-1)<0,-1/2<e(-2)<0,...,-1/2<e(-t+2)<0$
而$e(1)=1-{r-1}/{(t+1)r-2t}$,所以$0<e(1)<1/2$

mathe

为了证明10#中公式
$b(n)=[{r^{-1}(r-1)}/{(t+1)r-2t}r^n]$,这里$[x]$代表最接近x的整数
我们先证明
${r^{-1}(r-1)}/{(t+1)r-2t}<1/2$
其中1<r<2而且$r^{t+1}-2r^t+1=0$ ,
首先我们容易得出$(t+1)r-2t>0$
这个是因为方程$h(x)=x^{t+1}-2x^t+1$中，显然$h({2t}/{t+1})<0,h(2)>0$,而且前面已经证明r是h(x)唯一一个绝对值大于1的解，所以${2t}/{t+1}<r<2$
所以我们需要证明$2(1-r^{-1})<(t+1)r-2t$也就是$(2-r)r<2/{t+1}$
由于我们知道$r^t(2-r)=1$,所以只要证明$r^{t-1}>{t+1}/2$也就是$r>root{t-1}{{t+1}/2}$（其中$t>=2$）
而其中右边容易得出在$t=2$时有最大值1.5,而$r>{2t}/{t+1}$,所以在t>=4时都已经有不等式成立。
而对于t=3时，我们知道$r_3=1.83...>1.5$,对于t=2,$r_2=1.618...>1.5$
所以我们证明了${r^{-1}(r-1)}/{(t+1)r-2t}<1/2$
而更加容易的，我们可以证明$(r-1)/{(t+1)r-2t}>1/2$ (这个等价于r<2),
而又有前面的不等式得到$(r-1)/{(t+1)r-2t}<r/2<1$

mathe

原帖由 mathe 于 2008-7-20 15:07 发表
10#中估计公式的误差发现有很漂亮的写法:
$e(n)=1/{2pii}oint_{|z|=1}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$
而类似的，我们也可以有
$b(n)=1/{2pii}oint_{|z|=2}{(z-1)z^{n+t-2}}/{z^{t+1)-2z^t+1}dz$

上面这个积分式我们换一种形式就是函数
${z-1}/{z^{t+1}-2z^t+1}$分别在区域$1<|z|<2$和$|z|>2$中罗兰展开式中$1/{z^n}$的系数,也就是我们将这个问题转化回为特征函数问题

无心人

7
小气
俺不稀罕呢