If i have a sequence of bits. Say it is 010001011101. What is a sequence run?
I am trying to make a script that will check Golomb and this has to do with one of the three tests.
1
-
$\begingroup$ A run is a sequence of identical bits. Your sequence possibly begins with a run (of zeroes) length $1$: possiblt because we don't know what came before. Then there is a run (of ones) of length $1$, a run of three zeroes of length $3$, a run of ones of length $1$ etc. for a total of (possibly) eight runs, $6$ of length $1$, and two of length $3$. Golomb's criterion says that roughly half the total number of runs are of length $1$, one-quarter of length $2$, one-eighth of length $3$ etc. $\endgroup$– Dilip SarwateDec 1, 2011 at 23:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A run of a sequence $(a_1, a_2, \ldots, a_n)$ is a maximal subsequence consisting of a single character repeated. That is, a subsequence $(a_i, a_{i+1}, \ldots, a_j)$ (with $i \leqslant j$) is a run if and only if the following three conditions are satisfied:
- (Consists of a single character.) There is a character $z \in \{0,1\}$ such that $z = a_i = a_{i+1} = \cdots = a_j$.
- (The subsequence cannot be extended to the left.) Either $i = 1$ or $a_{i-1} \neq z$.
- (The subsequence cannot be extended to the right.) Either $j = n$ or $a_{j+1} \neq z$.
For example, the sequence $$\huge \color{Magenta}{0} \color{cyan}{1} \color{Red}{000} \color{Black}{1} \color{DarkOrange}{0} \color{DarkGreen}{111} \color{maroon}{0} \color{Blue}{1}$$ has eight runs as the color coding shows.
answered Dec 1, 2011 at 23:49