최소 하나의 SSSSS를 포함하는 이벤트 50 S의 첫 번째 발생에 필요한 시행 횟수 분포.

Question

확률이있는 두 결과 S (성공) 또는 F (실패)에 대한 반복적 인 독립 시행을 고려합니다. $p$ 과 $q$, 각각. 최소 하나의 SSSSS를 포함하는 이벤트 50 S의 첫 번째 발생에 필요한 시행 횟수의 분포를 결정합니다. 즉, 총 50 번의 성공과 5 번의 연속 성공은 최소 한 번 이상 발생해야합니다.

내 노력 :

허락하다 $M_n$ 완전히 처음 발생하는 데 필요한 시행 횟수 $n$ S. 우리는 $P(M_n=k)={k-1\choose n-1}p^{n}q^{k-n}$. 허락하다$N_n$ 완전히 처음 발생하는 데 필요한 시행 횟수 $n$S는 하나 이상의 SSSSS를 포함합니다. 그때$P(N_n=k)=0$ 만약 $n<5$. 우리는 분포를 결정하고 싶습니다$N_{50}$.

다음과 같은 가능한 초기 이벤트에 대한 조건 :

1. A1 : 처음 5 개의 결과는 Fxxxx (확률 포함) $q$ ), x = S 또는 F,
2. A2 : 처음 5 개의 결과는 SFxxx였습니다 (확률 $pq$ ),
3. A3 : 처음 5 개의 결과는 SSFxx였습니다 (확률 $p^2q$),
4. A4 : 처음 5 개의 결과는 SSSFx였습니다 (확률 $p^3q$),
5. A5 : 처음 5 개의 결과는 SSSSF였습니다 (확률 $p^4q$),
6. A6 : 처음 5 개의 결과는 SSSSS (확률 포함) $p^5$).

참고 $P(A_1)+P(A_2)+P(A_3)+P(A_4) +P(A_5)+P(A_6)=1$.

허락하다 $k>5$.

경우 1, $P(N_n=k∣\text{first result was F})=P(N_n=k−1)$ 왜냐하면 우리는 $n$ 첫 번째 결과가있는 SSSSS를 포함하는 S, 이제 $k−1$ 얻기 위해 남은 시련 $n$ S가 포함 된 SSSSS.

경우 2, $P(N_n=k∣\text{first two results were SF})=P(N_{n-1}=k−2)$. 처음 두 결과로 SSSSS를 향한 진전을 이루지 못했지만 S가 있고$(n-1)$S 남았습니다. 지금있다$k−2$ 얻기 위해 남은 시련 $(n-1)$ S가 포함 된 SSSSS.

3 번의 경우 $P(N_n=k∣\text{first three results were SSF})=P(N_{n-2} =k−3)$. 처음 세 개의 결과로 SSSSS를 향한 진전을 이루지 못했지만 두 개의 S가 있고$(n-2)$S 남았습니다. 지금있다$k−3$ 얻기 위해 남은 시련 $(n-2)$ S가 포함 된 SSSSS.

4 번의 경우 $P(N_n=k∣\text{first four results were SSSF})=P(N_{n-3} =k−4)$. 처음 4 개의 결과로 SSSSS를 향한 진전이 없었지만 3 개의 S가 있고$(n-3)$S 남았습니다. 지금있다$k−4$ 얻기 위해 남은 시련 $(n-3)$ S가 포함 된 SSSSS.

5 번의 경우 $P(N_n=k∣\text{first five results were SSSSF})=P(N_{n-4} =k−5)$. 처음 5 개의 결과로 SSSSS를 향한 진전이 없었지만 4 개의 S가 있고$(n-4)$S 남았습니다. 지금있다$k−5$ 얻기 위해 남은 시련 $(n-4)$ S가 포함 된 SSSSS.

6 번 경우 $P(N_n=k\mid\text{first five results were SSSSS})=P(M_{n-5}=k−5)$. 우리는 이미 SSSSS를 가지고 있습니다. 더 이상 SSSSS에 대해 걱정할 필요가 없습니다. 우리는 단지 얻을 필요가 있습니다$(n-5)$S와 우리는 끝났습니다. 지금있다$k−5$ 얻기 위해 남은 시련 $(n-5)$ 에스.

