내가 올바르게 이해했다면 문제는 개 이상의 헤드 의 첫 번째 실행이 끝나는 시간에 대한 확률 분포를 찾는 것 입니다.엔

$n$

$n$

편집 행렬 곱셈을 사용하여 확률을 정확하고 빠르게 확인할 수 있으며, 평균을 로, 분산을 으로 분석하여 계산할 수도 있습니다. 여기서 이지만 분포 자체에 대한 간단한 닫힌 형식은 없을 것입니다. 특정 수의 코인 플립 위에서 분포는 본질적으로 기하학적 분포입니다. 더 큰 대해이 형식을 사용하는 것이 좋습니다.σ 2 = 2 n + 2 ( μ − n – 3 ) − μ 2 + 5 μ μ = μ − + 1 tμ−= 2n + 1− 1

${\mu }_{-}=2^{n+1}-1$

$\mu_-=2^{n+1}-1$σ2= 2n + 2( μ − n − 3 ) − μ2+ 5 μ

${\sigma }^2=2^{n+2}(\mu -n-3)-{\mu }^2+5\mu$

$\sigma^2=2^{n+2}\left(\mu-n-3\right) -\mu^2 + 5\mu$μ = μ−+ 1

$\mu ={\mu }_{-}+1$

$\mu=\mu_-+1$티

$t$

$t$

상태 공간에서의 확률 분포 시간에서의 진화는 상태에 대한 전이 행렬을 사용하여 모델링 될 수 있으며 , 여기서 은 연속 코인 플립의 수이다. 상태는 다음과 같습니다., N =k = n + 2

$k=n+2$

$k=n+2$n =

$n=$

$n=$

• 상태 , 헤드 없음H0
  $H_0$

  $H_0$

• 상태 , 헤드, i 1 ≤ i ≤ ( n – 1 )H나는
  $H_i$

  $H_i$나는

  $i$

  $i$1 ≤ i ≤ ( n – 1 )

  $1\le i\le (n-1)$

  $1\le i\le(n-1)$

• 상태 , 개 이상의 헤드 nH엔
  $H_n$

  $H_n$엔

  $n$

  $n$

• 상태 , 개 이상의 헤드와 꼬리 nH※
  $H_{\ast }$

  $H_*$엔

  $n$

  $n$

상태 도달하면 다른 상태로 돌아갈 수 없습니다.H※

$H_{\ast }$

$H_*$

상태로 들어갈 수있는 상태 전이 확률은 다음과 같습니다.

• 주 : 확률 에서 , , 즉 자신을 포함하되 명시되지1H0
  $H_0$

  $H_0$ Hii=0,…,n–1Hn12

  $\frac{1}{2}$

  $\frac12$H나는

  $H_i$

  $H_i$i = 0 , … , n – 1

  $i=0,\dots ,n-1$

  $i=0,\ldots,n-1$H엔

  $H_n$

  $H_n$

• 주 : 확률 에서1H나는
  $H_i$

  $H_i$ Hi–112

  $\frac{1}{2}$

  $\frac12$H난 − 1

  $H_{i-1}$

  $H_{i-1}$

• 상태 : 에서 나오는 확률 , 즉 헤드와 그 자체 가있는 상태에서1H엔
  $H_n$

  $H_n$ Hn–1,Hnn–112

  $\frac{1}{2}$

  $\frac12$Hn – 1, H엔

  $H_{n-1},H_n$

  $H_{n-1},H_n$n – 1

  $n-1$

  $n-1$

• 주 : 확률 에서 에서 확률 1 (자체)1H※
  $H_{\ast }$

  $H_*$ HNH*12

  $\frac{1}{2}$

  $\frac12$H엔

  $H_n$

  $H_n$H※

  $H_{\ast }$

  $H_*$

예를 들어, , 이것은 전이 행렬을 제공합니다n = 4

$n=4$

$n=4$

$$X = \left\{ \begin{array}{c|cccccc} & H_0 & H_1 & H_2 & H_3 & H_4 & H_* \\ \hline H_0 & \frac12 & \frac12& \frac12& \frac12 &0 & 0 \\ H_1 & \frac12 &0 & 0 &0 & 0 & 0 \\ H_2 & 0 & \frac12 &0 &0 & 0 & 0 \\ H_3 & 0 & 0 &\frac12 &0 & 0 & 0 \\ H_4 & 0 & 0 &0 &\frac12 & \frac12 & 0 \\ H_* & 0 & 0 & 0&0 &\frac12 & 1 \end{array}\right\}$$

