Signatures of Infinity:\\ Nonergodicity and Resource Scaling in\\ Prediction, Complexity, and Learning
James P. Crutchfield
Sarah Marzen
We introduce a simple analysis of the structural complexity of infinite-memory processes built from random samples of stationary, ergodic finite-memory component processes. Such processes are familiar from the well known multi-arm Bandit problem. We contrast our analysis with computation-theoretic and statistical inference approaches to understanding their complexity. The result is an alternative view of the relationship between predictability, complexity, and learning that highlights the distinct ways in which informational and correlational divergences arise in complex ergodic and nonergodic processes. We draw out consequences for the resource divergences that delineate the structural hierarchy of ergodic processes and for processes that are themselves hierarchical. \vspace{0.2in \noindent {Keywords: mutual information, excess entropy, statistical learning theory %computational complexity, %Kolmogorov-Chaitin complexity, statistical learning theory, Akaike information %criterion, minimum description length, asymptotic normality
cmechabbrev.tex


\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}

% Abbreviations from CMPPSS:

\newcommand{\eM}     {\mbox{$\epsilon$-machine}}
\newcommand{\eMs}    {\mbox{$\epsilon$-machines}}
\newcommand{\EM}     {\mbox{$\epsilon$-Machine}}
\newcommand{\EMs}    {\mbox{$\epsilon$-Machines}}
\newcommand{\eT}     {\mbox{$\epsilon$-transducer}}
\newcommand{\eTs}    {\mbox{$\epsilon$-transducers}}
\newcommand{\ET}     {\mbox{$\epsilon$-Transducer}}

% cryptic
\newcommand{\order}[1]{order\protect\nobreakdash-$#1$}
\newcommand{\Order}[1]{Order\protect\nobreakdash-$#1$}
\newcommand{\cryptic}[1]{$#1$\protect\nobreakdash-cryptic}
\newcommand{\Cryptic}[1]{$#1$\protect\nobreakdash-Cryptic}
\newcommand{\crypticity}[1]{$#1$\protect\nobreakdash-crypticity}
\newcommand{\Crypticity}[1]{$#1$\protect\nobreakdash-Crypticity}

\newcommand{\ETs}    {\mbox{$\epsilon$-Transducers}}

% Processes and sequences

\newcommand{\Process}{\mathcal{P}}

\newcommand{\ProbMach}{\Prob_{\mathrm{M}}}
\newcommand{\Lmax}   { {L_{\mathrm{max}}}}
\newcommand{\MeasAlphabet}  {\mathcal{A}}
% Original symbol
%\newcommand{\MeasSymbol}   { {S} }
%\newcommand{\meassymbol}   { {s} }
% New symbol
\newcommand{\MeasSymbol}   { {X} }
\newcommand{\meassymbol}   { {x} }
\newcommand{\MeasSymbols}[2]{ \MeasSymbol_{#1:#2} }
\newcommand{\meassymbols}[2] { \meassymbol_{#1:#2} }
\newcommand{\BiInfinity}    { \smash{\overleftrightarrow {\MeasSymbol}} }
\newcommand{\biinfinity}    { \smash{\overleftrightarrow {\meassymbol}} }
%\newcommand{\Past} { \smash{\overleftarrow {\MeasSymbol}} }
\newcommand{\Past} { \MeasSymbols{}{0} }
%\newcommand{\past} { \smash{\overleftarrow {\meassymbol}} }
\newcommand{\past} { \meassymbols{}{0} }
\newcommand{\pastprime} { {\past}^{\prime}}
%\newcommand{\Future}   { \smash{\overrightarrow{\MeasSymbol}} }
\newcommand{\Future} { \MeasSymbols{0}{} }
%\newcommand{\future}   { \smash{\overrightarrow{\meassymbol}} }
\newcommand{\future} { \meassymbols{0}{} }
\newcommand{\futureprime}   { \smash{\future^{\prime}} }
\newcommand{\PastPrime}     { \smash{\Past^{\prime}} }
\newcommand{\FuturePrime}   { \smash{\overrightarrow{\meassymbol}^\prime} }
\newcommand{\PastDblPrime}  { \smash{\overleftarrow{\meassymbol}^{\prime\prime}} }
\newcommand{\FutureDblPrime}{ \smash{\overrightarrow{\meassymbol}^{\prime\prime}} }
\newcommand{\pastL} { \smash{\overleftarrow {\meassymbol}{}^L} }
\newcommand{\PastL} { \smash{\overleftarrow {\MeasSymbol}{}^L} }
\newcommand{\PastLt}      { \smash{\overleftarrow {\MeasSymbol}_t^L} }
\newcommand{\PastLLessOne}{ \smash{\overleftarrow {\MeasSymbol}^{L-1}} }
\newcommand{\futureL}     { \smash{\overrightarrow{\meassymbol}{}^L} }
\newcommand{\FutureL}     { \smash{\overrightarrow{\MeasSymbol}{}^L} }
\newcommand{\FutureLt}    { \smash{\overrightarrow{\MeasSymbol}_t^L} }
\newcommand{\FutureLLessOne}{ \smash{\overrightarrow{\MeasSymbol}^{L-1}} }
\newcommand{\pastLprime}    { \smash{\overleftarrow {\meassymbol}^{L^\prime}} }
\newcommand{\futureLprime}  { \smash{\overrightarrow{\meassymbol}^{L^\prime}} }
\newcommand{\AllPasts}      { \smash{\overleftarrow{ {\rm {\bf \MeasSymbol}} } } }
\newcommand{\AllFutures}    { \smash{\overrightarrow{ {\rm {\bf \MeasSymbol}} } } }
\newcommand{\FutureSet} { \smash{\overrightarrow{\bf \MeasSymbol}} }

\newcommand{\Present} {\MeasSymbol_0}

% Causal states and epsilon-machines
\newcommand{\CausalState}   { \mathcal{S} }
\newcommand{\CausalStatePrime}  { {\CausalState}^{\prime}}
\newcommand{\causalstate}   { \sigma }
\newcommand{\CausalStateSet}    { \boldsymbol{\CausalState} }
\newcommand{\AlternateState}    { \mathcal{R} }
\newcommand{\AlternateStatePrime}   { {\cal R}^{\prime} }
\newcommand{\alternatestate}    { \rho }
\newcommand{\alternatestateprime}   { {\rho^{\prime}} }
\newcommand{\AlternateStateSet} { \boldsymbol{\AlternateState} }
\newcommand{\PrescientState}    { \widehat{\AlternateState} }
\newcommand{\prescientstate}    { \widehat{\alternatestate} }
\newcommand{\PrescientStateSet} { \boldsymbol{\PrescientState}}
\newcommand{\CausalEquivalence} { {\sim}_{\epsilon} }
\newcommand{\CausalEquivalenceNot}  { {\not \sim}_{\epsilon}}

\newcommand{\NonCausalEquivalence}  { {\sim}_{\eta} }
\newcommand{\NextObservable}    { {\smash{\overrightarrow {\MeasSymbol}}^1} }
\newcommand{\LastObservable}    { {\smash{\overleftarrow {\MeasSymbol}}^1} }
%\newcommand{\Prob}     { {\rm P}}
\newcommand{\Prob}      {\Pr} % use standard command
\newcommand{\ProbAnd}   { {,\;} }
\newcommand{\LLimit}    { {L \rightarrow \infty}}
\newcommand{\Cmu}       {C_\mu}
\newcommand{\hmu}       {h_\mu}
\newcommand{\EE}        {\mathbf{E}}
\newcommand{\TI}        {\mathbf{T}}
\newcommand{\SI}        {\mathbf{S}}
\newcommand{\SE}        { H_{\mathrm{sync}} }
\newcommand{\Measurable}{{\bf \mu}}

% Process Crypticity
\newcommand{\PC}        {\chi}

% Causal Irreversibility
\newcommand{\CI}        {\Xi}
\newcommand{\ReverseMap}    {r}
\newcommand{\ForwardMap}    {f}

% Abbreviations from IB:
% None that aren't already in CMPPSS

% Abbreviations from Extensive Estimation:
\newcommand{\EstCausalState}    {\widehat{\CausalState}}
\newcommand{\estcausalstate}    {\widehat{\causalstate}}
\newcommand{\EstCausalStateSet} {\boldsymbol{\EstCausalState}}
\newcommand{\EstCausalFunc} {\widehat{\epsilon}}
\newcommand{\EstCmu}        {\widehat{\Cmu}}
\newcommand{\PastLOne}  {{\Past}^{L+1}}
\newcommand{\pastLOne}  {{\past}^{L+1}}

% Abbreviations from $\epsilon$-Transducers:
\newcommand{\InAlphabet}    { \mathcal{A}}
\newcommand{\insymbol}      { a}
\newcommand{\OutAlphabet}   { \mathcal{B}}
\newcommand{\outsymbol}     { b}
\newcommand{\InputSimple}   { X}
\newcommand{\inputsimple}   { x}
\newcommand{\BottleneckVar} {\tilde{\InputSimple}}
\newcommand{\bottleneckvar} {\tilde{\inputsimple}}
\newcommand{\InputSpace}    { \mathbf{\InputSimple}}
\newcommand{\InputBi}   { \overleftrightarrow {\InputSimple} }
\newcommand{\inputbi}   { \overleftrightarrow {\inputsimple} }
\newcommand{\InputPast} { \overleftarrow {\InputSimple} }
\newcommand{\inputpast} { \overleftarrow {\inputsimple} }
\newcommand{\InputFuture}   { \overrightarrow {\InputSimple} }
\newcommand{\inputfuture}   { \overrightarrow {\inputsimple} }
\newcommand{\NextInput} { {{\InputFuture}^{1}}}
\newcommand{\NextOutput}    { {\OutputFuture}^{1}}
\newcommand{\OutputSimple}  { Y}
\newcommand{\outputsimple}  { y}
\newcommand{\OutputSpace}   { \mathbf{\OutputSimple}}
\newcommand{\OutputBi}  { \overleftrightarrow{\OutputSimple} }
\newcommand{\outputbi}  { \overleftrightarrow{\outputsimple} }
\newcommand{\OutputPast}    { \overleftarrow{\OutputSimple} }
\newcommand{\outputpast}    { \overleftarrow{\outputsimple} }
\newcommand{\OutputFuture}  { \overrightarrow{\OutputSimple} }
\newcommand{\outputfuture}  { \overrightarrow{\outputsimple} }
\newcommand{\OutputL}   { {\OutputFuture}^L}
\newcommand{\outputL}   { {\outputfuture}^L}
\newcommand{\InputLLessOne} { {\InputFuture}^{L-1}}
\newcommand{\inputLlessone} { {\inputufutre}^{L-1}}
\newcommand{\OutputPastLLessOne}    {{\OutputPast}^{L-1}_{-1}}
\newcommand{\outputpastLlessone}    {{\outputpast}^{L-1}}
\newcommand{\OutputPastLessOne} {{\OutputPast}_{-1}}
\newcommand{\outputpastlessone} {{\outputpast}_{-1}}
\newcommand{\OutputPastL}   {{\OutputPast}^{L}}
\newcommand{\OutputLPlusOne}    { {\OutputFuture}^{L+1}}
\newcommand{\outputLplusone}    { {\outputfutre}^{L+1}}
\newcommand{\InputPastL}    {{\InputPast}^{L}}
\newcommand{\inputpastL}    {{\inputpast}^{L}}
\newcommand{\JointPast} {{(\InputPast,\OutputPast)}}
\newcommand{\jointpast} {{(\inputpast,\outputpast)}}
\newcommand{\jointpastone}  {{(\inputpast_1,\outputpast_1)}}
\newcommand{\jointpasttwo}  {{(\inputpast_2,\outputpast_2)}}
\newcommand{\jointpastprime} {{({\inputpast}^{\prime},{\outputpast}^{\prime})}}
\newcommand{\NextJoint} {{(\NextInput,\NextOutput)}}
\newcommand{\nextjoint} {{(\insymbol,\outsymbol)}}
\newcommand{\AllInputPasts} { { \overleftarrow {\rm \InputSpace}}}
\newcommand{\AllOutputPasts}    { {\overleftarrow {\rm \OutputSpace}}}
\newcommand{\DetCausalState}    { {{\cal S}_D }}
\newcommand{\detcausalstate}    { {{\sigma}_D} }
\newcommand{\DetCausalStateSet} { \boldsymbol{{\CausalState}_D}}
\newcommand{\DetCausalEquivalence}  { {\sim}_{{\epsilon}_{D}}}
\newcommand{\PrescientEquivalence}  { {\sim}_{\widehat{\eta}}}
\newcommand{\FeedbackCausalState}   { \mathcal{F}}
\newcommand{\feedbackcausalstate}   { \phi}
\newcommand{\FeedbackCausalStateSet}    { \mathbf{\FeedbackCausalState}}
\newcommand{\JointCausalState}      { \mathcal{J}}
\newcommand{\JointCausalStateSet}   { \mathbf{\JointCausalState}}
\newcommand{\UtilityFunctional} { {\mathcal{L}}}
\newcommand{\NatureState}   { {\Omega}}
\newcommand{\naturestate}   { {\omega}}
\newcommand{\NatureStateSpace}  { {\mathbf{\NatureState}}}
\newcommand{\AnAction}  { {A}}
\newcommand{\anaction}  { {a}}
\newcommand{\ActionSpace}   { {\mathbf{\AnAction}}}

% Abbreviations from RURO:
\newcommand{\InfoGain}[2] { \mathcal{D} \left( {#1} || {#2} \right) }

% Abbreviations from Upper Bound:
\newcommand{\lcm}   {{\rm lcm}}
% Double-check that this isn't in the math set already!

% Abbreviations from Emergence in Space
\newcommand{\ProcessAlphabet}   {\MeasAlphabet}
\newcommand{\ProbEst}           { {\widehat{\Prob}_N}}
\newcommand{\STRegion}          { {\mathrm K}}
\newcommand{\STRegionVariable}      { K}
\newcommand{\stregionvariable}      { k}
\newcommand{\GlobalPast}        { \overleftarrow{G}}
\newcommand{\globalpast}        { \overleftarrow{g}}
\newcommand{\GlobalFuture}      { \overrightarrow{G}}
\newcommand{\globalfuture}      { \overrightarrow{g}}
\newcommand{\GlobalState}       { \mathcal{G}}
\newcommand{\globalstate}       { \gamma}
\newcommand{\GlobalStateSet}        { {\mathbf \GlobalState}}
\newcommand{\LocalPast}         { \overleftarrow{L}}
\newcommand{\localpast}         { \overleftarrow{l}}
\newcommand{\AllLocalPasts}     { \mathbf{\LocalPast}}
\newcommand{\LocalPastRegion}       { \overleftarrow{\mathrm L}}
\newcommand{\LocalFuture}       { \overrightarrow{L}}
\newcommand{\localfuture}       { \overrightarrow{l}}
\newcommand{\LocalFutureRegion}     { \overrightarrow{\mathrm L}}
\newcommand{\LocalState}        { \mathcal{L}}
\newcommand{\localstate}        { \lambda}
\newcommand{\LocalStateSet}     { {\mathbf \LocalState}}
\newcommand{\PatchPast}         { \overleftarrow{P}}
\newcommand{\patchpast}         { \overleftarrow{p}}
\newcommand{\PatchPastRegion}       { \overleftarrow{\mathrm P}}
\newcommand{\PatchFuture}       { \overrightarrow{P}}
\newcommand{\patchfuture}       { \overrightarrow{p}}
\newcommand{\PatchFutureRegion}     { \overrightarrow{\mathrm P}}
\newcommand{\PatchState}        { \mathcal{P}}
\newcommand{\patchstate}        { \pi}
\newcommand{\PatchStateSet}     { {\mathbf \PatchState}}
\newcommand{\LocalStatesInPatch}    {\vec{\LocalState}}
\newcommand{\localstatesinpatch}    {\vec{\localstate}}
\newcommand{\PointInstantX}     { {\mathbf x}}
% Galles's original LaTeX for the cond. indep. symbol follows:
\newcommand{\compos}{\mbox{$~\underline{~\parallel~}~$}}
\newcommand{\ncompos}{\not\hspace{-.15in}\compos}
\newcommand{\indep}         { \rotatebox{90}{$\models$}}
\newcommand{\nindep}    {\not\hspace{-.05in}\indep}
\newcommand{\LocalEE}   {{\EE}^{loc}}
\newcommand{\EEDensity} {\overline{\LocalEE}}
\newcommand{\LocalCmu}  {{\Cmu}^{loc}}
\newcommand{\CmuDensity}    {\overline{\LocalCmu}}

%%%%%%%%%%% added by sasa
\newcommand{\FinPast}[1]    { \overleftarrow {\MeasSymbol} \stackrel{{#1}}{}}
\newcommand{\finpast}[1]    { \overleftarrow {\meassymbol}  \stackrel{{#1}}{}}
\newcommand{\FinFuture}[1]      { \overrightarrow{\MeasSymbol} \stackrel{{#1}}{}}
\newcommand{\finfuture}[1]      { \overrightarrow{\meassymbol} \stackrel{{#1}}{}}

\newcommand{\Partition} { \AlternateState }
\newcommand{\partitionstate}    { \alternatestate }
\newcommand{\PartitionSet}  { \AlternateStateSet }
\newcommand{\Fdet}   { F_{\rm det} }

\newcommand{\Dkl}[2] { D_{\rm KL} \left( {#1} || {#2} \right) }

\newcommand{\Period}    {p}

% To take into account time direction
\newcommand{\forward}{+}
\newcommand{\reverse}{-}
%\newcommand{\forwardreverse}{\:\!\diamond} % \pm
\newcommand{\forwardreverse}{\pm} % \pm
\newcommand{\FutureProcess} { {\Process}^{\forward} }
\newcommand{\PastProcess}   { {\Process}^{\reverse} }
\newcommand{\FutureCausalState} { {\CausalState}^{\forward} }
\newcommand{\futurecausalstate} { \sigma^{\forward} }
\newcommand{\altfuturecausalstate}  { \sigma^{\forward\prime} }
\newcommand{\PastCausalState}   { {\CausalState}^{\reverse} }
\newcommand{\pastcausalstate}   { \sigma^{\reverse} }
\newcommand{\BiCausalState}     { {\CausalState}^{\forwardreverse} }
\newcommand{\bicausalstate}     { {\sigma}^{\forwardreverse} }
\newcommand{\FutureCausalStateSet}  { {\CausalStateSet}^{\forward} }
\newcommand{\PastCausalStateSet}    { {\CausalStateSet}^{\reverse} }
\newcommand{\BiCausalStateSet}  { {\CausalStateSet}^{\forwardreverse} }
\newcommand{\eMachine}  { M }
\newcommand{\FutureEM}  { {\eMachine}^{\forward} }
\newcommand{\PastEM}    { {\eMachine}^{\reverse} }
\newcommand{\BiEM}      { {\eMachine}^{\forwardreverse} }
\newcommand{\BiEquiv}   { {\sim}^{\forwardreverse} }
\newcommand{\Futurehmu} { h_\mu^{\forward} }
\newcommand{\Pasthmu}   { h_\mu^{\reverse} }
\newcommand{\FutureCmu} { C_\mu^{\forward} }
\newcommand{\PastCmu}   { C_\mu^{\reverse} }
\newcommand{\BiCmu}     { C_\mu^{\forwardreverse} }
\newcommand{\FutureEps} { \epsilon^{\forward} }
\newcommand{\PastEps}   { \epsilon^{\reverse} }
\newcommand{\BiEps} { \epsilon^{\forwardreverse} }
\newcommand{\FutureSim} { \sim^{\forward} }
\newcommand{\PastSim}   { \sim^{\reverse} }
\newcommand{\FuturePC}  {\PC^{\forward}}
\newcommand{\PastPC}        {\PC^{\reverse}}
\newcommand{\BiPC}      {\PC^{\forwardreverse}}

% Used arrows for awhile, more or less confusing?
%\newcommand{\FutureCausalState}    { \overrightarrow{\CausalState} }
%\newcommand{\PastCausalState}  { \overleftarrow{\CausalState} }
%\newcommand{\eMachine} { M }
%\newcommand{\FutureEM} { \overrightarrow{\eMachine} }
%\newcommand{\PastEM}   { \overleftarrow{\eMachine} }
%\newcommand{\FutureCmu}    { \overrightarrow{\Cmu} }
%\newcommand{\PastCmu}  { \overleftarrow{\Cmu} }

%% time-reversing and mixed state presentation operators
\newcommand{\TR}{\mathcal{T}}
\newcommand{\MSP}{\mathcal{U}}
\newcommand{\one}{\mathbf{1}}

%% added for RURO2
%% Note that it will always be typesett in math mode.
%% Example usage:
%%    The 3-block entropy is \BE[t]{3}.
%%    The 3-block-state entropy from $t=0$ is $\BSE{3}$.
%%
%% The optional argument specifies the start time, defaulting to t=0.
%% The mandatory argument specifies the length of the block (not the stop time).
\newcommand{\lastindex}[2]{
  \edef\tempa{0}
  \edef\tempb{#2}
  \ifx\tempa\tempb
    % if the length is 0, then the final time equals the start time
    \edef\tempc{#1}
  \else
    % if the start time is different from zero, then we show the sum
    \edef\tempa{0}
    \edef\tempb{#1}
    \ifx\tempa\tempb
      \edef\tempc{#2}
    \else
      \edef\tempc{#1+#2}
    \fi
  \fi
  \tempc
}
\newcommand{\BE}[2][0]{
  \ensuremath{H[\MeasSymbols{#1}{#2}]}
}
\newcommand{\BSE}[2][0]{
  \ensuremath{H[\MeasSymbols{#1}{#2},\CausalState_{\lastindex{#1}{#2}}]}
}
\newcommand{\SBE}[2][0]{
  \ensuremath{H[\CausalState_{#1},\MeasSymbols{#1}{#2}]}
}
\newcommand{\SBSE}[2][0]{
  \ensuremath{H[\CausalState_{#1},\MeasSymbols{#1}{#2},
                \CausalState_{\lastindex{#1}{#2}}]}
}
\newcommand{\AltSBE}[2][0]{
  \ensuremath{H[\AlternateState_{#1},\MeasSymbols{#1}{#2}]}
}
\newcommand{\AltBSE}[2][0]{
  \ensuremath{H[\MeasSymbols{#1}{#2},\AlternateState_{\lastindex{#1}{#2}}]}
}
\newcommand{\AltSBSE}[2][0]{
  \ensuremath{H[\AlternateState_{#1},\MeasSymbols{#1}{#2},
                \AlternateState_{\lastindex{#1}{#2}}]}
}
\newcommand{\SGBE}[2][0]{
  \ensuremath{H[\CausalState_{#2} | \MeasSymbols{#1}{#2}]}
}

\newcommand{\GI}{\varphi}
\newcommand{\OI}{\zeta}
% cryptic, gauge, oracular, Markov, and synchronization
\newcommand{\COrder}{k_{\PC}}
\newcommand{\GOrder}{k_{\GI}}
\newcommand{\OOrder}{k_{\OI}}
\newcommand{\MOrder}{R}
\newcommand{\SOrder}{k_{\SI}}
\newcommand{\Lsync} {\mathcal{L}_{\mathrm{sync}}}

%% stuff for the anatomy paper

\newcommand{\rhomu}{\rho_\mu}
\newcommand{\rmu}{r_\mu}
\newcommand{\bmu}{b_\mu}
\newcommand{\qmu}{q_\mu}
\newcommand{\wmu}{w_\mu}
\newcommand{\imu}{i_\mu}
\newcommand{\sigmamu}{\sigma_\mu}
\newcommand{\EER}{\EE_R}
\newcommand{\EEB}{\EE_B}
\newcommand{\EEQ}{\EE_Q}
\newcommand{\EEW}{\EE_W}
\newcommand{\I}{\mathbf{I}}

%% Added to standardize the order of causal states
%% Example usage:
%%    $\BiCmu = H[\CSjoint] = H[\CSjoint[,]]$
%%    $\EE = I[\CSjoint[:]] = I[\CSjoint[;]]$
\newcommand{\CSjoint}[1][,]{
   \edef\tempa{:}
   \edef\tempb{#1}
   \ifx\tempa\tempb
      % arg1 was a colon, insert a small negative space
      \ensuremath{\FutureCausalState\!#1\PastCausalState}
   \else
      % arg1 was not a colon, usually a comma or semicolon
      \ensuremath{\FutureCausalState#1\PastCausalState}
   \fi
}

%% (cje)
%% Provide a command \ifpm which is true when \pm
%% is meant to be understood as "+ or -", opposed
%% to "bidirectional". This differs from the usage
%% in TBA.  Essentially, if \forwardreverse is defined
%% as something different, perhaps a \diamond, then
%% we are free to interpret \pm as "+ or -".
\newif\ifpm
\edef\tempa{\forwardreverse}
\edef\tempb{\pm}
\ifx\tempa\tempb
   \pmfalse
\else
   \pmtrue
\fi




soi.tex
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Signatures of Infinity:
% 	Nonergodicity and Resource Scaling in Prediction, Complexity, and Learning
% jpc: 1/17/15, 1/25/15, 2/16/15, 3/21/15
% sm: 1/15/15

\documentclass[pre,twocolumn,showpacs,superscriptaddress,preprintnumbers,floatfix]{revtex4-1}

\usepackage{etex}
\usepackage{ifpdf}
\usepackage{hyperref}
\usepackage{dcolumn}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amscd}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{xfrac}
\usepackage{braket}
\usepackage{bm}   % bold math
\usepackage{bbm}
\usepackage{verbatim}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\usetikzlibrary{positioning}
\usetikzlibrary{plotmarks}
\usepackage{pgfplots}
\pgfplotsset{compat=newest}

\tikzstyle{vaucanson}=[
  node distance=2.5cm,
  bend angle=15,
  auto,
  % For some reason, the loop direction cannot be overwritten if we set the
  % style for "every loop" to be "->".  Curiously, this doesn't seem to be
  % an issue for "every edge".
  every loop/.style={},
  every edge/.style={->,draw=black,line width=1.2,>=latex,shorten <=1pt,shorten >=1pt},
  every state/.style={draw=black,line width=2,font=\large},
  loop right/.style={right,out=22,in=-22,loop},
  loop above/.style={above,out=112,in=68,loop},
  loop left/.style={left,out=202,in=158,loop},
  loop below/.style={below,out=292,in=248,loop},
  loop above right/.style={right,out=67,in=23,loop},
  loop above left/.style={left,out=157,in=113,loop},
  loop below left/.style={left,out=247,in=203,loop},
  loop below right/.style={right,out=337,in=293,loop},
]

\newcommand{\Symbol}[1]{\textcolor{blue}{#1}}
\newcommand{\Edge}[2]{$#1|\Symbol{#2}$}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\Label}[1]{{\footnotesize $\Symbol{#1}$}}

% \ifpdf
%   \usepackage[pdftex]{graphicx}
% \else
%   \usepackage[dvips]{graphicx}
% \fi

\theoremstyle{plain}    \newtheorem{Lem}{Lemma}
\theoremstyle{plain}    \newtheorem*{ProLem}{Proof}
\theoremstyle{plain}    \newtheorem{Cor}{Corollary}
\theoremstyle{plain}    \newtheorem*{ProCor}{Proof}
\theoremstyle{plain}    \newtheorem{The}{Theorem}
\theoremstyle{plain}    \newtheorem*{ProThe}{Proof}
\theoremstyle{plain}    \newtheorem{Prop}{Proposition}
\theoremstyle{plain}    \newtheorem*{ProProp}{Proof}
\theoremstyle{plain}    \newtheorem*{Conj}{Conjecture}
\theoremstyle{plain}    \newtheorem*{Rem}{Remark}
\theoremstyle{plain}    \newtheorem{Def}{Definition}
\theoremstyle{plain}    \newtheorem*{Not}{Notation}
\theoremstyle{plain}    \newtheorem{Alg}{Algorithm}

\input{cmechabbrev}

%\addtolength{\abovedisplayskip}{-.05in}
%\addtolength{\belowdisplayskip}{-.05in}
%\addtolength{\dbltextfloatsep}{-.10in}
%\addtolength{\abovecaptionskip}{-.10in}
%\addtolength{\belowcaptionskip}{-.10in}
\parskip 0pt

\renewcommand{\H}{\operatorname{H}}
\renewcommand{\I}{\operatorname{I}}

\newcommand{\alert}[1]{\textbf{\textcolor{red}{#1}}}
\newcommand{\old}[1]{\textbf{\textcolor{blue}{#1}}}

\newcommand{\edge}[1] {\stackrel{\Symbol{#1}}{\rightarrow}}

\colorlet {R_color}    {blue}
\colorlet {k_color}    {black!30!green}

% TUGboat, Volume 0 (2001), No. 0
% For comparison, the existing overlap macros:
% \def\llap#1{\hbox to 0pt{\hss#1}}
% \def\rlap#1{\hbox to 0pt{#1\hss}}
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{%
\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{%
\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{%
\clap{$\mathsurround=0pt#1{#2}$}}
%=================================================================

\begin{document}

\title{Signatures of Infinity:\\
Nonergodicity and Resource Scaling in\\
Prediction, Complexity, and Learning}

\author{James P. Crutchfield}
\email{chaos@ucdavis.edu}
\affiliation{Complexity Sciences Center and Department of Physics, University of
  California at Davis, One Shields Avenue, Davis, CA 95616}

\author{Sarah Marzen}
\email{smarzen@berkeley.edu}
\affiliation{Department of Physics, University of California at Berkeley,
Berkeley, CA 94720-5800}

\date{\today}
\bibliographystyle{unsrt}

% ************************* ABSTRACT *************************
\begin{abstract}
We introduce a simple analysis of the structural complexity of infinite-memory
processes built from random samples of stationary, ergodic finite-memory
component processes. Such processes are familiar from the well known multi-arm
Bandit problem. We contrast our analysis with computation-theoretic and
statistical inference approaches to understanding their complexity. The result
is an alternative view of the relationship between predictability, complexity,
and learning that highlights the distinct ways in which informational and
correlational divergences arise in complex ergodic and nonergodic
processes. We draw out consequences for the resource divergences that
delineate the structural hierarchy of ergodic processes and for
processes that are themselves hierarchical.

\vspace{0.2in}
\noindent
{\bf Keywords}: mutual information, excess entropy, statistical learning theory
%computational complexity,
%Kolmogorov-Chaitin complexity, statistical learning theory, Akaike information
%criterion, minimum description length, asymptotic normality

\end{abstract}

\pacs{
02.50.-r  %  Probability theory, stochastic processes, and statistics
89.70.+c  %  Information science
05.45.Tp  %  Time series analysis
02.50.Ey  %  Stochastic processes
% 02.50.Ga  %  Markov processes
% 05.20.-y  %  Classical statistical mechanics
% 05.45.-a  %  Nonlinear dynamics and nonlinear dynamical systems
% 89.75.Kd  %  Complex Systems: Patterns
}
%
\preprint{Santa Fe Institute Working Paper 15-03-XXX}
\preprint{arxiv.org:1503.XXXX [physics.gen-ph]}

\maketitle

% ****************************************************************

%\tableofcontents
\setstretch{1.1}

% Handy abbreviations in the following
\newcommand{\Abet}{\ProcessAlphabet}
\newcommand{\MS}{\MeasSymbol}
\newcommand{\ms}{\meassymbol}
\newcommand{\SSet}{\CausalStateSet}
\newcommand{\St}{\CausalState}
\newcommand{\st}{\causalstate}
\newcommand{\MxSt}{\AlternateState}
\newcommand{\MxSSet}{\AlternateStateSet}
\newcommand{\mxst}{\mu}
\newcommand{\mxstt}[1]{\mu_{#1}}
\newcommand{\StartMS}{\bra{\delta_\pi}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

%Much of experimental physics uses data to estimate constants---the electron's
%charge-to-mass ratio or a complex material's critical exponents, for example.
%In this kind of data-driven science, given a particular parametrized model, we
%fit a model \emph{to} data. However, this begs the question of where such a
%good models come from in the first place. Especially outside of physics, a
%reasonable model is almost never known \emph{a priori}. Faced with this, many
%instead try to find simple and physically reasonable models that fit
%observations well. This is a different, and perhaps more modern, data science:
%Use data to choose a model. More prosaically, this task is called \emph{model
%selection}. It is far harder than estimating parameters from data. Both
%tasks---estimating parameters and model selection---in effect assume an
%observer with a collection of parameterized models in hand. If this observer
%does not include a ``correct'' model in her collection, then she will not
%manage to learn the true model, no matter how much data she has been given.
%This is where we run into the one of the most fundamental problems in data
%science: Choosing one among a large number of possible models is
%computationally intractable. What criteria can we use to restrict the
%collection of models that we choose between?

Truly complex stochastic processes---the \emph{infinitary processes}
\cite{Crut01a} whose mutual information between past and future
diverges---arise in many physical and biological systems
\cite{Crut89e,Bial00a,Trav11b,Debo12a}, such as those in critical states. They
are implicated in many natural phenomena, from the geophysics of earthquakes
\cite{Turc97a} and physiological measurements of neural avalanches
\cite{Begg03a} to semantics in natural language \cite{Debo11a} and cascading
failure in power transmission grids \cite{Dobs07a}. Their apparent infinite
memory makes empirical estimation and modeling particularly challenging. The
difficulty is reflected in the computational complexity of
inference \cite{Kear94a}: the
resources required to predict and model them diverge in sample size, in memory
for storing model parameters, and in memory required for prediction. Resource
scaling, an analog of the venerable technique of finite-size scaling in
statistical mechanics, suggests that for infinitary processes we look for
statistical signatures that track divergences. Since resource divergences are
sensitive to a process's inherent randomness and organization, one hopes that
their scaling forms are uniquely revealing indicators of process complexity and
can guide the selection of appropriate models.

To date, though, there are few tractable constructions with which to explore
possible general relationships between prediction, complexity, and learning for
infinitary processes. One of the few tractable and general constructions is the
class of \emph{Bandit processes} constructed from repeated trials of an
experiment whose properties are, themselves, varying stochastically from trial
to trial \cite{Cove70a,Berr72a}. Even if each individual trial is a realization
generated by a stationary process with finite memory and exponentially decaying
correlations, the resulting process over many trials can be infinitary
\cite{Bial00a,Trav11b,Debo12a}.

Why can the past-future mutual information of Bandit processes diverge?
The answer is remarkably simple: Bandit processes are nonergodic. More to the
point, the divergence is driven by memory in the nonergodic part of their
construction---the mechanism in each trial that selects and then remembers the
operant ergodic component. Here, we use that insight to provide a simple,
alternative derivation of information divergence for this class of infinitary
process: a structural complexity scaling that directly accounts for
nonergodicity.

Information divergence in Bandit processes has been interpreted as reflecting a
universal property of learning: a unique indicator of the number of process
parameters \cite{Bial00a}. The derivation presented here recovers the
connection between the complexity of parameter estimation and divergence in
past-future information.  However, it also identifies other structural
features, such as infinitary ergodic components, that can drive divergences.
Thus, information divergences in Bandit processes reflect particular structural
properties of this class, rather than overarching principles of prediction,
complexity, and learning for infinitary processes. Nonetheless, the issues
raised highlight the need for a more balanced view of truly complex processes
and their challenges. We hope our simplified analysis introduces tools
appropriate to further, detailed scaling analysis of both ergodic and nonergodic
infinitary processes.

Analyzing structural complexity is often conflated with statistical and
computation-theoretic approaches to complex processes. To ameliorate this, the
next section reviews these alternatives. Then we move on to construct Bandit
processes and analyze their structural complexity. We then discuss the results,
draw out contrasts with computation-theoretic and statistical approaches,
highlight the structural hierarchy of ergodic processes, and close with a brief
discussion of hierarchical processes with nested organization.

\section{Prediction, Complexity, and Learning}
\label{sec:PCL}

There is a relationship between, on the one hand, the inherent unpredictability
and memory in a process and, on the other, the difficulty of learning a model
from time series samples and predicting the time series. Alternative framings
lead to different views of this relationship. There are those that attempt to
exactly describe a time series, those that try to express persistent
regularities, and those that consider the consequences for inference. Their
methods are closely related.

The \emph{Kolmogorov-Chaitin complexity} monitors the computational
resources---specifically, length of the minimal program for a given Universal Turing Machine (UTM)---required to reconstruct an individual time series
\cite{Kolm65,Chai66,Mart66a,Kolm83,Brud83,Vita93a}. It is a measure of
randomness: A random time series has no smaller description than itself.
Elaborating on this, \emph{logical depth} \cite{Benn88} and
\emph{sophistication} \cite{Kopp91a} track complementary computational
resources. Logical depth is the number of compute steps the minimal UTM program
requires to generate the time series.  Sophistication is the length of
that part of the UTM program which captures regularities and organization,
effectively discounting the time series' irreducible randomness. All these are
uncomputable, though, even if one is given a generative model.

Fortunately, for a process' typical realizations the Kolmogorov-Chaitin
complexity grows linearly with time series length, with coefficient equal to
\emph{Shannon source entropy rate} $\hmu$ (a measure of a process' unpredictability)
and offset equal to the \emph{statistical complexity} $\Cmu$ (a measure of a process'
memory) \cite[and references therein]{Crut12a}. Given a generative model called
the \emph{\eM}, both the entropy rate and statistical complexity are
computable; if the \eM\ is finite, they are calculable in closed form
\cite{Crut13a}.

We say that $\hmu$, $\Cmu$, and the finite-time excess entropy discussed later are intrinsic measures of a process' structure, randomness, and organization.  By \emph{intrinsic}, we mean that these measures exist independently of the amount of data that we have observed.  The aforementioned algorithmic complexities explicitly depend on the amount of data seen so far, but if the process is ergodic, then algorithmic complexities are also (almost always) intrinsic to a process in the limit of an arbitrarily large amount of data.

Such analyses of intrinsic properties should be contrasted with how statistical
inference approaches complex processes. Statistical learning theory
\cite{Mack03a,Hast11a} analyses and machine learning complexity controls
\cite{Wall87a, Riss89a, Akai74a, Akai77a} are not intrinsic in the sense that
they show how to choose the best in-class model, but the choice of that class
remains subjective. The problem of out-of-class modeling always exists as a
practical necessity, but it is rarely, if ever, tackled directly.  Of course,
in the happy circumstance a correct generative model is in-class, then one has
identified something intrinsic about a process. This, however, begs the
question of discovering the class in the first place. And, practically, such
luck is rarely the case.  Worse, when they do not work well, complexity
controls give no prescription for choosing an alternative class.

%In general, data scientists wish to infer the ``minimally complex'' model which is ``maximally consistent'' with some finite amount of data, and different frameworks have different ways of quantifying complexity and consistency.  The \emph{minimum message length} \cite{Wall87a} and \emph{minimum description length} \cite{Riss89a} tally the cost of encoding the model and encoding the total error, and search for the model with minimal total cost.  \emph{Maximum a posteriori} approaches look for the model which maximizes the probability of the model given data, and here, model complexity is quantified by the evidence and consistency is quantified by the likelihood \cite{}.  Akaike's information criterion is the large data limit of the latter prescription \cite{}.

%How do a process's intrinsic properties---randomness, memory, active
%degrees-of-freedom, number of parameters, and the like---affect statistical
%inference of generative models \cite{Solo64ab}?
%There are two issues of
%note: sample-size complexity and model complexity. \alert{You describe ``two issues of note'' here and ``two broad settings'' somewhere later, so what are you trying to say?  I think both sample size complexity and model complexity fall within the realm of in-class modeling, and you should fucking point that out now.}  \emph{Sample-size
%complexity} is framed as the problem of statistical parameter estimation: Given
%a particular model, how does the estimation error in its parameters scale as a
%function of sample size? \alert{Is sample size complexity a term that you made up?  I don't think it deserves the name ``complexity''.  I'd rather not introduce this as a type of complexity at all.  I don't care that our paper is about ``sample-size complexity'', it fucking doesn't deserve this name.}  Then, more generally, given a range of differently
%parametrized models in a specified class, how does sample size affect
%\emph{model complexity}; that is, how does one choose the appropriate number of
%model parameters? This introduces the problem of \emph{generalization}: Select
%the model with a sufficient set of parameters to reduce prediction error, but
%not overfit to statistical fluctuations in a given sample.
%
%A range of operational prescriptions has been provided, each trading off
%estimation error against model complexity. Most notably, there are
%code-theoretic approaches that parallel the formal setting of
%Kolmogorov-Chaitin complexity. They represent a time series as a two-part
%encoding: the model (the regularities) and the error (data not predicted by the
%model). These are found in the principles of \emph{minimum message length}
%\cite{Wall87a} and \emph{minimum description length} \cite{Riss89a}. The
%lengths tally the cost of encoding the model and encoding the error data. Given
%a finite sample, if one selects the model with the smallest encoding length,
%then the generalization error over many realizations is minimized. Such
%sample-size effects are also addressed via more modern Bayesian approaches to
%inferring a process's Markov model from time series \cite{Stre07a}.

%This synopsis of how Kolmorogov-Chaitin complexity, parameter estimation,
%sample size, and generalization frame the relationship between complexity,
%prediction, and learning is important backdrop for the main question of
%interest to us here. This is \emph{structural complexity}: Given a process,
%determine the appropriate model class and parameter space dimension. It is
%important to emphasize that this issue on its own does not concern sample size.
%It assumes, in a sense, that there is more than sufficient data to estimate
%model parameters as needed.  \alert{This makes it sound like model complexity is somehow only about statistical fluctuations, but model complexity is also about choosing the parameter space dimension.  Maybe you want to say that parameter space dimension is solely the realm of model complexity, and model class (topology) is solely the realm of structural complexity?  But, then, the terminology doesn't really make so much sense to me.  When someone says model complexity, I don't think parameter space dimension.}
%
%\alert{I don't think this text makes it clear enough that model order selection is basically the same question of model complexity from before, choosing the appropriate number of model parameters.}
%
%There are two broad settings. The first is that encountered most generally, but typically ignored: \emph{out-of-class modeling}, in which we do not know a priori the appropriate model class, but must guess a class to get started. (Despite its obvious open-endedness, one can make progress on this by moving up a hierarchy, from restricted to more general model classes; see, e.g., Ref. \cite{Stre07a}.) The other, tractable setting is \emph{in-class modeling}, where through design, fundamental theory, or something else, we know the appropriate class with which to model a process. Then we are concerned as to which model is best and this boils down to determining the correct parameter space dimension.

%In this way, in-class modeling restricts structural complexity to the
%problem of \emph{model-order selection}: Find the model with the smallest set
%of parameters that maximizes the likelihood the model generated the process.
%One of the earliest approaches is Akaike's \emph{information criteria} (AIC) \cite{Akai74a,Akai77a}. Within a set of candidates AIC selects the model $M$ minimizing $2 \ln |M| - 2 \ln \Prob(M)$, where $|M|$ is the number of parameters and $\Prob(M)$ is the model's likelihood for the given data. Thus, AIC depends on the sample size, but in the large-sample limit it selects the model with minimal parameters that saturates the likelihood.

%Finally, we arrive at a question which is more directly related to this paper: How is our ability to infer the \eM\ or any other model consistent with a process affected by its intrinsic properties, e.g. randomness, memory, active
%degrees-of-freedom, number of parameters, and the like \cite{Solo64ab}?

Intrinsic complexity characterizations have been most constructively and thoroughly developed for
finite-memory, finite-randomness processes, despite the fact that many
important natural processes are infinitary. The latter include the critical
phenomena \cite{Binn92a} of statistical physics and the routes to chaos in
nonlinear dynamics \cite{Crut89e}, to mention only two. They exhibit
arbitrarily long-range spatiotemporal correlations, infinite memory, and
infinite parameter space dimension. The relationship between prediction,
complexity, and learning is especially interesting when confronted with infinitary
processes, and we re-investigate that relationship for nonergodic Bandit processes.

%How is one to empirically model infinitary processes, especially
%when we always only have access to finite samples?  A first step is assume
%adequate samples, temporarily skirting the issue of sample size. And that is
%what we do here: analyze the structural complexity of infinitary Bandit-like
%processes.

%
%Paralleling Refs. \cite{Crut89e,Bial00a}, we explore using the asymptotic rates
%of mutual-information divergence as a function of past-future time horizons to
%quantify a process's structural complexity class. The working hypothesis behind
%this is that the faster the divergence, the more structurally complex the
%class. And the consequence is that it is harder to learn a predictive model of
%such processes. This seems quite reasonable but, as we argue, when applied to
%nonergodic processes the results do not capture the general case. Prediction,
%complexity, and learning for infinitary processes are much richer than
%a singular focus on information divergences would suggest.

\section{Bandit Process Construction}
\label{sec:2}

The simplest construction of a Bandit process is the following. Consider the
stochastic process generated by a biased coin whose bias $\textbf{P}$ is itself
a random variable. First, a coin bias $p$ is chosen from a user-specified
distribution $\Prob(\textbf{P})$; next, a bi-infinite sequence $\mathbf{x}^1 =
\ms_{-1} \ms_0 \ms_1 \ms_2 \ldots$ is generated from a coin with this
particular bias; then, this is repeated for an arbitrarily large number of such
trials; generating an ensemble $\{\mathbf{x}^1, \mathbf{x}^2, \mathbf{x}^3,
\ldots\}$ of sequences at different biases. The process of interest is this
sequence ensemble. We denote the random variable block between times $a$ and
$b$, but not that at time $b$, as $X_{a:b} = X_a X_{a+1} \ldots X_{b-1}$. We
suppress denoting indices that are infinite. And so, the process of interest is
denoted $X_{:}$. To denote the random variable block conditioned on a random
variable $Z$ taking realization $z$ we use $\MS_{a:b} | Z=z$. So here, the
subprocess $X_{:}|\textbf{P}=p$ is that produced by a coin with bias $p$.

A single one of these bi-infinite sequences comes from an ergodic process that
is memoryless in every sense of the word. In particular, since in each trial
past and future are independent, the conditional past-future mutual information
$I[\MS_{-M:0};\MS_{0:N}|\textbf{P}=p]$ vanishes for any $M$, $N$, and $p$.
However, each of these bi-infinite chains is statistically distinct. The mean
number of heads, say, in one is very different than the mean number of heads in
another. For sufficiently long chains, such differences are almost surely not
the consequence of finite-sample fluctuations.

The overall process $\MS_{:}$ does not distinguish between sequences generated
by different biased coins. So, by making the coin bias a random variable, the
past and future are no longer independent. Both share information about the
underlying coin bias $p$. As we will now show, the shared information or
\emph{excess entropy} $\EE(M,N) = I[\MS_{-M:0};\MS_{0:N}]$ diverges with $M$
and $N$ when $\textbf{P}$ is a continuous random variable.

\section{Information Analysis}
\label{sec:InfoAnal}

To see why, we abstract to a more general case. What follows is an alternative,
direct derivation of results in Ref. \cite[Sec. 4]{Bial00a} that, due to its
simplicity, lends additional transparency to the mechanisms driving the
divergence.

Let $\Theta$ be a random variable with realizations $\theta$ in a (parameter)
space of dimension $K$. $\Theta$ has some as-yet unspecified relationship with
observations $\MS_{:} = \ldots \MS_{-2},\MS_{-1},\MS_0,\MS_1,\ldots$.
We can always perform the following information-theoretic
decomposition of the composite process's excess entropy:
\begin{align}
I[\MS_{-M:0};\MS_{0:N}] & = I[\MS_{-M:0};\MS_{0:N}|\Theta] \nonumber \\
  & \quad + I[\MS_{-M:0};\MS_{0:N};\Theta]
  ~.
\label{eq:1}
\end{align}
The first term quantifies the range of temporal correlations of the observed
process \emph{given} $\Theta$, and the second term quantifies the dependencies
between past and future purely due to $\Theta$. When the fixed-parameter
process $\MS_{:}|\Theta=\theta$ is ergodic and the composite process $\MS_{:}$
is not, then Eq.~(\ref{eq:1}) can be viewed as a decomposition of
$I[\MS_{-M:0};\MS_{0:N}]$ into ergodic and nonergodic contributions, respectively.

The second term $I[\MS_{-M:0};\MS_{0:N};\Theta]$ is a multivariate mutual
information \cite{Jame11a} or \emph{co-information} \cite{Bell03a}.
It is closely related to
parameter estimation, as expected \cite{Bial00a}, since it provides information
about the dimension $K$ of $\Theta$. Standard information-theoretic identities
yield:
\begin{align}
I[\MS_{-M:0};\MS_{0:N};\Theta] & = H[\Theta] + H[\Theta|\MS_{-M:N}] \nonumber \\
  & \quad - H[\Theta|\MS_{-M:0}] - H[\Theta|\MS_{0:N}]
  ~.
\label{eq:2}
\end{align}
The first term $H[\Theta]$ quantifies our intrinsic uncertainty in the bias.
When $\Theta$ is a continuous random variable, $H[\Theta]$ is a differential
entropy. The subsequent terms describe how our uncertainty in $\Theta$
decreases after seeing blocks of lengths $M+N$, $M$, or $N$.

Altogether, Eqs.~(\ref{eq:1}) and (\ref{eq:2}) give:
\begin{align}
I[\MS_{-M:0};\MS_{0:N}]
  & = I[\MS_{-M:0};\MS_{0:N}|\Theta] + H[\Theta] \nonumber \\
  & \quad + H[\Theta|\MS_{-M:N}] - H[\Theta|\MS_{-M:0}] \nonumber \\
  & \quad - H[\Theta|\MS_{0:N}]
  ~.
\label{eq:3}
\end{align}
Thus, assuming one chose a prior with finite entropy $H[\Theta]$, divergences
in $I[\MS_{-M:0};\MS_{0:N}]$ can come from divergences in
$I[\MS_{-M:0};\MS_{0:N}|\Theta]$ or from divergences in $H[\Theta|\MS_{-M:N}] -
H[\Theta|\MS_{-M:0}]- H[\Theta|\MS_{0:N}]$.

Let's take the cases covered in Ref. \cite[Secs. 4.1-4.4]{Bial00a}. There,
$\Theta$ consists of the model parameters, $\theta$ are realizations of
$\Theta$, and $\MS_{:}|\Theta=\theta$ consists of (noisy, potentially
temporally correlated) sequences generated by the model with parameters
$\theta$. For instance, $\Theta$ could be the firing rate of a Poisson neuron
and $\MS_{:}|\Theta=\theta$ could be the time-binned spike trains at firing
rate $\theta$. Or, $\Theta$ could be transition probabilities in a finite
Hidden Markov Model (HMM) and $\MS_{:}|\Theta=\theta$ could be the generated
process given transition probabilities $\theta$. The result, in any case, is a
nonergodic process $\MS_{:}$ constructed from a mixture of ergodic component
processes $\MS_{:}|\Theta=\theta$.

In these examples, the component-process excess entropy
$I[\MS_{-M:0};\MS_{0:N}|\Theta] = \langle
I[\MS_{-M:0};\MS_{0:N}|\Theta=\theta]\rangle_{\theta}$ does not diverge with
$M$ or $N$, since finite HMMs have finite excess entropy, which is bounded by
the internal state entropy \cite{Trav11b,Lohr09a}. In fact, the excess entropy
for many ergodic stochastic processes is finite, even if generated by
infinite-state HMMs. Any divergence in the composite process
$I[\MS_{-M:0};\MS_{0:N}]$ therefore comes from divergences in
$H[\Theta|\MS_{-M:N}]-H[\Theta|\MS_{-M:0}]-H[\Theta|\MS_{0:N}]$. 

Since the composite process includes sequences $\mathbf{\ms}^i$ from trials
with different $\theta$, one's intuition might suggest that
$\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$ is multimodal for most
$\ms_{-M:0}$. However, existing results \cite{walker1969asymptotic,
heyde1979asymptotic, sweeting1992asymptotic, weng2008asymptotic} on the
asymptotic normality of posteriors carry over to this setting, since they
essentially rely on the log-likelihood function $\log
\Prob(\MS_{-M:0}=\ms_{-M:0}|\Theta=\theta)$ being sufficiently well behaved.

%Here, since $\MS_{:}|\Theta=\theta$ are ergodic processes, various statistical learning theory results (e.g. from Ref. \cite{heyde1979asymptotic, sweeting1992asymptotic, weng2008asymptotic}) imply that asymptotic normality for $\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$, $\Prob(\Theta=\theta|\MS_{0:N}-\ms_{0:N})$, and $\Prob(\Theta=\theta|\MS_{-M:N}=\ms_{-M:N})$ in the large $M$, $N$ limit under various combinations of rather weak conditions.

For instance, consider the Bandit process construction of Sec.~\ref{sec:2}.
A crude derivation of the asymptotic normality of $\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$ \cite{hartigan1983asymptotic} starts with Bayes Rule:
%\begin{widetext}
\begin{align*}
\Prob(\Theta=\theta & | \MS_{-M:0}=\ms_{-M:0}) \\
   & = \frac{\Prob(\MS_{-M:0}=\ms_{-M:0}|\Theta=\theta) 
   \Prob(\Theta=\theta)}{\Prob(\MS_{-M:0}=\ms_{-M:0})}
   ~.
\end{align*}
%\end{widetext}
The denominator $\Prob(\MS_{-M:0}=\ms_{-M:0})$ is quite complicated to calculate, but
this normalization factor does not affect the $\theta$-dependence of
$\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$. More to the point, the prior's
contribution $\Prob(\Theta=\theta)$ is dwarfed by the likelihood:
\begin{align*}
\Prob(|\MS_{-M:0}=\ms_{-M:0} & | \Theta=\theta) \\
  & = \theta^{\sum_{i=0}^{M-1} \ms_i} (1-\theta)^{M-\sum_{i=0}^{M-1} \ms_i}
  ~,
\end{align*}
in the large-$M$ limit.  Let $\theta^*$ be the unique maximum of
$\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$: $\theta^* =
\frac{1}{M}\sum_{i=0}^{M-1} \ms_i + O(1/M)$. Taylor-expanding $\log
\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$ about $\theta^*$ suggests that
$\Prob(\Theta=\theta|\MS_{-M:0}=\ms_{-M:0})$ is approximately normal in the
large-$M$ limit, with variance decaying as $\sim 1/M$. (Any one of the many
sources \cite{walker1969asymptotic, heyde1979asymptotic, sweeting1992asymptotic, weng2008asymptotic}
on asymptotic normality of posteriors provides rigorous and generalized
statements.)

Armed with such asymptotic normality, we now turn our attention to find the
asymptotic form of $H[\Theta|\MS_{-M:0}=\ms_{-M:0}]$,
$H[\Theta|\MS_{0:N}=\ms_{0:N}]$, and $H[\Theta|\MS_{-M:N}=\ms_{-M:N}]$ in the
large-$M$ and -$N$ limits. The differential entropy of a normal distribution
is $\frac{1}{2}\log |\det \Sigma|$, where $\Sigma$ is the covariance matrix;
here, $\det \Sigma \sim 1/M$. This captures the error distribution
for each of the $K$ parameters. So, this and asymptotic normality of the
posterior imply that:
\begin{align*}
H[\Theta|\MS_{-M:0}=\ms_{-M:0}] &\sim -\frac{K}{2}\log M
  ~,
\end{align*}
plus corrections of $O(1)$ in $M$, and thus:
\begin{align*}
H[\Theta|\MS_{-M:0}] &\sim -\frac{K}{2}\log M
  ~,
\end{align*}
where $K$ is the parameter space dimension.

At first blush, the result is counterintuitive. In the limit that $M$ and $N$ tend to
infinity, and we see longer and longer sequences $\ms_{-M:0}$, we become more
certain as to $\Theta$'s value. This increasing certainty should mean
that the conditional entropy $H[\Theta|\MS_{-M:0}=\ms_{-M:0}]$ vanishes.
However, if $\Theta$ is a continuous random variable (such as a Poisson rate),
then $H[\Theta|\MS_{-M:0}=\ms_{-M:0}]$ is a differential entropy.  As our
variance in $\Theta|\MS_{-M:0}=\ms_{-M:0}$ decreases to $0$, the differential
entropy $H[\Theta|\MS_{-M:0}=\ms_{-M:0}]$ diverges to negative infinity. It is
exactly this well known divergence that causes a divergence in
$I[\MS_{-M:0};\MS_{0:N}]$ for the nonergodic processes we are considering.

From these results and Eq. (\ref{eq:3}), one has:
\begin{align*}
I[\MS_{-M:0};\MS_{0:N};\Theta] \sim \frac{K}{2}\log \frac{MN}{M+N}
  ~.
\end{align*}
And, recalling that the ergodic-component information does not diverge,
we immediately recover:
\begin{align}
I[\MS_{-M:0};\MS_{0:N}] \sim \frac{K}{2}\log \frac{MN}{M+N}
  ~.
\end{align}
Lower-order terms in $M$ and $N$ include the expected log-determinant of the
Fisher information matrix for maximum likelihood estimates of $\Theta$
\cite{Lehm98a}.

A similar information-theoretic decomposition can be used to upper-bound the
excess entropy of ergodic processes as well. For instance, App.~\ref{sec:Spin},
uses a similar decomposition to show that the temporal excess entropy of an
Ising spin on a two-dimensional Ising lattice at criticality is finite.

%\section{Discussion}

%\subsection{Forms of Information Divergence}

%To summarize, as $M, N \to \infty$, there is a logarithmic divergence in excess
%entropy, the coefficient of which is the number $K$ of process parameters. For
%Bandit-like processes the coefficient identifies the number of ergodic
%components. Practically, this suggests that one could use the scaling of empirical
%estimates of past-future information as a function of sequence length to
%estimate a process's parameter space dimension. Mathematically and somewhat
%surprisingly, the derivation shows that the reason Bandit-like processes
%exhibit information divergences derives from the role nominally finite-sample
%effects (asymptotic normality) play in a framework that otherwise assumes
%arbitrarily large amounts of data.

Logarithmic divergences in excess entropy also occur in stationary ergodic
processes, such as exhibited at the onset of chaos through period-doubling
\cite{Crut89e}. And, alternative scalings are known, such as power-law
divergences \cite[Sec. 4.5]{Bial00a}. For natural language texts there is
empirical evidence that the excess entropy diverges. One form is referred to as
Hilberg's Law \cite{Ebel91a,Ebel94a,Debo11a}: $I[\MS_{-N:0};\MS_{0:N}]
\propto \sqrt{N}$.

In contrast with Sec. \ref{sec:InfoAnal}'s rather direct calculation, it is far
less straightforward to analyze these power-law divergences:
\begin{align}
I[\MS_{:0};\MS_{0:N}] \sim N^\gamma
  ~,
\end{align}
with $\gamma \in [0,1)$. While there are results on asymptotics of posteriors
for nonparametric Bayesian inference, many aim to establish asymptotic normality
of the posterior; e.g., as in Refs. \cite{wasserman1998asymptotic,
ghosal2000asymptotic}. As far as we know, no result yet recovers the
aforementioned power-law divergence; likely, since existing asymptotic analyses
avoid the essential singularity for the prior utilized in Ref. \cite[Sec.
4.5]{Bial00a} to obtain power-law divergence.

%\subsection{Intrinsic Information versus Statistical Inference}
%
%Such analyses of intrinsic properties should be contrasted with how statistical
%inference approaches complex processes. Statistical learning theory
%\cite{Mack03a,Hast11a} analyses are not intrinsic in the sense that they show
%how to choose the best in-class model, but the choice of that class remains
%subjective. The problem of out-of-class modeling always exists as a practical
%necessity, but it is rarely, if ever, tackled directly. Though they compare
%models of different sizes, approaches employing Sec. \ref{sec:PCL}'s
%information criteria---e.g., AIC---are also nonintrinsic since they require an
%explicit, practically enumerable model class. Of course, in the happy
%circumstance a correct generative model is in-class, then one has identified
%something intrinsic about a process. This, however, begs the question of
%discovering the class in the first place. And, practically, such luck is rarely
%the case.  Worse, when they do not work well, information criteria give no
%prescription for choosing an alternative class.
%
%This challenge suggests one analyze intrinsic properties, such as the
%algorithmic measures reviewed in Sec. \ref{sec:PCL}. Uncomputable in general,
%they are very difficult even to approximate. One reason is that they require
%deducing the correct minimal model (UTM). They do,
%however, capture resources required to encode regularities and randomness; the
%Kolmogorov-Chaitin complexity captures both. Fortunately, when adapted to
%describe ensembles, they are directly related to such information measures as
%the statistical complexity $\Cmu$ (regularities) and source entropy rate $\hmu$
%(randomness) \cite{Crut12a}. Aside from Bandit-like processes, in the general
%setting $\EE(M,N)$ is not obviously encoding either regularities in an
%underlying mechanism or its randomness. As we showed, although scaling does
%help identify model class---ergodic components controlled by continuous random
%variables---it does \emph{not} reveal the structure of the underlying
%generative mechanism. Nonetheless, knowing the number of parameters (or its
%scaling) in a process restricts an observer's model class considerably.

\section{Discussion}

We investigated one large, but particular class of infinitary processes in
terms of how information measures diverge; recovering, in short order, a
previously reported logarithmic divergence in Bandit-like process past-future
mutual information. Practically, this suggests that one could use the scaling of empirical
estimates of past-future information as a function of sequence length to
estimate a process's parameter space dimension. Mathematically and somewhat
surprisingly, the derivation shows that the reason Bandit-like processes
exhibit information divergences derives from the role nominally finite-sample
effects (asymptotic normality) play in a framework that otherwise assumes
arbitrarily large amounts of data.

%One must note, in fairness, that estimating the
%past-future mutual information $I[\MS_{-M:0};\MS_{0:N}]$ is not necessarily free of
%model-class assumptions. A moment's reflection shows that the effective model
%class is that of histograms of length $M+N$ sequences; essentially, the class
%of joint distributions $\Pr(\MS_{-M:N})$. \alert{Do you mean that estimating the finite length excess entropy from actual data isn't free of model-class assumptions?  I agree with that, but your model assumption could be a unfilar HMM in order to estimate that particular information measure, i.e. we estimate \eM\ to get MSP to get $\hmu(M)$ to get $\EE(M)$.  More precision please.}  Thus, while the information
%divergence is apparently incisive, one is still left to wonder what other kinds
%of divergence-scaling might arise when employing other representations, such as
%the conditional distributions $\Prob(\MS_{0:N}|\MS_{-M:0})$ that are the basis
%for \eMs. \alert{What do you want them to do exactly?  Look at $\Cmu^{+_M}$?  Can you be more specific?} These alternative scalings too will be structurally informative.
%
%Indeed, it is well known that for most continuous-time stochastic processes $\hmu(M) = H[\MS_0|\MS_{-M:0}]$ diverges \cite{Gasp93a}. \alert{But that's just when you use discrete-time limits instead of going directly to a continuous time framework.} The statistical complexity $\Cmu$, too, is often infinite, even for discrete processes. For typical nonunifilar HMMs in which all pasts are even slightly predictively different, $\Cmu(M) \approx \hmu M$. This complicates using it to distinguish between infinitary process classes. In short, $\Cmu$ appears too sensitive to a process's internal state structure. Tellingly, $\EE(M,N)$ does not usually diverge, not for many of the processes where $\Cmu$ diverges. Moreover, when it diverges, then its rate of divergence indicates much about a process' underlying structure. Thus, while not obviously a measure of structure, for infinitary processes it is a very useful measure of organization. The lesson here is to use divergences to our advantage to detect structural complexity classes of finitary and infinitary processes.

\begin{figure}[htp]
\includegraphics[width=.35\columnwidth]{StationaryPredHierarchy_tikz2}
\caption{Prediction hierarchy for stationary ergodic processes: Each level
  describes a process class with finite informational quantities. A class above
  finitely models the processes in the class below. Classes are separated by
  divergence in the corresponding informational quantity. Moving up the
  hierarchy corresponds to it diverging. Example processes that are finitely
  presented at each level, but infinitely presented at the preceding lower
  level.
  \emph{Sofic}: typical unifilar HMMs, e.g., Even Process \cite{Crut01a};
%  \emph{Recurrent}: infinite transient causal states, e.g., in the Alternating
%  Biased Coin Process \cite{Trav11a}; 
%  \emph{Predictive}: countably infinite recurrent causal states in the Simple
%  Nonunifilar Source \cite{Crut01a};
  \emph{Generative}: typical nonunifilar HMMs \cite{Lohr09a};
  \emph{Finitary}: typical infinite nonunifilar HMMs;
  \emph{Infinitary}: highly atypical infinite HMMs with long-range memory,
  e.g., the ergodic construction in Ref. \cite{Trav11b}.
  }
\label{fig:Hierarchy}
\end{figure}

Section \ref{sec:InfoAnal}'s scaling analysis left open the possibility that
information divergences can be driven by the ergodic components themselves. So,
what is known about information divergences in ergodic processes?  An
information divergence hints at a structural level in the space of ergodic
processes; a space that is itself highly organized. This is seen in the
hierarchy of divergences separating processes into classes of distinct
architecture, depicted in Fig. \ref{fig:Hierarchy}. (See also Table 1, Fig. 18,
and Sec. 5 in Ref. \cite{Crut92c}.) Processes at each level are distinguished
by different scalings for their complexity and in how difficult they are to
learn and predict.

%The hierarchy can be succinctly described in terms of
%process \eMs\ \cite{Crut12a}: specifically, the cardinality of their transient and recurrent causal states. The broadest distinctions are whether or not these
%state sets are finite or infinite.

At the lowest level (\emph{Markov}) are processes described by finite \eMs\
with finite history dependence (finite Markov order $\MOrder$); e.g., those
described by existing Maximum Caliber models \cite{Presse13} or by measure
subshifts of finite type \cite{Lind95a}. Though very commonly posited as
models, they inhabit a vanishingly small measure in the space of processes
\cite{Jame10a}. At the next level (\emph{Sofic}) of structure are processes
described by \eMs\ with finite $\Cmu$.  These typically have infinite
Markov order; e.g., the measure-sofic processes.
%The next step up
%(\emph{Recurrent}) leads to processes with finite recurrent causal states, but
%a divergent number of transient causal states. An observer finds these
%processes difficult to synchronize to.
%The step up from finite- to infinite-recurrent state \eMs\ leads to processes
%(\emph{Predictive}) described by \eMs\ with a countably infinite set of
%recurrent causal states, but finite state-information ($\Cmu < \infty$). This
%implies finite average memory use, but infinite storage space. 
Above this level
are processes generated by general (that is, nonunifilar) HMMs with uncountable
recurrent causal states and divergent statistical complexity that, nonetheless,
have finite generative complexity, $C_\text{gen} < \infty$ \cite{Lohr09a}.
Processes at the \emph{generative} level not only have infinite Markov order
and storage, but also require a growing amount of memory for accurate
prediction. One consequence is that they are inherently unpredictable by any
observer with finite resources. Note, however, that predictability is
complicated at all levels by \emph{cryptic processes} \cite{Crut08b}---those
with arbitrarily small excess entropy, but large statistical complexity. When
the smallest generative model is infinite but the process still has short-term memory, we arrive at the class of
\emph{finitary} processes ($\EE < \infty$).

Processes with divergent excess entropy---infinitary processes---inhabit the
upper reaches of this hierarchy. Predicting such processes necessarily requires
infinite resources, but accurate prediction can also return infinite
dividends. We agree, here, with Ref. \cite{Bial00a}: the asymptotic rate of
information divergence is a useful proxy for process complexity. Historically,
this view appears to have been anticipated in Shannon's introduction of the
\emph{dimension rate} \cite[App. 7]{Shan48a} of an ensemble of functions:\begin{align*}
\lambda = \lim_{\delta \to 0} \lim_{\epsilon \to 0} \lim_{T \to
\infty}  \frac{N(\epsilon,\delta,T)}{T \log \epsilon}
  ~,
\end{align*}
where $N(\epsilon,\delta,T)$ is the smallest number of elements that can be
chosen such that all elements of the ensemble, apart from a set of measure
$\delta$, are within the distance $\epsilon$ of at least one of those chosen. 

However, it is as important to know which process mechanism drives the
divergence as it is to know the divergence rate. Infinitary Bandit processes
store memory entirely in their nonergodic component. Our analysis identified
the divergence in this memory with the well known divergence in the
differential entropy of highly peaked distributions of vanishing width.
Generalizing Bandit processes to have \emph{structured} ergodic components, we
now see that even finite \eMs\ trivially generate infinitary processes when
their transition probabilities are continuous random variables.

Thus, in this case, we also agree that information divergence is a ``necessary
but not sufficient'' criteria for process complexity \cite{Debo12a}. (Appendix
\ref{sec:Spin}, however, looks at critical phenomena in spin systems to call
out a caveat.) This leaves open a broad challenge to understand the sufficient
mechanisms for information divergences. For example, we have yet to develop
similar informational and computation-theoretic analyses for the infinitary
ergodic processes in Refs. \cite{Trav11b,Debo12a}.

Looking forward, the simplicity of our structural complexity analysis opens up
the possibility to better frame information in hierarchical processes
\cite[Sec. 5]{Crut92c}, such as the structural hierarchy in biology \cite[Fig.
6]{Shen06a}, epochal evolution \cite{Nimw96a}, and knowledge hierarchies in
social systems such as semantics in human language \cite{Chom56}. These are
processes in which multiple levels of mechanism are manifest and operate
simultaneously and in which each level is separated from those below via
phase transitions that lead to various signatures of informational and
structural divergence.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{-0.1in}
\acknowledgments
\vspace{-0.1in}

We thank N. Ay, W. Bialek, R. D'Souza, C. Ellison, C. Hillar, and I. Nemenman for useful conversations.
The authors thank the Santa Fe Institute for its hospitality during visits.
JPC is an SFI External Faculty member.
This material is based upon work supported by, or in part by, the
U. S. Army Research Laboratory and the U. S. Army Research Office under
contracts W911NF-12-1-0288, W911NF-13-1-0390, and W911NF-13-1-0340.
SM was funded by a National Science Foundation Graduate Student Research Fellowship and the U.C. Berkeley Chancellor's Fellowship.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\vspace{-0.1in}
\appendix
\vspace{-0.1in}

\section{Truly Complex Spin Systems?}
\label{sec:Spin}
\vspace{-0.1in}

Reference \cite{Debo12a} pointed out that many infinitary processes do not
satisfy intuitive definitions for complexity. It suggested that divergence in
$\EE$ is a ``necessary but not sufficient condition'' for a process being truly
complex. While intuitively compelling, perhaps divergent $\EE$ is not even a necessary condition. Let's explain.

Spin systems at criticality are one of the most familiar examples of truly
complex processes: global correlations emerge from purely local interactions
\cite{Binn92a}. Evidence of this complexity appears even if we are only allowed
to observe a single spin's interaction with another on the lattice. At the
critical temperature, the interaction has a power-law autocorrelation function;
at all other temperatures, the spin's autocorrelation function is
asymptotically exponential. The \emph{spatial} excess entropy of these
configurations appears to diverge at criticality \cite{Lau12a}, too. However,
does the \emph{temporal} excess entropy $\EE(M,N)$---roughly, the interaction a
single spin with itself at later times---also diverge at criticality?

Surprisingly, the excess entropy of the dynamics of a single spin on an Ising
lattice is finite, even at the critical temperature, \emph{unless} there are
nonlocal spatial interactions between lattice spins. Consider evolving the
lattice configurations via Glauber dynamics for concreteness \cite{Binn92a}.
That is, spin $j$'s next state $\sigma^j_{t+1}$ is determined stochastically by
its previous state $\sigma^j_t$ and its effective magnetic field $h^j_t =
\sum_{i} J_{ij} \sigma^i_t$. In other words, $h^j_t$ and $\sigma^j_t$ causally
shield the past $\overleftarrow{\sigma}^j_t$ from the future
$\overrightarrow{\sigma}^j_t$, implying that:
\begin{align*}
I[\sigma^j_{t-M:t}; \sigma^j_{t+1:t+N}|h^j_t]
  & = I[\sigma^j_t;\sigma^j_{t+1} | h^j_t] \\
  & \leq H[\sigma^j_t]
  ~.
\end{align*}
Given a finite set of spin values and local interactions, $h^j_t$ can only take
a finite number of values. Thus, $H[h^j_t] < \infty$, and so:
\begin{align*}
\big\vert I[\sigma^j_{t-M:t}; \sigma^j_{t+1:t+N};h^j_t] \big\vert
  & \leq H[h^j_t] \\
  & < \infty
  ~,
\end{align*}
as well.

A more familiar example makes this concrete. For the standard two-dimensional
Ising lattice $J_{ij} = J$, if $i$ and $j$ are nearest neighbors, and $J_{ij} =
0$, otherwise. There, $h^j_t$ can only take $5$ possible
values---$h^j \in \{0,~J,~2J,~3J$, and $4J\}$---giving:
\begin{align*}
\big\vert I[\sigma^j_{t-M:t}; \sigma^j_{t+1:t+N};h^j_t] \big\vert
  & \leq H[h^j_t] \\
  & \leq \log_2 5 ~\text{bits}
  ~.
\end{align*}

The information-theoretic decomposition in Eq.~(\ref{eq:1}) applies in this
particular situation. Here, observed variables $\MS_t$ are spins $\sigma_t$, and
the parameters $\Theta$ are replaced by $h^j$. The bounds above then directly
imply that $\EE(M,N) < \infty$ for all $M$ and $N$. In fact, for the standard
two-dimensional Ising lattice, we find that $\EE(-\infty,\infty) \leq 1 +\log_2
5 = 3.4$ bits. We expect excess entropy to diverge only when $h^j$ is a
continuous random variable. This can happen when $J_{ij}$ is nonzero for an
infinite number of $i$'s. However, this necessitates global, not local,
spin-spin couplings.

On the one hand, this analysis does not negate $\EE$'s utility as a generalized
order parameter \cite{Feld98a}. It is still likely maximized at the critical
point, even if its temporal version does not diverge. On the other, our
analysis shows that phenomena---here, spin lattices with purely local
couplings---do not necessarily have divergent $\EE$ even when many would
consider their dynamics to be truly complex when the system is critical.

At first glance, the analysis contradicts the experiments in Fig. $1$ of Ref.
\cite{Bial00a} for the Ising lattice with only local interactions. A more
careful look reveals that there is no contradiction at all. There, coupling
strengths were randomly changed every $400,000$ iterations, so the resultant time
series looked like a concatenation of samples from a Bandit
process. The analysis in Sec.~\ref{sec:InfoAnal} then predicts the
observed logarithmic scaling in Fig. $1$ there for $N \lesssim 25$. However, it also
implies that $\EE(-\infty,N)$ will stop increasing logarithmically at or before
$N = 400,000$.

%=================================================================
% References:
%=================================================================
% Use the following option to include external BibTeX files:
\bibliography{chaos}

\end{document}

soi.bbl
\begin{thebibliography}{10}

\bibitem{Crut01a}
J.~P. Crutchfield and D.~P. Feldman.
\newblock Regularities unseen, randomness observed: Levels of entropy
  convergence.
\newblock {\em CHAOS}, 13(1):25--54, 2003.

\bibitem{Crut89e}
J.~P. Crutchfield and K.~Young.
\newblock Computation at the onset of chaos.
\newblock In W.~Zurek, editor, {\em Entropy, Complexity, and the Physics of
  Information}, volume VIII of {\em SFI Studies in the Sciences of Complexity},
  pages 223 -- 269, Reading, Massachusetts, 1990. Addison-Wesley.

\bibitem{Bial00a}
W.~Bialek, I.~Nemenman, and N.~Tishby.
\newblock Predictability, complexity, and learning.
\newblock {\em Neural Computation}, 13:2409--2463, 2001.

\bibitem{Trav11b}
N.~Travers and J.~P. Crutchfield.
\newblock Infinite excess entropy processes with countable-state generators.
\newblock {\em Entropy}, 16:1396--1413, 2014.

\bibitem{Debo12a}
L.~Debowski.
\newblock On hidden {Markov} processes with infinite excess entropy.
\newblock {\em J. Theo. Prob.}, 27(2):539--551, 2012.

\bibitem{Turc97a}
D.~L. Turcotte.
\newblock {\em Fractals and Chaos in Geology and Geophysics}.
\newblock Cambridge University Press, Cambridge, United Kingdom, second
  edition, 1997.

\bibitem{Begg03a}
J.~M. Beggs and D.~Plenz.
\newblock Neuronal avalanches in neocortixal circuits.
\newblock {\em J. Neurosci.}, 23(35):11167--11177, 2003.

\bibitem{Debo11a}
L.~Debowski.
\newblock Excess entropy in natural language: {Present} state and perspectives.
\newblock {\em CHAOS}, 21(3):037105, 2011.

\bibitem{Dobs07a}
I.~Dobson, B.~A. Carreras, V.~E. Lynch, and D.~E. Newman.
\newblock Complex systems analysis of series of blackouts: {Cascading} failure,
  critical points, and self-organization.
\newblock {\em CHAOS}, 17(2):26103, 2007.

\bibitem{Kear94a}
M.~J. Kearns and U.~Vazirani.
\newblock {\em An Introduction to Computational Learning Theory}.
\newblock MIT Press, 1994.

\bibitem{Cove70a}
T.~M. Cover and M.~E. Hellman.
\newblock The two-armed-bandit problem with time-invariant finite memory.
\newblock {\em IEEE Trans. Info. Th.}, IT-16(2):185--195, 1970.

\bibitem{Berr72a}
D.~A. Berry.
\newblock A {Bernoulli} two-armed bandit.
\newblock {\em Ann. Math. Stat.}, 43(3):871--897, 1972.

\bibitem{Kolm65}
A.~N. Kolmogorov.
\newblock Three approaches to the concept of the amount of information.
\newblock {\em Prob. Info. Trans.}, 1:1, 1965.

\bibitem{Chai66}
G.~Chaitin.
\newblock On the length of programs for computing finite binary sequences.
\newblock {\em J. ACM}, 13:145, 1966.

\bibitem{Mart66a}
P.~Martin-Lof.
\newblock The definition of random sequences.
\newblock {\em Info. Control}, 9:602--619, 1966.

\bibitem{Kolm83}
A.~N. Kolmogorov.
\newblock Combinatorial foundations of information theory and the calculus of
  probabilities.
\newblock {\em Russ. Math. Surveys}, 38:29--40, 1983.

\bibitem{Brud83}
A.~A. Brudno.
\newblock Entropy and the complexity of the trajectories of a dynamical system.
\newblock {\em Trans. Moscow Math. Soc.}, 44:127, 1983.

\bibitem{Vita93a}
M.~Li and P.~M.~B. Vitanyi.
\newblock {\em An Introduction to Kolmogorov Complexity and its Applications}.
\newblock Springer-Verlag, New York, 1993.

\bibitem{Benn88}
C.~H. Bennett.
\newblock Dissipation, information, computational complexity, and the
  definition of organization.
\newblock In D.~Pines, editor, {\em Emerging Syntheses in the Sciences}.
  Addison-Wesley, Redwood City, 1988.

\bibitem{Kopp91a}
M.~Koppel and H.~Atlan.
\newblock An almost machine-independent theory of program-length complexity,
  sophistication, and induction.
\newblock {\em Information Sciences}, 56(1-3):23--33, 1991.

\bibitem{Crut12a}
J.~P. Crutchfield.
\newblock Between order and chaos.
\newblock {\em Nature Physics}, 8(January):17--24, 2012.

\bibitem{Crut13a}
J.~P. Crutchfield, P.~Riechers, and C.~J. Ellison.
\newblock Exact complexity: {Spectral} decomposition of intrinsic computation.
\newblock submitted.
\newblock Santa Fe Institute Working Paper 13-09-028; arXiv:1309.3792
  [cond-mat.stat-mech].

\bibitem{Mack03a}
D.~J.~C. MacKay.
\newblock {\em Information Theory, Inference and Learning Algorithms}.
\newblock Cambridge, Cambridge, United Kingdom, 2003.

\bibitem{Hast11a}
T.~Hastie, R.~Tibshirani, and J.~Friedman.
\newblock {\em The Elements of Statistical Learning: {Data} Mining, Inference,
  and Prediction}.
\newblock Spinger, New York, second edition, 2011.

\bibitem{Wall87a}
C.~S. Wallace and F.~P. Freeman.
\newblock Estimation and inference by compact coding.
\newblock {\em J. R. Statist. Soc. B}, 49:240, 1987.

\bibitem{Riss89a}
J.~Rissanen.
\newblock {\em Stochastic Complexity in Statistical Inquiry}.
\newblock World Scientific, Singapore, 1989.

\bibitem{Akai74a}
H.~Akaike.
\newblock A new look at the statistical model identification.
\newblock {\em IEEE Trans. Auto. Control}, 19(6):716--723, 1974.

\bibitem{Akai77a}
H.~Akaike.
\newblock An objective use of {Bayesian} models.
\newblock {\em Ann. Inst. Statist. Math.}, 29A:9, 1977.

\bibitem{Binn92a}
J.~J. Binney, N.~J. Dowrick, A.~J. Fisher, and M.~E.~J. Newman.
\newblock {\em The Theory of Critical Phenomena}.
\newblock Oxford University Press, Oxford, 1992.

\bibitem{Jame11a}
R.~G. James, C.~J. Ellison, and J.~P. Crutchfield.
\newblock Anatomy of a bit: {Information} in a time series observation.
\newblock {\em CHAOS}, 21(3):037109, 2011.

\bibitem{Bell03a}
A.~J. Bell.
\newblock The co-information lattice.
\newblock In S.~Makino S.~Amari, A.~Cichocki and N.~Murata, editors, {\em
  Proceedings of the Fifth International Workshop on Independent Component
  Analysis and Blind Signal Separation}, volume ICA 2003, New York, 2003.
  Springer.

\bibitem{Lohr09a}
W.~Lohr.
\newblock Properties of the statistical complexity functional and partially
  deterministic {HMMs}.
\newblock {\em Entropy}, 11(3):385--401, 2009.

\bibitem{walker1969asymptotic}
A.~M. Walker.
\newblock On the asymptotic behaviour of posterior distributions.
\newblock {\em J. Roy. Stat. Soc. Series B (Methodological)}, 31:80--88, 1969.

\bibitem{heyde1979asymptotic}
C.~C. Heyde and I.~M. Johnstone.
\newblock On asymptotic posterior normality for stochastic processes.
\newblock {\em J. Roy. Stat. Soc. Series B (Methodological)}, 41(2):184--189,
  1979.

\bibitem{sweeting1992asymptotic}
T.~J. Sweeting.
\newblock On asymptotic posterior normality in the multiparameter case.
\newblock {\em Bayesian Statistics}, 4:825--835, 1992.

\bibitem{weng2008asymptotic}
R.~C. Weng and W-C. Tsai.
\newblock Asymptotic posterior normality for multiparameter problems.
\newblock {\em J. Stat. Plan. Infer.}, 138(12):4068--4080, 2008.

\bibitem{hartigan1983asymptotic}
J.~A. Hartigan.
\newblock Asymptotic normality of posterior distributions.
\newblock In {\em Bayes Theory}, pages 107--118. Springer, 1983.

\bibitem{Lehm98a}
E.~L. Lehman and G.~Casella.
\newblock {\em Theory of Point Estimation}.
\newblock Springer, second edition, 1998.

\bibitem{Ebel91a}
W.~Ebeling and G.~Nicolis.
\newblock Entropy of symbolic sequences: {The} role of correlations.
\newblock {\em Europhys. Lett.}, 14:191--196, 1991.

\bibitem{Ebel94a}
W.~Ebeling and T.~Poschel.
\newblock Entropy and long-range correlations in literary {English}.
\newblock {\em Europhys. Lett.}, 26:241--246, 1994.

\bibitem{wasserman1998asymptotic}
L.~Wasserman.
\newblock Asymptotic properties of nonparametric {Bayesian} procedures.
\newblock In {\em Practical Nonparametric and Semiparametric {Bayesian}
  Statistics}, pages 293--304. Springer, 1998.

\bibitem{ghosal2000asymptotic}
S.~Ghosal.
\newblock Asymptotic normality of posterior distributions for exponential
  families when the number of parameters tends to infinity.
\newblock {\em J. Multivariate Anal.}, 74(1):49--68, 2000.

\bibitem{Crut92c}
J.~P. Crutchfield.
\newblock The calculi of emergence: Computation, dynamics, and induction.
\newblock {\em Physica D}, 75:11--54, 1994.

\bibitem{Presse13}
S.~Press\'e, K.~Ghosh, J.~Lee, and K.~A. Dill.
\newblock Principles of maximum entropy and maximum caliber in statistical
  physics.
\newblock {\em Rev. Mod. Phys.}, 85:1115--1141, Jul 2013.

\bibitem{Lind95a}
D.~Lind and B.~Marcus.
\newblock {\em An Introduction to Symbolic Dynamics and Coding}.
\newblock Cambridge University Press, New York, 1995.

\bibitem{Jame10a}
R.~G. James, J.~R. Mahoney, C.~J. Ellison, and J.~P. Crutchfield.
\newblock Many roads to synchrony: Natural time scales and their algorithms.
\newblock {\em Phys. Rev. E}, 89:042135, 2014.

\bibitem{Crut08b}
C.~J. Ellison, J.~R. Mahoney, and J.~P. Crutchfield.
\newblock Prediction, retrodiction, and the amount of information stored in the
  present.
\newblock {\em J. Stat. Phys.}, 136(6):1005--1034, 2009.

\bibitem{Shan48a}
C.~E. Shannon.
\newblock A mathematical theory of communication.
\newblock {\em Bell Sys. Tech. J.}, 27:379--423, 623--656, 1948.

\bibitem{Shen06a}
Q.~Shen, Q.~Hao, and S.~M. Gruner.
\newblock Macromolecular phasing.
\newblock {\em Physics Today}, 59(3):46--52, 2006.

\bibitem{Nimw96a}
E.~van Nimwegen, J.~P. Crutchfield, and M.~Mitchell.
\newblock Finite populations induce metastability in evolutionary search.
\newblock {\em Phys. Lett. A}, 229:144--150, 1997.

\bibitem{Chom56}
N.~Chomsky.
\newblock Three models for the description of language.
\newblock {\em IRE Trans. Info. Th.}, 2:113--124, 1956.

\bibitem{Lau12a}
H.~W. Lau and P.~Grassberger.
\newblock Information theoretic aspects of the two-dimensional {Ising} model.
\newblock 2012.
\newblock arxiv.org:1210.5707 [cond-mat.stat-mech].

\bibitem{Feld98a}
D.~P. Feldman.
\newblock {\em Computational Mechanics of Classical Spin Systems}.
\newblock PhD thesis, University of California, Davis, 1998.
\newblock {P}ublished by University Microfilms Intl, Ann Arbor, Michigan.

\end{thebibliography}