총 확률의 법칙을 사용하여 모든 것을 합치면 $$P(N_n =k)=P(N_n =k\mid A_1)P(A_1)+P(N_n =k\mid A_2)P(A_2)+ +\cdots+P(N_n =k\mid A_6)P(A_6),$$ 어디 $A_1, A_2, A_3, \ldots, A_6$ 6 개의 가능한 초기 이벤트가 있으면 다음에 대한 재귀 공식을 얻습니다. $k> 5$,

$$P(N_n =k)=qP(N_n =k−1)+pqP(N_{n-1} =k−2)+p^2qP(N_{n-2} =k−3) +\cdots+ p^4qP(N_{n-4} =k−5)+p^5P(M_{n-5}=k−5)$$

내가 올바른 길을 가고 있는가? 기본 케이스를 계산하려고 할 때 이상한 일이 발생합니다.$P(N_5=k)$. 무엇인지 알려주세요$P(N_5=k)$ 재귀 관계를 확인할 수 있도록 도와주세요. $P(N_6=k)$.

Answer 1

이 답변은 Goulden-Jackson Cluster Method 기반의 생성 함수 접근 방식 입니다. 우리는$5\leq r\leq k$: \ begin {align *} \ color {blue} {P (M_r = k)} & \ color {blue} {= \ left (\ sum_ {j \ geq 1} (-1) ^ {j + 1} \ binom {k-r + 1} {j} \ binom {k-5j} {kr} \ right.} \\ & \ qquad \ color {blue} {\ left .- \ sum_ {j \ geq 1} (- 1) ^ {j + 1} \ binom {kr} {j} \ binom {k-1-5j} {k-1-r} \ right) p ^ rq ^ {kr}} \ tag {1} \ end {align *} 여기서 (1)의 합은 유한합니다.$\binom{s}{t}=0$ 적분 $0<s<t$.

첫 번째 단계 : 생성 함수

우리는 길이의 단어 세트를 고려합니다. $k\geq 0$ 알파벳으로 만든 $$\mathcal{V}=\{S,F\}$$ 그리고 세트 $B=\{SSSSS\}$의 나쁜 단어 우리는 첫 번째 단계에서 찾고있는 단어의 일부가 될 수 없습니다. 생성 함수를 유도합니다.$G(z)$ 어디 $[z^k]G(z)$, 계수 $z^k$ 의 $G(z)$ 길이의 이진 단어 수를 제공합니다. $k$ 포함하지 않는 $SSSSS$.

우리는 단어의 수를 원하기 때문에 할 포함을$SSSSS$, 우리는 모든 이진 단어의 생성 기능을 취합니다. $1+2z+4z^2+8z^3+\cdots = \frac{1}{1-2z}$ 빼기 $G(z)$그것에서. 이 방법으로 우리는$H(z) = \frac{1}{1-2z}-G(z)$.

논문에 따르면 (p.7) 생성 기능 $G(z)$ 인 {정렬} * G (z) = \ 시작 \ FRAC {1} {1 dz- \ 텍스트 중량 {} (\ mathcal {C})} \ {2} 태그 \ {단부 정렬 *} 와$d=|\mathcal{V}|=2$, 알파벳의 크기 및 $\mathcal{C}$\ begin {align *} \ text {weight} (\ mathcal {C}) = \ text {weight} (\ mathcal {C} [SSSSS]) \ end {align *} 가있는 비속어 의 가중치 분자

논문 \ begin {align *} \ text {weight} (\ mathcal {C} [S ^ 5]) & =-z ^ 5-z \ cdot \ text {weight} (\ mathcal {C} [S ^ 5])-\ cdots-z ^ 4 \ cdot \ text {weight} (\ mathcal {C} [S ^ 5]) \ tag {3} \\ \ end {align *}

