# Random Variables with Measurability Constraints with Application to
Opportunistic Scheduling

Michael J. Neely
University of Southern California
https://viterbi-web.usc.edu/~mjneely/

###### Abstract

This paper proves a representation theorem regarding sequences of random
elements that take values in a Borel space and are measurable with respect to
the sigma algebra generated by an arbitrary union of sigma algebras. This,
together with a related representation theorem of Kallenberg, is used to
characterize the set of multidimensional decision vectors in a discrete time
stochastic control problem with measurability and causality constraints,
including opportunistic scheduling problems for time-varying communication
networks. A network capacity theorem for these systems is refined, without
requiring an implicit and arbitrarily complex extension of the state space, by
introducing two measurability assumptions and using a theory of constructible
sets. An example that makes use of well known pathologies in descriptive set
theory is given to show a nonmeasurable scheduling scheme can outperform all
measurable scheduling schemes.

##  I Introduction

Let $(\Omega,{{\cal{F}}})$ and $(\Gamma,{{\cal{G}}})$ be two measurable
spaces. Let $X:\Omega\rightarrow\mathbb{R}$ be a Borel measurable function and
let $Y:\Omega\rightarrow\Gamma$ be a measurable function. The Doob-Dynkin
lemma states that $X$ is $\sigma(Y)$-measurable if and only if $X=h(Y)$ for
some Borel measurable function $h:\Gamma\rightarrow\mathbb{R}$ [1][2][3].
Suppose we know only that $X$ is
$\sigma({{\cal{H}}}_{1}\cup{{\cal{H}}}_{2})$-measurable, where
${{\cal{H}}}_{1}\subseteq{{\cal{F}}}$ and
${{\cal{H}}}_{2}\subseteq{{\cal{F}}}$ are two subsigma algebras on $\Omega$.
Is it necessarily true that $X=h(Y_{1},Y_{2})$ for some Borel measurable
function $h:[0,1]^{2}\rightarrow\mathbb{R}$ and some Borel measurable
functions $Y_{i}:\Omega\rightarrow[0,1]$ such that $Y_{i}$ is
${{\cal{H}}}_{i}$-measurable for each $i\in\\{1,2\\}$?

This question motivates the more general question of characterizing all
sequences of Borel measurable functions that satisfy certain _measurability
constraints_. Fix $K$ as a nonempty set that is finite or countably infinite.
For each $k\in K$ let $X_{k}:\Omega\rightarrow\mathbb{R}$ be a function. Let
$J$ be a nonempty set with arbitrarily large cardinality. For each $j\in J$,
let ${{\cal{H}}}_{j}\subseteq{{\cal{F}}}$ be a given subsigma algebra on
$\Omega$. We characterize all $(X_{k})_{k\in K}$ that satisfy

$X_{k}\mbox{ is $\sigma(\cup_{j\in
J_{k}}{{\cal{H}}}_{j})$-measurable}\quad\forall k\in K$ (1)

where $J_{k}$ are given nonempty sets that satisfy $J_{k}\subseteq J$ for all
$k\in K$. The first result is that $(X_{k})_{k\in K}$ satisfies (1) if and
only if

$X_{k}=h_{k}((Y_{j})_{j\in\tilde{J}_{k}})\quad\forall k\in K$ (2)

for some Borel measurable functions $Y_{j}:\Omega\rightarrow[0,1]$ that are
${{\cal{H}}}_{j}$-measurable for each $j\in J$, some countable subsets
$\tilde{J}_{k}\subseteq J_{k}$, and some Borel measurable functions
$h_{k}:[0,1]^{\tilde{J}_{k}}\rightarrow\mathbb{R}$ for each $k\in K$.
Measurability of each function $h_{k}$ is with respect to the product sigma
algebra on $[0,1]^{\tilde{J}_{k}}$. Observe that each $X_{k}$ in (2) draws
from the the _same_ collection of functions $(Y_{j})_{j\in J}$ (rather than
defining variables $Y_{j,k}$ separately for each $k$). In particular, a single
function $Y_{j}$ can be used to represent the influence of the sigma algebra
${{\cal{H}}}_{j}$ whenever that influence is required. A special case of this
result gives an affirmative answer to the question posed in the first
paragraph. The result (1)-(2) immediately generalizes to allow $X_{k}$ to be a
random element of any Borel space, such as the space
$(\mathbb{R}^{m},{{\cal{B}}}(\mathbb{R}^{m}))$ for some positive integer $m$.

###  I-A Applications to stochastic control

The measurability constraints (1) have applications to stochastic control. For
example, consider a discrete time system that operates over time slots
$k\in\\{1,2,3,\ldots\\}$ according to some probability triplet
$(\Omega,{{\cal{F}}},P)$. Let $S_{k}:\Omega\rightarrow\Omega_{S}$ be the
_system state_ that can be observed at time $k$, which is a random element
associated with some measurable space $(\Omega_{S},{{\cal{F}}}_{S})$ with
arbitrary structure. Every step $k$ the system controller observes $S_{k}$ and
chooses a _decision_ that affects a vector of attributes
$X_{k}\in\mathbb{R}^{m}$, where $m$ is some fixed positive integer. The vector
$X_{k}$ is required to satisfy the following _system constraints_

$X_{k}\in C(S_{k})\quad\forall k\in\\{1,2,3,\ldots\\}$ (3)

where $C:\Gamma\rightarrow Pow(\mathbb{R}^{m})$ is a given set-valued function
that maps the observed state $S_{k}$ to a subset of $\mathbb{R}^{m}$ that
consists of all decision options for $X_{k}$ (where $Pow(\mathbb{R}^{m})$
denotes the power set of $\mathbb{R}^{m}$). The next state $S_{k+1}$ can be
influenced by the prior states and decisions according to some model supported
by the probability space, such as a Markov chain model. The $m$ components of
$X_{k}$ can represent rewards, prices, power expenditures, and so on,
associated with time slot $k$, and can also include values that affect the
next state. This work is motivated by the application of _opportunistic
scheduling_ , where $(S_{k})_{k=1}^{\infty}$ are independent and identically
distributed (i.i.d.) random channel states that are sequentially observed in a
wireless communication system at the start of each slot $k$, $X_{k}$ is a
vector of transmission rates over $m$ different channels, and $C(S_{k})$ is
the set of all possible transmission rate vectors that can be supported on
slot $k$ when the observed channel state is $S_{k}$.

Consider _causal and measurable_ decision policies that are constrained to
make decisions that yield valid random variables and are based only on
observations of the past. Assume the decisions can be _stochastic_ , so they
can be informed by an external source of randomness that is represented by
some sigma algebra ${{\cal{G}}}\subseteq{{\cal{F}}}$ on $\Omega$. For example,
${{\cal{G}}}$ might be the sigma algebra generated by an infinite sequence of
i.i.d. random elements in some arbitrary measurable space and whose values are
selected by an independent computing device at time $0$ (before any control
decisions are made). Then we require:

$X_{k}\mbox{ is
$\sigma(\sigma(S_{1})\cup\cdots\cup\sigma(S_{k})\cup{{\cal{G}}})$-measurable}\quad\forall
k\in\\{1,2,3,\ldots\\}$ (4)

where $\sigma(S_{i})$ is the sigma algebra generated by the random element
$S_{i}$. Under any such causal and measurable decision policy the result (2)
implies

$X_{k}=h_{k}(Y_{1},\ldots,Y_{k},R)\quad\forall k\in\\{1,2,3,\ldots\\}$ (5)

for some Borel measurable functions $h_{k}$, some ${{\cal{G}}}$-measurable
random variable $R$ that takes values in $[0,1]$, and some
$\sigma(S_{i})$-measurable random variables $Y_{i}$ that take values in
$[0,1]$. It is interesting that the _same_ random variables
$R,\\{Y_{i}\\}_{i=1}^{\infty}$ can be used to construct $X_{k}$ for all time
steps $k$. In particular:

  * •

While the observed random elements $S_{i}$ are associated with an arbitrarily
complex measurable space $(\Omega_{S},{{\cal{F}}}_{S})$ where $\Omega_{S}$ has
arbitrary cardinality, it suffices to boil these random elements down to real-
valued random variables $Y_{i}:\Omega\rightarrow[0,1]$ where each $Y_{i}$ is a
measurable function of $S_{i}$.

  * •

While the external source of randomness is from an arbitrarily complex sigma
algebra ${{\cal{G}}}$ on $\Omega$, it suffices to boil it down to a single
draw of a random variable $R:\Omega\rightarrow[0,1]$ that is
${{\cal{G}}}$-measurable.

The constraint $X_{k}\in C(S_{k})$ seems to require knowledge of the full
value of $S_{k}$, while the form (5) says this constraint must be sustained
only by observing the “boiled” variables $Y_{1},\ldots,Y_{k},R$ (all of which
take values in $[0,1]$). In particular, all policies that satisfy (3)-(4) are
characterized according to the following choices:

  1. 1.

Choose a single ${{\cal{G}}}$-measurable random variable
$R:\Omega\rightarrow[0,1]$.

  2. 2.

Choose Borel measurable functions $\theta_{k}:\Omega_{S}\rightarrow[0,1]$ from
which $Y_{k}=\theta_{k}(S_{k})$ are defined for all $k\in\\{1,2,3,\ldots\\}$.

  3. 3.

For each $k\in\\{1,2,3,\ldots\\}$, define a Borel measurable function
$h_{k}:[0,1]^{k+1}\rightarrow\mathbb{R}^{m}$ such that

$h_{k}(\theta_{1}(S_{1}(\omega)),\theta_{2}(S_{2}(\omega)),\ldots,\theta_{k}(S_{k}(\omega)),R(\omega))\in
C(S_{k}(\omega))\quad\forall\omega\in\Omega$ (6)

If the constraint (6) is impossible to meet, then no causal decision policy
that meets the required measurability constraints exists. Sufficient
conditions for (6) are given in Section IV using two measurability assumptions
that include the existence of a _measurable choice function_. Measurable
choice is a classical problem in descriptive set theory and conditions for
existence in certain cases are found in the _selection theorems_ of
[4][5][6][7][8][9][10]. In particular, the works [6][7][8] use measurable
choice to establish cost minimizing policies for economics and dynamic
programming applications. Our work gives a simple application to the
multidimensional _capacity region_ in the opportunistic scheduling problem. A
theory of _constructible sets_ from [11], together with measurable choice, is
used to refine the capacity results of [12][13][14]. We also apply classical
pathological cases from descriptive set theory to show an example where a
nonmeasurable policy produces significantly larger time averages in comparison
to any measurable policy.

###  I-B Related work

The Doob-Dynkin lemma is proven on page 603 in [1] (see also Lemma 1.13 in
[2], and [3]). Recent discussion of this lemma is in [15]. The Doob-Dynkin
lemma can be used to directly characterize all
$\sigma({{\cal{H}}}_{1}\cup{{\cal{H}}}_{2})$-measurable functions
$X:\Omega\rightarrow\mathbb{R}$ in the special case when
${{\cal{H}}}_{i}=\sigma(Y_{i})$ for some random variables $Y_{i}$ for
$i\in\\{1,2\\}$. In that special case the Doob-Dynkin lemma implies
$X=h(Y_{1},Y_{2})$. The difficulty is that the sigma algebras
${{\cal{H}}}_{1}$ and ${{\cal{H}}}_{2}$ can be arbitrarily complex, including
sigma algebras that cannot be generated by any real-valued random variable. An
early version of this question was addressed by the author on StackExchange in
[16] using Dynkin’s multiplicative class theorem (see Theorem 18.51 in [17])
together with several techniques that are refined and generalized in the
current paper.111The question of $X$ being
$\sigma({{\cal{H}}}_{1}\cup{{\cal{H}}}_{2})$-measurable was posed by the
author as a StackExchange question in [16]. Users initially conjectured the
representation $X=h(Y_{1},Y_{2})$ was generally impossible but suggested
proving a weaker representation by a monotone class argument; the strong
result was eventually proven by the author using Dynkin’s multiplicative class
theorem [17]. Rather than using a multiplicative class argument, the current
paper establishes a related sigma algebra fact that is of interest in its own
right.

