# Controlled Random Walks

Authors
Source
Legacy

## Abstract

CONTROLLED RANDOM WALKS DAVID BLACKWELL 1. Introduction. Let M = ||w^-|| be an rXs matrix whose elements m{j are probability distributions on the Borei sets of a closed bounded convex subset X of &-space. We associate with M a game between two players, I and II, with the following infinite sequence of moves, where n = 0, 1, 2, . . .: Move 4^ + 1-" I selects i = 1, . . . , r. Move 4n + 2: II selects j = 1, . . . , s not knowing the choice of I at move an + 1. Move 4^ + 3: a point x is selected according to the distribution mijm Move 4w + 4: x is announced to I and II. Thus, a mixed strategy for I is a function /, defined for all finite sequences a = (ax, . . . , an) with ak e X, n = 0, 1, 2, . . . , with values in the set Pr of y-vectors p = (px, . . . , pr), pt ^ 0, S pi = 1: the ith coordinate of f(ax, .. .,an) specifies the probability of selecting i at move 4n + 1 when ax, . . ., an are the ^-points produced during the first 4n moves. A strategy g for II is similar, except that its values are in Ps. For a given pair /, g of strategies, the X-points produced are a sequence of random vectors xx, x2, . . . , such that the conditional distribution of xn+x given xx, . . ., xn is 2 fi(xx, . . ., xn) m^g^x^ . . ., xn), where i,i fit gj are the ith and jth coordinates of /, g. The problem to be considered in this paper is the following: To what extent can a given player control the limiting behavior of the random variables %n = ( % + ••• + xn)/n? For a given closed nonempty subset 5 of X, we shall denote by H(f,g) the probability that xn approaches 5 as n -> oo, i.e., the distance from the point xn to the set 5 approaches zero, where xx, x2, . . . is the sequence of random variables determined by /, g. We shall say that 5 is approachable by I with /* (II with g*) if H(f*,g) = 1 (H(f, g*) = 1) for all g(f), and shall say that S is approachable by I (II) if there is an f(g) such that S is approachable by I with / (II with g). We shall say that S is excludable

Seen <100 times