# Probability of a winning consecutive $k$-subset out of $n$ coin flips

Assume we flip a coin $n$ times. A $k$-sequence is defined as any consecutive sequence of coin flips of length $k$. Call a $k$-sequence "winning" if there are strictly more heads than tails. What is the probability of there being a winning consecutive $k$-sequence in $n$ tosses?

In order to clarify some of the definitions, here are some examples. Assume we have flipped the sequence $\rm HHTHT$.

$2$-sequences: $\rm \underbrace{HH}THT, H\underbrace{HT}HT, HH\underbrace{TH}T, HHT\underbrace{HT}$, so $\rm HH, HT, TH, HT$ are consecutive $2$-sequences.

Winning $2$-sequences: $\rm HH$.

All $4$-flips with winning $2$-sequences highlighted, if there are multiples, I have selected the first one:

• $\rm \underbrace{HH}HH$

• $\rm \underbrace{HH}HT$

• $\rm \underbrace{HH}TH$

• $\rm \underbrace{HH}TT$

• $\rm HT\underbrace{HH}$

• $\rm HTHT$ (no winning $2$-sequences)

• $\rm HTTH$ (no winning $2$-sequences)

• $\rm HTTT$ (no winning $2$-sequences)

• $\rm T\underbrace{HH}H$

• $\rm T\underbrace{HH}T$

• $\rm THTH$ (no winning $2$-sequences)

• $\rm THTT$ (no winning $2$-sequences)

• $\rm TT\underbrace{HH}$

• $\rm TTHT$ (no winning $2$-sequences)

• $\rm TTTH$ (no winning $2$-sequences)

• $\rm TTTT$ (no winning $2$-sequences)

Out of the $8$ combinations, there are $4$ which have winning $2$-sequences (we can choose $2$ consecutive flips from the sequence which have more heads than tails). So $p(4, 2) = 8/16 = 1/2$.

• @CalvinLin, They should be right next to each other, so $\rm TT$ is not included because the two tails are not consecutive. – George V. Williams Jul 19 '13 at 0:18
• I'm having difficulty understanding your definitions. WHat do you mean that the two tails in TT are not consecutive? Isn't TT a consecutive sequence of coin flips of length 2? I also don't understand why HT is listed twice. – Calvin Lin Jul 19 '13 at 0:20
• @CalvinLin, I understand the definitions are confusing, unfortunately I'm unfamiliar with the proper vocabulary. I added some braces in order to help. Does this answer your question? – George V. Williams Jul 19 '13 at 0:23
• I think that if I understood your definition well, we should have $p(4,2) = 11/16$ : there is 1 example with no $T$s, 4 examples with $1$ T, $6$ examples with two $T$'s, which sum up to $11$ examples where the number of heads is at least bigger than the number of tails in four coin flips in a row. Am I right? – Patrick Da Silva Jul 19 '13 at 0:39
• @PatrickDaSilva, no, I attempted to clarify some more. I might just scrape this question and return when I can find a more illuminating example. – George V. Williams Jul 19 '13 at 0:56

I suspect there is no closed form, but here's how you can calculate this for small values of $k$. I will be talking about binary strings, but it's the same problem.

If $S_k$ is the set of winning binary $k$-strings, consider the generalized question of, given a finite set $S$, deciding whether any given string contains a string from $S$. This is the problem of recognizing a regular language, and is solved by constructing a finite-state automaton corresponding to the set $S$. (See any reference on FSAs and the problem of matching regular expressions, etc.)