For the probability space $(\Omega,{{\cal{F}}},P)$ used in the stochastic
control problem, consider the special case when we are given some measurable
space $(\Omega_{Q},{{\cal{F}}}_{Q})$ and we are told ${{\cal{G}}}=\sigma(Q)$
for some random element $Q:\Omega\rightarrow\Omega_{Q}$ that is measurable
with respect to $(\Omega,{{\cal{F}}})$ and $(\Omega_{Q},{{\cal{F}}}_{Q})$. The
causal and measurable constraint (4) is thus equivalent to

$X_{k}\mbox{ is
$\sigma(\sigma(S_{1})\cup\cdots\cup\sigma(S_{k})\cup\sigma(Q))$-measurable}\quad\forall
k\in\\{1,2,3,\ldots\\}$

from which the Doob-Dynkin lemma immediately implies

$X_{k}=h_{k}(S_{1},S_{2},\ldots,S_{k},Q)\quad\forall k\in\\{1,2,3,\ldots\\}$
(7)

for some measurable function
$h_{k}:\Omega_{S}^{k}\times\Omega\rightarrow\mathbb{R}$. However, the reason
(5) is stronger (and nontrivial) is that the ${{\cal{G}}}$-measurable random
variable $R:\Omega\rightarrow[0,1]$ takes values only in $[0,1]$ regardless of
the complexity of the random element $Q$ that generates ${{\cal{G}}}$;
Similarly each $Y_{j}$ is ${{\cal{H}}}_{j}$-measurable and takes values on
$[0,1]$.

An important representation theorem related to (5) is given by Kallenberg in
Proposition 5.13 of [2]: There it is shown that if $X$ is a random element of
a Borel space and $S$ is a random element of an arbitrary measurable space,
and if the probability space is _extended_ (using standard product space
concepts) to include a random variable $U$ that is uniformly distributed over
$[0,1]$ and that is independent of everything else, then $X=g(S,W)$ almost
surely, where $g$ is some measurable function and $W$ is some random variable
that is uniformly distributed over $[0,1]$ and independent of $S$. It is not
difficult to strengthen this result to _surely_ rather than _almost surely_
(this is done in Section IV-A for completeness). When applied to the
stochastic control problem, if we assume $(\Omega,{{\cal{F}}},P)$ is the
already-extended space and ${{\cal{G}}}=\sigma(U)$, the result immediately
implies

$X_{k}=g_{k}(S_{k},W_{k})\quad\forall k\in\\{1,2,3,\ldots\\}$

where for each $k\in\\{1,2,3,\ldots\\}$, $g_{k}$ is a Borel measurable
function and $W_{k}$ is a random variable that is uniformly distributed over
$[0,1]$ and independent of $S_{k}$. However, the $g_{k}$ functions cannot be
viewed as defining a control policy because the value $W_{k}$ and its
structure within the $g_{k}$ function can depend on the realizations of
$S_{1},\ldots,S_{k-1}$.

Selection theorems for measurable choice are developed by Blackwell and Ryll-
Nardzewski [4], Kuratowski and Ryll-Nardzewski [5], and Von Neumann [9] (see
also [10][18]). Measurable choice for economics and dynamic programming are
considered by Maitra [7], Aumann [8], and Dubins and Savage [6]. For example,
[7] considers a set $S$ for _current states_ and a set $A$ for _action
choices_ , where $S$ is a Borel subset of a Polish space and $A$ is a compact
metric space, and shows (see also [6]) that if $u$ is a bounded upper semi-
continuous function on $S\times A$ then there is a measurable choice function
$\psi:S\rightarrow A$ such that

$u(s,\psi(s))=\max_{a\in A}u(s,a)\quad\forall s\in S$

Continuous time control with measurable choice is in [19].

Fundamental optimality properties for dynamic programming with general state
and action sets are in [20][21][7][22]. For example, Blackwell in [20]
considers one step of a finite stage dynamic program with Borel spaces $A,S,H$
where $A$ is the set of possible actions, $S$ the set of current states, and
$H$ the set of historical states from the past (see also [6]). The one-step
goal is to observe $s\in S$ and $h\in H$ and choose an action $a\in A$ to
maximize a utility $u(s,a)$ (so the utility depends only on the current state
and action). Mild conditions imply that for any policy that chooses $a$ as a
measurable function of both $s$ and $h$, and for any $\epsilon>0$, there is a
measurable _memoryless strategy_ that chooses $a\in A$ based only on the
current state $s$ that achieves utility at most $\epsilon$ worse (for almost
all $a,h$ defined in a probabilistic sense). However, [20] also gives a
counter-example to show this is impossible without the mild conditions. This
counter-example is similar in spirit to the example in Section V-A of the
current paper. However, the structure of our example is different: It treats
the infinite horizon opportunistic scheduling problem; It uses a different
pathological set from descriptive set theory than the one used in [20]; It
compares a nonmeasurable policy to all possible measurable policies, rather
than comparing a measurable policy of two variables to all possible measurable
policies in one variable. Optimality of stationary policies in multi-step
dynamic programs over Borel spaces is considered in [21][7] and related
nonstationary problems are in [22]. Nonmeasurable gambling strategies are
treated in [6].

Tassiulas and Ephremides establish the _capacity region_ for a class of time-
varying networks in [14] and prove that a max-weight rule stabilizes the
network whenever possible. Capacity regions for more general systems that
choose $X_{k}\in C(S_{k})$ are treated in [13][12][23], see also related
problems of network utility maximization [24][25][26][27] and energy
minimization [28]. The general result in [12] makes implicit assumptions
regarding measurability and probability space extension. The current paper
refines a capacity theorem from [12] without extending the space by
introducing two measurability assumptions, including a measurable choice
assumption, together with a property of _constructible sets_ from [11].

The field of descriptive set theory was initiated in the classic works of
Souslin [29] and Lusin [30]. Souslin showed existence of a two dimensional
Borel set that has a non-Borel projection onto the first dimension. Examples
of multidimensional Borel sets that do not contain a measurable choice
function are developed by Blackwell [31], Novikoff [32], Sierpiński [33], and
Addison [34] (see also Example 5.1.7 in [10]). In [35] Sierpiński constructs a
subset of $[0,1]$ that has inner measure 0 and outer measure 1 (see also
[36][37]). These classic pathological examples are used in Section V to show
examples where nonmeasurable decisions can be used in the opportunistic
scheduling problem to enable time averages that are superior to those achieved
by any measurable policy.

##  II Preliminaries

###  II-A Terminology

Let $\mathbb{N}=\\{1,2,3,\ldots\\}$ denote the natural numbers, $\mathbb{R}$
the real numbers, and ${{\cal{B}}}(\mathbb{R})$ the standard Borel sigma
algebra on $\mathbb{R}$. For $A\in{{\cal{B}}}(\mathbb{R})$ define
${{\cal{B}}}(A)=\\{B\in{{\cal{B}}}(\mathbb{R}):B\subseteq A\\}$. A _measurable
space_ is a pair $(\Omega,{{\cal{F}}})$ where $\Omega$ is a nonempty set and
${{\cal{F}}}$ is a sigma algebra on $\Omega$. Suppose
$(\Omega_{1},{{\cal{F}}}_{1})$ and $(\Omega_{2},{{\cal{F}}}_{2})$ are two
measurable spaces. Let ${{\cal{H}}}\subseteq\Omega_{1}$ be another sigma
algebra on $\Omega_{1}$. With respect to the measurable space
$(\Omega_{2},{{\cal{F}}}_{2})$, a function $g:\Omega_{1}\rightarrow\Omega_{2}$
is said to be _${{\cal{H}}}$ -measurable_ if

$g^{-1}(A)\in{{\cal{H}}}\quad\forall A\in{{\cal{F}}}_{2}$

where $g^{-1}(A)=\\{\omega\in\Omega_{1}:g(\omega)\in A\\}$. With respect to
the two measurable spaces $(\Omega_{1},{{\cal{F}}}_{1})$ and
$(\Omega_{2},{{\cal{F}}}_{2})$, a function $g:\Omega_{1}\rightarrow\Omega_{2}$
is said to be _measurable_ if it is ${{\cal{F}}}_{1}$-measurable. Two
measurable spaces $(\Omega_{1},{{\cal{F}}}_{1})$ and
$(\Omega_{2},{{\cal{F}}}_{2})$ are _isomorphic_ if there is a bijective
function $b:\Omega_{1}\rightarrow\Omega_{2}$ that is measurable and has a
measurable inverse; such a function is called an _isomorphism_. A measurable
space $(\Omega,{{\cal{F}}})$ is called a _Borel space_ if it is isomorphic to
$(A,{{\cal{B}}}(A))$ for some $A\in{{\cal{B}}}([0,1])$. If
$(\Omega_{2},{{\cal{F}}}_{2})$ is a Borel space then a measurable function
$g:\Omega_{1}\rightarrow\Omega_{2}$ is sometimes referred to as a _Borel
measurable function_ as a reminder that the target space is a Borel space.

Fix $J$ as a nonempty set (possibly uncountably infinite). Let
$(\Omega_{j},{{\cal{F}}}_{j})$ be measurable spaces for each $j\in J$. Define

$\times_{j\in J}\Omega_{j}=\\{(x_{j})_{j\in J}:x_{j}\in\Omega_{j}\quad\forall
j\in J\\}$

Define ${{\cal{C}}}$ as the collection of subsets of $\times_{j\in
J}\Omega_{j}$ of the form $\times_{j\in J}A_{j}$ for some sets $A_{j}$ that
satisfy: (i) $A_{j}\in{{\cal{F}}}_{j}$ for all $j\in J$; (ii)
$A_{j}=\Omega_{j}$ for all but at most one index $j\in J$. Define the product
sigma algebra on $\times_{j\in J}\Omega_{j}$, also called the cylindrical
sigma algebra, as

$\otimes_{j\in J}{{\cal{F}}}_{j}=\sigma({{\cal{C}}})$

where $\sigma({{\cal{C}}})$ denotes the sigma algebra generated by the
collection of sets ${{\cal{C}}}$. For a given measurable space
$(\Omega,{{\cal{F}}})$ define $\Omega^{J}=\times_{j\in J}\Omega$ and define
its product sigma algebra as $\otimes_{j\in J}{{\cal{F}}}$. A special case of
interest is $[0,1]^{J}$ with product sigma algebra $\otimes_{j\in
J}{{\cal{B}}}([0,1])$ (this measurable space is a Borel space whenever $J$ is
a finite or countably infinite set).

A _probability space_ is a triplet $(\Omega,{{\cal{F}}},P)$ where
$(\Omega,{{\cal{F}}})$ is a measurable space and
$P:{{\cal{F}}}\rightarrow[0,1]$ is a probability measure. A _random variable_
is a measurable function $X:\Omega\rightarrow\mathbb{R}$. A _random element_
is a measurable function $S:\Omega\rightarrow\Omega_{S}$ where
$(\Omega_{S},{{\cal{F}}}_{S})$ is some given measurable space. By
$U\sim{{\cal{U}}}[0,1]$ we mean that $U:\Omega\rightarrow[0,1]$ is a random
variable that is uniformly distributed over $[0,1]$.

###  II-B Standard results

###### Lemma 1

There is an isomorphism $\phi:[0,1]\rightarrow[0,1]^{\mathbb{N}}$. [See
Theorem A.47 in [38] and Chapter 13 of [39].]

###### Lemma 2

If $D$ is an uncountably infinite Borel measurable subset of a Borel space
then there is an isomorphism $b:D\rightarrow[0,1]$. [This is a result of
Kuratowski in [40], see also statement and proof in Theorem 3.3.13 of [10].]

###### Lemma 3

Let $J$ be a nonempty set (possibly uncountably infinite). Let
$(\Omega,{{\cal{F}}})$ and $(\Omega_{j},{{\cal{F}}}_{j})$ for $j\in J$ be
measurable spaces. Then [see similar Lemmas 1.7, 1.8 in [2]]:

  * •

Composition: If $f:\Omega_{1}\rightarrow\Omega_{2}$ and
$g:\Omega_{2}\rightarrow\Omega_{3}$ are measurable functions, the composition
$g\circ f$ is measurable.

  * •