얻을 \ FRAC {Z ^ 5 (1-Z - \ {정렬 *} \ 텍스트 {중량} (\ mathcal {C}) = \ 텍스트 {중량} (\ mathcal {C}을 [S ^ 5) = 시작할 )} {1-z ^ 5} \ end {align *}

다음은 (2) 및 (3)입니다.

\ begin {align *} G (z) & = \ frac {1} {1-dz- \ text {weight} (\ mathcal {C})} \\ & = \ frac {1} {1-2z + \ frac {z ^ 5 (1-z)} {1-z ^ 5}} \\ & = \ frac {1-z ^ 5} {1-2z + z ^ 6} \ tag {4} \\ \ end { 정렬 *}

(4)에서 \ begin {align *} H (z) = \ frac {1} {1-2z}-\ frac {1 + z ^ 5} {1-2z + z ^ 6} \ tag {5 } \ end {정렬 *}

두 번째 단계 : 개선

길이의 유효한 단어 수를 찾고 있기 때문에 $k$ 포함하는 $50 S$ resp. $r\geq 5$ S 일반적으로 우리는 $H(z)$ 성공 횟수를 추적하기 위해 $S$. 이를 위해 우리는 성공을 표시합니다.$s$.

(3) \ begin {align *} \ text {weight} (\ mathcal {C} [S ^ 5]) & =-(sz) ^ 5- (sz) \ text {weight} (\ mathcal { C} [S ^ 5])-\ cdots- (sz) ^ 4 \ text {weight} (\ mathcal {C} [S ^ 5]) \ end {align *} 및 \ begin {align *} \ text 가져 오기 {weight} (\ mathcal {C}) =-\ frac {(sz) ^ 5 (1-sz)} {1- (sz) ^ 5} \ end {align *}

이 일반화 된 가중치를 사용하여 생성 함수를 얻습니다. $H(z;s)$ \ begin {align *} H (z; s) & = \ frac {1} {1- (1 + s) z}-\ frac {1} {1- (1 + s) z + \ frac {(sz) ^ 5 (1-sz)} {1- (sz) ^ 5}} \\ & = \ frac {1} {1- (1 + s) z}-\ frac {1- (sz) ^ 5} { 1- (1 + s) z + s ^ 5z ^ 6} \ end {align *}

세 번째 단계 : 성공으로 끝나는 단어 $S$.

계수 $[s^rz^k]H(z;s)$ 길이의 단어 수를 제공합니다. $k$ 정확히 포함 $r$ 길이의 S- 런이있는 S $5$하지만 반드시 끝에 S가있는 것은 아닙니다. 이를 강제하기 위해 길이의 단어를 뺍니다.$k$ 정확히 포함하는 $r$ 길이 S의 S 및 S 런 $5$ 및 종료 $F$.

이렇게하면 마침내 원하는 생성 함수 \ begin {align *} \ color {blue} {H (z; s) (1-z)} & \ color {blue} {= \ frac {1-z} {1 -(1 + s) z}-\ frac {\ left (1- (sz) ^ 5 \ right) (1-z)} {1- (1 + s) z + s ^ 5z ^ 6}} \ tag {6} \\ & = s ^ 5z ^ 5 + (s + f) s ^ 5z ^ 6 + \ left (s ^ 2 + 3sf + f ^ 2 \ right) s ^ 5z ^ 7 \\ & \ qquad + \ 왼쪽 (s ^ 3 + 5s ^ 2f + 5sf ^ 2 + f ^ 3 \ right) s ^ 5z ^ 8 \\ & \ qquad + \ left (s ^ 4 + 7s ^ 3f + \ color {blue} {12} s ^ 2f ^ 2 + 7sf ^ 3 + f ^ 4 \ right) s ^ 5z ^ 9 + \ cdots \ end {align *} 마지막 줄은 Wolfram Alpha의 도움으로 계산되었습니다.

시리즈의 계수는 @GCab에 명시된 표 항목과 일치합니다.

예를 들어 파란색으로 표시된 계수를 보면 $12$ 의 $s^7f^2z^9$ 이것은 길이의 단어 수를 제공합니다 $9$ 포함 $7$ S 최소한 한 번 실행 $5$S와 S로 끝납니다.이 단어는 \ begin {align *} \ color {blue} {SSSSS} SFFS & \ qquad SSFF \ color {blue} {SSSSS} \\ \ color {blue} {SSSSS} FSFS & \ qquad SFSF \입니다. color {blue} {SSSSS} \\ \ color {blue} {SSSSS} FFSS & \ qquad SFFS \ color {blue} {SSSSS} \\ SF \ color {blue} {SSSSS} FS & \ qquad FSSF \ color {blue} { SSSSS} \\ FS \ color {blue} {SSSSS} FS & \ qquad FSFS \ color {blue} {SSSSS} \\ F \ color {blue} {SSSSS} FSS & \ qquad FFSS \ color {blue} {SSSSS} \ end 가장 오른쪽에있는 {align *}$5$ S는 파란색으로 표시됩니다.

계수 $H(z;s)(1-z)$:

마지막으로 계수를 계산합니다. $H(z;s)(1-z)$. 우리는

\ begin {align *} [s ^ rz ^ k] H (z; s) & = [s ^ rz ^ k] \ frac {1} {1- (1 + s) z}-[s ^ rz ^ k ] \ frac {1} {1- (1 + s) z + \ frac {(sz) ^ 5 (1- (sz))} {1- (sz) ^ 5}} \\ & = [s ^ rz ^ k] \ frac {1} {1- (1 + s) z}-[s ^ rz ^ k] \ frac {1- (sz) ^ 5} {1- (1 + s) z + s ^ 5z ^ 6} \ end {align *}

처음에는 쉬운 부분 :

\ begin {align *} \ color {blue} {[s ^ rz ^ k] \ frac {1} {1- (1 + s) z}} = [s ^ rz ^ k] \ sum_ {j = 0} ^ {\ infty} (1 + s) ^ jz ^ j = [s ^ r] (1 + s) ^ k \, \, \ color {blue} {= \ binom {k} {r}} \ tag { 7} \ end {align *}

이제 다소 긴 부분입니다. 우리는

\ begin {align *} \ color {blue} {[s ^ rz ^ k]} & \ color {blue} {\ frac {1} {1- (1 + s) z + s ^ 5z ^ 6}} \ \ & = [s ^ rz ^ k] \ sum_ {j = 0} ^ \ infty \ left ((1 + s) zs ^ 5z ^ 6 \ right) ^ j \\ & = [s ^ rz ^ k] \ sum_ {j = 0} ^ \ infty z ^ j \ left ((1 + s) -s ^ 5z ^ 5 \ right) ^ j \\ & = [s ^ r] \ sum_ {j = 0} ^ k [ z ^ {kj}] \ sum_ {l = 0} ^ j \ binom {j} {l} (-1) ^ ls ^ {5l} z ^ {5l} (1 + s) ^ {jl} \ tag { 8} \\ & = [s ^ r] \ sum_ {j = 0} ^ k [z ^ j] \ sum_ {l = 0} ^ {kj} \ binom {kj} {l} (-1) ^ ls ^ {5l} z ^ {5l} (1 + s) ^ {kjl} \ tag {9} \\ & = [s ^ r] \ sum_ {j = 0} ^ {\ left \ lfloor k / 5 \ right \ rfloor} [z ^ {5j}] \ sum_ {l = 0} ^ {k-5j} \ binom {k-5j} {l} (-1) ^ ls ^ {5l} z ^ {5l} (1 + s) ^ {k-5j-l} \ tag {10} \\ & = [s ^ r] \ sum_ {j = 0} ^ {\ left \ lfloor k / 5 \ right \ rfloor} \ binom {k -5j} {j} (-1) ^ js ^ {5j} (1 + s) ^ {k-6j} \ tag {11} \\ & = \ sum_ {j = 0} ^ {\ min \ {\ left \ lfloor k / 5 \ right \ rfloor, \ left \ lfloor r / 5 \ right \ rfloor \}} (-1) ^ j \ binom {k-5j} {j} [s ^ {r-5j}] (1+ 초) ^ {k-6j} \\ & = \ sum_ {j \ geq 0} (-1) ^ j \ binom {k-5j} {j} \ binom {k-6j} {r-5j } \ tag {12} \\ & \, \, \ color {blue} {= \ sum_ {j \ geq 0} (-1) ^ j \ binom {kr} {j} \ binom {k-5j} { kr}} \ tag {13} \ end {align *}

논평:

• (8)에서 우리는 규칙을 적용합니다 $[z^s]z^tA(z)=[z^{s-t}]A(z)$. 또한 외부 합계의 상한을$k$ 다른 값은 계수에 기여하지 않기 때문에 $z^k$.

• (9)에서 우리는 외부 합계의 합산 순서를 변경합니다. $j \to k-j$.

• (10)에서 우리는 $5$ 인덱스의 $j$ 용어 때문에 $z^{5l}$.

• (11)에서 우리는 계수를 선택합니다 $z^{5j}$.

• (12)에서 우리는 계수를 선택합니다 $s^{r-5j}$.

• (13)에서는 이항 항등식 \ begin {align *} \ binom {k-5j} {j} \ binom {k-6j} {r-6j} & = \ frac {(k-5j)!} {를 사용합니다. j!} \, \ frac {1} {(r-6j)! (krj)!} \\ & = \ frac {1} {j! (r-6j)!} \, \ frac {(k-5j )!} {(kr)!} = \ binom {r-5j} {j} \ binom {k-5j} {kr} \ end {align *}

그리고 (6)과 (13)에서 이어집니다 : \ begin {align *} [s ^ rz ^ k] & \ frac {1- (sz) ^ 5} {1- (1 + s) z + s ^ 5z ^ 6} \\ & = \ left ([s ^ rz ^ k]-[s ^ {r-5} z ^ {k-5}] \ right) \ frac {1} {1- (1 + s) z + s ^ 5z ^ 6} \\ & = \ sum_ {j \ geq 0} (-1) ^ j \ binom {kr} {j} \ binom {k-5j} {kr}-\ sum_ {j \ geq 0} (-1) ^ j \ binom {kr} {j} \ binom {k-5-5j} {kr} \\ & = \ binom {k} {r} + \ sum_ {j \ geq 1} \ binom {kr} {j} \ binom {k-5j} {kr} + \ sum_ {j \ geq 1} (-1) ^ j \ binom {kr} {j-1} \ binom {k-5j} {kr} \\ & = \ binom {k} {r} + \ sum_ {j \ geq 1} (-1) ^ j \ binom {k-r + 1} {j} \ binom {k-5j} { kr} \ tag {14} \ end {align *}

우리가 구 {정렬 *}를 시작 \ \ 색 {블루} {[S ^ RZ ^ K] H (Z, S)} = [S ^ RZ ^ K] \ FRAC {1} {1- (1 + S ) z}-[s ^ rz ^ k] \ frac {1- (sz) ^ 5} {1- (1 + s) z + s ^ 5z ^ 6} \\ & \, \, \ color {blue} {= \ sum_ {j \ geq 1} (-1) ^ {j + 1} \ binom {k-r + 1} {j} \ binom {k-5j} {kr}} \ tag {15} \ end {정렬 *}

마지막 단계 : 모두 합치기

우리는 (흥미로운) 경우를 고려합니다 $5\leq r\leq k$뿐. (6)과 (15)의 결과를 취하여 이제 계수를 작성할 수 있습니다.$H(z;s)(1-z)$ 같이

\ begin {align *} [s ^ rz ^ k] & H (z; s) (1-z) \\ & = [s ^ rz ^ k] H (z; s)-[s ^ rz ^ {k- 1}] H (z; s) \\ & = \ sum_ {j \ geq 1} (-1) ^ {j + 1} \ binom {k-r + 1} {j} \ binom {k-5j} {kr} \\ & \ qquad- \ sum_ {j \ geq 1} (-1) ^ {j + 1} \ binom {kr} {j} \ binom {k-1-5j} {k-1-r } \ end {align *} 및 클레임 (1)이 이어집니다.

Answer 2

a) 재발을 추론하는 방법이 정확합니다. 문제는 적절한 초기 조건과 유효성 경계를 수정하는 것입니다.

