Some Shannon-McMillan approximation theorems for Markov chain field on the generalized Bethe tree (Q535516): Difference between revisions

Infinite trees are considered in which any vertex \(i\) at level (distance) \(n\) from the root has the same number \(N(n+1)\) of neighbours \(j\) in \(A(i)\) at the next level for \(n=1,2,\dots\) so that there are \(t(n)=1+N(1)+N(1)N(2)+\cdots+N(1)\cdots N(n)\) vertices in the subtree \(T(n)\) with the root and \(n\) levels. A random field \(X\) is defined on the vertices and takes values in some discrete state space \(S\). A Markov field is given by an initial probability distribution \(q\) on \(S\) for the root and a conditional transition probability matrix \(Q\) on \((S,S)\) for any edge of the tree. Let \(H(n,Q)\) be the average of the conditional entropies of state transitions over edges in \(T(n)\). Convergence properties of \(X\) restricted to \(T(n)\) are considered for increasing \(n\). In particular, conditions are given on a general random field so that \([- \log P(X(i)\) for \(i\) in \(T(n))]/t(n) - H(n,Q)\) converges almost surely to zero as \(n\) tends to infinity. As a consequence, the asymptotic distribution of the states of the vertices in \(T(n)\) is uniform and determined by the expected entropy of state transitions over edges.