의 경우 확률 의 초기 벡터 는 입니다. 일반적으로 초기 벡터는
, P , P = ( 1 , 0 , 0 , 0 , 0 , 0 ) , P가 나는 = { 1 난 = 0 0 I > 0n = 4

$n=4$

$n=4$피

$\mathbf{p}$

$\mathbf{p}$p =(1,0,0,0,0,0)

$\mathbf{p}=(1,0,0,0,0,0)$

$\mathbf{p}=(1,0,0,0,0,0)$

$$\mathbf{p}_i=\begin{cases}1&i=0\\0&i>0\end{cases}$$

벡터 는 주어진 시간 동안 공간 에서의 확률 분포입니다 . 필요한 cdf는 시간 의 cdf이며 , 시간 ( 의해 적어도 코인 플립이 끝날 가능성이있다 . 로 쓸 수 있는데 , 이는 연속적인 동전 뒤집기 실행의 마지막 단계 이후 상태 1 타임 스텝에 도달했음을 나타 냅니다. n t ( X t + 1 p ) k H ∗피

$\mathbf{p}$

$\mathbf{p}$엔

$n$

$n$티

$t$

$t$( Xt + 1p )케이

$(X^{t+1}\mathbf{p}{)}_k$

$(X^{t+1}\mathbf{p})_k$H※

$H_{\ast }$

$H_*$

시간에 필요한 pmf는 로 쓸 수 있습니다 . 그러나 수치 적으로 이것은 훨씬 더 큰 수 ( ) 에서 매우 작은 수를 제거하고 정밀도를 제한합니다. 따라서 계산에서 대신 하는 것이 좋습니다. 그런 다음 결과 행렬 를 쓰면 pmf는 입니다. 이것은 아래의 간단한 R 프로그램에서 구현되며 에서 작동합니다 . ≈ 1 X K , K = 0 X ‘ X ‘ = X | X k , k = 0 ( X ′ t + 1 p ) k n ≥ 2( Xt + 1p )케이− ( X티p )케이

$(X^{t+1}\mathbf{p}{)}_k-(X^t\mathbf{p}{)}_k$

$(X^{t+1}\mathbf{p})_k - (X^{t}\mathbf{p})_k$≈ 1

$\approx 1$

$\approx 1$엑스k , k= 0

$X_{k,k}=0$

$X_{k,k}=0$엑스‘

$X^{\prime }$

$X'$엑스‘= X| 엑스k , k= 0

$X^{\prime }=X|X_{k,k}=0$

$X'=X|X_{k,k}=0$( X′ t + 1p )케이

$(X^{\prime t+1}\mathbf{p}{)}_k$

$(X'^{t+1}\mathbf{p})_k$n ≥ 2

$n\ge 2$

$n\ge 2$

n=4
k=n+2
X=matrix(c(rep(1,n),0,0, # first row
           rep(c(1,rep(0,k)),n-2), # to half-way thru penultimate row
           1,rep(0,k),1,1,rep(0,k-1),1,0), # replace 0 by 2 for cdf
         byrow=T,nrow=k)/2
X

t=10000
pt=rep(0,t) # probability at time t
pv=c(1,rep(0,k-1)) # probability vector
for(i in 1:(t+1)) {
  #pvk=pv[k]; # if calculating via cdf
  pv = X %*% pv;
  #pt[i-1]=pv[k]-pvk # if calculating via cdf
  pt[i-1]=pv[k] # if calculating pmf
}

m=sum((1:t)*pt)
v=sum((1:t)^2*pt)-m^2
c(m, v)

par(mfrow=c(3,1))
plot(pt[1:100],type="l")
plot(pt[10:110],type="l")
plot(pt[1010:1110],type="l")

위 그림은 0에서 100 사이의 pmf를 보여줍니다. 아래 두 그림은 p10에서 10과 110 사이 그리고 1010과 1110 사이에서 pmf를 보여줍니다. 안정 기간 후의 기하학적 분포에 의해 근사됩니다.

의 고유 벡터 분해를 사용하여이 동작을 추가로 조사 할 수 있습니다 . 그렇게하면 충분히 큰 에 대한 . 여기서 은 방정식 . 이 근사값은 을 증가 시키면 더 좋아지고 을 계산하기위한 아래의 로그 오류 그림 (무지개 색, 빨간색)에 표시된 것처럼 값에 따라 약 30에서 50까지의 범위에서 에 대해 우수 대해 왼쪽t p t + 1 ≈ c ( n ) p t c ( n ) 2 n + 1 c n ( c − 1 ) + 1 = 0 n t n p 100 n = 2 t엑스

$X$

$X$티

$t$

$t$피t + 1≈ c ( n ) p티

$p_{t+1}\approx c(n)p_t$

$p_{t+1}\approx c(n)p_t$c ( n )

$c(n)$

$c(n)$2n + 1씨엔( c − 1 ) + 1 = 0

$2^{n+1}{c}^n(c-1)+1=0$

$2^{n+1}c^n(c-1)+1=0$엔

$n$

$n$티

$t$

$t$엔

$n$

$n$피100

$p_{100}$

$p_{100}$n = 2

$n=2$

$n=2$). 실제로 숫자로 인해 가 클 때 확률에 대해 기하 근사를 사용하는 것이 좋습니다 .티

$t$

$t$

나는 다음과 같이 계산 한 평균과 분산 때문에 분포에 사용할 수있는 닫힌 양식이 있다고 생각합니다.

$$\begin{array}{r|rr} n & \text{Mean} & \text{Variance} \\ \hline 2 &7& 24& \\ 3 &15& 144& \\ 4 &31& 736& \\ 5 &63& 3392& \\ 6 &127& 14720& \\ 7 &255& 61696& \\ 8 &511& 253440& \\ 9 &1023& 1029120& \\ 10&2047& 4151296& \\ \end{array}$$

(나는 t=100000이것을 얻기 위해 시간 범위를 넘어서야 했지만 프로그램은 여전히 약 10 초 이내에 모든 에 대해 실행되었습니다.) 특히 그 수단은 매우 명백한 패턴을 따릅니다. 차이가 적습니다. 나는 과거에 더 간단한 3 상태 전이 시스템을 해결했지만 지금까지는 간단한 분석 솔루션으로는 운이 없습니다. 어쩌면 전이 행렬과 관련하여 내가 모르는 유용한 이론이있을 수 있습니다.n = 2 , … , 10

$n=2,\dots ,10$

$n=2,\ldots,10$

편집 : 많은 잘못된 시작 후 나는 반복 공식을 생각해 냈습니다. 를 시간 에서 상태 에 있을 확률 이라고하자 . 하자 상태에있는 누적 확률 될 시간에, 즉 최종 상태, . NB H i t q ∗ , t H ∗ t피나는 , t

$p_{i,t}$

$p_{i,t}$H나는

$H_i$

$H_i$티

$t$

$t$큐∗ , t

$q_{\ast ,t}$

$q_{*,t}$H※

$H_{\ast }$

$H_*$티

$t$

$t$

• 주어진 에 대해 및 는 공간 대한 확률 분포 이며, 바로 아래에서 확률이 1에 추가된다는 사실을 사용합니다.p i , t , 0 ≤ i ≤ n q ∗ , t i티
  $t$

  $t$피나는 , t, 0 ≤ i ≤ n

  $p_{i,t},0\le i\le n$

  $p_{i,t}, 0\le i\le n$큐∗ , t

  $q_{\ast ,t}$

  $q_{*,t}$나는

  $i$

  $i$

• t피∗ , t
  $p_{\ast ,t}$

  $p_{*,t}$ 는 시간 대한 확률 분포를 형성합니다 . 나중에이 방법을 사용하여 평균과 분산을 도출합니다.티

  $t$

  $t$

시간 에서 제 1 상태 , 즉 헤드가 없을 확률은 시간 ( 에서 복귀 할 수있는 상태 (전 확률 이론을 사용하여) 로부터 전이 확률에 의해 주어진다 .

하지만 상태 에서 데 단계 가 걸리므로 및

다시 한번 총 확률 이론에 의해 상태t p 0 , t + 1t + 1

$t+1$

$t+1$티

$t$

$t$H0Hn−1n−1pn−1,t+n−1=1

$$\begin{align} p_{0,t+1} &= \frac12p_{0,t} + \frac12p_{1,t} + \ldots \frac12p_{n-1,t}\\ &= \frac12\sum_{i=0}^{n-1}p_{i,t}\\ &= \frac12\left( 1-p_{n,t}-q_{*,t} \right) \end{align}$$ H0

$H_0$

$H_0$Hn – 1

$H_{n-1}$

$H_{n-1}$n – 1

$n-1$

$n-1$pn−1,t+n=1피n − 1 , t + n − 1= 12n – 1피0 , t

$p_{n-1,t+n-1}=\frac{1}{2^{n-1}}{p}_{0,t}$

$p_{n-1,t+n-1} = \frac1{2^{n-1}}p_{0,t}$Hnt+1 p n , t + 1

$$p_{n-1,t+n} = \frac1{2^n}\left( 1-p_{n,t}-q_{*,t} \right)$$ H엔

$H_n$

$H_n$시간 은

및 사실 사용 ,

따라서 ,
t + 1

$t+1$

$t+1$

$$\begin{align} p_{n,t+1} &= \frac12p_{n,t} + \frac12p_{n-1,t}\\ &= \frac12p_{n,t} + \frac1{2^{n+1}}\left( 1-p_{n,t-n}-q_{*,t-n} \right)\;\;\;(\dagger)\\ \end{align}$$ 큐∗ , t + 1− q∗ , t= 12피n , t⟹피n , t= 2 Q∗ , t + 1– 2 Q∗ , t

$q_{\ast ,t+1}-q_{\ast ,t}=\frac{1}{2}{p}_{n,t}⟹p_{n,t}=2q_{\ast ,t+1}-2q_{\ast ,t}$

$q_{*,t+1}-q_{*,t}=\frac12p_{n,t} \implies p_{n,t} = 2q_{*,t+1}-2q_{*,t}$

$$\begin{align} 2q_{*,t+2} - 2q_{*,t+1} &= q_{*,t+1}-q_{*,t}+\frac1{2^{n+1}}\left( 1-2q_{*,t-n+1}+q_{*,t-n} \right) \end{align}$$ t → t + n

$t\to t+n$

$t\to t+n$

$$2q_{*,t+n+2} - 3q_{*,t+n+1} +q_{*,t+n} + \frac1{2^n}q_{*,t+1} - \frac1{2^{n+1}}q_{*,t} - \frac1{2^{n+1}} = 0$$

이 되풀이 수식은 경우 및 합니다. 예를 들어, 에 대해이 공식의 도표 는 기계 순서 정확도 를 제공합니다.n = 4

$엔=4$

$n=4$n = 6

$엔=6$

$n=6$n = 6

$엔=6$

$n=6$t=1:994;v=2*q[t+8]-3*q[t+7]+q[t+6]+q[t+1]/2**6-q[t]/2**7-1/2**7

편집 이 되풀이 관계에서 닫힌 양식을 찾기 위해 어디로 가야하는지 알 수 없습니다. 그러나 입니다 평균에 대한 폐쇄 양식을 얻을 수.

부터 출발 , 그 주목 ,

에서 합계 촬영 에 , 평균의 수식을 적용 와 그 주목 확률 분포는
( † )

$(†)$

$(\dagger)$피∗ , t + 1= 12피n , t

${피}_{※,티+1}=\frac{1}{2}{피}_{엔,티}$

$p_{*,t+1}=\frac12p_{n,t}$

$$\begin{align} p_{n,t+1} &= \frac12p_{n,t} + \frac1{2^{n+1}}\left( 1-p_{n,t-n}-q_{*,t-n} \right)\;\;\;(\dagger)\\ 2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right)+2p_{*,t+1} &= 1-q_{*,t} \end{align}$$ t = 0

$티=0$

$t=0$∞

$\mathrm{\infty }$

$\infty$이자형[ X] = ∑∞x = 0( 1 – F( x ) )

$\mathrm{이자형}[\mathrm{엑스}]=\sum _{\mathrm{엑스}=0}^{\mathrm{\infty }}(1-\mathrm{에프}(\mathrm{엑스}))$

$E[X] = \sum_{x=0}^\infty (1-F(x))$피∗ , t

${피}_{※,티}$

$p_{*,t}$

$$\begin{align} 2^{n+1}\sum_{t=0}^\infty \left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2\sum_{t=0}^\infty p_{*,t+1} &= \sum_{t=0}^\infty(1-q_{*,t}) \\ 2^{n+1} \left(2\left(1-\frac1{2^{n+1}}\right)-\;1\;\right) + 2 &= \mu \\ 2^{n+1} &= \mu \end{align}$$
이것은 상태 에 도달하기위한 평균입니다 . 머리 끝의 평균은 이것보다 하나 적습니다.H※

$H_{※}$

$H_*$

편집 화학식 이용한 유사한 방법이 질문 에서 분산 이 산출됩니다.
이자형[ X2] = ∑∞x = 0( 2 x + 1 ) ( 1 − F( x ) )

$\mathrm{이자형}[{\mathrm{엑스}}^2]=\sum _{\mathrm{엑스}=0}^{\mathrm{\infty }}(2\mathrm{엑스}+1)(1-\mathrm{에프}(\mathrm{엑스}))$

$E[X^2] = \sum_{x=0}^\infty (2x+1)(1-F(x))\;$

$$\begin{align} \sum_{t=0}^\infty(2t+1)\left (2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2 p_{*,t+1}\right) &= \sum_{t=0}^\infty(2t+1)(1-q_{*,t}) \\ 2\sum_{t=0}^\infty t\left (2^{n+1}\left(2p_{*,t+n+2}-p_{*,t+n+1}\right) + 2 p_{*,t+1}\right) + \mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(2\left(\mu-(n+2)+\frac1{2^{n+1}}\right)-(\mu-(n+1))\right) + 4(\mu-1) &\\+ \mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(2(\mu-(n+2))-(\mu-(n+1))\right) + 5\mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(\mu-n-3\right) + 5\mu &= \sigma^2 + \mu^2 \\ 2^{n+2}\left(\mu-n-3\right) -\mu^2 + 5\mu &= \sigma^2 \end{align}$$

평균과 분산은 프로그래밍 방식으로 쉽게 생성 할 수 있습니다. 예를 들어 위 표에서 사용 된 평균과 분산을 확인하십시오.

n=2:10
m=c(0,2**(n+1))
v=2**(n+2)*(m[n]-n-3) + 5*m[n] - m[n]^2

마지막으로, 당신이 쓸 때 당신이 무엇을 원했는지 잘 모르겠습니다

꼬리가 치고 머리의 행진이 끊어지면 카운트는 다음 플립에서 다시 시작됩니다.

당신은에 대한 확률 분포 무엇을 의미하는 경우에는 다음 의 첫 번째 실행되는 시간 이상의 헤드의 끝이 다음 중요한 점은이에 포함 @Glen_b에 의해 코멘트 프로세스가 다시 시작이다, 하나 개 꼬리 후 CF ( 이상의 헤드를 즉시 얻을 수있는 초기 문제 ).엔

$엔$

$n$엔

$엔$

$n$

예를 들어 첫 번째 이벤트까지의 평균 시간은 이지만 이벤트 사이의 평균 시간은 항상 (분산은 동일 함). 전이 매트릭스를 사용하여 시스템이 “정착 된”상태의 장기적인 확률을 조사 할 수도 있습니다. 적절한 전이 행렬을 얻으려면 시스템 이 상태 에서 상태 즉시 돌아 오도록 및 을 설정하십시오 . 그런 다음 이 새로운 행렬 의 스케일 된 첫 번째 고유 벡터는 고정 확률을 제공합니다 . 함께 이 정적 확률은μ – 1

$\mu -1$

$\mu-1$μ + 1

$\mu +1$

$\mu+1$엑스k , k ,= 0

${\mathrm{엑스}}_{\mathrm{케이},\mathrm{케이},}=0$

$X_{k,k,}=0$엑스1 , k= 1

${\mathrm{엑스}}_{1,\mathrm{케이}}=1$

$X_{1,k}=1$H0

$H_0$

$H_0$H※

$H_{※}$

$H_*$n = 4

$엔=4$

$n=4$

$$\begin{array}{c|cccccc} & \text{probability} \\ \hline H_0 & 0.48484848 \\ H_1 & 0.24242424 \\ H_2 & 0.12121212 \\ H_3 & 0.06060606 \\ H_4 & 0.06060606 \\ H_* & 0.03030303 \end{array}$$
상태 간의 예상 시간은 확률의 역수로 제공됩니다. 따라서 방문 사이의 예상 시간 입니다.H※= 1 / 0.03030303 = 33 = μ + 1

$H_{※}=1/0.03030303=33=\mu +1$

$H_* = 1/0.03030303 = 33 = \mu + 1$

부록 : n= 연속 헤드 수에 대한 정확한 확률을 생성하는 데 사용되는 Python 프로그램 N.

import itertools, pylab

def countinlist(n, N):
    count = [0] * N
    sub = 'h'*n+'t'
    for string in itertools.imap(''.join, itertools.product('ht', repeat=N+1)):
        f = string.find(sub)
        if (f>=0):
            f = f + n -1 # don't count t, and index in count from zero 
            count[f] = count[f] +1
            # uncomment the following line to print all matches
            # print "found at", f+1, "in", string
    return count, 1/float((2**(N+1)))

n = 4
N = 24
counts, probperevent = countinlist(n,N)
probs = [count*probperevent for count in counts]

for i in range(N):
    print '{0:2d} {1:.10f}'.format(i+1,probs[i])
pylab.title('Probabilities of getting {0} consecutive heads in {1} tosses'.format(n, N))
pylab.xlabel('toss')
pylab.ylabel('probability')
pylab.plot(range(1,(N+1)), probs, 'o')
pylab.show()