Following an idea I learnt from "Analytic Combinatorics" by Flajolet and Sedgewick, it is very easy to construct a generating function for a regular language (a language described by an FSA). Let $L_\alpha$ be the generating function corresponding to the state $\alpha$, so that the $n$-th coefficient counts the number of length-$n$ input strings such that the FSA, started from state $\alpha$, will finish in a terminal state. Let $\bar Q$ be the set of terminal states, and let $q(\alpha, a)$ be the transition function that gives the next state, where $\alpha$ is the current state and $a$ is the next input letter (belonging to the FSA's alphabet). Then the generating functions satisfy $$L_\alpha(z) = [\alpha\in\bar Q] + z\sum_{\text{letter }a} L_{q(\alpha, a)}(z).$$ If we denote by $T$ the adjacency matrix of the directed graph of transitions of the FSA ($T_{\alpha\beta} = \sum_{a}[q(\alpha,a)=\beta]$), we get $$\mathbf{L}(z) = v + z T \mathbf{L}(z),$$ where $\mathbf{L}=(L_\alpha)_\alpha$ and $v_\alpha=[\alpha\in\bar Q]$. This is a system of linear equations in $L$, which can be solved for $L_0$, the generating function for the initial state. Then $L_0$ is the generating function for the number of strings of length $n$ that belong to the regular language recognized by the FSA.

A short implementation (hopefully correct) leads me to the following generating functions for small $k$. Here $g_k(z)$ is the generating function for the set of binary strings that contain a winning $k$-string.

$$g_2(z) = \frac{1}{1-2z}+\frac{1+z}{-1+z+z^2}.$$ $$g_3(z) = -z^2+\frac{1}{1-2z}+\frac{1+z+z^2}{-1+z+z^3}.$$ $$g_4(z) = -z^3+\frac{1}{1-2z}+\frac{-1-z-z^2-z^3+z^4+z^5}{1-z-z^2-z^4+z^6}.$$ $$g_5(z) = -z^3-5 z^4+\frac{1}{1-2z}+\frac{-1-z-2 z^2-2 z^3-2 z^4+z^5+z^6+2 z^7+z^8+z^9}{1-z-z^3-2 z^5+z^8+z^{10}}.$$ $$g_6(z) = \frac{1}{8 (-1+z)}-z^4-6 z^5+\frac{1}{8 (1+z)}+\frac{1}{1-2z}+\frac{\left(4+3 z+9 z^2+11 z^3+22 z^4+19 z^5+8 z^6+6 z^7+6 z^8-2 z^9-9 z^{10}-10 z^{11}-z^{13}+3 z^{15}+4 z^{16}+3 z^{17}\right)}{\left(4 \left(-1+z+z^3+2 z^5+3 z^6+2 z^7+z^9+z^{11}-3 z^{12}+z^{18}\right)\right)}.$$ g_7(z) = -z^4-6 z^5-22 z^6+\frac{1}{1-2z}+\left(\begin{aligned}1&+z+2 z^2+3 z^3+5 z^4+6 z^5+5 z^6-4 z^7-5 z^8-9 z^9-10 z^{10}\\&-17 z^{11}-17 z^{12}-14 z^{13}-4 z^{14}+4 z^{15}+8 z^{16}+11 z^{17}+19 z^{18}\\&+13 z^{19}+12 z^{20}+2 z^{21}-4 z^{22}-5 z^{23}-8 z^{24}-9 z^{25}-5 z^{26}\\&-5 z^{27}+z^{29}+z^{30}+2 z^{31}+2 z^{32}+z^{33}+z^{34}\end{aligned}\right)/\left(\begin{aligned}-1&+z+z^3+z^5+z^6+5 z^7+z^8-3 z^{10}-z^{11}-4 z^{12}-z^{13}-10 z^{14}\\&-5 z^{15}-z^{16}+3 z^{17}-z^{18}+6 z^{19}+10 z^{21}+3 z^{22}\\&-z^{24}-4 z^{26}-5 z^{28}+z^{33}+z^{35}\end{aligned}\right)

For $n\geq k$, $k=3,4,5,6$, the coefficients of $g_k-\frac{1}{1-2z}$ reproduce A000930, A118647, A120118 and A133551. Also, $g_2$ matches the answer by Jean-Sebastien (A008466).

Edit. Here is also $g_8$ (I realize it's a mess): $$g_8(z) = -z^5-7 z^6-29 z^7+\frac{1}{1-2 z} + \frac{\sum_{j\geq0}p_{8,j}z^j}{\sum_{j\geq0}q_{8,j}z^j},$$ \begin{aligned}(p_{8,j})_{0\leq j\leq 69} = \{&-1,-1,-1,-2,-3,-5,-7,-2,19,22, 16,15,8,17,40,10,-42,-76,\\&-73,-39,-12,-24,-52,-18,54,141,100,33,-16,-1,37,35,-41,\\&-146,-56,-19,14,14,-24,-38,45,104,12,14,-18,-21,14,13,-36,\\&-49,1,-3,18,17,-4,0,15,15,0,-1,-8,-7,0,0,-2,-2,0,0,1,1\}.\end{aligned} \begin{aligned}(q_{8,j})_{0\leq j\leq 70} = \{&1,-1,-1,0,-1,0,1,-3,-8,0,8, 8,10,5,-8,2,28,15,-25,-24,-28,\\&-24,19,18,-51,-40,55,16,55,45,-51,-36,61,45,-70,16,-67,\\&-40,70,19,-56,-24,58,-24,56,15,-56,2,28,5,-28,8,-28,0,28,\\&-3,-8,0,8,0,8,-1,-8,0,1,0,-1,0,-1,0,1\}.\end{aligned} Here $g_8-\frac1{1-2z}$ matches A212398.

• Your case k=3 doesn't match mine, though, and the etiquette of mine, oeis.org/A118645 is said to be winning 3-sequences – Jean-Sébastien Jul 21 '13 at 6:53
• Also I think your $k=4$ counts sequences formed with two $1$ 's and two $0$"s as a winning sequence – Jean-Sébastien Jul 21 '13 at 8:12
• @Jean-Sébastien My $k=4$ counts $THHH$, $HTHH$, $HHTH$, $HHHT$, $HHHH$. My $k=3$ counts $THH$, $HTH$, $HHT$, $HHH$ and $g_3$ matches oeis.org/A118645 up to $n=31$. – Kirill Jul 21 '13 at 13:42
• Yes my bad, I didn't catch at first that the sequences you linked where $g_k-1/1-2z$. – Jean-Sébastien Jul 21 '13 at 16:13
• @Jean-Sébastien The difference $g_k-\frac1{1-2z}$ counts the strings with no winning substrings, that's why I did that. – Kirill Jul 21 '13 at 16:49

Throwing in some observations that could help someone go further.

1. Some notation, I use $N(k,n)$ for the number of length $n$ sequences that have at least one $k$ winning sequence. Define this to be $0$ when $k>n$.
2. Remark that $N(n,n)=2^{n-1} - ((1+(-1)^n)/4){n\choose n/2}$. This is the number of binary sequence with more $1$ than $0$. See A058622
3. Observe that $N(k,n)=2N(k,n-1)+$Offset since any "good" sequence of length $n-1$ will be "good" at length $n$ whether we add $H$ or $T$. The problem is then to characterize the offset.
4. Let's look at the offset for the case $k=2$

• First for $n=2$, we have $$\color{green}{HH}\\ HT\\ \color{blue}{TH}\\ TT$$ The green one is a good one and the blue one is one that can become winnning at the next step.

• We keep going on with $n=3$ $$\color{green}{HHH}\\ \color{green}{HHT}\\ \color{blue}{HTH}\\ HTT\\ \color{green}{THH}\\ THT\\ \color{blue}{TTH}\\ TTT$$ Colors are as above. We have some sort of characterization of the offset for $N(k,n)$. It is the number of blue colored sequence in the sets of length $n-1$. Call this number $F(n-1)$, so that $N(2,n)=2N(2,n-1)+F(n-1)$. Black at time $n$ is blue at time $n-1$ plus black at time $n-1$ (Those that will add a $T$). Blue at time $n$ is black at time $n-1$ (Those that will ad a $H$). From this, we see that $F(n-1)$ is the (n-1)^{th} Fibonacci number.

• We finally get that $N(2,n)= 2N(2,n-1)+Fibo(n-1)$. This is A008466

I believe some similar offset exists for other $k$, but I haven't been able to figure it out. For $k=3$, I believe the formula is given by this sequence. It is not explicitely written as $N(3,n)=2N(3,n-1)+$ offset,however if we write it this way, the offset (the number of blue) seems to be this one. The reccurence relation for Blue and Black in this case seems to be $$Blue(n)=Black(n-1)+Black(n-2)\\ Black(n)=Black(n-2)+Blue(n-2)$$ I conjectured that the blue/black reccurence for $k$ would be $$Blue(n)=\sum_{i=1}^{k-1} Black(n-i)\\ Black(n)=Black(n-(k-1))+Blue(n-(k-1))$$ However both seems to fail for $k=4$. The number $N(4,n)$ is given by this, and the first Blue and Black numbers are, starting at Blue$(4)$ and Black$(4)$, Blue: $\{3,5,9,17,28,47,81,\cdots\}$ and the Black: $\{8,14,24,40,69,119,204\}$. Found no pattern on those yet.

Not an answer, but in case someone wants to check, here some numerical values (by brute force). These are the complementary probabities: $P(N,K)=$probability that in a binary sequence of length $N$ all runs of length $K$ have at most $K/2$ ones.

                            K
----------------------------------------------------------------------------
N        4           5           6           10           16           20
----------------------------------------------------------------------------
4   0.687500000
5   0.593750000 0.500000000
6   0.515625000 0.406250000 0.656250000
7   0.445312500 0.335937500 0.578125000
8   0.378906250 0.277343750 0.515625000
9   0.324218750 0.226562500 0.460937500
10   0.278320313 0.181640625 0.411132813 0.623046875
11   0.238769531 0.146484375 0.364746094 0.561523438
12   0.204589844 0.118896484 0.320800781 0.513671875
13   0.175292969 0.096679688 0.282958984 0.472656250
14   0.150268555 0.078552246 0.250305176 0.435974121
15   0.128814697 0.063690186 0.221649170 0.402374268
16   0.110412598 0.051605225 0.196289063 0.371124268  0.598190308
17   0.094635010 0.041839600 0.173744202 0.341751099  0.549095154
18   0.081115723 0.033943176 0.153697968 0.313926697  0.511455536
19   0.069528580 0.027538300 0.135940552 0.287410736  0.479543686
20   0.059596062 0.022337914 0.120257378 0.262016296  0.451251030  0.588098526
21   0.051082134 0.018116474 0.106403351 0.239145279  0.425523281  0.544049263
22   0.043784618 0.014692545 0.094150305 0.218657494  0.401744604  0.510432720
23   0.037529707 0.011916757 0.083306193 0.200160742  0.379518390  0.482032537
24   0.032168329 0.009665787 0.073707640 0.183359027  0.358571470  0.456922412
25   0.027572840 0.007839948 0.065212995 0.168030113  0.338706225  0.434139192
26   0.023633853 0.006358862 0.057697296 0.154000729  0.319774225  0.413120329
27   0.020257585 0.005157508 0.051048629 0.141132876  0.301660635  0.393503577
28   0.017363641 0.004183140 0.045166563 0.129314799  0.284274448  0.375039458
29   0.014883118 0.003392879 0.039962310 0.118455445  0.267542088  0.357547507
30   0.012756955 0.002751918 0.035357597 0.108481467  0.251403042  0.340892179
31   0.010934530 0.002232038 0.031283361 0.099334799  0.235806767  0.324968616
32   0.009372453 0.001810368 0.027678560 0.090960133  0.220710414  0.309693736
33   0.008033529 0.001468358 0.024489160 0.083297889  0.206685320  0.295000401
34   0.006885880 0.001190960 0.021667299 0.076287380  0.193737437  0.280833456
35   0.005902182 0.000965968 0.019170608 0.069871258  0.181745356  0.267146955
36   0.005059012 0.000783481 0.016961605 0.063997068  0.170600487  0.253902159
37   0.004336295 0.000635468 0.015007139 0.058617391  0.160213479  0.241066065
38   0.003716823 0.000515418 0.013277880 0.053689560  0.150509918  0.228610295
39   0.003185848 0.000418047 0.011747882 0.049175161  0.141427161  0.216510245
40   0.002730726 0.000339071 0.010394186 0.045039480  0.132911899  0.204744417
41   0.002340622 0.000275015 0.009196475 0.041250977  0.124918332  0.193684165
42   0.002006247 0.000223060 0.008136775 0.037780835  0.117406770  0.183348903
43   0.001719640 0.000180920 0.007199183 0.034602590  0.110342580  0.173671888
44   0.001473977 0.000146741 0.006369628 0.031691846  0.103695359  0.164588973
45   0.001263408 0.000119019 0.005635663 0.029026116  0.097438306  0.156045255
46   0.001082921 0.000096535 0.004986271 0.026584739  0.091547743  0.147993642
47   0.000928218 0.000078298 0.004411708 0.024348776  0.086002762  0.140393520
48   0.000795615 0.000063506 0.003903352 0.022300894  0.080785017  0.133209609
49   0.000681956 0.000051509 0.003453573 0.020425243  0.075878618  0.126411051
50   0.000584533 0.000041778 0.003055621 0.018707323  0.071268539  0.119970677
51   0.000501028 0.000033885 0.002703525 0.017133869  0.066939301  0.113864423
52   0.000429453 0.000027484 0.002392001 0.015692739  0.062874931  0.108070858
53   0.000368102 0.000022292 0.002116373 0.014372815  0.059059529  0.102570803
54   0.000315516 0.000018080 0.001872505 0.013163909  0.055477700  0.097347026
55   0.000270442 0.000014665 0.001656739 0.012056688  0.052114792  0.092383987
56   0.000231808 0.000011894 0.001465834 0.011042600  0.048957002  0.087667632
57   0.000198692 0.000009647 0.001296928 0.010113810  0.045991400  0.083185232
58   0.000170308 0.000007825 0.001147484 0.009263143  0.043205923  0.078925249
59   0.000145978 0.000006347 0.001015261 0.008484026  0.040589333  0.074877237
60   0.000125124 0.000005148 0.000898273 0.007770439  0.038131168  0.071031786
61   0.000107249 0.000004175 0.000794766 0.007116871  0.035821691  0.067380506
62   0.000091928 0.000003386 0.000703186 0.006518274  0.033651830  0.063915439
63   0.000078795 0.000002747 0.000622159 0.005970024  0.031613126  0.060628501
64   0.000067539 0.000002228 0.000550468 0.005467887  0.029697671  0.057511382
65   0.000057890 0.000001807 0.000487038 0.005007985  0.027898065  0.054555717
66   0.000049620 0.000001466 0.000430917 0.004586765  0.026207367  0.051753268
67   0.000042532 0.000001189 0.000381263 0.004200974  0.024619051  0.049096042
68   0.000036456 0.000000964 0.000337331 0.003847631  0.023126973  0.046576366
69   0.000031248 0.000000782 0.000298460 0.003524008  0.021725340  0.044186928
70   0.000026784 0.000000634 0.000264069 0.003227605  0.020408692  0.041920790
71   0.000022958 0.000000514 0.000233641 0.002956133  0.019171884  0.039771388
72   0.000019678 0.000000417 0.000206718 0.002707493  0.018010074  0.037732530
73   0.000016867 0.000000338 0.000182899 0.002479767  0.016918706  0.035798376
74   0.000014457 0.000000274 0.000161823 0.002271195  0.015893501  0.033963423
75   0.000012392 0.000000223 0.000143177 0.002080165  0.014930438  0.032222488
76   0.000010622 0.000000181 0.000126678 0.001905203  0.014025741  0.030570687
77   0.000009104 0.000000146 0.000112081 0.001744957  0.013175866  0.029003416
78   0.000007804 0.000000119 0.000099166 0.001598190  0.012377485  0.027516329
79   0.000006689 0.000000096 0.000087740 0.001463766  0.011627477  0.026105327
80   0.000005733 0.000000078 0.000077629 0.001340650  0.010922909  0.024766531
81   0.000004914 0.000000063 0.000068684 0.001227888  0.010261027  0.023496271
82   0.000004212 0.000000051 0.000060770 0.001124611  0.009639248  0.022291070
83   0.000003610 0.000000042 0.000053767 0.001030020  0.009055141  0.021147626
84   0.000003095 0.000000034 0.000047572 0.000943386  0.008506427  0.020062804
85   0.000002653 0.000000027 0.000042090 0.000864038  0.007990961  0.019033623
86   0.000002274 0.000000022 0.000037240 0.000791364  0.007506732  0.018057244
87   0.000001949 0.000000018 0.000032949 0.000724802  0.007051845  0.017130971
88   0.000001670 0.000000015 0.000029152 0.000663840  0.006624524  0.016252237
89   0.000001432 0.000000012 0.000025793 0.000608004  0.006223099  0.015418604
90   0.000001227 0.000000010 0.000022821 0.000556865  0.005846000  0.014627756
91   0.000001052 0.000000008 0.000020191 0.000510028  0.005491752  0.013877493
92   0.000000902 0.000000006 0.000017865 0.000467129  0.005158972  0.013165728
93   0.000000773 0.000000005 0.000015806 0.000427839  0.004846357  0.012490482
94   0.000000662 0.000000004 0.000013985 0.000391854  0.004552685  0.011849876
95   0.000000568 0.000000003 0.000012373 0.000358895  0.004276809  0.011242130
96   0.000000487 0.000000003 0.000010948 0.000328709  0.004017650  0.010665555
97   0.000000417 0.000000002 0.000009686 0.000301061  0.003774195  0.010118550
98   0.000000358 0.000000002 0.000008570 0.000275739  0.003545492  0.009599597
99   0.000000306 0.000000001 0.000007583 0.000252547  0.003330648  0.009107257
`
• Thanks for this! It's nice to see how slow the growth is in practice. In fact by using principles from the theory of large deviations you can see that, almost surely, the largest admissible $k$ is $\gg \log n$. By this I mean that if $C_n$ is the random variable denoting the length of the longest consecutive "> 50% winning" subsequence in $n$ tosses, then $\lim_n C_n/\log n = \infty$ almost surely. – Christos Jul 27 '13 at 3:05
• Well, I think it's easy to show that, for odd $K$, $2^{-N+K-1}\le P(N,K) \le 2^{-N/K}$, or asymptotically for any $K$, $2^{-N}\le P(N,K) \le 2^{-N/K}$ – leonbloy Jul 27 '13 at 3:27