Analytical Approach to Probabilistic Problems on Words

Principal Investigator: Wojciech Szpankowski

A variety of applied probability problems on words can be reduced to the study of the asymptotic behavior of the so called Poisson transform L (z, u) (where z and u are complex) which satisfies the following differential-functional equation

with, say , where , are constants b is a positive integer, p + q = 1, and a (z,u) is a given function. This equation arises, for example, in the following context: An integer valued random variable is transformed into the probability generating function as an intermediate step in obtaining the Poisson transform that satisfies the above equation. The Poisson version of the problem replaces the deterministic input n by a Poisson variable N with mean z = n. Such a poissonization is often useful since it leads to a simpler solution (due to some unique properties of the Poisson process). In this research we aim at providing an asymptotic solution of the above (and others) differential-functional equation for in a cone around real axis. This leads to a solution of the problem at hand within the Poisson model framework. To translate it into the original model one needs (subtle) depoissonization results that are our second topic of the proposed research. Most of our depoissonization findings fall into the following general scheme: if the Poisson transform is appropriately bounded in a cone around the real axis and does not grow too fast outside such a cone, then one can asymptotically depoissonize by replacing the Poisson process by its mean. Not unexpectedly, actual formulations of depoissonization depend on the nature of the bound, and thus we shall investigate diagonal depoissonization theorems. Finally, we apply our results to a variety of challenging problems on words arising in pattern matching, data compression, security, cryptology, coding, molecular biology, and so forth.