3473：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, s₀, δ, F>, where:

• Σ is the input alphabet (a finite nonempty set of symbols).
• S is a finite nonempty set of states.
• s₀ is an element in S designated as the initial state.
• δ is a function δ : S × Σ → S known as the transition function.
• F is a (possibly empty) subset of S whose elements are designated as the final states.

An FSA with the above description operates as follows:

• At the beginning, the automaton starts in the initial state s₀.
• The automaton continuously reads symbols from its input, one symbol at a time, and transits between states according to the transition function δ. To be specific, let s be the current state and w the symbol just read, the automaton transits to the state given by δ(s, w).
• When the automaton reaches the end of the input, if the current state belongs to F, the string consisting sequentially of the symbols read by the automaton is declared accepted, otherwise it is declared rejected.

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:

• A is an n-by-n nonnegative square matrix.
• b is an n-dimensional nonnegative column vector.

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:

• At the beginning, the automaton selects randomly a positive integer not exceeding n, i, as the initial state with probability b_i, the i-th component of b. (It is required that the components of b sum to exactly 1.)
• At any stage before the automation halts, let j be the current state, the automaton selects randomly a positive integer not exceeding n, i, with probability a_ij, the element of A located in the i-th row and the j-th column, or 0 with probability __poj_jax_start__\textstyle 1-\sum_{i=1}^na_{ij}__poj_jax_end__. If the automaton selects 0, it halts immediately, otherwise it transits to state i. (It is required that the sum of elements of every column of A be not less than or equal to 1.)

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⁻⁶ is used to verify the output.

For a random variable X, Var(X) = E(X²) − (E(X))².