NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
Distribution functions of probabilistic automataEach probabilistic automaton M over an alphabet A defines a probability measure Prob sub(M) on the set of all finite and infinite words over A. We can identify a k letter alphabet A with the set {0, 1,..., k-1}, and, hence, we can consider every finite or infinite word w over A as a radix k expansion of a real number X(w) in the interval [0, 1]. This makes X(w) a random variable and the distribution function of M is defined as usual: F(x) := Prob sub(M) { w: X(w) < x }. Utilizing the fixed-point semantics (denotational semantics), extended to probabilistic computations, we investigate the distribution functions of probabilistic automata in detail. Automata with continuous distribution functions are characterized. By a new, and much more easier method, it is shown that the distribution function F(x) is an analytic function if it is a polynomial. Finally, answering a question posed by D. Knuth and A. Yao, we show that a polynomial distribution function F(x) on [0, 1] can be generated by a prob abilistic automaton iff all the roots of F'(x) = 0 in this interval, if any, are rational numbers. For this, we define two dynamical systems on the set of polynomial distributions and study attracting fixed points of random composition of these two systems.
Document ID
20020003536
Document Type
Conference Paper
Authors
Vatan, F. (Jet Propulsion Lab., California Inst. of Tech. Pasadena, CA United States)
Date Acquired
August 20, 2013
Publication Date
January 1, 2001
Publication Information
Publication: CONF PROC ANNU ACM SYMP THEORY COMPUT. CONF PROC ANNU ACM SYMP THEORY COMPUT
ISSN: 0734-9025
Subject Category
Statistics and Probability
Distribution Limits
Public
Copyright
Other
Keywords
Denotational semantics
Probabilistic automata