| Abstrakt: |
Starting at state x∃X, a player selects the next state x from the collection Τ( x) of those available and then selects x from Τ( x ) and so on. Suppose the object is to control the path x , x , ... so that every x will lie in a subset A of X. A famous lemma of König is equivalent to the statement that if every Τ( x) is finite and if, for every n, the player can obtain a path in A of length n, then the player can obtain an infinite path in A. Here paths are not necessarily deterministic and, for each x, Τ( x) is the collection of possible probability distributions for the next state. Under mild measurability conditions, it is shown that if, for every n, there is a random path of length n which lies in A with probability larger than α, then there is an infinite random path with the same property. Furthermore, the measurability and finiteness assumptions can be dropped if, in the hypothesis, the positive integers n are replaced by stop rules t. An analogous result holds when the object is to visit A infinitely many times. [ABSTRACT FROM AUTHOR] |
Full text from SpringerLink