Using Logic with functions

This was my assignment:

function[N] = script27_firstname_lastname(M) 

The function should flip a fair coin until M heads and then M tails in a row 
occur. The output N is the total number of flips that were required. 
An M = 2 example: the sequence generated is H T T H H T H T H H T T, so N = 12. 
An M = 3 example: the sequence generated is H T T T H H H T T H T H T T T H H H T T T, so N = 21.

This is what I have so far:

function[N] = script27(M)
N = 0; M = 3;
heads_counter = 0;
tails_counter = 0;
while heads_counter < M && tails_counter < M
    flip = randi(2)
    N = N + 1;
    if flip == 1
        tails_counter = 0;
        heads_counter = heads_counter + 1;
    else
        heads_counter = 0;
        tails_counter = tails_counter + 1;
    end
end
N

I can get it to count three heads or count three tails in a row but not both. Hints?

Answer 1

[Walter Roberson]

Hint: at any one time you can be in one of a number of states

State1: looking for the initial heads.

• if you receive a tail, reset the head count to 0 and stay in State1
• if you receive a head, increment the head count. If the head count reaches M, move to State2

State2: looking for first tail

• if you receive a head, stay in State2. This corresponds to more-than-enough heads, which is still "M heads in a row"
• if you receive a tail, enter State3

State3: counting tails

• if you receive a head, go back to State1. Not enough tails in a row
• if you receive a tail, increment the tail count. If the tail count reaches M, you are done.

This can be packed down to two states if you want to bother.

[Joseph Cheng]

Or since you know you need at least M*2 flips you can just look at the last M*2 flips for half of them to be head and other tails. so you can look at:

      headstails = flip(end-2*m+1:end)==[ones(1,m) 2*ones(1,m)];
      tailsheads = flip(end-2*m+1:end)==[2*ones(1,m) ones(1,m)];

and then break out of your loop if the sum of either headstails OR tailsheads equal 2*M.

by the way i'm saving each flip in an array:

 flip(flipnumber) = randi(2);

[Walter Roberson]

Hmmm, I suppose.

Note that the problem statement is that heads have to occur and then tails, so your tailsheads is not needed.

Also, instead of asking sum(headstails)==2*M, test all(headstails)

[Walter Roberson]

Finite state machine encoding:

headstates = [2:M+1, M+1, ones(1,M)];
tailstates = [ones(1,M), M+2:2*M+1, 0];
FSM = [headstates(:), tailstates(:)];

Initial state: 1.

If you are in state K and you receive a H, go to state FSM(K,1). If you are in state K and you receive a T, go to state FSM(K,2). State 0 means "accept", that you are done.

Answer 2

[Image Analyst]

Why not just do it in 3 lines of code with strfind():

% Flip it 100 times.  1 = H, 2 = T
flipStates = randi([1, 2], 1, 100)
% Find the sequence HHTT = [1,1,2,2].
% Index is of the first H in the HHTT sequence.
% Add 3 to count the number of flips required.
indexes = strfind(flipStates, [1,1,2,2]);
flipsRequired = indexes(1)+3