Multidimensional expansion: Let $Y_{j}:\Omega\rightarrow\Omega_{j}$ be
measurable functions for each $j\in J$. The function
$Y:\Omega\rightarrow\times_{j\in J}\Omega_{j}$ given by $Y=(Y_{j})_{j\in J}$
is measurable with respect to $(\Omega,{{\cal{F}}})$ and $(\times_{j\in
J}\Omega_{j},\otimes_{j\in J}{{\cal{F}}}_{j})$. In particular, if
${{\cal{H}}}_{j}$ is another sigma algebra on $\Omega$ for each $j\in J$, and
if $Y_{j}$ is ${{\cal{H}}}_{j}$-measurable, then $Y$ is $\sigma(\cup_{j\in
J}{{\cal{H}}}_{j})$-measurable.

##  III Representation of Borel measurable functions

Throughout this section assume: $(\Omega,{{\cal{F}}})$ is a measurable space;
$J$ is a nonempty set (possibly uncountably infinite);
${{\cal{H}}}_{j}\subseteq{{\cal{F}}}$ is a subsigma algebra on $\Omega$ for
each $j\in J$.

###### Proposition 1

Define ${{\cal{C}}}$ as the set of functions $X:\Omega\rightarrow[0,1]$ of the
form $X=h(\vec{Y})$ where $h:[0,1]^{J}\rightarrow[0,1]$ is measurable,
$\vec{Y}=(Y_{j})_{j\in J}$, and $Y_{j}:\Omega\rightarrow[0,1]$ is
${{\cal{H}}}_{j}$-measurable for each $j\in J$. Define ${{\cal{Z}}}$ as the
following collection of subsets of $\Omega$:

${{\cal{Z}}}=\\{X^{-1}(B)\subseteq\Omega:B\in{{\cal{B}}}([0,1]),X\in{{\cal{C}}}\\}$

Then

a) ${{\cal{Z}}}$ is a sigma algebra on $\Omega$.

b) $\sigma(\cup_{j\in J}{{\cal{H}}}_{j})={{\cal{Z}}}$.

c) $X:\Omega\rightarrow[0,1]$ is $\sigma(\cup_{j\in
J}{{\cal{H}}}_{j})$-measurable if and only if $X\in{{\cal{C}}}$.

###### Proof:

(Part (a) of Proposition 1) We show ${{\cal{Z}}}$ satisfies the three
properties of a sigma algebra on $\Omega$:

  1. 1.

To show $\Omega\in{{\cal{Z}}}$, define the measurable functions $h=0$,
$Y_{j}=0$ for all $j\in J$, and $X=h(\vec{Y})=0\in{{\cal{C}}}$. Define
$B=[0,1]\in{{\cal{B}}}([0,1])$. Then $\Omega=X^{-1}(B)\in{{\cal{Z}}}$.

  2. 2.

Fix $A\in{{\cal{Z}}}$. We want to show $A^{c}\in{{\cal{Z}}}$. Since
$A\in{{\cal{Z}}}$ there exists $X\in{{\cal{C}}}$ and $B\in{{\cal{B}}}([0,1])$
such that $A=X^{-1}(B)$. Then $A^{c}=X^{-1}(B^{c})\in{{\cal{Z}}}$.

  3. 3.

Let $\\{A_{n}\\}_{n=1}^{\infty}$ be an infinite sequence of sets in
${{\cal{Z}}}$. We want to show $\cup_{n=1}^{\infty}A_{n}\in{{\cal{Z}}}$. It
suffices to show $\cap_{n=1}^{\infty}A_{n}^{c}\in{{\cal{Z}}}$. For each
positive integer $n$ there exists $X_{n}\in{{\cal{C}}}$ and
$B_{n}\in{{\cal{B}}}([0,1])$ such that $A_{n}=X_{n}^{-1}(B_{n})$ and so
$A_{n}^{c}=X_{n}^{-1}(B_{n}^{c})$. Let
$\phi:[0,1]\rightarrow[0,1]^{\mathbb{N}}$ be an isomorphism (recall Lemma 1).
Define

$\displaystyle X$ $\displaystyle=\phi^{-1}\left((X_{n})_{n=1}^{\infty}\right)$
(8) $\displaystyle B$
$\displaystyle=\phi^{-1}\left(\times_{n=1}^{\infty}B_{n}^{c}\right)$

Since $\phi^{-1}$ maps measurable sets to measurable sets we have
$B\in{{\cal{B}}}([0,1])$. Then:

$\displaystyle\cap_{n=1}^{\infty}A_{n}^{c}$
$\displaystyle=\left\\{\omega\in\Omega:X_{n}(\omega)\in B_{n}^{c}\quad\forall
n\in\mathbb{N}\right\\}$
$\displaystyle=\left\\{\omega\in\Omega:\phi^{-1}\left((X_{n}(\omega))_{n=1}^{\infty}\right)\in\phi^{-1}\left(\times_{n=1}^{\infty}B_{n}^{c}\right)\right\\}$
$\displaystyle=X^{-1}(B)$

Considering the structure of set ${{\cal{Z}}}$, it remains to show that
$X\in{{\cal{C}}}$. Fix $n\in\mathbb{N}$. Since $X_{n}\in{{\cal{C}}}$ we have

$X_{n}=h^{(n)}(\vec{Y}^{(n)})$ (9)

for some measurable function $h^{(n)}:[0,1]^{J}\rightarrow[0,1]$ and some
$\vec{Y}^{(n)}=(Y^{(n)}_{j})_{j\in J}$ such that
$Y^{(n)}_{j}:\Omega\rightarrow[0,1]$ is ${{\cal{H}}}_{j}$-measurable for all
$j\in J$. For each $j\in J$ define $W_{j}:\Omega\rightarrow[0,1]$ by

$W_{j}=\phi^{-1}(Y_{j}^{(1)},Y_{j}^{(2)},Y_{j}^{(3)},\ldots)$ (10)

Note that $W_{j}$ is a composition of the measurable function
$\phi^{-1}:[0,1]^{\mathbb{N}}\rightarrow[0,1]$ with the
${{\cal{H}}}_{j}$-measurable function $Z:\Omega\rightarrow[0,1]^{\mathbb{N}}$
given by
$Z(\omega)=(Y_{j}^{(1)}(\omega),Y_{j}^{(2)}(\omega),Y_{j}^{(3)}(\omega),\ldots)$
and hence $W_{j}$ is itself ${{\cal{H}}}_{j}$-measurable (recall Lemma 3).
Write function $\phi$ according to its components
$\phi=(\phi_{1},\phi_{2},\phi_{3},\ldots)$ and note that each component
function $\phi_{n}:[0,1]\rightarrow[0,1]$ is measurable. For each $j\in J$ we
have from (10)

$\displaystyle(Y_{j}^{(1)},Y_{j}^{(2)},Y_{j}^{(3)},\ldots)$
$\displaystyle=\phi(W_{j})$
$\displaystyle=(\phi_{1}(W_{j}),\phi_{2}(W_{j}),\phi_{3}(W_{j}),\ldots)$

and so $Y_{j}^{(n)}=\phi_{n}(W_{j})$ for all $j\in J,n\in\mathbb{N}$, that is,

$\vec{Y}^{(n)}=\left(\phi_{n}(W_{j})\right)_{j\in J}$

Substituting the above equality into (9) yields

$X_{n}=h^{(n)}((\phi_{n}(W_{j}))_{j\in J})$ (11)

Define the function $\alpha^{(n)}:[0,1]^{J}\rightarrow[0,1]$ for each
$x=(x_{j})_{j\in J}$ by

$\alpha^{(n)}(x)=h^{(n)}((\phi_{n}(x_{j}))_{j\in J})$

Define $\vec{W}=(W_{j})_{j\in J}$. Using this and the definition of
$\alpha^{(n)}$ in (11) gives:

$X_{n}=\alpha^{(n)}(\vec{W})$ (12)

Define the function $h:[0,1]^{J}\rightarrow[0,1]$ by

$h(x)=\phi^{-1}(\alpha^{(1)}(x),\alpha^{(2)}(x),\alpha^{(3)}(x),\ldots)\quad\forall
x\in[0,1]^{J}$

The functions $\alpha^{(n)}$ and $h$ are formed by compositions and
multidimensional expansions of measurable functions and so they are themselves
measurable (recall Lemma 3). By definition of $h$ it holds that

$\displaystyle h(\vec{W})$
$\displaystyle=\phi^{-1}(\alpha^{(1)}(\vec{W}),\alpha^{(2)}(\vec{W}),\alpha^{(3)}(\vec{W}),\ldots)$
$\displaystyle\overset{(a)}{=}\phi^{-1}(X_{1},X_{2},X_{3},\ldots)$
$\displaystyle\overset{(b)}{=}X$

where (a) holds by substituting (12); (b) holds by definition of $X$ in (8).
Thus, $X\in{{\cal{C}}}$.

∎

###### Proof:

(Part (b) of Proposition 1) To show that
${{\cal{Z}}}\subseteq\sigma(\cup_{j\in J}{{\cal{H}}}_{j})$, fix
$A\in{{\cal{Z}}}$. By definition of ${{\cal{Z}}}$, there exists
$B\in{{\cal{B}}}([0,1])$ and $X\in{{\cal{C}}}$ such that $A=X^{-1}(B)$, where
$X=h(\vec{Y})$ for some measurable function $h:[0,1]^{J}\rightarrow[0,1]$ and
some vector-valued function $\vec{Y}=(Y_{j})_{j\in J}$ composed of
${{\cal{H}}}_{j}$-measurable functions $Y_{j}:\Omega\rightarrow[0,1]$ for each
$j\in J$. Thus

$\displaystyle A$ $\displaystyle=X^{-1}(B)$
$\displaystyle=\\{\omega\in\Omega:h(\vec{Y})\in B\\}$ (13)

Lemma 3 ensures that $h(\vec{Y})$ is $\sigma(\cup_{j\in
J}{{\cal{H}}}_{j})$-measurable, and so the right-hand-side of (13) is a set in
$\sigma(\cup_{j\in J}{{\cal{H}}}_{j})$, which implies the desired conclusion
$A\in\sigma(\cup_{j\in J}{{\cal{H}}}_{j})$.

We now show $\sigma(\cup_{j\in J}{{\cal{H}}}_{j})\subseteq{{\cal{Z}}}$. Fix
$m\in J$. Let $A_{m}$ be a subset of $\Omega$ such that
$A_{m}\in{{\cal{H}}}_{m}$. Define $\vec{Y}=(Y_{j})_{j\in J}$ by $Y_{j}=0$ if
$j\neq m$ and

