|Online Judge||Problem Set||Authors||Online Contests||User|
Stochastic Finite State Automaton
The finite state automaton (FSA) is an important model of behavioral investigations in computer science, linguistics as well as many other different areas of study. In theoretical computer science literature, an FSA is typically modeled as a string pattern recognizer described with a quintuple <Σ, S, s0, δ, F>, where:
An FSA with the above description operates as follows:
We will not delve into further details concerning the FSA but focus on a slightly simplified variant – the stochastic finite state automaton (SFSA). An SFSA is described with a duple <A, b>, where:
The automaton assumes the first n positive integers as its states. Unlike a normal FSA, it does not read any symbols and consequently does not have an input alphabet. And its transitions are completely self-determined. Concretely speaking, an SFSA operates as follows:
Deriving from the above description, we can draw several implications concerning the SFSA. For instance, observably, the automaton may make an infinite number of transits and never halt, but intuitively, this is very unlikely to occur. Before scrutinizing the behavioral features of the SFSA, it is advisable to first investigate its statistical characteristics, namely, we want to know for each state i, the probability that the automaton decides to halt in that state and, given that automaton halts in that state, the expectation as well as the standard deviation of the number of transitions that have been made.
The input consists of a single test case. The first input line contains the number n (1 ≤ n ≤ 200) alone. The next n lines each contain n nonnegative numbers, giving the elements of an n-by-n square matrix A in row-major order. On the last line, there are n nonnegative numbers which are the components of an n-dimensional column vector b in increasing order of their indices. The sum of elements in every column of A is strictly less than 1, and the components of b sum to exactly 1. The duple <A, b> constitutes the description of an SFSA.
For each state in increasing order of their numerical values, output in order and as accurate as possibly the probability that the automaton decides to halt in that state and, given that automaton halts in that state, the expectation as well as the standard deviation of the number of transitions that have been made. A special checker program that admits an relative error of 10−6 is used to verify the output.
3 0.25 0 0 0.25 0 0 0.25 0 0 1 0 0
0.33333333 0.33333333 0.66666667 0.33333333 1.33333333 0.66666667 0.33333333 1.33333333 0.66666667
For a random variable X, Var(X) = E(X2) − (E(X))2.
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator