Tree interactive encoding and decoding: Conditionally Φ-mixing sources

Interactive encoding and decoding with tree decoding (referred to simply as tree interactive encoding and decoding (TRIED)) is considered for the problem of lossless source coding with decoder only side information. A TRIED scheme is proposed and demonstrated that when applied to encode any conditionally Φ-mixing source of length n, its error probability decays polynomially with respect to n, average rate is around conditional entropy rate, and average computational complexity of encoding and decoding is O(n ln n).