14
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @CalvinLin, They should be right next to each other, so $\rm TT$ is not included because the two tails are not consecutive. $\endgroup$ – George V. Williams Jul 19 '13 at 0:18
  • $\begingroup$ 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. $\endgroup$ – Calvin Lin Jul 19 '13 at 0:20
  • $\begingroup$ @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? $\endgroup$ – George V. Williams Jul 19 '13 at 0:23
  • $\begingroup$ 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? $\endgroup$ – Patrick Da Silva Jul 19 '13 at 0:39
  • $\begingroup$ @PatrickDaSilva, no, I attempted to clarify some more. I might just scrape this question and return when I can find a more illuminating example. $\endgroup$ – George V. Williams Jul 19 '13 at 0:56
2
+200
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your case k=3 doesn't match mine, though, and the etiquette of mine, oeis.org/A118645 is said to be winning 3-sequences $\endgroup$ – Jean-Sébastien Jul 21 '13 at 6:53
  • $\begingroup$ Also I think your $k=4$ counts sequences formed with two $1$ 's and two $0$"s as a winning sequence $\endgroup$ – Jean-Sébastien Jul 21 '13 at 8:12
  • $\begingroup$ @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$. $\endgroup$ – Kirill Jul 21 '13 at 13:42
  • $\begingroup$ Yes my bad, I didn't catch at first that the sequences you linked where $g_k-1/1-2z$. $\endgroup$ – Jean-Sébastien Jul 21 '13 at 16:13
  • $\begingroup$ @Jean-Sébastien The difference $g_k-\frac1{1-2z}$ counts the strings with no winning substrings, that's why I did that. $\endgroup$ – Kirill Jul 21 '13 at 16:49
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Christos Jul 27 '13 at 3:05
  • $\begingroup$ 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}$ $\endgroup$ – leonbloy Jul 27 '13 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.