The caption of Figure 6 of the paper mentioned in the title says:
The input stream used for this figure contained high-order sequences mixed with random elements. The maximum possible average prediction accuracy of this data stream is 50%.
@jhawkins, @subutai, I don’t really get why the average prediction accuracy would just be 50%, even in the presence of noise. Btw, the amount of noise added to the sequence is not even specified.