b) 명확하게 해결하기 위해 다음과 같이 진행해야합니다.

성공 확률과 함께 일련의 Bernoulli 시행이 주어짐 $p$ (실패 $q=(1-p)$), 이진 문자열로 표현할 수 있습니다. $1 = $ 성공, $0 =$링크하려는 다른 게시물과 일치하지 않도록 실패했습니다.
같은 이유로 적절한 초기 조건으로 귀하의 재발을두기 위해 귀하의 교단을 변경하고 고려할 수 있습니다.

길이의 이진 문자열 $n$, 데 $m$ 0과 $s$끈 끝에 고정되는 것을 포함하는 것;
또한 일반적으로 가자 연속적인 길이의 실행을 고려하십시오.$r$.

우리는 $$ P(s,r,n) = N_c (s,r,n)\, p^{\,s } q^{\,n - s} $$ 길이의 문자열에서 $n$, 총 $s$ 1로 끝나고 1로 끝나는 연속적인 길이의 실행이있을 수 있습니다. $r$ 이상.

이제 당신의 반복은 $$ \eqalign{ & P(s,r,n) = q\,P(s,r,n - 1) + pq\,P(s - 1,r,n - 2) + p^{\,2} q\,P(s - 1,r,n - 2) + \cr & + \cdots + p^{\,4} q\,P(s - r + 1,r,n - r) + \left( \matrix{ n - 1 - r \hfill \cr s - 1 - r \hfill \cr} \right)p^{\,s} q^{\,n - s} \cr} $$

