Northeastern University
Sign Up
Northeastern University, 511 Lake Hall Free Event
Free Event


The Stochastic Context Tree (SCOT) is a memory structure of a homogeneous finite m-Markov Chain (m-MC). It captures the phenomenon that the probability distribution of the next symbol sometimes depend on less than m of the most recent symbols. Context trees can be used to reduce an m-MC to a 1-MC. The goal is to find the smallest possible context tree representing an m-MC.


Recently I discovered a necessary and sufficient condition (“TailClosed”) for a tree to be the context tree of an m-MC over a finite alphabet. It turned out that this TailClosed context tree structure is independent of the prediction probability distribution. 


In my talk I will explain the notions involved and the basic ideas behind the proof. And I will show some properties and algorithms related to TailClosed context trees. This talk is self-contained, no prerequisites are required.


Index terms: context tree, memory tree source, m-MC, probability estimate, dimension reduction, recursive / non-recursive algorithms, partially ordered set, rooted tree.

Event Details

  • Tong Zhang

1 person is interested in this event

User Activity

No recent activity