$Y_{m}(\omega)=\left\\{\begin{array}[]{cc}1&\mbox{ if $\omega\in A_{m}$}\\\
0&\mbox{ else}\end{array}\right.$

It is clear that $Y_{j}$ is ${{\cal{H}}}_{j}$-measurable for all $j\in J$.
Define the measurable function $h:[0,1]^{J}\rightarrow[0,1]$ by
$h((x_{j})_{j\in J})=x_{m}$. Define $B=\\{1\\}\in{{\cal{B}}}([0,1])$. Then

$A_{m}=\\{\omega\in\Omega:h(\vec{Y}(\omega))\in B\\}$

so by definition of ${{\cal{Z}}}$ we have $A_{m}\in{{\cal{Z}}}$. This holds
for all $m\in J$ and $A_{m}\in{{\cal{H}}}_{m}$ so

$\cup_{j\in J}{{\cal{H}}}_{j}\subseteq{{\cal{Z}}}$

Taking the sigma algebra of both sides gives

$\sigma(\cup_{j\in J}{{\cal{H}}}_{j})\subseteq\sigma({{\cal{Z}}})$

Part (a) implies that $\sigma({{\cal{Z}}})={{\cal{Z}}}$, which completes the
proof. ∎

###### Proof:

(Part (c) of Proposition 1) Suppose $X\in{{\cal{C}}}$. Then $X=h(\vec{Y})$ for
some measurable $h$ and for $\vec{Y}=(Y_{j})_{j\in J}$ with
$Y_{j}:\Omega\rightarrow[0,1]$ being ${{\cal{H}}}_{j}$-measurable for all
$j\in J$. Lemma 3 implies that $X$ is $\sigma(\cup_{j\in
J}{{\cal{H}}}_{j})$-measurable.

Now suppose $X:\Omega\rightarrow[0,1]$ is $\sigma(\cup_{j\in
J}{{\cal{H}}}_{j})$-measurable. It is well known that $X$ is the pointwise
limit of _simple_ functions $X_{m}$, so that

$X(\omega)=\lim_{m\rightarrow\infty}X_{m}(\omega)\quad\forall\omega\in\Omega$
(14)

where for each positive integer $m$ the function
$X_{m}:\Omega\rightarrow[0,1]$ has the form

$X_{m}=\sum_{i=1}^{k_{m}}v_{i,m}1_{\\{X\in I_{i,m}\\}}$ (15)

where $k_{m}$ is some positive integer; $I_{1,m},I_{2,m},\ldots,I_{k_{m},m}$
are some disjoint sets in ${{\cal{B}}}([0,1])$ whose union is $[0,1]$; $1_{A}$
is an indicator function that is 1 if event $A$ is true and $0$ else;
$v_{i,m}$ are some real numbers in $[0,1]$ for each
$i\in\\{1,\ldots,k_{m}\\}$.

Since $X$ is $\sigma(\cup_{j\in J}{{\cal{H}}}_{j})$-measurable, we have for
each positive integer $m$ and each $i\in\\{1,\ldots,k_{m}\\}$:

$\\{X\in I_{i,m}\\}\in\sigma(\cup_{j\in J}{{\cal{H}}}_{j})={{\cal{Z}}}$

where the final equality holds by part (b). It follows by definition of
${{\cal{Z}}}$ that

$\\{X\in I_{i,m}\\}=\\{\omega\in\Omega:X_{i,m}(\omega)\in B_{i,m}\\}$ (16)

for some $B_{i,m}\in{{\cal{B}}}([0,1])$ and some $X_{i,m}\in{{\cal{C}}}$.
Substituting (16) into (15) and using (14) we obtain

$X=\limsup_{m\rightarrow\infty}\sum_{i=1}^{k_{m}}v_{i,m}1_{\\{X_{i,m}\in
B_{i,m}\\}}$ (17)

where we have used the fact that the limit exists and so must be equal to the
$\limsup$.

By definition of ${{\cal{C}}}$, each function $X_{i,m}\in{{\cal{C}}}$ has the
form

$X_{i,m}=h^{(i,m)}((Y_{j}^{(i,m)})_{j\in J})$ (18)

for measurable functions $h^{(i,m)}:[0,1]^{J}\rightarrow[0,1]$ and some
${{\cal{H}}}_{j}$-measurable functions $Y_{j}^{(i,m)}:\Omega\rightarrow[0,1]$
for $j\in J$. Let $L$ be the (countably infinite) set of all indices $(i,m)$
such that $m\in\mathbb{N}$ and $i\in\\{1,\ldots,k_{m}\\}$. Let
$\phi:[0,1]\rightarrow[0,1]^{L}$ be an isomorphism. For each $j\in J$ define
$W_{j}=\phi^{-1}((Y_{j}^{(i,m)})_{(i,m)\in L})$. Since $W_{j}$ is the
composition of the measurable function $\phi^{-1}$ with the multidimensional
expansion of ${{\cal{H}}}_{j}$-measurable functions, it is itself
${{\cal{H}}}_{j}$-measurable (recall Lemma 3). Define $\phi_{i,m}$ as the
$(i,m)$ component of the $\phi$ function for each $(i,m)\in L$. Then from (18)

$\displaystyle X_{i,m}$
$\displaystyle=h^{(i,m)}\left((\phi_{i,m}(W_{j}))_{j\in J}\right)$

Define $\vec{W}=(W_{j})_{j\in J}$. Then

$(X_{i,m})_{(i,m)\in L}=\alpha(\vec{W})$ (19)

where $\alpha:[0,1]^{J}\rightarrow[0,1]^{L}$ is the measurable function
defined for $x=(x_{j})_{j\in J}$ by component functions $\alpha_{i,m}(x)$ for
each $(i,m)\in L$ by

$\alpha_{i,m}(x)=h^{(i,m)}\left((\phi_{i,m}(x_{j}))_{j\in J}\right)$

Define the measurable function $g:[0,1]^{L}\rightarrow[0,1]$ for each
$x=(x_{i,m})_{(i,m)\in L}$ by

$g(x)=\limsup_{m\rightarrow\infty}\sum_{i=1}^{k_{m}}v_{i,m}1_{\\{x_{i,m}\in
B_{i,m}\\}}$

where we observe the limsup is in the set $[0,1]$ because for each $m$, all
$v_{i,m}$ values are in $[0,1]$ and at most one term in the sum is nonzero. It
follows that

$\displaystyle X$ $\displaystyle\overset{(a)}{=}g((X_{i,m})_{(i,m)\in L})$
$\displaystyle\overset{(b)}{=}g(\alpha(\vec{W}))$

where (a) holds by (17); (b) holds by (19). We can now define the measurable
function $h:[0,1]^{J}\rightarrow[0,1]$ by $h(x)=g(\alpha(x))$ and we see that
$X=h(\vec{W})$, where $\vec{W}=(W_{j})_{j\in J}$ for
$W_{j}:\Omega\rightarrow[0,1]$ being ${{\cal{H}}}_{j}$-measurable for all
$j\in J$. It follows that $X$ has the required form for inclusion in the set
${{\cal{C}}}$. ∎

Now fix $K$ as a finite or countably infinite set. For each $k\in K$ let
$(V_{k},{{\cal{F}}}_{k})$ be a Borel space. We consider measurable functions
$X_{k}:\Omega\rightarrow V_{k}$.

###### Proposition 2

Fix $J$ as a nonempty set (possibly uncountably infinite). For each $j\in J$,
let ${{\cal{H}}}_{j}\subseteq{{\cal{F}}}$ be a sigma algebra on $\Omega$. Fix
functions $X_{k}:\Omega\rightarrow V_{k}$ for $k\in K$, where
$(V_{k},{{\cal{F}}}_{k})$ are given Borel spaces. For each $k\in K$, fix
$J_{k}\subseteq J$. Then

$X_{k}\mbox{ is $\sigma(\cup_{j\in
J_{k}}{{\cal{H}}}_{j})$-measurable}\quad\forall k\in K$ (20)

if and only if for each $k\in K$ we have

$X_{k}=h_{k}((Y_{j})_{j\in\tilde{J}_{k}})$ (21)

where $h_{k}:[0,1]\rightarrow V_{k}$ is some measurable function,
$Y_{j}:\Omega\rightarrow[0,1]$ are some ${{\cal{H}}}_{j}$-measurable functions
for each $j\in J$, and $\tilde{J}_{k}$ is a finite or countably infinite
subset of $J_{k}$ for each $k\in K$.

###### Proof:

For the reverse direction, it is clear from Lemma 3 that if $(X_{k})_{k\in K}$
has the given form $X_{k}=h_{k}((Y_{j})_{j\in\tilde{J}_{k}})$ then (20) holds.
To prove the forward direction, suppose that (20) holds. Fix $k\in K$. Since
$(V_{k},{{\cal{F}}}_{k})$ is a Borel space, there is a set
$D_{k}\in{{\cal{B}}}([0,1])$ and an isomorphism $b_{k}:V_{k}\rightarrow
D_{k}$. Define $Z_{k}:\Omega\rightarrow[0,1]$ by $Z_{k}=b_{k}(X_{k})$. Lemma 3
implies that $Z_{k}$ is $\sigma(\cup_{j\in J_{k}}{{\cal{H}}}_{j})$-measurable.
By Proposition 1 we have $Z_{k}=g^{(k)}\left((Y_{j}^{(k)})_{j\in
J_{k}}\right)$ with $Y_{j}^{(k)}:\Omega\rightarrow[0,1]$ being
${{\cal{H}}}_{j}$-measurable for all $j\in J$, and
$g^{(k)}:[0,1]^{J_{k}}\rightarrow[0,1]$ is measurable. For every such real-
valued measurable function $g^{(k)}$, there is a countable subset
$\tilde{J}_{k}\subseteq J_{k}$ for which the function only depends on the
variables $y_{j}$ for $j\in\tilde{J}_{k}$ [see, for example, related Exercise
1.1.22 in [41] and Section 3.13d in [3]]. Thus, we modify the $g^{(k)}$
functions to $f^{(k)}:[0,1]^{\tilde{J}_{k}}\rightarrow[0,1]$ measurable for
which

$Z_{k}=f^{(k)}\left((Y_{j}^{(k)})_{j\in\tilde{J}_{k}}\right)$ (22)

Let $\phi:[0,1]\rightarrow[0,1]^{K}$ be an isomorphism. For each $j\in J$
define

$Y_{j}=\phi^{-1}((Y_{j}^{(k)})_{k\in K})$

Since each function $Y_{j}^{(k)}$ is ${{\cal{H}}}_{j}$-measurable, $Y_{j}$ is
also ${{\cal{H}}}_{j}$-measurable (recall Lemma 3). For each $k\in K$ let
$\phi_{k}$ denote the $k$th component of $\phi$. Then

$\phi_{k}(Y_{j})=Y_{j}^{(k)}$

which gives by substitution into (22):

$\displaystyle Z_{k}$
$\displaystyle=f^{(k)}\left((\phi_{k}(Y_{j}))_{j\in\tilde{J}_{k}}\right)$
$\displaystyle=\alpha^{(k)}\left((Y_{j})_{j\in\tilde{J}_{k}}\right)$ (23)

where $\alpha^{(k)}:[0,1]^{\tilde{J}_{k}}\rightarrow[0,1]$ is defined as the
measurable function for each $x=(x_{j})_{j\in\tilde{J}_{k}}$ by

$\alpha^{(k)}(x)=f^{(k)}\left((\phi_{k}(x_{j}))_{j\in\tilde{J}_{k}}\right)$

Substituting the definition $Z_{k}=b_{k}(X_{k})$ into the left-hand-side of
(23) gives

$b_{k}(X_{k})=\alpha^{(k)}\left((Y_{j})_{j\in\tilde{J}_{k}}\right)$

Taking $b_{k}^{-1}(\cdot)$ of both sides gives

$X_{k}=b_{k}^{-1}\left(\alpha^{(k)}\left((Y_{j})_{j\in\tilde{J}_{k}}\right)\right)$

This holds for all $k\in K$ and has the desired form
$X_{k}=h_{k}\left((Y_{j})_{j\in\tilde{J}_{k}}\right)$ when the measurable
function $h_{k}:[0,1]^{\tilde{J}_{k}}\rightarrow V_{k}$ is defined by
$h_{k}(x)=b_{k}^{-1}(\alpha^{(k)}(x))$ for all $x\in[0,1]^{\tilde{J}_{k}}$. ∎

###### Corollary 1

Let $(V,{{\cal{F}}}_{V})$ be a Borel space. Let $J$ be a nonempty set and let
$(\Omega_{j},{{\cal{F}}}_{j})$ be measurable spaces for each $j\in J$. If
$f:\times_{j\in J}\Omega_{j}\rightarrow V$ is a measurable function with
respect to $(\times_{j\in J}\Omega_{j},\otimes_{j\in J}{{\cal{F}}}_{j})$ and
$(V,{{\cal{F}}}_{V})$ and $\omega=(\omega_{j})_{j\in J}$ then

$f(\omega)=h((\theta_{j}(\omega_{j}))_{j\in\tilde{J}})\quad\forall\omega\in\times_{j\in
J}\Omega_{j}$

where $\tilde{J}\subseteq J$ is a finite or countably infinite set,
$\theta_{j}:\Omega_{j}\rightarrow[0,1]$ is a measurable function for each
$j\in\tilde{J}$, and $h:\times_{j\in\tilde{J}}\Omega_{j}\rightarrow V$ is some
measurable function with respect to
$(\times_{j\in\tilde{J}}\Omega_{j},\otimes_{j\in J}{{\cal{F}}}_{j})$ and
$(V,{{\cal{F}}}_{V})$.

###### Proof:

Define $S_{j}:\Omega\rightarrow\Omega_{j}$ by $S_{j}(\omega)=\omega_{j}$ for
$j\in J$. Define ${{\cal{H}}}_{j}=\sigma(S_{j})$. Then $f$ is
$\sigma(\cup_{j\in J}{{\cal{H}}}_{j})$-measurable and Proposition 2 implies
$f=h((Y_{j})_{j\in\tilde{J}})$ for a countable subset $\tilde{J}\subseteq J$,
a measurable function $h$, and for $Y_{j}$ being $\sigma(S_{j})$ measurable
for each $j\in\tilde{J}$. The Doob-Dynkin lemma implies
$Y_{j}=\theta_{j}(S_{j})=\theta_{j}(\omega_{j})$ for $j\in\tilde{J}$. ∎

##  IV Stochastic control

Throughout this section we fix a probability triplet $(\Omega,{{\cal{F}}},P)$.
Let $(\Omega_{S},{{\cal{F}}}_{S})$ be a measurable space and let
$(\Omega_{X},{{\cal{F}}}_{X})$ be a Borel space. Consider a discrete time
system that evolves over time slots $k\in\\{1,2,3,\ldots\\}$. Let
$(S_{k})_{k=1}^{\infty}$ be a sequence of random elements of the form
$S_{k}:\Omega\rightarrow\Omega_{S}$. The value $S_{k}$ represents a system
characteristic or state at time $k$. Let ${{\cal{G}}}\subseteq{{\cal{F}}}$ be
a sigma algebra on $\Omega$ that is used as a source of randomness to
facilitate stochastic decisions. Let $(X_{k})_{k=1}^{\infty}$ be a sequence of
random elements of the form $X_{k}:\Omega\rightarrow\Omega_{X}$. Each $X_{k}$
represents a decision that is made at time $k$ based on observing
$S_{1},\ldots,S_{k}$. Assume decisions for each step $k$ are made to ensure

$\displaystyle X_{k}\mbox{ is
$\sigma(\sigma(S_{1})\cup\cdots\cup\sigma(S_{k})\cup{{\cal{G}}})$-measurable}$
(24) $\displaystyle X_{k}\in C(S_{k})\quad$ (25)

where $C:\Omega_{S}\rightarrow Pow(\Omega_{X})$ is a set-valued map and
$Pow(\Omega_{X})$ is the set of all subsets of $\Omega_{X}$. Constraint (24)
is the _causal and measurable_ constraint. Constraint (25) is a system
constraint that restricts the $X_{k}$ value to a set that depends on $S_{k}$.
Values of $S_{k+1}$ are determined by some probability rule on the system and
are possibly dependent on $S_{1},\ldots,S_{k}$ and $X_{1},\ldots,X_{k}$. A
special case is when $S_{k}$ represents the state of a discrete time Markov
chain and there is some transition probability kernel that specifies the
conditional distribution of $S_{k+1}$ given $S_{k}$ and $X_{k}$.

Decisions $X_{k}$ can be vector valued with components that represent power
expenditures, costs, or rewards incurred or earned by different parts of the
system at time $k$. We want to characterize all decision elements
$(X_{k})_{k=1}^{\infty}$ that satisfy (24)-(25). Proposition 2 ensures that if
(24)-(25) hold then

$X_{k}=h_{k}(Y_{1},\ldots,Y_{k},R)\in C(S_{k})\quad\forall k\in\mathbb{N}$

for some Borel measurable functions
$h_{k}:\Omega_{S}^{k}\times[0,1]\rightarrow\Omega_{X}$, some
${{\cal{G}}}$-measurable random variable $R:\Omega\rightarrow[0,1]$, and some
random variables $Y_{k}=\theta_{k}(S_{k})$ for some measurable functions
$\theta_{k}:\Omega_{S}\rightarrow[0,1]$. It immediately follows that

$X_{k}=g_{k}(S_{1},\ldots,S_{k},R)\in C(S_{k})\quad\forall k\in\mathbb{N}$
(26)

where $g_{k}:\Omega_{S}^{k}\times[0,1]\rightarrow\Omega_{X}$ is defined

$g_{k}(s_{1},\ldots,s_{k},r)=h_{k}(\theta_{1}(s_{1}),\ldots,\theta_{k}(s_{k}),r)$

Consider the following additional assumptions:

###### Assumption 1

There is a deterministic measurable choice function
$\psi:\Omega_{S}\rightarrow\Omega_{X}$ such that $\psi(s)\in C(s)$ for all
$s\in\Omega_{S}$.

###### Assumption 2

$\\{(s,x)\in\Omega_{S}\times\Omega_{X}:x\in
C(s)\\}\in{{\cal{F}}}_{S}\otimes{{\cal{F}}}_{X}$

Both assumptions hold if $\Omega_{S}$ is a finite or countably infinite set,
${{\cal{F}}}_{S}=Pow(\Omega_{S})$, and $C(s)$ is a nonempty subset of
${{\cal{F}}}_{X}$ for each $s\in\Omega_{S}$. Assumptions 1-2 also hold in the
case when a vector of resources $P_{k}\in\mathbb{R}^{a}$ (such as power
allocations) is chosen on each slot $k\in\mathbb{N}$ and affects a vector of
rewards $R_{k}\in\mathbb{R}^{b}$ (such as transmission rates over links of a
communication system) via $R_{k}=f(S_{k},P_{k})$, where $a,b$ are given
positive integers, $\Omega_{P}$ is a given Borel measurable subset of
$\mathbb{R}^{a}$, $f:\Omega_{S}\times\Omega_{P}\rightarrow\mathbb{R}^{b}$ is a
given measurable function, and

$C(s)=\\{(p,f(s,p))\in\mathbb{R}^{a+b}:p\in\Omega_{P}\\}\quad\forall
s\in\Omega_{S}$ (27)

Indeed, Assumption 1 holds for (27) because $\psi(s)=(0,f(s,0))$ is a
deterministic measurable choice function; Assumption 2 can be seen to hold for
(27) by defining the measurable function
$g:\Omega_{S}\times\Omega_{P}\times\mathbb{R}^{b}\rightarrow\mathbb{R}^{b}$ by
$g(s,p,r)=r-f(s,p)$ and observing that $g^{-1}(\\{0\\})$ is measurable. More
general sufficient conditions for existence of a deterministic measurable
choice function are given in the _selection theorems_ of Blackwell and Ryll-
Nardzewski [4], Kuratowski and Ryll-Nardzewski [5], Dubins and Savage [6],
Maitra [7], Aumann [8], Schäl [42], Von Neumann [9], Srivastava [10], and
Cascales, Kadets, Rodríguez [18].

###### Lemma 4

Suppose Assumptions 1 and 2 hold. The sequence $(X_{k})_{k=1}^{\infty}$ of
Borel measurable random elements of the form
$X_{k}:\Omega\rightarrow\Omega_{X}$ satisfies (24)-(25) if and only if there
are measurable functions
$v_{k}:\Omega_{S}^{k}\times[0,1]\rightarrow\Omega_{X}$ for each
$k\in\mathbb{N}$ such that

$v_{k}(s_{1},\ldots,s_{k},r)\in
C(s_{k})\quad\forall(s_{1},\ldots,s_{k},r)\in\Omega_{S}^{k}\times[0,1]$ (28)

and a ${{\cal{G}}}$-measurable random variable $R:\Omega\rightarrow[0,1]$ such
that

$X_{k}=v_{k}(S_{1},\ldots,S_{k},R)\quad\forall k\in\mathbb{N}$ (29)

###### Proof:

Suppose $(X_{k})_{k=1}^{\infty}$ satisfy (24)-(25). Then (26) holds for some
measurable functions $g_{k}:\Omega_{S}^{k}\times[0,1]\rightarrow\Omega_{X}$
and some ${{\cal{G}}}$-measurable random variable $R:\Omega\rightarrow[0,1]$.
Define $v_{k}:\Omega_{S}^{k}\times[0,1]\rightarrow\Omega_{X}$ by

$v_{k}(s_{1},\ldots,s_{k},r)=\left\\{\begin{array}[]{cc}g_{k}(s_{1},\ldots,s_{k},r)&\mbox{
if $g_{k}(s_{1},\ldots,s_{k},r)\in C(s_{k})$}\\\ \psi(s_{k})&\mbox{
else}\end{array}\right.$

Assumptions 1, 2, and measurability of $g_{k}$ imply that $v_{k}$ is
measurable. Since $\psi(s)\in C(s)$ for all $s\in\Omega_{S}$, function $v_{k}$
satisfies (28). By (26) and definition of $v_{k}$ we obtain (29).

Conversely, suppose there are $v_{k}$ functions and a random variable $R$ that
satisfy (28)-(29). Properties (28)-(29) imply $X_{k}\in C(S_{k})$ for all $k$,
while measurability of $v_{k}$ and the structure
$X_{k}=v_{k}(S_{1},\ldots,S_{k},R)$ ensure (by the Doob-Dynkin lemma) that
$X_{k}$ is $\sigma(S_{1},\ldots,S_{k},R)$-measurable. Since
$\sigma(R)\subseteq{{\cal{G}}}$ it holds that $X_{k}$ is
$\sigma(\sigma(S_{1})\cup\cdots\cup\sigma(S_{k})\cup{{\cal{G}}})$-measurable,
so that (24)-(25) hold. ∎

The $v_{k}$ functions and the random variable $R:\Omega\rightarrow[0,1]$ in
the above result completely specify a causal and measurable control policy: At
time $0$, generate a ${{\cal{G}}}$-measurable random variable
$R:\Omega\rightarrow[0,1]$. At each step $k\in\\{1,2,3,\ldots\\}$, observe
$(S_{1},\ldots,S_{k})$ and make the decision
$X_{k}=v_{k}(S_{1},\ldots,S_{k},R)$. The above lemma ensures that, if
Assumptions 1-2 hold, all policies that satisfy (24)-(25) can be specified in
this way.

###  IV-A Another representation

The following representation theorem from Kallenberg [2] bears some
resemblance to (26) and uses the concept of a _randomization variable $U$_.

###### Theorem 1

(Proposition 5.13 in [2]) Fix $(\Omega,{{\cal{F}}},P)$ as a probability
triplet and let $X:\Omega\rightarrow\Omega_{X}$ and
$S:\Omega\rightarrow\Omega_{S}$ be random elements where
$(\Omega_{X},{{\cal{F}}}_{X})$ is a Borel space and
$(\Omega_{S},{{\cal{F}}}_{S})$ is a measurable space. Suppose there is a
random variable $U\sim{{\cal{U}}}[0,1]$ that is independent of $(S,X)$ ($U$ is
called a _randomization variable_). Then

$X=f(S,R)\quad\mbox{almost surely}$

for some measurable function $f:\Omega_{S}\times[0,1]\rightarrow\Omega_{X}$
and some random variable $R\sim{{\cal{U}}}[0,1]$ that is independent of $S$.
Further, $R$ is $\sigma(S,X,U)$-measurable.

The next simple corollary changes “almost surely” to “surely.”

###### Corollary 2

Under the same assumptions as Theorem 1 we can ensure $X=g(S,W)$ surely for
some measurable function $g:\Omega_{S}\times[0,1]\rightarrow\Omega_{X}$ and
some random variable $W\sim{{\cal{U}}}[0,1]$ that is independent of $S$ and
that is $\sigma(S,X,U)$-measurable.

###### Proof:

First consider the case when $\Omega_{X}$ is an uncountably infinite set.
Theorem 1 implies $X=f(S,R)$ almost surely for some measurable $f$ and some
random variable $R\sim{{\cal{U}}}[0,1]$ that is independent of $S$. Let $C$ be
an uncountable Borel measurable subset of $[0,1]$ that has measure 0, such as
the Cantor set. Let $b:C\rightarrow\Omega_{X}$ be an isomorphism (recall Lemma
2). Define the random variable $W:\Omega\rightarrow[0,1]$ by

$W=\left\\{\begin{array}[]{cc}R&\mbox{ if $X=f(S,R)$ and $R\notin C$}\\\
b^{-1}(X)&\mbox{ else}\end{array}\right.$

Since $P[X=f(S,R)]=1$ and $P[R\notin C]=1$ we have that $P[W=R]=1$ and so $W$
is also uniformly distributed over $[0,1]$ and independent of $S$. By
definition of $W$ we have

$\displaystyle W\notin C\implies\mbox{($W=R$ and $X=f(S,R)$)}$ (30)
$\displaystyle W\in C\implies W=b^{-1}(X)$ (31)

Define the measurable function $g:\Omega_{S}\times[0,1]\rightarrow\Omega_{X}$
by

$g(s,w)=\left\\{\begin{array}[]{cc}f(s,w)&\mbox{ if $w\notin C$}\\\
b(w)&\mbox{ else}\end{array}\right.$

It remains to show $X=g(S,W)$. If $W\notin C$ then by definition of $g$ we
have

$\displaystyle g(S,W)$ $\displaystyle=f(S,W)$ $\displaystyle\overset{(a)}{=}X$

where (a) holds by (30). If $W\in C$ then by definition of $g$ we have

$g(S,W)=b(W)=b(b^{-1}(X))=X$

where we have used (31). The case when $\Omega_{X}$ is finite or countably
infinite is similar and proceeds by defining $C$ as a subset of $[0,1]$ with
the same cardinality as $\Omega_{X}$. ∎

###### Corollary 3

If random elements $(S_{k})_{k=1}^{\infty}$ and $(X_{k})_{k=1}^{\infty}$
satisfy $X_{k}\in C(S_{k})$ for all $k\in\mathbb{N}$ (where each
$X_{k}:\Omega\rightarrow\Omega_{X}$ is measurable with respect to the Borel
space $(\Omega_{X},{{\cal{F}}}_{X})$; each $S_{k}:\Omega\rightarrow\Omega_{S}$
is measurable with respect to the general measurable space
$(\Omega_{S},{{\cal{F}}}_{S})$), and if there is a random variable
$U\sim{{\cal{U}}}[0,1]$ that is independent of $(S_{k},X_{k})_{k=1}^{\infty}$,
then

a) For all $k\in\mathbb{N}$ we (surely) have $X_{k}=g_{k}(S_{k},W_{k})\in
C(S_{k})$ for some measurable function
$g_{k}:\Omega_{S}\times[0,1]\rightarrow\Omega_{X}$ and some random variable
$W_{k}\sim{{\cal{U}}}[0,1]$ that is independent of $S_{k}$.

b) If Assumptions 1-2 hold then for all $k\in\mathbb{N}$ there is a measurable
function $v_{k}:\Omega_{S}\times[0,1]\rightarrow\Omega_{X}$ that satisfies
$v_{k}(s,r)\in C(s)$ for all $(s,r)\in\Omega_{S}\times[0,1]$ such that

$X_{k}=v_{k}(S_{k},W_{k})$ (32)

where the random variables $W_{k}$ are the same as in part (a).

###### Proof:

Part (a) follows immediately from Corollary 2. To prove (b), fix
$k\in\\{1,2,3,\ldots\\}$ and define

$v_{k}(s,r)=\left\\{\begin{array}[]{cc}g_{k}(s,r)&\mbox{ if $g_{k}(s,r)\in
C(s)$}\\\ \psi(s)&\mbox{ else}\end{array}\right.$

where $g_{k}$ is from part (a). Assumptions 1 and 2 and measurability of
$g_{k}$ ensure measurability of $v_{k}$. Since $\psi(s)\in C(s)$ for all
$s\in\Omega_{S}$, it is clear that $v_{k}(s,r)\in C(s)$ for all
$(s,r)\in\Omega_{S}\times[0,1]$. By part (a) it holds that
$X_{k}=v_{k}(S_{k},W_{k})$. ∎

The equality (32) has a simpler structure than (29). However, the $v_{k}$
functions in (29) completely specify a causal and measurable control policy.
In contrast, the $v_{k}$ functions in (32) do not specify a control policy
because each $W_{k}$ may have some unknown dependence on
$S_{1},\ldots,S_{k-1}$ as well as on additional sources of (potentially
noncausal) randomness.

###  IV-B Opportunistic scheduling

The following special case is of interest in the area of wireless networks.
Fix $m\in\mathbb{N}$ and let $(\mathbb{R}^{m},{{\cal{B}}}(\mathbb{R}^{m}))$ be
the measurable space for the decision elements $X_{k}$. There are $m$
different wireless links that can change over time according to states
$(S_{k})_{k=1}^{\infty}$, where $S_{k}$ describes the state of all channels on
slot $k$. At the start of each slot $k\in\mathbb{N}$ we observe $S_{k}$ and
then choose a transmission rate vector $X_{k}\in C(S_{k})$, where
$C(S_{k})\subseteq\mathbb{R}^{m}$ is the set of all transmission rate options
available when the channel state is $S_{k}$ (different rate options arise, for
example, from different modulation and coding choices). This is called an
_opportunistic scheduling system_ because the state $S_{k}$ is known before
$X_{k}$ is decided. Control strategies for such systems consider network
stability [14][23], utility maximization [13][12][24][25][26][27], and energy
minimization [28]. Assume $(S_{k})_{k=1}^{\infty}$ are identically distributed
random elements associated with a measurable space
$(\Omega_{S},{{\cal{F}}}_{S})$ and a distribution
$\lambda:{{\cal{F}}}_{S}\rightarrow[0,1]$:

$\lambda(A)=P[S_{k}\in A]\quad\forall A\in{{\cal{F}}}_{S}$

The full sequence $(S_{k})_{k=1}^{\infty}$ is “chosen by nature” at time 0. In
a causal decision scenario, on step $k$ the controller only knows the values
of $S_{1},\ldots,S_{k}$ before choosing $X_{k}\in C(S_{k})$. In a noncausal
scenario the full $(S_{k})_{k=1}^{\infty}$ sequence is known. Assume
${{\cal{G}}}\subseteq{{\cal{F}}}$ is a subsigma algebra independent of
$\sigma((S_{k})_{k=1}^{\infty})$ that is used as a source of randomness to
facilitate stochastic decisions. Assume there is a random variable
$U\sim{{\cal{U}}}[0,1]$ that is ${{\cal{G}}}$-measurable.

The work [12] defines the _network rate region_ $\Gamma$ as the set of all
expectations of $X_{1}$ that can be achieved on the first slot, shows this set
is the same for all slots, and determines the fundamental _capacity region_
(see also [14][23]) when such a transmission system is used for single and
multi-hop queueing networks.222For 1-hop networks the _capacity region_ is the
set of all vectors that are dominated by a vector in the closure of $\Gamma$.
For multi-hop networks the capacity region depends on all possible multi-hop
flow allocations available on graphs associated with points in the closure of
$\Gamma$ [23][13][43]. The argument in [12] implicitly allows expanding the
probability space to ensure the sigma algebra ${{\cal{G}}}$ is complex enough
to emulate an independent virtual system with identical stochastics over any
number of virtual slots before the slot $1$ decision on the actual system is
made. The next results do not require expanding the probability space and
allow ${{\cal{G}}}$ to be as simple as ${{\cal{G}}}=\sigma(U)$.

###### Assumption 3

For the function $C:\Omega_{S}\rightarrow Pow(\mathbb{R}^{m})$, there is a
bounded subset $D\subseteq\mathbb{R}^{m}$ such that $C(s)$ is nonempty and
$C(s)\subseteq D$ for all $s\in\Omega_{S}$.333Assumption 3 is mainly for
convenience and can be replaced by the weaker assumption that expectations of
random vectors $X_{k}\in C(S_{k})$ are finite.

###### Definition 1

Given a distribution $\lambda:{{\cal{F}}}_{S}\rightarrow[0,1]$ and a function
$C:\Omega_{S}\rightarrow Pow(\mathbb{R}^{m})$ that satisfies Assumption 3,
define the _rate region_ $\Gamma\subseteq\mathbb{R}^{m}$ as the set of all
expectation vectors $\mathbb{E}\left[v(S,U)\right]$ that can be achieved by
some measurable function
$v:\Omega_{S}\times\mathbb{R}\rightarrow\mathbb{R}^{m}$ that satisfies
$v(s,w)\in C(s)$ for all $s\in\Omega_{S}$ and $w\in\mathbb{R}$, and on a
probability space with independent random elements $S$ and $U$ such that $S$
has distribution $\lambda$ and $U\sim{{\cal{U}}}[0,1]$.

Define $\overline{\Gamma}$ as the closure of the set $\Gamma$. Using Corollary
3b, it is straightforward to show that Assumptions 1, 2, 3 imply that $\Gamma$
is nonempty, bounded, and convex, while $\overline{\Gamma}$ is nonempty,
compact, and convex. It can be shown the definition of $\Gamma$ is unchanged
if one allows $U$ to be a random variable of _any_ distribution, provided that
$U$ and $S$ are independent. The next lemma shows that $\overline{\Gamma}$
captures all time average expectations of $X_{k}$ that can be achieved at any
time $k$ by a measurable decision policy for choosing $X_{k}\in C(S_{k})$,
regardless of whether or not the policy is causal. Sample path time averages
are also considered in the lemma using a theory of _constructible sets_ [11].
Counter-examples in Section V show that time averages can be far outside the
set $\overline{\Gamma}$ if the controller can make nonmeasurable decisions.

###### Proposition 3

Suppose Assumptions 1, 2, 3 hold for the opportunistic scheduling problem with
identically distributed random elements $(S_{k})_{k=1}^{\infty}$ with some
distribution $\lambda$. Let $(X_{k})_{k=1}^{\infty}$ be a sequence of (Borel
measurable) random vectors that satisfy $X_{k}\in C(S_{k})$ surely for each
$k\in\mathbb{N}$. Then

a) For all $k\in\mathbb{N}$ we have $\mathbb{E}\left[X_{k}\right]\in\Gamma$
and $\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[X_{i}\right]\in\Gamma$.

b) If $(S_{k})_{k=1}^{\infty}$ is i.i.d. and $S_{k}$ is independent of
$(X_{1},\ldots,X_{k-1})$ for all $k\in\\{2,3,4,\ldots\\}$ then for all
$k\in\mathbb{N}$

$\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]\in\overline{\Gamma}\quad\mbox{almost
surely}$

