1
$\begingroup$

So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.

My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.

I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.

For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.

$\endgroup$
  • $\begingroup$ You have to think something like this: if the first coin throw ends as head and next as also head then the current coin can be head ? HHTHH..... recursion + memorization should do. $\endgroup$ – noman pouigt Dec 1 '17 at 2:48
  • $\begingroup$ You're using permutations in the everyday sense, but this word has a different and very particular meaning in mathematics which doesn't fit here. This could hamper communication with computer scientists, who use the language of mathematics. $\endgroup$ – Yuval Filmus Dec 1 '17 at 10:49
3
$\begingroup$

Method 1: DFA. Construct a DFA that accepts the language of valid coin tosses (of any length). Let $A$ be a $Q \times Q$ matrix (where $Q$ is a set of states) such that $A(j,i)$ is the number of symbols that cause the DFA to transition from state $i$ to state $j$. The number of coin tosses that you're after is $1_F A^{32} 1_{\{q_0\}}$, where $q_0$ is the initial state, $F$ is the set of final states, and $1_S$ is the characteristic vector of $S \subseteq Q$.

This method actually works with more general automaton models. For example, you can have a DFA in which some transitions are "missing": when at state $i$, upon reading a symbol $\sigma$ you might just get stuck. More generally, UFAs would work.

Method 2: Recurrence relation. This is a reformulation of the DFA approach without mentioning DFAs. Let $A(n,i)$ be the number of binary words $w$ of length $n$ such that $wH^i \notin L$ but (if $i \neq 0$) $wH^{i-1} \in L$, where $L$ consists of all strings with no three consecutive heads. You're after $B(n) = A(n,1) + A(n,2) + A(n,3)$. These sequences are given by the following recurrence:

  • $A(0,1) = A(0,2) = 0$, $A(0,3) = 1$.
  • $A(n+1,1) = A(n,2)$.
  • $A(n+1,2) = A(n,3)$.
  • $A(n+1,3) = A(n,1) + A(n,2) + A(n,3)$.

I'll let you figure out where these recurrences come from.

We can also come up with a direct recurrence for $B$:

  • $B(0) = 1$, $B(1) = 2$, $B(2) = 4$.
  • $B(n+3) = B(n+2) + B(n+1) + B(n)$.

You can prove this recurrence from the preceding ones for $A(n,i)$, and also directly.

Standard methods show that $B(n) \sim C \alpha^n$, where $\alpha \approx 1.839$ and $C \approx 1.137$. In fact, $B(n)$ can be calculated as the integer closest to $C \alpha^n$ for $n$ larger than some constant.

$\endgroup$

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.