각 항은 다음에서 동종 다항식입니다. $p^s\, q^{n-s}$, 그래서 우리는 그것들을 가지고 다닐 필요가 없으며 우리는 주어진 문자열의 수에 유익하게 집중할 수 있습니다. $N_c$, 그건 $$ \bbox[lightyellow] { \eqalign{ & N_c (s,r,n) = \cr & = \left\{ {\matrix{ 1 & {\left| \matrix{ \;0 \le r \le s \hfill \cr \;1 \le s = n \hfill \cr} \right.} \cr {\sum\limits_{k = 0}^{r - 1} {N_c (s - k,r,n - 1 - k)} + \binom{ n - r - 1 }{ s - r - 1 } } & {\left| \matrix{ \;0 \le r \le s \hfill \cr \;1 \le s < n \hfill \cr} \right.} \cr 0 & {{\rm otherwise}} \cr } } \right. \cr} } \tag{1}$$

조건에 관해서는

• 경우 $s=n$ 건설에 포함되지 않았으며 추가해야합니다.
• 마지막 위치에있는 사람 때문에 $s$ 보다 클 것이다 $1$;
• 나머지는 분명합니다.

위의 반복은 더 작은 매개 변수 값에 대한 직접 계산으로 확인되었습니다.
예:

c) 반복 (1)은 유한 합으로 닫힌 형태로 풀 수 있습니다.