where ${{\cal{H}}}_{k}=\sigma(X_{1},\ldots,X_{k-1})$ for $k\geq 2$ and
${{\cal{H}}}_{1}=\\{\phi,\Omega\\}$.

c) If $(S_{k})_{k=1}^{\infty}$ is i.i.d. and $S_{k}$ is independent of
$(X_{1},\ldots,X_{k-1})$ for all $k\in\\{2,3,4,\ldots\\}$ then

$\lim_{k\rightarrow\infty}\mbox{dist}\left(\frac{1}{k}\sum_{i=1}^{k}X_{i},\overline{\Gamma}\right)=0\quad\mbox{almost
surely}$

where $\mbox{dist}(x,\overline{\Gamma})$ is the Euclidean distance between a
point $x\in\mathbb{R}^{m}$ and the compact and convex set
$\overline{\Gamma}\subseteq\mathbb{R}^{m}$.

###### Proof:

Without loss of generality, for parts (a)-(b) we can assume existence of a
random variable $U\sim{{\cal{U}}}[0,1]$ of the form $U:\Omega\rightarrow[0,1]$
that is independent of $(S_{k},X_{k})_{k=1}^{\infty}$. Indeed, if this does
not hold then we can extend the probability space to a new space
$(\tilde{\Omega},\tilde{{{\cal{F}}}},\tilde{P})$ such that

