We are now ready to formulate the context-tree weighting algorithm.
We start by making the practical assumption that in node s of the
context tree we only store 
and 
, i.e. the number
of zeroes and ones in the subsequence associated with context s.
First we consider a leaf s of the context tree, i.e. a
node (context) at depth D.
Since only and are available in this node, we can
assume nothing more than that the subsequence associated with node s
is memoryless and that 
is a good weighted
probability for it, i.e.
These weighted probabilities are needed to start the recursion described in the next paragraph.
Figure 5: Parent node s and its children 0s and 1s.
For an internal node s in the context tree, the following argument
holds.
Suppose that we have good weighted probabilities 
and 
for the subsequences associated with nodes 0s and
1s, the children (see figure 5) of s.
Then for the subsequence associated with context s there are two
possible alternatives.
It could be memoryless, in which case would be
good coding probability for it.
Or, it could not be memoryless, and then splitting up the sequence
in the two subsequences that are associated with 0s and 1s would
be necessary, and the product of the weighted probabilities
and could serve as a good coding
probability.
Following the philosophy in section 9 it is completely
clear that we should just weight these two alternatives:
In the root 
of the context tree we will now find weighted
probabilities which can be used as coding probabilities for arithmetic
encoding and decoding.
Example:
Figure 6: Weighted context tree for source sequence 0100110 with past
.
Again suppose that the source generated the sequence 0100110 while the
past symbols were .
This results in the counts and , and weighted
probabilities 
, for s with depth 
, which are
depicted in the context tree in figure 6.
