Dynamic Programming Recursive Algorithm - Series of coin tosses

Question

I have this programming prompt where I have been asked to find the number of permutations of a 32 coin toss sequence that do not have three consecutive heads in a row.

I have been tasked to find this with dynamic programming and I am having a hell of a time trying to figure out the recursive algorithm.

I have tried a two variable approach where I try and keep track of whether the previous two flips were heads or tails and then incrementing based upon that. I have also tried breaking it into sub-problems where I start with a singular toss and then work my way up the full 32 tosses.

And I'm having a hard time visualizing how to approach this and figuring out how to keep track of everything as the algorithm commences.

Any help would be greatly appreciated.

Answer 1

Let $x(n)$ be the number of $n$-terms sequences of heads and tails, avoiding three consecutive heads.

The goal is to compute $x(32)$ via dynamic programming.

I'll do it in two different ways . . .

Method $(1)$:$\;1$-variable recursion.

By direct calculation, $$x(0)=1,\;\;x(1)=2,\;\;x(2)=4$$ and for $n \ge 3$, we get $$x(n)=x(n-1)+x(n-2)+x(n-3)$$ Explanation:

Call a sequence of heads and tails "qualifying" if it avoids three consecutive heads.

Assuming $n \ge 3$, an $n$-term sequence of heads and tails is qualifying if and only if it has one of the forms \begin{align*} &Ts'\\[4pt] &HTs''\\[4pt] &HHTs'''\\[4pt] \end{align*} where $s',s'',s'''$ are qualifying sequences of lengths $n-1,n-2,n-3$, respectively.

Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n \le 2, return 2^n
    a,b,c= 1,2,4
    i = 0
    loop begin
        d=a+b+c
        i = i + 1
        if i = n then break
        a,b,c=b,c,d 
    loop end
    return d
end function

Method $(2)$:$\;2$-variable recursion.

We have $x(n) = f(0,n)$, where $f(h,n)$ is the number of qualifying $n$-term sequences, assuming $h$ consecutive heads are already in progress.

Then $f(h,n)$ satisfies the recursion \begin{align*} &\text{if}\;h \ge 3,\;\text{then}\\[4pt] &\;\;\;\;f(h,n) = 0\\[4pt] &\text{else if}\;n = 0,\;\text{then}\\[4pt] &\;\;\;\;f(h,n) = 1\\[4pt] &\text{else}\\[4pt] &\;\;\;\;f(h,n) = f(0,n-1)+f(h+1,n-1)\\[4pt] &\text{end if}\\[4pt] \end{align*} Explanation:

• If there are $3$ consecutive heads in progress, there are no qualifying sequences.$\\[4pt]$
• Else if there are no tosses remaining, the empty sequence qualifies.$\\[4pt]$
• Else a tail resets $h$ to zero, a head increases $h$ by $1$, and either way, $n$ decreases by $1$.$\\[4pt]$

Based on the above recursion, we get the following dynamic program, expressed as pseudocode . . .

function x(n):
    if n = 0, return 1
    a0,a1,a2 = 1,1,1
    i = 0
    loop begin
        b0 = a0 + a1
        b1 = a0 + a2
        b2 = a0
        i = i + 1
        if i = n then break
        a0,a1,a2 = b0,b1,b2 
    loop end
    return b0
end function

With either of the two methods, we get $x(32) = 334745777$.

Answer 2

I asked my calculus professor this questions and he said it can be solved using a geometric series. So in a handful of lines of code. The answer he gave me was still roughly 4.1 billion possibilities where you do not have heads 3 times. The series simplified to this: 2^32 - 2^28 + 1 Any thoughts?

Answer 3

This is the same person who posted the below post

Here is what my professor said: Start by listing out/counting the bad sequences:

2^29 H H H _ _ _ _ ... (2^29 because there are 29 more flips to be made that could go 2 ways) 2^28 T H H H _ _ _ _ ..... 2^27 T T H H H _ _ _ _ ...... 2^26 T T T H H H _ _ _ _ ..... and so on... He said that by doing it this way it still accounts for the possibility of HHH occurring later in the sequence. This translates to the series: (2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + .... + 2^29) which is a geometric series. (2^0 + 2^1 + 2^2 + .... + 2^29) = 1-2^28/1-2 = 1-2^28/-1 = 2^28 - 1 bad cases. So then to get the good cases it would be 2^32 - (2^28 - 1) = 2^32 - 2^28 + 1 = 2^28(2^4 - 1) + 1 when simplified completely.

From my understanding, dynamic programming is a recursive algorithm that does not use recursion. From the first post, isn't the code recursive? It would still have to iterate through all the coin flip possibilities which is not what was asked of us for the assignment.