User Tools

Site Tools



We need to avoid overly complicated, ambiguous, and inconsistent notation. This page will serve to aggregate the notation of Computational Mechanics into a single usable source, leaving analysis and interpretation to their appropriate pages.

This notation is taken from the various papers on Computational Mechanics, specifically RURO, CMPPSS, TBA, PRATISP, and IACP.

Notation for Processes

<latex> \mathcal{A} </latex> : A countable set which is the alphabet of some process.

<latex> \overleftrightarrow{S} = \ldots S_{-1}S_0S_1\ldots </latex> : The bi-infinite sequence of random variables <latex> S_i </latex>.

<latex> \overrightarrow{S}^L =S_1 S_2 \ldots S_L </latex> : The length <latex> L </latex> sequence of random variables beginning at <latex> S_1 </latex> (a “Future” of length <latex> L </latex>).

<latex> \overleftarrow{S}^L = S_{-L+1} \ldots S_{-2} S_{-1} S_0 </latex> : The length <latex> L </latex> sequence of random variables going up to, but not including <latex> S_1 </latex> (a “Past” of length <latex> L </latex>).

<latex> \overrightarrow{S} = S_1 S_2 S_3 \ldots </latex> : The semi-infinite sequence of random variables starting at <latex> S_1 </latex> (the entire “Future”).

<latex> \overleftarrow{S} = \ldots S_{-2} S_{-1}S_0 </latex> : The semi-infinite sequence of random variables ending at <latex> S_0 </latex> (the entire “Past” including the “Present”).

<latex> \mathcal{R} </latex> : A partition of the space of all histories into equivalence classes with respect to predict the future.

<latex> \mathcal{S} </latex> : The partition of the space of histories that corresponds to the causal states.

Additional Comments

Strictly speaking, the arrows are a notational shorthand which avoids having to be explicit about the indexes. They tell us which way to count, given a start index. For example, consider the following sequence of output symbols:


\cdots X_{-3} X_{-2} X_{-1} X_0 X_1 X_2 \cdots


We can associate the (forward) direction of time with increasing indexes on the random variables. Thus, we might denote a generic random variable for the output symbol at time <latex> t </latex> as <latex> X_t </latex>. To denote a sequence of random variables of length <latex> L </latex> beginning at time <latex> t </latex>, we would write:


\overrightarrow{X}_t^L = X_t X_{t+1} \cdots X_{t+L-1}


where the right arrow indicates that the unspecified index should occur later in time than index <latex> t </latex>. For a variety of reasons (explained below), this notation can be confusing when you need to make explicit use of indexes. In such situations, consider the following alternative notation:


X_{t:t+L} = X_t X_{t+1} \cdots X_{t+L-1}


In this notation, we explicitly state the start and stop indexes of the random variable. The trade-off from the standard notation is that the length of the interval is no longer explicitly stated and must be inferred.

Also, notice that we did not write <latex> X_{t:t+L-1} </latex>. That is, the index interval was inclusive on the left and exclusive on the right. One might argue that the more natural notation would be to make the interval inclusive on the left and right, but this would make it difficult to concatenate intervals.

Typically, we define the “present” as occurring immediately before index <latex>t=0</latex>. So, random variables with indexes <latex>t \geq 0</latex> are considered to have occurred in the future and random variables with indexes <latex> t<0 </latex> are considered to have occurred in the past.

Too frequently, we associate the “right arrow” with a “future” word, but this is not always true and depends on the start time. For example, if <latex> t = -10, L=3</latex>, then the word is definitely not a word in the future as every index occurs before the “present”. Similarly, the “left arrow” does not necessarily mean that the word occurred in the past. Rather, the “left arrow” tells us that we must count backwards from the start index. Further, since we are always inclusive on the earliest index and exclusive on the latest index, the “left arrow” says we do not include the start index. Finally, we might say that the arrow notation has too many degrees of freedom since a “future” word can be written using either left or right arrows (examples below). Potentially, this can be confusing, and for all of these reasons, it is probably best to use the arrow notation only when there is no need to be explicit about indexes, throughout the discussion. However, sometimes it is important to specify the scan direction of the random variables. In such cases, the direction of the arrow should not be interpreted as a statement of whether the word occurred in the past/future, but rather, a specification on the scan direction.

To illustrate both notations and some of the nuances, consider the following examples and commentary.

Sequence Notation Alt Notation Comment
<latex> X_3 X_4 \cdots </latex> <latex> \overrightarrow{X}_3 </latex> <latex> X_{3:} </latex> All symbols after <latex> t=3 </latex>, inclusive.
<latex> \cdots X_1 X_2 </latex> <latex> \overleftarrow{X}_3 </latex> <latex> X_{:3} </latex> All symbols before <latex> t=3 </latex>, exclusive.
<latex> \cdots X_1 X_2 X_3 X_4 \cdots </latex> <latex> \overleftrightarrow{X}_3 = \overleftarrow{X}_3 \overrightarrow{X}_3 </latex> <latex> X_{:3:} = X_{:3} X_{3:} </latex> All symbols with artifical break at <latex>t=3</latex>.
<latex> X_3 X_4 </latex> <latex> \overrightarrow{X}_32 </latex> <latex> X_{3:5} </latex> Start at <latex>t=3</latex>, inclusive, and count forward 2 time steps to end at <latex>t=5</latex>, exclusive.
<latex> X_1 X_2 </latex> <latex> \overleftarrow{X}_32 </latex> <latex> X_{1:3} </latex> Start at <latex>t=3</latex>, exclusive, and count backward 2 time steps to end at <latex>t=1</latex>, inclusive.
<latex> X_1 X_2 X_3 X_4 </latex> <latex> \overleftrightarrow{X}_32 = \overleftarrow{X}_32 \overrightarrow{X}_32 </latex> <latex> X_{1:5} = X_{1:3} X_{3:5} </latex> A “future” word written as the concatenation of a left and right arrow, at the same time index.
<latex> X_2 X_3 X_4 X_5 X_6 X_7 X_8 </latex> <latex> \overrightarrow{X}_27 = \overrightarrow{X}_23 \overrightarrow{X}_54 </latex> <latex> X_{2:9} = X_{2:5}X_{5:9} </latex> A “future” word written as the concatenation of two right arrows.
<latex> X_2 X_3 X_4 X_5 X_6 X_7 X_8 </latex> <latex> \overleftarrow{X}_97 = \overleftarrow{X}_53 \overleftarrow{X}_94 </latex> <latex> X_{2:9} = X_{2:5}X_{5:9} </latex> A “future” word written as the concatenation of two left arrows.

Summary: If the index is early, then it is inclusive. If the index is late, then it is exclusive.

cm/notation.txt · Last modified: 2010/01/25 23:50 by ellisocj