Content area
Abstract
Let (P(,n)) be an (s x s) convergent non-homogeneous stochastic chain. Then we can associate with (P(,n)) a partition {T,C(,1),C(,2),..,C(,p)} of the set {1,2,..,s} called the basis of the chain. If P(,n)'s are bistochastic, then T = (phi) and it is known that
(DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI)
is finite whenever i (epsilon) C(,m) and j (epsilon) C(,n) (m (NOT=) n). Also, in the bistochastic case, each of the smaller chains (P(,n)(C(,i))) defined by
(DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI)
and q,j (epsilon) C(,i) is strongly ergodic. This result is also true if (P(,n)) is a purely stochastic chain that is convergent with a basis in which T = (phi). In this dissertation, the above problem is considered for arbitrary, non-homogeneous, convergent, stochastic chains for which the 'T' set in the basis need not be empty. Some conditions sufficient for the above to hold in the case of general chains are given. Also, some conditions necessary for a non-homogeneous stochastic chain (P(,n)) to converge with the basis {T,C(,1),..,C(,p)} are explored in depth.
The second part of this dissertation is concerned with the structure of idempotent boolean matrices. A characterization theorem on the structure of such matrices is given. Some applications of boolean matrices in the context of non-homogeneous Markov chains are also explored briefly in the first part of this thesis.
The final part of this dissertation is concerned with an open problem on probabilistic context-free grammars. It has been proved that the average derivation length and the average word length of the words in a probabilistic context-free language are respectively equal to the mean derivation length and the mean word length of the words in a sample from the language whenever the production probabilities are estimated from the sample.