실제로이 유형의 문자열을 고려하십시오.

그들의 총 수는 $\binom{n}{s}$ 그리고 길이가 긴 사람들 $r$ 이상은 $N_c (s+1,r, n+1)$. 따라서$N_c$ 동일한 아키텍처의 문자열을 나타냅니다. $r-1$.

위와 같이 구성되지만 마지막 문자열을 제외하고 최대 길이의 문자열 수 $r-1$ ~에 의해 주어진다 $$ N_b (s,r - 1,m + 1) $$ 어디 $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ 다양한 게시물에서 설명했듯이 주로 this 와 this 다른 게시물을 참조하십시오 .

그러나 끝에 1이 있기 때문에 우리는 0 더하기로 끝나는 문자열 위에서 공제해야합니다. $ r-1$ 하나, 최종 실행을 제공 $r$.
이것들은 $$ N_b (s-r+1,r - 1,m ) $$ 그리고 우리는 $$ \bbox[lightyellow] { \eqalign{ & N_c (s + 1,r,n + 1) = N_c (s + 1,r,s + m + 1) = \cr & = \left( \matrix{ s + m \cr s \cr} \right) - N_b (s,r - 1,m + 1) + N_b (s - r + 1,r - 1,m) = \cr & = \left( \matrix{ n \cr s \cr} \right) - N_b (s,r - 1,n - s + 1) + N_b (s - r + 1,r - 1,n - s) \quad \left| {\;0 \le s,r,m} \right. \cr} } \tag{2}$$

$N_b$문헌에 더 많이 존재하고 많은 반복 관계가 있으며 단순한 ogf가 있습니다. 대답을 너무 길게하지 않기 위해 더 자세히 설명하지 않겠습니다.

