[Spectra of] random block sequences

Analytical forms for all but the last spectrum are: 1, u^{2}/(1 + 8u^{2}), 1/(1 + 8 u^{2}), u^{2}, (1 - 4u^{2})^{2}/(1 - 5u^{2} + 8u^{4}), u^{2}/(1 - 5u^{2} + 8u^{4}), u^{2} + 1/36 DiracDelta[ω - 1/3], where u=Cos[π ω], and ω runs from 0 to 1/2 in each plot. Given a list of blocks such as {{1, 1}, {0}} each element of Flatten[list] can be thought of as a state in a finite automaton or a Markov process (see page 1084). The transitions between these states have probabilities given by m[Map[Length, list]] where

m[s_] := With[{q = FoldList[Plus, 0, s]}, ReplacePart[RotateRight[IdentityMatrix[Last[q]], {0, 1}], 1/Length[s], Flatten[Outer[List, Rest[q], Drop[q, -1] + 1], 1]]]

The average spectrum of sequences generated according to these probabilities can be obtained by computing the correlation function for elements a distance r apart

ξ[list_, r_] := With[{w = (# - Apply[Plus, #]/Length[#]) &[Flatten[list]]}, w.MatrixPower[m[Map[Length, list]], r].w/Length[w]]

then forming Sum[ξ[Abs[r]] Cos[2π r ω], {r, -n/2, n/2}] and taking the limit n->∞. If ξ[r] =λ^{r} then the spectrum is (1 - λ^{2})/(λ^{2} - 2*λ*Cos[2*π*ω] + 1) - 1. For a random walk (see page 977) in which ±1 occur with equal probability the spectrum is Csc[π*ω]^{2}/2, or roughly 1/ω^{2}.

The same basic setup also applies to spectra associated with linear filters and ARMA time series processes (see page 1083), in which elements in a sequence are generated from external random noise by forming linear combinations of the noise with definite configurations of elements in the sequence.