$\tilde{\Omega}=\Omega\times[0,1],\quad\tilde{{{\cal{F}}}}={{\cal{F}}}\otimes{{\cal{B}}}([0,1]),\quad\tilde{P}=P\otimes\mu$

where $\mu$ is the standard Borel measure on Borel subsets of $[0,1]$. Each
outcome of the new sample space has the form $\tilde{\omega}=(\omega,t)$ where
$\omega\in\Omega$ and $t\in[0,1]$. Then define
$\tilde{S}_{k}:\tilde{\Omega}\rightarrow\Omega_{S}$ and
$\tilde{X}_{k}:\tilde{\Omega}\rightarrow\mathbb{R}^{m}$ by

$\tilde{S}_{k}(\omega,t)=S_{k}(\omega)\quad,\quad\tilde{X}_{k}(\omega,t)=X_{k}(\omega)$

Also define $U:\tilde{\Omega}\rightarrow[0,1]$ by $U(\omega,t)=t$ and observe
that $U\sim{{\cal{U}}}[0,1]$ and $U$ is independent of
$(\tilde{X}_{k},\tilde{S}_{k})_{k=1}^{\infty}$. Then
$(\tilde{X}_{k},\tilde{S}_{k})_{k=1}^{\infty}$ on the extended probability
space has the same distribution as $(X_{k},S_{k})_{k=1}^{\infty}$ on the
original space. Thus, $X_{k}$ and $\tilde{X}_{k}$ have the same expectation
(useful for part (a)); $f(X_{1},\ldots,X_{k-1})$ and
$f(\tilde{X}_{1},\ldots,\tilde{X}_{k-1})$ have the same distribution for any
measurable function $f$ (useful for part (b)).

