Count number of alternations in a coin flip sequence

Question

I have a sequence of ones and zeros and I would like to count the number of alternations. e.g.

x <- rbinom(10, 1, 1/2)
> x
 [1] 0 0 1 1 1 1 1 0 1 0

Thus I would like to count (in R) how many times the sequence alternates (or flips) from one to zero. In the above sequence the number of alternations (counted by hand) is 4.

Answer 1

You can use diff() :

> x <- rbinom(10,1,1/2)

> x
 [1] 0 0 0 1 1 1 1 0 1 0

> sum(diff(x)!=0)
[1] 4

Answer 2

The rle function will count the number of 'runs' of the same value in a vector. Hence the length of this vector (minus 1) gives you the number of alterations:

> x
 [1] 0 0 0 1 1 1 1 0 1 0
> rle(x)
Run Length Encoding
  lengths: int [1:5] 3 4 1 1 1
  values : num [1:5] 0 1 0 1 0
> length(rle(x)$lengths)-1
[1] 4

Might be quicker or slower than the diff() method, but it also gives you the run lengths if you need them...

Answer 3

It definitely doesn't beat diff in terms of elegance but another way:

sum(x[-1] != head(x, n=-1))

On my system, this seems to be a teeny bit faster:

> x <- rbinom(1e6, 1, 0.5)
> system.time(replicate(100, sum(x[-1] != head(x, n=-1))))
   user  system elapsed 
  8.421   3.688  12.150 
> system.time(replicate(100, sum(diff(x) != 0)))
   user  system elapsed 
  9.431   4.525  14.248

It seems like there ought to be a nice analytic solution for the distribution of the number of unequal adjacent elements in the sequence.

Answer 4

Pseudocode (sequence is an array with your coin flips):

variable count = 0
variable state = sequence[0]
iterate i from sequence[1] to sequence[n]
    if (state not equal sequence[i])
        state = 1 - state
        count++

count should be your result