d) 합산 $n$.

para.의 스케치에 표시된대로 구성된 문자열을 고려하십시오. c) 위.

그들의 총 수는 $\binom {s+m}{s} = \binom {n}{s}$ 그리고 각각은 같은 확률을가집니다 $p^{s+1}\, q^m = p^{s+1}\, q^{n-s}$.

유지 $n$ 고정, 합산 $s$ 우리는 얻는다 $$ \sum\limits_{\left( {0\, \le } \right)\,s\,\left( { \le \,n} \right)} {\binom{ n }{ s } p^{\,s + 1} q^{\,n - s} } = p\left( {p + q} \right)^{\,n} = p $$ 0으로 끝나는 보완 문자열을 추가하면 $(p+q)^{n+1} =1$.

대신 유지 $s$ 고정 및 합산 $n$, 합계를 의미합니다. $m$, 제공 $$ \eqalign{ & \sum\limits_{\left( {0\, \le \,s\, \le } \right)\,n\,} {\binom{ n }{s} p ^{\,s + 1} q^{\,n - s} } = \sum\limits_{\left( {0\, \le } \right)\,\,m\,} {\binom{ s + m }{m} p^{\,s + 1} q^{\,m} } = \cr & = p^{\,s + 1} \sum\limits_{\left( {0\, \le } \right)\,\,m\,} {\binom{ - s - 1 }{m} \left( { - 1} \right)^{\,m} q^{\,m} } = {{p^{\,s + 1} } \over {\left( {1 - q} \right)^{\,s + 1} }} = 1 \cr} $$ 이는이다 음 이항 분포를 .

그 이후로 우리는 조합 적 의미로 $$ \left\{ \matrix{ 0 \le N_c (s + 1,r,n + 1) \le N_c (s + 1,r - 1,n + 1) \le \binom{n }{ s } \hfill \cr N_c (s + 1,s + 2,n + 1) = 0 \hfill \cr N_c (s + 1,s + 1,n + 1) = 1 \hfill \cr N_c (s + 1,1,n + 1) = \binom{n }{ s } \hfill \cr N_c (s + 1,0,n + 1) = \binom{n }{ s } \hfill \cr } \right. $$ 그때 $$ 0 \le P_c (s + 1,r,p) = \sum\limits_{\left( {0\, \le \,s\, \le } \right)\,n\,} {N_c (s + 1,r,n + 1)p^{\,s + 1} q^{\,n - s} } \le 1 \quad \left| \matrix{ \,0 \le s \hfill \cr \;0 \le r \le s + 1 \hfill \cr \;0 < p < 1 \hfill \cr} \right. $$ (느리지 만) 수렴 하고 주어진$s,p$, 그것은 CDF입니다$(s+1-r)$ (지원이 더 이동하는 경우).

불행히도 내 지식에 관해서는 $n$ 의 $N_c$ (및 $N_b$)에는 닫힌 형식이 없습니다 : re. 이 이미 인용 된 게시물에 .
그러나 관심이 있다면 (2)에서 double ogf를 계산할 수 있습니다.

Answer 3

더 간단한 방법이있을 수 있습니다.

위의 조건에서 N을 시행 횟수이고 P (N)을 확률로 설정합니다.

$$P(N) = \sum_{S \in S'} p^5\prod_{j \in S} q^{j} p_{j}$$ 여기서 S '는 고정 길이가 45이고 N> = 50 인 0을 포함하는 N-50의 모든 정수 파티션 (및 반복되는 중복 요소가없는 다른 가능한 순열)입니다.

그리고 일반적으로 M 개의 성공이 있고 m 개의 연속적인 성공이있는 경우 N의 분포를 찾으려면 다음을 수행합니다.

$$P(N) = \sum_{S \in S'} p^m \prod_{j \in S} q^{j} p_{j}$$

여기서 S '는 고정 길이 Nm 및 N> = M 인 0을 포함하는 NM의 모든 정수 분할 (및 반복되는 중복 요소가없는 다른 가능한 순열)입니다.

PS 그것은 솔루션을 위해 폐쇄되지는 않았지만 시뮬레이션보다 충분히 유용하고 낫습니다.