To prove (a), suppose there is a sequence of random vectors
$(X_{k})_{k=1}^{\infty}$ that satisfy $X_{k}\in C(S_{k})$ surely for each
$k\in\\{1,2,3,\ldots\\}$. Assuming existence of $U\sim{{\cal{U}}}[0,1]$ that
is independent of $(S_{k},X_{k})_{k=1}^{\infty}$, apply Corollary 3b to obtain

$X_{k}=v_{k}(S_{k},W_{k})$ (33)

for some measurable function
$v_{k}:\Omega_{S}\times[0,1]\rightarrow\mathbb{R}^{m}$ that satisfies
$v_{k}(s,v)\in C(s)$ for all $s\in\Omega_{S},t\in[0,1]$ and some random
variable $W_{k}\sim{{\cal{U}}}[0,1]$ that is independent of $S_{k}$. By
definition of $\Gamma$ it holds that $\mathbb{E}\left[X_{k}\right]\in\Gamma$.
This holds for all $k\in\mathbb{N}$. Convexity of $\Gamma$ ensures that
$\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[X_{k}\right]\in\Gamma$ for all
$k\in\mathbb{N}$.

To prove (b), assume $(S_{k})_{k=1}^{\infty}$ are i.i.d. and fix
$k\in\\{2,3,4,\ldots\\}$. Let $Z$ be a version of
$\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]$. Since $\overline{\Gamma}$ is a
closed subset of $\mathbb{R}^{m}$ it is Borel measurable and
$\\{Z\notin\overline{\Gamma}\\}$ is an event. Suppose
$P[Z\notin\overline{\Gamma}]>0$ (we reach a contradiction). Since
$\overline{\Gamma}$ is compact and convex it is _constructible_ , meaning it
is the countable intersection of closed half-spaces (see Proposition 7.5.6 in
[11]):

$\overline{\Gamma}=\cap_{j=1}^{\infty}\\{x\in\mathbb{R}^{m}:a_{j}^{\top}x\leq
b_{j}\\}$ (34)

for some $a_{j}\in\mathbb{R}^{m}$ and $b_{j}\in\mathbb{R}$ for
$j\in\mathbb{N}$. Then

$P\left[Z\notin\overline{\Gamma}\right]=P[\cup_{j=1}^{\infty}\\{a_{j}^{\top}Z>b_{j}\\}]$

Since the above probability is positive, there must be an index
$i\in\mathbb{N}$ for which $P[a_{i}^{\top}Z>b_{i}]>0$. Define the event
$A=\\{a_{i}^{\top}Z>b_{i}\\}$. Then $P[A]>0$. Since $Z$ is a version of
$\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]$ it is
${{\cal{H}}}_{k}$-measurable and $A\in{{\cal{H}}}_{k}$. By the defining
property of a conditional expectation it holds that

$\mathbb{E}\left[Z1_{A}\right]=\mathbb{E}\left[X_{k}1_{A}\right]$

and so

$\frac{\mathbb{E}\left[a_{i}^{\top}Z1_{A}\right]}{P[A]}=\frac{a_{i}^{\top}\mathbb{E}\left[X_{k}1_{A}\right]}{P[A]}$

Since $U\sim{{\cal{U}}}[0,1]$ is independent of the random element
$(S_{k},1_{A})\in\Omega_{S}\times\\{0,1\\}$ we have by Corollary 3b

$X_{k}=v(S_{k},1_{A},W)$

for some random variable $W\sim{{\cal{U}}}[0,1]$ that is independent of
$(S_{k},1_{A})$, and for some measurable function
$v:\Omega_{S}\times\\{0,1\\}\times[0,1]\rightarrow\mathbb{R}^{m}$ such that

$v(s,b,w)\in C(s)\quad\forall s\in\Omega_{S},b\in\\{0,1\\},w\in[0,1]$

Then

$\displaystyle\frac{\mathbb{E}\left[a_{i}^{\top}Z1_{A}\right]}{P[A]}$
$\displaystyle=\frac{a_{i}^{\top}\mathbb{E}\left[v(S_{k},1_{A},W)1_{A}\right]}{P[A]}$
(35) $\displaystyle=a_{i}^{\top}\mathbb{E}\left[v(S_{k},1,W)|A\right]$ (36)
$\displaystyle=a_{i}^{\top}\mathbb{E}\left[v(S_{k},1,W)\right]$ (37)

where we have used the fact that $(S_{k},W)$ is independent of $A$ (recall
that $W$ is independent of $(S_{k},1_{A})$ and $S_{k}$ is independent of the
${{\cal{H}}}_{k}$-measurable random variable $1_{A}$, so that $S_{k},W,1_{A}$
are mutually independent). Defining $y=\mathbb{E}\left[v(S_{k},1,W)\right]$,
it follows by definition of $\Gamma$ that
$y\in\Gamma\subseteq\overline{\Gamma}$ and so $a_{i}^{\top}y\leq b_{i}$
(recall (34)). Thus

$\frac{\mathbb{E}\left[a_{i}^{\top}Z1_{A}\right]}{P[A]}\leq b_{i}$

and so

$\mathbb{E}\left[(a_{i}^{\top}Z-b_{i})1_{A}\right]\leq 0$ (38)

By definition of event $A=\\{a_{i}^{\top}Z>b_{i}\\}$, the random variable
$(a_{i}^{\top}Z-b_{i})1_{A}$ is nonnegative, so (38) implies

$(a_{i}^{\top}Z-b_{i})1_{A}=0\quad\mbox{almost surely}$

However, $(a_{i}^{\top}Z-b_{i})1_{A}>0$ if and only if $1_{A}>0$, which
contradicts the fact that $P[A]>0$.

To prove (c), define $M_{1}=X_{1}-\mathbb{E}\left[X_{1}\right]$ and define
$M_{k}=X_{k}-\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]$ for
$k\in\\{2,3,4,\ldots\\}$. Then $\\{M_{k}\\}_{k=1}^{\infty}$ is a zero mean
sequence of bounded random vectors in $\mathbb{R}^{m}$ where each component
forms a martingale difference, and so the law of large numbers for martingale
differences implies that $\frac{1}{k}\sum_{i=1}^{k}M_{i}$ converges to 0
almost surely [44]. Thus,
$\frac{1}{k}\sum_{i=1}^{k}X_{i}-\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]$
converges to 0 almost surely. However, part (b) implies
$\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]\in\overline{\Gamma}$ almost
surely, and convexity of $\overline{\Gamma}$ implies
$\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[X_{k}|{{\cal{H}}}_{k}\right]\in\overline{\Gamma}$
almost surely. ∎

Conversely, if $(S_{k})_{k=1}^{\infty}$ is identically distributed with
distribution $\lambda$ and $U\sim{{\cal{U}}}[0,1]$ is independent of
$(S_{k})_{k=1}^{\infty}$, then for any $x\in\overline{\Gamma}$ it is
straightforward to see there is a causal and measurable decision policy that
chooses $X_{k}\in C(S_{k})$ to ensure:

$\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[X_{i}\right]=x$

and if $(S_{k})_{k=1}^{\infty}$ are i.i.d. then we can further ensure

$\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=1}^{k}X_{i}=x\quad\mbox{almost
surely}$

This is done by first mapping the random variable $U\sim{{\cal{U}}}[0,1]$ to a
sequence of i.i.d. ${{\cal{U}}}[0,1]$ random variables
$(U_{1},U_{2},U_{3},\ldots)$ by using the bits corresponding to the binary
expansion of $U$. Then fix any sequence of points $x_{k}\in\Gamma$ that
satisfy $x_{k}\rightarrow x$ and define $X_{k}=v_{k}(S_{k},U_{k})$ for
$k\in\mathbb{N}$ where $v_{k}$ is the corresponding measurable function in the
definition of $\Gamma$ that ensures $X_{k}\in C(S_{k})$ and
$\mathbb{E}\left[X_{k}\right]=x_{k}$ for all $k\in\mathbb{N}$.

##  V Counter-examples

This section considers pathological cases for the opportunistic scheduling
problem with i.i.d. channel states $(S_{k})_{k=1}^{\infty}$ and only $m=1$
channel. We use $(\Omega_{S},{{\cal{F}}}_{S})=([0,1],{{\cal{B}}}([0,1]))$
throughout.

###  V-A Nonmeasurable policies

This example gives an opportunistic scheduling system for which a
nonmeasurable policy produces larger time averages in comparison to any
measurable policy. It is similar in spirit to the example given by Blackwell
in [20] which shows that a single decision at one step of a finite stage
dynamic program can bring arbitrarily more utility if it makes a measurable
decision based on both the current state and memory, rather than only on the
current state (even if the utility function depends only on the current state
and the current decision). However, the structure of that example is different
from ours and compares two measurable policies rather than a nonmeasurable
policy in comparison to any measurable decision.

Define

$\Omega=[0,1]^{\mathbb{N}},\quad{{\cal{F}}}=\otimes_{k\in\mathbb{N}}{{\cal{B}}}([0,1]),\quad
P=\otimes_{k\in\mathbb{N}}\mu$

where $\mu$ is the standard Borel measure on $[0,1]$. Each outcome has the
structure $\omega=(\omega_{0},\omega_{1},\omega_{2},\ldots)$. Define
$U:\Omega\rightarrow[0,1]$ and $S_{k}:\Omega\rightarrow[0,1]$ by
$U(\omega)=\omega_{0}$ and $S_{k}(\omega)=\omega_{k}$ for
$k\in\\{1,2,3,\ldots\\}$. Then $(S_{k})_{k=1}^{\infty}$ are i.i.d.
${{\cal{U}}}[0,1]$ variables; $U\sim{{\cal{U}}}[0,1]$ is independent of
$(S_{k})_{k=1}^{\infty}$.

Fix $A\subseteq[0,1]$ as a set with inner measure 0 and outer measure 1 (such
sets exist under the Axiom of Choice [35][36][37]). In particular, neither $A$
nor its complement $A^{c}=[0,1]\setminus A$ contains a Borel subset of
positive measure. Define $C:[0,1]\rightarrow Pow(\mathbb{R})$ by

$C(s)=\left\\{\begin{array}[]{cc}\\{0,1\\}&\mbox{ if $s\in A$}\\\
\\{0,2\\}&\mbox{ if $s\in A^{c}$}\end{array}\right.$

A measurable choice function for this system is $\psi(s)=0$ for all
$s\in[0,1]$ and so Assumption 1 holds. However, it can be shown that
Assumption 2 fails.

Consider any decision policy that is measurable, meaning that it produces
valid random variables $(X_{k})_{k=1}^{\infty}$ that satisfy $X_{k}\in
C(S_{k})$ surely for all $k\in\mathbb{N}$. For each fixed $k\in\mathbb{N}$
define the set

$\displaystyle D_{k}$ $\displaystyle=\\{\omega\in\Omega:\omega_{k}\in A\\}$

It turns out that every ${{\cal{F}}}$-measurable subset of $D_{k}$ has measure
0, and every ${{\cal{F}}}$-measurable subset of $D_{k}^{c}$ also has measure 0
(proof postponed to the next paragraph). Since $X_{k}$ is a valid random
variable we know $\\{X_{k}=1\\}$ and $\\{X_{k}=2\\}$ are valid events (i.e.,
in ${{\cal{F}}}$). Since $X_{k}\in C(S_{k})$ we have $\\{X_{k}=1\\}\subseteq
D_{k}$ and so $P[X_{k}=1]=0$. Likewise, $\\{X_{k}=2\\}\subseteq D_{k}^{c}$ and
so $P[X_{k}=2]=0$. It follows that $X_{k}=0$ almost surely for all
$k\in\mathbb{N}$ and so
$\lim_{k\rightarrow\infty}\frac{1}{k}\sum_{i=1}^{k}X_{i}=0$ almost surely. On
the other hand, the (nonmeasurable) policy that chooses $X_{k}=1$ if $S_{k}\in
A$ and $X_{k}=2$ otherwise surely yields $X_{k}\in C(S_{k})$ and $X_{k}\geq 1$
for all $k\in\mathbb{N}$, so
$\liminf_{k\rightarrow\infty}\frac{1}{k}\sum_{i=1}^{k}X_{i}\geq 1$ surely.

It remains to show that every ${{\cal{F}}}$-measurable subset of $D_{k}$ has
probability 0 (the corresponding proof for $D_{k}^{c}$ is similar). Let $Z$ be
a ${{\cal{F}}}$-measurable subset of $D_{k}$. Let $\pi_{k}(Z)$ be the
projection of $Z$ onto the dimension $k$. Then $\pi_{k}(Z)\subseteq A$. Since
$Z\in{{\cal{F}}}$, $Z$ can be viewed as a Borel measurable subset of the
Polish space $[0,1]^{\mathbb{N}}$, and since the projection onto one dimension
is a continuous function, the set $\pi_{k}(Z)$ is an analytic subset of
$[0,1]$ and hence a Lebesgue measurable subset of $[0,1]$ [10]. It follows
that $\pi_{k}(Z)=B\cup R$ where $B$ is a Borel set and $R$ is a subset of a
Borel set $\tilde{R}$ with $\mu(\tilde{R})=0$. Since
$B\subseteq\pi_{k}(Z)\subseteq A$ we have $\mu(B)=0$ (recall that all Borel
measurable subsets of $A$ have measure 0). Therefore

$\displaystyle P[Z]$ $\displaystyle\leq P\left[\omega\in\Omega:\omega_{k}\in
B\cup\tilde{R}\right]$ $\displaystyle=\mu(B\cup\tilde{R})$
$\displaystyle\leq\mu(B)+\mu(\tilde{R})=0$

###  V-B Randomization without deterministic measurable choice

This example shows a probability space with random elements $X_{k}\in
C(S_{k})$ for all $k\in\mathbb{N}$, so that a form of randomized choice
exists, without the measurable choice assumption (Assumption 1). Famous
examples in the field of descriptive set theory by Blackwell [31], Novikoff
[32], Sierpiński [33], and Addison [34] prove existence of a Borel measurable
set $A\subseteq[0,1]^{2}$ with a projection $\pi_{1}(A)$ onto the first
component that satisfies $\pi_{1}(A)=[0,1]$ and such that there is no
measurable function $\psi:[0,1]\rightarrow[0,1]$ that satisfies
$(x,\psi(x))\in A$ for all $x\in[0,1]$ (see also Example 5.1.7 in [10]).
Define

$C(s)=\\{y:(s,y)\in A\\}\quad\forall s\in[0,1]$

Assumption 2 holds for this system because $\\{(s,x)\in[0,1]^{2}:x\in
C(s)\\}=A$ is a Borel set, while Assumption 1 fails because there is no
measurable choice function $\psi(s)$. Nevertheless a probability space can
have i.i.d. random vectors $(S_{k},X_{k})_{k=1}^{\infty}$ that satisfy
$X_{k}\in C(S_{k})$ surely for all $k\in\mathbb{N}$ as follows: Let
$(U_{k})_{k=0}^{\infty}$ be i.i.d. ${{\cal{U}}}[0,1]$ variables. Since $A$ is
an uncountably infinite Borel measurable subset of $\mathbb{R}^{2}$, there is
an isomorphism $b:[0,1]\rightarrow A$. Define $(S_{k},X_{k})=b(U_{k})$ for all
$k\in\mathbb{N}$. Then $(S_{k},X_{k})_{k=1}^{\infty}$ are indeed i.i.d. random
vectors and $(S_{k},X_{k})\in A$ and so $X_{k}\in C(S_{k})$ surely for all
$k\in\mathbb{N}$. Fix $k\in\mathbb{N}$. Using randomization variable $U_{0}$
with Corollary 2 implies $X_{k}=h_{k}(S_{k},W_{k})$ for some Borel measurable
function $h_{k}$ and some random variable $W_{k}\sim{{\cal{U}}}[0,1]$ that is
independent of $S_{k}$. Since Assumption 2 holds, any probability space that
contains a random element $(S,W)$ with the same distribution as
$(S_{k},W_{k})$ yields

$P[h_{k}(S,W)\in C(S)]=1$

##  VI Conclusion

This paper considers sequences of Borel measurable functions where each
function $X_{k}$ is constrained to be measurable with respect to the sigma
algebra generated by the union of an arbitrary number of sigma algebras
associated with index $k$. Specifically, each $X_{k}$ is $\sigma(\cup_{j\in
J_{k}}{{\cal{H}}}_{j})$-measurable, where $J_{k}$ is an arbitrary index set
and ${{\cal{H}}}_{j}$ is a sigma algebra for each $j\in J_{k}$. It is shown
that each $X_{k}$ can be expressed as the composition of a Borel function
$h_{k}$ with some real-valued measurable functions $Y_{j}$ for $j\in J_{k}$,
each $Y_{j}$ being measurable with respect to the sigma algebra
${{\cal{H}}}_{j}$. The same $Y_{j}$ functions can be used to represent the
influence of ${{\cal{H}}}_{j}$ for all indices $k$ in which $j\in J_{k}$. For
applications to stochastic control, this enables functional representations of
all possible decision vectors that satisfy causality and measurability
constraints. This leads to a refined theorem on network capacity for
opportunistic scheduling in time-varying wireless networks. The theorem uses
two measurability assumptions, including an assumption on existence of a
measurable choice function. By utilizing classical pathological counter-
examples in the field of descriptive set theory, an example opportunistic
scheduling system is developed for which a nonmeasurable policy yields
significantly better time averages in comparison to any measurable policy.

## Acknowledgements

This work was supported in part by one or more of: NSF CCF-1718477, NSF
SpecEES 1824418.

## References

  * [1] J. L. Doob.  Stochastic Processes.  Wiley, 1953.
  * [2] O. Kallenberg.  Foundations of Modern Probability, 2nd ed., Probability and its Applications.  Springer-Verlag, 2002.
  * [3] D. Williams.  Probability with Martingales.  Cambridge Mathematical Textbooks, Cambridge University Press, 1991.
  * [4] D. Blackwell and C. Ryll-Nardzewski.  Non-existence of everywhere proper conditional distributions.  Ann. Math. Statist., 34(1):223–225, 1963.
  * [5] K. Kuratowski and C. Ryll-Nardzewski.  A general theorem on selectors.  Bull. Polish Acad. des Sciences, 13:397–403, 1965.
  * [6] L. E. Dubins and L. J. Savage.  How to Gamble if you Must: Inequalities for Stochastic Processes.  Courier Corp., 2014.
  * [7] A. Maitra.  Discounted dynamic programming on compact metric spaces.  Indian Journal of Statistics, Series A, 30(2):211–216, 1968.
  * [8] R. J. Aumann.  Measurable utility and the measurable choice theorem.  In G. T. Guilbaud, editor, La Decision, chapter 15, pages 15–26. Editions du Centre National de la Recherche Scientifique, Paris, 1969\.
  * [9] J. Von Neumann.  On rings of operators: Reduction theory.  Annals of Mathematics, 50:401–485, 1949.
  * [10] S. M. Srivastava.  A Course on Borel Sets.  Springer New York, NY, 1998.
  * [11] J. M. Borwein and J. D. Vanderwerff.  Convex Functions: Constructions, Characterizations and Counterexamples.  Cambridge University Press, 2010.
  * [12] M. J. Neely.  Stochastic Network Optimization with Application to Communication and Queueing Systems.  Morgan & Claypool, 2010.
  * [13] L. Georgiadis, M. J. Neely, and L. Tassiulas.  Resource allocation and cross-layer control in wireless networks.  Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006\.
  * [14] L. Tassiulas and A. Ephremides.  Dynamic server allocation to parallel queues with randomly varying connectivity.  IEEE Transactions on Information Theory, vol. 39, no. 2, pp. 466-478, March 1993.
  * [15] G. Taraldsen.  Optimal learning from the Doob-Dynkin lemma.  arXiv:1801.00974, 2018.
  * [16] https://math.stackexchange.com/questions/3752941/if-x-is-sigma-mathcalg-cup-mathcalh-measurable-can-we-write-x-fg.
  * [17] B. K. Driver.  Analysis Tools with Examples.  Springer, New York, 2004.
  * [18] B. Cascales, V. Kadets, and J. Rodríguez.  Measurability and selections of multi-functions in banach spaces.  Journal of Convex Analysis, 17:229–240, 02 2010.
  * [19] C. Olech.  Existence theorems for optimal problems with vector-valued cost function.  Trans. of American Mathematical Society, pages 159–180, Feb. 1969\.
  * [20] D. Blackwell.  Memoryless strategies in finite-stage dynamic programming.  Annals of Mathematical Statistics, 1963.
  * [21] D. Blackwell.  Discounted dynamic programming.  Annals of Mathematical Statistics, 1964.
  * [22] M. Schäl.  On dynamic programming: Compactness of the space of policies.  Stochastic Processes and their Applications, 3:345–364, 1975.
  * [23] M. J. Neely, E. Modiano, and C. E Rohrs.  Dynamic power allocation and routing for time varying wireless networks.  IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005.
  * [24] X. Liu, E. K. P. Chong, and N. B. Shroff.  A framework for opportunistic scheduling in wireless networks.  Computer Networks, vol. 41, no. 4, pp. 451-474, March 2003.
  * [25] A. Eryilmaz and R. Srikant.  Joint congestion control, routing, and MAC for stability and fairness in wireless networks.  IEEE Journal on Selected Areas in Communications, Special Issue on Nonlinear Optimization of Communication Systems, vol. 14, pp. 1514-1524, Aug. 2006.
  * [26] A. Stolyar.  Maximizing queueing network utility subject to stability: Greedy primal-dual algorithm.  Queueing Systems, vol. 50, no. 4, pp. 401-457, 2005.
  * [27] M. J. Neely, E. Modiano, and C. Li.  Fairness and optimal stochastic control for heterogeneous networks.  IEEE/ACM Transactions on Networking, vol. 16, no. 2, pp. 396-409, April 2008.
  * [28] M. J. Neely.  Energy optimal control for time varying wireless networks.  IEEE Transactions on Information Theory, vol. 52, no. 7, pp. 2915-2934, July 2006.
  * [29] M. Souslin.  Sur une definition des ensembles B sans nombres tranfinis.  C. R. Acad. Sciences, Paris, 164:88–91, 1917.
  * [30] N. Lusin.  Sur la classification de M. Baire.  C. R. Acad. des Sci, Paris, 164:91–94, 1917.
  * [31] D. Blackwell.  A Borel set not containing a graph.  The Annals of Mathematical Statistics, 39(4):1345–1347, 1968.
  * [32] D. Novikoff.  Sur les functions implicites mesurables.  B. Fund. Math., 17:8–25, 1931.
  * [33] W. Sierpiński.  Sur deux complémentaires analytiques non séparables.  B. Fund. Math., 17:296–297, 1931.
  * [34] J. W. Addison.  Separation principles in the hierarchies of classical and effective descriptive set theory.  Fund. Math, 46:123–135, 1958.
  * [35] W. Sierpiński and N. Lusin.  Sur une décompostion d’un intervalle en une infinité non dénumberable d’ensembles non measurables.  Comptes Rendus de l’Academie des Sciences, pages 422–426, 1917\.
  * [36] A. Abian.  Partition of nondenumerable closed sets of reals.  Czechoslovak Math. J., 26:207–210, 1976.
  * [37] D. Rizzolo.  Strange uniform variables.  ArXiv:1301.7148v1, 2013.
  * [38] L. Breiman.  Probability.  SIAM, Philadelphia, 2nd edition, 1968-92.
  * [39] R. M. Dudley.  Real Analysis and Probability.  Wadsworth Pub. Co., Pacific Grove, CA, 1989.
  * [40] K. Kuratowski.  Sur une généralisation de la notion d’homéomorphie.  Fund. Math, 22:206–220, 1934.
  * [41] A. Dembo.  Probability theory: Stat 310 / math 230.  Stanford University; unpublished notes, 2013.
  * [42] M. Schäl.  A selection theorem for optimization problems.  Arch. Math., 25:219–224, 1974.
  * [43] L. Tassiulas and A. Ephremides.  Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks.  IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.
  * [44] Y. S. Chow.  On a strong law of large numbers for martingales.  Ann. Math Statist, vol. 38, no. 2, 1967.