# Directed Information on Abstract Spaces: Properties and Extremum Problems

Charalambos D. Charalambous and Photios A. Stavrou  ECE Department, University
of Cyprus, Nicosia, Cyprus
e-mail:{ chadcha<EMAIL_ADDRESS>
###### Abstract

This paper describes a framework in which directed information is defined on
abstract spaces. The framework is employed to derive properties of directed
information such as convexity, concavity, lower semicontinuity, by using the
topology of weak convergence of probability measures on Polish spaces. Two
extremum problems of directed information related to capacity of channels with
memory and feedback, and non-anticipative and sequential rate distortion are
analyzed showing existence of maximizing and minimizing distributions,
respectively.

##  I Introduction

Directed information from a sequence of Random Variables (RV’s)
$X^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{X_{0},X_{1},\ldots,X_{n}\\}\in{\cal
X}_{0,n}\stackrel{{\scriptstyle\triangle}}{{=}}\times_{i=0}^{n}{\cal X}_{i}$,
to another sequence
$Y^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{Y_{0},Y_{1},\ldots,Y_{n}\\}\in{\cal
Y}_{0,n}\stackrel{{\scriptstyle\triangle}}{{=}}\times_{i=0}^{n}{\cal Y}_{i}$
is often defined via [1, 2]111Unless otherwise, integrals with respect to
measures are over the spaces on which these are defined.

$\displaystyle
I(X^{n}\rightarrow{Y}^{n})\stackrel{{\scriptstyle\triangle}}{{=}}\sum_{i=0}^{n}I(X^{i};Y_{i}|Y^{i-1})$
(1)
$\displaystyle=\sum_{i=0}^{n}\int\log\bigg{(}\frac{P_{Y_{i}|Y^{i-1},X^{i}}(dy_{i}|y^{i-1},x^{i})}{P_{Y_{i}|Y^{i-1}}(dy_{i}|y^{i-1})}\bigg{)}{P}_{X^{i},Y^{i}}(dx^{i},dy^{i})$
(2)
$\displaystyle\equiv\mathbb{I}_{X^{n}\rightarrow{Y}^{n}}(P_{X_{i}|X^{i-1},Y^{i-1}},P_{Y_{i}|Y^{i-1},X^{i}}:i=0,\ldots,n)$
(3)

Since the joint distribution in (2) is decomposed via
$P_{X^{i},Y^{i}}(dx^{i},dy^{i})=\otimes_{j=0}^{i}{P}_{X_{j}|X^{j-1},Y^{j-1}}(dx_{j}|x^{j-1},y^{j-1})\otimes{P}_{Y_{j}|Y^{j-1},X^{j}}(dy_{j}|y^{j-1},x^{j})$,
the notation $\mathbb{I}_{X^{n}\rightarrow{Y}^{n}}(\cdot,\cdot)$ denotes the
functional dependence on two collections of non-anticipative or causal
conditional distributions
$\\{P_{X_{i}|X^{i-1},Y^{i-1}}(\cdot|\cdot,\cdot),~{}P_{Y_{i}|Y^{i-1},X^{i}}(\cdot|\cdot,\cdot)~{}:~{}i=0,1,\ldots,n\\}$.
In information theory, directed information (1)-(3) or its variants are used
to characterize capacity of channels with memory and feedback [3, 4, 5], lossy
data compression with feedforward information at the decoder [6], lossy data
compression of sequential codes [4], lossy data compression of non-
anticipative codes [7], and capacity of networks such as the two-way channel,
multiple access channel [8, 9], etc. The previous references derive coding
theorems based on $a)$ stationary ergodic processes
$\\{(X_{i},Y_{i})\\}_{i=0}^{\infty}$, $b)$ Dobrushin’s stability of the
information density
$\log\otimes_{i=0}^{n}\frac{P_{Y_{i}|Y^{i-1},X^{i}}(dy_{i}|y^{i-1},x^{i})}{P_{Y_{i}|Y^{i-1}}(dy_{i}|y^{i-1})}$,
and $c)$ via information spectrum methods [10].
Capacity of Channels with Feedback. Based on $a)$ or $b)$ the operational
definition of channels with memory and feedback is given by

$\displaystyle
C^{f}(P)\stackrel{{\scriptstyle\triangle}}{{=}}\lim_{n\rightarrow\infty}\sup_{\overleftarrow{P}_{X^{n}|Y^{n-1}}(\cdot|\cdot)\in\overleftarrow{\cal{P}}(P)}\frac{1}{n+1}I(X^{n}\rightarrow{Y^{n}})$
(4)

where $\overleftarrow{\cal{P}}(P)$ denotes the power constraint set, and

$\displaystyle\overleftarrow{P}_{X^{n}|Y^{n-1}}(dx^{n}|dy^{n-1})\stackrel{{\scriptstyle\triangle}}{{=}}\otimes_{i=0}^{n}{P}_{X_{i}|X^{i-1},Y^{i-1}}(dx_{i}|x^{i-1},y^{i-1})$

Sequential and Non-Anticipative Rate Distortion Function. Based on $a)$ or
$b)$ the operational definition of sequential and non-anticipative rate
distortion function is given by expression

$\displaystyle
R^{c}(D)\stackrel{{\scriptstyle\triangle}}{{=}}\lim_{n\rightarrow\infty}\inf_{\overrightarrow{P}_{Y^{n}|X^{n}}(\cdot|\cdot)\in\overrightarrow{Q}(D)}\frac{1}{n+1}I({X^{n}}\rightarrow{Y^{n}})$
(5)

where $\overrightarrow{Q}(D)$ is the distortion fidelity constraint and

$\displaystyle\overrightarrow{P}_{Y^{n}|X^{n}}(dy^{n}|x^{n})\stackrel{{\scriptstyle\triangle}}{{=}}\otimes_{i=0}^{n}{P}_{Y_{i}|Y^{i-1},X^{i}}(dy_{i}|y^{i-1},x^{i}),$
$\displaystyle{P}_{X_{i}|X^{i-1},Y^{i-1}}(dx_{i}|x^{i-1},y^{i-1})=P_{X_{i}|X^{i-1}}(dx_{i}|x^{i-1})-a.s.$

The complete investigation of existence, characterization, and properties of
the above extremum problems requires extensive analysis of the functional
$\mathbb{I}_{X^{n}\rightarrow{Y^{n}}}(\cdot,\cdot)$ as defined in (3). This is
analogous to capacity of channels without feedback which involves maximization
of mutual information $I({X^{n}};{Y^{n}})$ over the power constraint set, and
to classical rate distortion function which involves minimization of mutual
information $I({X^{n}};{Y^{n}})$ over the fidelity constraint. However, mutual
information
$I(X^{n};Y^{n})\equiv\mathbb{I}_{X^{n};Y^{n}}(P_{X^{n}},P_{Y^{n}|X^{n}})$,
inherits from its information divergence definition
$I(X^{n};Y^{n})\stackrel{{\scriptstyle\triangle}}{{=}}\mathbb{D}(P_{X^{n},Y^{n}}||P_{X^{n}}\times{P}_{Y^{n}})$,
several important functional properties such as convexity, concavity, lower
semicontinuity, etc. These properties are vital both for finite alphabet
spaces, as well as abstract alphabet spaces [11, 12]. The difficulty
associated with directed information $I(X^{n}\rightarrow{Y^{n}})$, rises from
the fact that this information measure (1)-(3) is a functional
$\mathbb{I}_{X^{n}\rightarrow{Y}^{n}}(\cdot,\cdot)$ of the collection of
conditional distributions
$\\{P_{X_{i}|X^{i-1},Y^{i-1}}(\cdot|\cdot,\cdot):i=0,1,\ldots,n\\}$ and
$\\{P_{Y_{i}|Y^{i-1},X^{i}}(\cdot|\cdot,\cdot):i=0,1,\ldots,n\\}$.
The objective of this paper is to address the following questions, when ${\cal
X}_{0,n}$ and ${\cal Y}_{0,n}$ are complete separable metric spaces (Polish
spaces).

  * 1.

Is there an equivalent directed information definition expressed via
information divergence $\mathbb{D}(\cdot||\cdot)$ as a functional of two
appropriate conditional distributions ${\bf P}(\cdot|{\bf y})$ on ${\cal
X}^{\mathbb{N}}\stackrel{{\scriptstyle\triangle}}{{=}}\times_{i=0}^{\infty}{\cal
X}_{i}$ for ${\bf y}=(y_{0},y_{1},\ldots)\in{\cal
Y}^{\mathbb{N}}\stackrel{{\scriptstyle\triangle}}{{=}}\times_{i=0}^{\infty}{\cal
Y}_{i}$ and ${\bf Q}(\cdot|{\bf x})$ on ${\cal Y}^{\mathbb{N}}$ for ${\bf
x}\in{\cal X}^{\mathbb{N}}$ which uniquely define
$\\{P_{X_{i}|X^{i-1},Y^{i-1}}:i=0,1,\ldots\\}$ and
$\\{P_{Y_{i}|Y^{i-1},X^{i}}:i=0,1,\ldots\\}$, respectively, and vice-versa?

  * 2.

Is directed information convex and concave functional with respect to the
conditional distributions ${\bf P}(\cdot|{\bf y})$ and ${\bf Q}(\cdot|{\bf
x})$?

  * 3.

Is directed information a lower semicontinuous functional of the conditional
distributions ${\bf P}(\cdot|{\bf y})$ and ${\bf Q}(\cdot|{\bf x})$?

  * 4.

What are appropriate conditions for existence of the maximizing encoder
admissible distributions and minimizing distortion admissible distributions?

This paper answers the above questions by invoking the topology of weak
convergence of probability measures on Polish spaces and Prohorov’s theorems.
The paper is organized as follows. Section II provides the construction of two
equivalent definitions of causal channels on abstract spaces while in Section
III the main properties of directed information are given. Finally, in Section
IV the extremum problems (4), (5) are discussed. The derivations of theorems
are outlined since they are quite lengthy.

##  II Causal Channels on Abstract Spaces

In this section, the aim is to establish two equivalent definitions of
conditional distributions or basic processes, which define any probabilistic
channel with causal feedback, that relates causally the input-output behavior
of any channel. This formulation is necessary to investigate questions 1.–4.
Let $\mathbb{N}\stackrel{{\scriptstyle\triangle}}{{=}}\\{0,1,2,\ldots\\},$ and
$\mathbb{N}^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{0,1,2,\ldots,n\\}.$
Introduce two sequence of spaces $\\{({\cal X}_{n},{\cal B}({\cal
X}_{n})):n\in\mathbb{N}\\}$ and $\\{({\cal Y}_{n},{\cal B}({\cal
Y}_{n})):n\in\mathbb{N}\\},$ where ${\cal X}_{n},{\cal Y}_{n},n\in\mathbb{N}$
are topological spaces, and ${\cal B}({\cal X}_{n})$ and ${\cal B}({\cal
Y}_{n})$ are Borel $\sigma-$algebras of subsets of ${\cal X}_{n}$ and ${\cal
Y}_{n},$ respectively. Points in ${\cal
X}^{\mathbb{N}}\stackrel{{\scriptstyle\triangle}}{{=}}{{\times}_{n\in\mathbb{N}}}{\cal
X}_{n},$ ${\cal
Y}^{\mathbb{N}}\stackrel{{\scriptstyle\triangle}}{{=}}{\times_{n\in\mathbb{N}}}{\cal
Y}_{n}$ are denoted by ${\bf
x}\stackrel{{\scriptstyle\triangle}}{{=}}\\{x_{0},x_{1},\ldots\\}\in{\cal
X}^{\mathbb{N}},$ ${\bf
y}\stackrel{{\scriptstyle\triangle}}{{=}}\\{y_{0},y_{1},\ldots\\}\in{\cal
Y}^{\mathbb{N}},$ respectively, while their restrictions to finite coordinates
by
$x^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{x_{0},x_{1},\ldots,x_{n}\\}\in{\cal
X}_{0,n},$
$y^{n}\stackrel{{\scriptstyle\triangle}}{{=}}\\{y_{0},y_{1},\ldots,y_{n}\\}\in{\cal
Y}_{0,n},$ for $n\in\mathbb{N}$.
Let ${\cal B}({\cal
X}^{\mathbb{N}})\stackrel{{\scriptstyle\triangle}}{{=}}\odot_{i\in\mathbb{N}}{\cal
B}({\cal X}_{i})$ denote the $\sigma-$algebra on ${\cal X}^{\mathbb{N}}$
generated by cylinder sets $\\{{\bf x}=(x_{0},x_{1},\ldots)\in{\cal
X}^{\mathbb{N}}:x_{0}\in{A}_{0},x_{1}\in{A}_{1},\ldots,x_{n}\in{A}_{n}\\},A_{i}\in{\cal
B}({\cal X}_{i}),0\leq{i}\leq{n},n\geq 1$, and similarly for ${\cal B}({\cal
Y}^{\mathbb{N}})\stackrel{{\scriptstyle\triangle}}{{=}}\odot_{i\in\mathbb{N}}{\cal
B}({\cal Y}_{i})$. Hence, ${\cal B}({\cal X}_{0,n})$ and ${\cal B}({\cal
Y}_{0,n})$ denote the $\sigma-$algebras of cylinder sets in ${\cal
X}^{\mathbb{N}}$ and ${\cal Y}^{\mathbb{N}},$ respectively, with bases over
$A_{i}\in{\cal B}({\cal X}_{i})$, and $B_{i}\in{\cal B}({\cal
Y}_{i}),~{}0\leq{i}\leq{n}$, respectively.
Backward or Feedback Channel. Suppose for each $n\in\mathbb{N},$ the
distributions $\\{p_{n}(dx_{n}|x^{n-1},y^{n-1}):n\in\mathbb{N}\\}$ with
$p_{0}(dx_{0}|x^{-1},y^{-1})\stackrel{{\scriptstyle\triangle}}{{=}}{p}_{0}(x_{0})$
satisfy the following conditions.
i) For $n\in\mathbb{N},$ $p_{n}(\cdot|x^{n-1},y^{n-1})$ is a probability
measure on ${\cal B}({\cal X}_{n});$
ii) For $n\in\mathbb{N},$ $A_{n}\in{\cal B}({\cal X}_{n})$,
$p_{n}(A_{n}|x^{n-1},y^{n-1})$ is $\odot^{n-1}_{i=0}{\cal B}({\cal
X}_{i})\odot{\cal B}({\cal Y}_{i})-$measurable in $x^{n-1}\in{\cal
X}_{0,n-1},$ $y^{n-1}\in{\cal Y}_{0,n-1}.$
Given the collection $\\{p_{n}(dx_{n}|x^{n-1},y^{n-1}):n\in\mathbb{N}\\}$
satisfying conditions i), ii), one can construct a family of distributions on
$({\cal X}^{\mathbb{N}},{\cal B}({\cal
X}^{\mathbb{N}}))\stackrel{{\scriptstyle\triangle}}{{=}}\big{(}\times_{i\in\mathbb{N}}{\cal
X}_{i},\odot_{i\in\mathbb{N}}{\cal B}({\cal X}_{i})\big{)}$ as follows.
Let $C\in{\cal B}({\cal X}_{0,n})$ be a cylinder set of the form
$C\stackrel{{\scriptstyle\triangle}}{{=}}\big{\\{}{\bf x}\in{\cal
X}^{\mathbb{N}}:x_{0}\in{C_{0}},x_{1}\in{C_{1}},\ldots,x_{n}\in{C_{n}}\big{\\}},~{}C_{i}\in{\cal
B}({\cal X}_{i}),~{}0\leq i\leq n$. Define a family of measures ${\bf
P}(\cdot|{\bf y})$ on ${\cal B}({\cal X}^{\mathbb{N}})$ by

$\displaystyle{\bf P}(C|{\bf y})$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}\int_{C_{0}}p_{0}(dx_{0})\ldots\int_{C_{n}}p_{n}(dx_{n}|x^{n-1},y^{n-1})$
(6)
$\displaystyle\equiv{\overleftarrow{P}}_{0,n}(C_{0,n}|y^{n-1}),~{}C_{0,n}=\times_{i=0}^{n}{C_{i}}$
(7)

The notation ${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})$ is used to denote the
restriction of the measure ${\bf P}(\cdot|{\bf y})$ on cylinder sets
$C\in{\cal B}({\cal X}_{0,n})$, for $n\in\mathbb{N}$.
Thus, if conditions i) and ii) hold then for each ${\bf y}\in{\cal
Y}^{\mathbb{N}},$ the right hand side of $(\ref{equation2})$ defines a
consistent family of finite-dimensional distribution on $({\cal
X}^{\mathbb{N}},{\cal B}({\cal X}^{\mathbb{N}}))$, and hence there exists a
unique measure on $({\cal X}^{\mathbb{N}},{\cal B}({\cal X}^{\mathbb{N}})),$
from which $p_{n}(dx_{n}|x^{n-1},y^{n-1})$ is obtained. This leads to the
first, usual definition of a feedback channel, as a family of functions
$p_{n}(dx_{n}|x^{n-1},y^{n-1})$ satisfying conditions ${\bf i)}$ and ${\bf
ii)}.$
An alternative, equivalent definition of a feedback channel is established as
follows. Introduce the assumption
${\bf iii)}$ $\\{{\cal X}_{n}:n\in\mathbb{N}\\}$ are complete separable metric
spaces (Polish Spaces) and $\\{{\cal B}({\cal X}_{n}):n\in\mathbb{N}\\}$ are
the $\sigma-$algebras of Borel sets.
Consider a family of measures ${\bf P}(\cdot|{\bf y})$ on $({\cal
X}^{\mathbb{N}},{\cal B}({\cal X}^{\mathbb{N}}))$ satisfying the following
consistency condition.
C1: If $E\in{\cal B}({\cal X}_{0,n})$, then ${\bf P}(E|{\bf y})$ is ${\cal
B}({\cal Y}_{0,n-1})-$measurable function of ${\bf y}\in{\cal
Y}^{\mathbb{N}}$.
Then, by assumption ${\bf iii)}$, for any family of measures ${\bf
P}(\cdot|{\bf y})$ satisfying C1 one can construct a collection of versions of
conditional distributions $\\{p_{n}(dx_{n}|x^{n-1},y^{n-1}):n\in\mathbb{N}\\}$
satisfying conditions ${\bf i)}$ and ${\bf ii)}$ which are connected with
${\bf P}(\cdot|{\bf y})$ via relation $(\ref{equation2}).$
Therefore, for Polish Spaces $\\{{\cal X}_{n}:n\in\mathbb{N}\\}$ the second
equivalent definition is given by a family of measures ${\bf P}(\cdot|{\bf
y})$ on $({\cal X}^{\mathbb{N}},{\cal B}({\cal X}^{\mathbb{N}}))$ depending
parametrically on ${\bf y}\in{\cal Y}^{\mathbb{N}}$ and satisfying the
consistency condition C1.
The point to be made here is that the second equivalent definition of a
feedback channel, together with similar definition for the forward channel is
convenient to define directed information via relative entropy, similar to the
mutual information definition, and extend well-known functional properties of
mutual information to directed information.
Forward Channel. The previous methodology is repeated for the collection of
functions $\\{q_{n}(dy_{n}|y^{n-1},x^{n}):n\in\mathbb{N}\\}$ which satisfy the
following conditions.
iv) For $n\in\mathbb{N},$ $q_{n}(\cdot|y^{n-1},x^{n})$ is a probability
measure on ${\cal B}({\cal Y}_{n});$
v) For $n\in\mathbb{N}$, $B_{n}\in{\cal B}({\cal Y}_{n})$,
$q_{n}(B_{n}|y^{n-1},x^{n})$ is $\odot^{n-1}_{i=0}{\cal B}({\cal
Y}_{i})\odot_{i=0}^{n}{\cal B}({\cal X}_{i})-$measurable function of
$x^{n}\in{\cal X}_{0,n},$ $y^{n-1}\in{\cal Y}_{0,n-1}$.
Similarly as before, given a cylinder set
$D\stackrel{{\scriptstyle\triangle}}{{=}}\Big{\\{}{\bf y}\in{\cal
Y}^{\mathbb{N}}:y_{0}{\in}D_{0},y_{1}{\in}D_{1},\ldots,y_{n}{\in}D_{n}\Big{\\}},~{}D_{i}\in{\cal
B}({\cal Y}_{i}),~{}0\leq i\leq n$, define a family of measures on ${\cal
B}({\cal Y}^{\mathbb{N}})$ by

$\displaystyle{\bf Q}(D|{\bf x})$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}\int_{D_{0}}q_{0}(dy_{0}|x_{0})\ldots\int_{D_{n}}q_{n}(dy_{n}|y^{n-1},x^{n})$
(8)
$\displaystyle\equiv{\overrightarrow{Q}}_{0,n}(D_{0,n}|x^{n}),~{}D_{0,n}=\times_{i=0}^{n}{D_{i}}$
(9)

Similarly as before, there exists a unique measure on $({\cal
Y}^{\mathbb{N}},{\cal B}({\cal Y}^{\mathbb{N}}))$ for which the family of
distributions $\\{q_{n}(dy_{n}|y^{n-1},x^{n}):n\in\mathbb{N}\\}$ is obtained.
Introduced the assumption
${\bf vi)}$ $\\{{\cal Y}_{n}:n\in\mathbb{N}\\}$ are Polish Spaces and
$\\{{\cal B}({\cal Y}_{n}):n\in\mathbb{N}\\}$ are the $\sigma-$algebras of
Borel sets.
Consider a family of measures ${\bf Q}(D|{\bf x})$ satisfying the following
consistency condition.
C2: If $F\in{\cal B}({\cal Y}_{0,n}),$ then ${\bf Q}(F|{\bf x})$ is ${\cal
B}({\cal X}_{0,n})-$measurable function of ${\bf x}\in{\cal X}^{\mathbb{N}}.$
Then, by assumption ${\bf vi)}$, for any family of measures ${\bf
Q}(\cdot|{\bf x})$ on $({\cal Y}^{\mathbb{N}},{\cal B}({\cal
Y}^{\mathbb{N}}))$ satisfying consistency condition C2 one can construct a
collection of functions $\\{q_{n}(dy_{n}|y^{n-1},x^{n}):n\in\mathbb{N}\\}$
satisfying conditions ${\bf iv)}$ and ${\bf v)}$ which are connected with
${\bf Q}(\cdot|{\bf x})$ via relation $(\ref{equation4})$. Note that
Kolmogorov’s extension theorem guarantees the construction of countable
additive probability measures for both ${\bf P}(\cdot|{\bf y})$ and ${\bf
Q}(\cdot|{\bf x})$.
Given the basic measures ${\bf P}(\cdot|{\bf y})$ on ${\cal X}^{\mathbb{N}}$
and ${\bf Q}(\cdot|{\bf x})$ on ${\cal Y}^{\mathbb{N}}$ satisfying consistency
condition ${\bf C1}$ and ${\bf C2}$, respectively, construct the collections
of conditional distributions as follows.
Let $A^{(n)}=\\{{\bf x}:x_{n}{\in}A\\},$ $A\in{\cal B}({\cal X}_{n})$ and
$B^{(n)}=\\{{\bf y}:y_{n}{\in}B\\},$ $B\in{\cal B}({\cal Y}_{n}).$ In
addition, let ${\bf P}(A^{(n)}|{\bf y}|{{\cal B}({\cal X}_{0,n-1})})$ denote
the conditional probability of $A^{(n)}$ with respect to ${\cal B}({\cal
X}_{0,n-1})$ calculated on the probability space $\big{(}{\cal
X}^{\mathbb{N}},{\cal B}({\cal X}^{\mathbb{N}}),{\bf P}(\cdot|{\bf
y})\big{)},$ and similarly for ${\bf Q}(B^{(n)}|{\bf x}|{{\cal B}({\cal
Y}_{0,n-1})})$. Then

$\displaystyle\mathbb{P}\big{\\{}X_{n}{\in}A|X^{n-1}=x^{n-1},Y^{n-1}=y^{n-1}\big{\\}}$
$\displaystyle={\bf P}\big{(}\\{{\bf x}:x_{n}{\in}A\\}|{\bf y}|{{\cal B}({\cal
X}_{0,n-1})}\big{)}=p_{n}(A_{n};x^{n-1},y^{n-1})-a.s.$
$\displaystyle\mathbb{P}\big{\\{}Y_{n}{\in}B|Y^{n-1}=y^{n-1},X^{n}=x^{n}\big{\\}}$
$\displaystyle={\bf Q}\big{(}\\{{\bf y}:y_{n}{\in}B\\}|{\bf x}|{{\cal B}({\cal
Y}_{0,n-1})}\big{)}=q_{n}(B_{n};y^{n-1},x^{n})-a.s.$

Note that $p_{n}(\cdot;\cdot,\cdot)\in{\cal Q}({\cal X}_{n};{\cal
X}_{0,n-1}\times{\cal Y}_{0,n-1})$ and $q_{n}(\cdot;\cdot,\cdot)\in{\cal
Q}({\cal Y}_{n};{\cal Y}_{0,n-1}\times{\cal X}_{0,n})$ are stochastic kernels
[13], determined from ${\bf P}(\cdot|\cdot)$ and ${\bf Q}(\cdot|\cdot),$
respectively, (e.g., related via $(\ref{equation2})$, $(\ref{equation4})$).
The distribution of RV’s $\\{(X_{i},Y_{i}):i\in\mathbb{N}\\}$ is defined by

$\displaystyle{P}$
$\displaystyle\big{\\{}X_{0}{\in}A_{0},Y_{0}\in{B}_{0},\ldots,X_{n}{\in}A_{n},Y_{n}{\in}B_{n}\big{\\}}$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}\int_{A_{0}}p_{0}(dx_{0})\int_{B_{0}}q_{0}(dy_{0};x_{0})\ldots\int_{B_{n}}q_{n}(dy_{n};y^{n-1},x^{n})$

Hence, for any ${\bf P}(\cdot|\cdot)$ and ${\bf Q}(\cdot|\cdot)$ satisfying
consistency conditions there exist a probability space and a sequence of RV’s
$\\{(X_{i},Y_{i}):i\in\mathbb{N}\\}$ defined on it, whose joint probability
distribution is defined uniquely via ${\bf P}(\cdot|\cdot)$ and ${\bf
Q}(\cdot|\cdot)$.

##  III Directed Information Properties and Compactness

In this section, directed information $I(X^{n}\rightarrow{Y^{n}})$ will be
defined via relative entropy, using the basic measures ${\bf P}(\cdot|{\bf
y})$ and ${\bf Q}(\cdot|{\bf x})$, and identify its properties. Define

$\displaystyle{\cal Q}^{\bf C1}({\cal X}^{\mathbb{N}};{\cal
Y}^{\mathbb{N}})\stackrel{{\scriptstyle\triangle}}{{=}}\Big{\\{}{\bf
P}(\cdot|{\bf y})\in{\cal M}_{1}({\cal X}^{\mathbb{N}}):{\bf P}(\cdot|{\bf
y})~{}\mbox{are regular}$ $\displaystyle\mbox{ probability measures and
satisfy consistency condition {\bf C1}}\Big{\\}}.$ $\displaystyle{\cal Q}^{\bf
C2}({\cal Y}^{\mathbb{N}};{\cal
X}^{\mathbb{N}})\stackrel{{\scriptstyle\triangle}}{{=}}\Big{\\{}{\bf
Q}(\cdot|{\bf x})\in{\cal M}_{1}({\cal Y}^{\mathbb{N}}):{\bf Q}(\cdot|{\bf
x})~{}\mbox{ are regular}$ $\displaystyle\mbox{probability measures and
satisfy consistency condition {\bf C2}}\Big{\\}}.$

Given conditional distributions ${\bf P}(\cdot|\cdot)\in{\cal Q}^{\bf
C1}({\cal X}^{\mathbb{N}};{\cal Y}^{\mathbb{N}})$ and ${\bf
Q}(\cdot|\cdot)\in{\cal Q}^{\bf C2}({\cal Y}^{\mathbb{N}};{\cal
X}^{\mathbb{N}})$ define the following measures.
P1: The joint distribution on ${\cal X}^{\mathbb{N}}\times{\cal
Y}^{\mathbb{N}}$ defined uniquely by

$\displaystyle({\overleftarrow{P}}_{0,n}$
$\displaystyle\otimes{\overrightarrow{Q}}_{0,n})(\times^{n}_{i=0}A_{i}{\times}B_{i}),A_{i}\in{\cal
B}({\cal X}_{i}),~{}B_{i}\in{\cal B}({\cal Y}_{i}),$
$\displaystyle{\stackrel{{\scriptstyle\triangle}}{{=}}}\mathbb{P}\big{\\{}X_{0}{\in}A_{0},Y_{0}\in{B}_{0},\ldots,X_{n}{\in}A_{n},Y_{n}{\in}B_{n}\big{\\}}$
(10)

P2: The marginal distributions on ${\cal X}^{\mathbb{N}}$ defined uniquely by

$\displaystyle\mu_{0,n}(\times^{n}_{i=0}A_{i}),~{}A_{i}\in{\cal B}({\cal
X}_{i}),~{}1\leq i\leq n$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}\mathbb{P}\\{X_{0}\in{A}_{0},Y_{0}\in{\cal
Y}_{0},\ldots,X_{n}\in{A}_{n},Y_{n}\in{\cal Y}_{n}\\},$
$\displaystyle=({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n})(\times^{n}_{i=0}(A_{i}\times{\cal
Y}_{i}))$

P3: The marginal distributions on ${\cal Y}^{\mathbb{N}}$ defined uniquely for
$B_{i}\in{\cal B}({\cal Y}_{i}),~{}1\leq i\leq n$ by

$\displaystyle\nu_{0,n}(\times^{n}_{i=0}B_{i})=({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n})(\times^{n}_{i=0}({\cal
X}_{i}\times{B}_{i}))$

P4: The measure ${\overrightarrow{\Pi}}_{0,n}:{\cal B}({\cal
X}_{0,n})\odot{\cal B}({\cal Y}_{0,n})\mapsto[0,1]$ defined uniquely for
$A_{i}\in{\cal B}({\cal X}_{i})$, $B_{i}\in{\cal B}({\cal Y}_{i})$, $1\leq
i\leq n$ by

$\displaystyle{\overrightarrow{\Pi}}_{0,n}(\times^{n}_{i=0}(A_{i}{\times}B_{i}))$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}({\overleftarrow{P}}_{0,n}\otimes\nu_{0,n})(\times^{n}_{i=0}(A_{i}{\times}B_{i}))$

P5: The measure ${\overleftarrow{\Pi}}_{0,n}:{\cal B}({\cal
Y}_{0,n})\odot{\cal B}({\cal X}_{0,n})\mapsto[0,1]$ defined uniquely for
$A_{i}\in{\cal B}({\cal X}_{i})$, $B_{i}\in{\cal B}({\cal Y}_{i})$, $1\leq
i\leq n$ by

$\displaystyle{\overleftarrow{\Pi}}_{0,n}(\times^{n}_{i=0}(A_{i}{\times}B_{i}))$
$\displaystyle\stackrel{{\scriptstyle\triangle}}{{=}}(\mu_{0,n}\otimes{\overrightarrow{Q}}_{0,n})(\times^{n}_{i=0}(A_{i}{\times}B_{i}))$

###  III-A Directed Information

Let ${\bf P}(\cdot|\cdot)\in{\cal Q}^{\bf C1}({\cal X}^{\mathbb{N}};{\cal
Y}^{\mathbb{N}})$ and ${\bf Q}(\cdot|\cdot)\in{\cal Q}^{\bf C2}({\cal
X}^{\mathbb{N}};{\cal Y}^{\mathbb{N}}).$ By invoking the definition of
directed information (1) or (2), it can be shown that

$\displaystyle
I(X^{n}\rightarrow{Y}^{n})=\mathbb{D}({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}||{\overrightarrow{\Pi}}_{0,n})$
(11)
$\displaystyle=\int\log\Big{(}\frac{{\overrightarrow{Q}}_{0,n}(dy^{n}|x^{n})}{\nu_{0,n}(dy^{n})}\Big{)}({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n})(dx^{n},dy^{n})$
$\displaystyle\equiv{\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
(12)

The right hand side of (11) follows from repeated application of chain rule of
relative entropy [13], while (12) follows from the fact that
${\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}<<{\overleftarrow{P}}_{0,n}\otimes\nu_{0,n}$
if and only if ${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})<<\nu_{0,n}(\cdot)$ for
$\mu_{0,n}-$almost all $x^{n}\in{\cal X}_{0,n}$. Further, if
${\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}<<{\overleftarrow{P}}_{0,n}\otimes\nu_{0,n}$
then the Radon-Nikodym derivative
$\frac{({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n})}{({\overleftarrow{P}}_{0,n}\otimes\nu_{0,n})}(x^{n},y^{n})$
represents a version of
$\frac{{\overrightarrow{Q}}_{0,n}(\cdot|x^{n})}{\nu_{0,n}(\cdot)}(y^{n})$,
$\mu_{0,n}-a.s$ for all $x^{n}\in{\cal X}_{0,n}$.
The notation ${\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}(\cdot,\cdot)$ indicates
the functional dependence of $I(X^{n}\rightarrow{Y^{n}})$ on
$\\{{\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n}\\}$.

###  III-B Convexity and Concavity of Directed Information

Let ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$, ${\cal Q}^{\bf
C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ be the restrictions of ${\cal Q}^{\bf
C1}({\cal X}^{\mathbb{N}};{\cal Y}^{\mathbb{N}})$ and ${\cal Q}^{\bf C2}({\cal
Y}^{\mathbb{N}};{\cal X}^{\mathbb{N}})$, respectively, to cylinder sets with
bases over $A_{i}\in{\cal B}({\cal X}_{i})$, and $B_{i}\in{\cal B}({\cal
Y}_{i})$, $i=0,1,\ldots,n$. These are regular conditional distributions.

######  Theorem 1.

Let $\\{({\cal X}_{n},{\cal B}({\cal X}_{n})):n\in{\mathbb{N}}\\},$ $\\{({\cal
Y}_{n},{\cal B}({\cal Y}_{n})):n\in{\mathbb{N}}\\}$ be Polish spaces. Then

  * 1)

${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$, ${\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n})$ are convex sets.

  * 2)

${\mathbb{I}}_{X^{n}\rightarrow{Y}^{n}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
is a convex functional of ${\overrightarrow{Q}}_{0,n}\in{\cal Q}^{\bf
C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ for a fixed
${\overleftarrow{P}}_{0,n}\in{\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal
Y}_{0,n-1})$.

  * 3)

${\mathbb{I}}_{X^{n}\rightarrow{Y}^{n}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
is a concave functional of ${\overleftarrow{P}}_{0,n}\in{\cal Q}^{\bf
C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$ for a fixed
${\overrightarrow{Q}}_{0,n}\in{\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal
X}_{0,n}).$

###### Proof:

1) Utilize the convexity of regular conditional distributions, and then the
consistency condition ${\bf C1}$, ${\bf C2}$. 2), 3), follow from log-sum
formulae. ∎

###  III-C Lower semicontinuity-Continuity of Directed Information

This part discusses the lower-semicontinuity and continuity of directed
information as a functional of
${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal Q}^{\bf C1}({\cal
X}_{0,n};{\cal Y}_{0,n-1})$ and $\overrightarrow{Q}_{0,n}(\cdot|x^{n})\in{\cal
Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n})$. Before establishing the main
results, sufficient conditions for weak compactness of the set of measures
${{\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})}$, ${{\cal Q}}^{\bf
C2}({\cal Y}_{0,n};{\cal X}_{0,n}),$ and joint and marginal measures are
given.

######  Theorem 2.

Part A. Let ${\cal Y}_{0,n}$ be a compact Polish space and ${\cal X}_{0,n}$ a
Polish space. Assume ${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal Q}^{\bf
C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$ satisfy the following condition.
CA: For all $g(\cdot){\in}BC({\cal X}_{0,n})$, where $BC({\cal X}_{0,n})$
denotes the set of bounded continuous real-valued functions on ${\cal
X}_{0,n}$,

$\displaystyle(x^{n-1},y^{n-1})\longmapsto\int_{{\cal
X}_{n}}g(x)p_{n}(dx;x^{n-1},y^{n-1})\in\mathbb{R}$ (13)

is jointly continuous in $(x^{n-1},y^{n-1})\in{\cal X}_{0,n-1}\times{\cal
Y}_{0,n-1}$.
Then the following weak convergence results hold.

  * A1)

Let ${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal Q}^{\bf C1}({\cal
X}_{0,n};{\cal Y}_{0,n-1})$ and
$\big{\\{}{\overrightarrow{Q}}_{0,n}^{\alpha}(\cdot|{x^{n}})\big{\\}}_{\alpha\geq
1}\in{\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n}).$ Then the joint measure
$({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}^{\alpha})(dx^{n},dy^{n})\buildrel
w\over{\Longrightarrow}({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}^{0})(dx^{n},dy^{n}),$
where ${\overrightarrow{Q}}_{0,n}^{0}(\cdot|x^{n})\in{\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n}).$

  * A2)

Let ${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal Q}^{\bf C1}({\cal
X}_{0,n};{\cal Y}_{0,n-1})$ and
$\big{\\{}{\overrightarrow{Q}}_{0,n}^{\alpha}(\cdot|{x^{n}})\big{\\}}_{\alpha\geq
1}\in{\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ and define the family
of joint measures
$\big{\\{}({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}^{\alpha})(dx^{n},dy^{n})\big{\\}}_{\alpha\geq
1}$ having marginals $\\{\nu_{0,n}^{\alpha}\\}_{\alpha\geq 1}$ on ${\cal
Y}_{0,n}$ and $\\{\mu_{0,n}^{\alpha}\\}_{\alpha\geq 1}$ on ${\cal X}_{0,n}$.
Then $\nu_{0,n}^{\alpha}(dy^{n})\buildrel
w\over{\Longrightarrow}\nu_{0,n}^{0}(dy^{n})$ and
$\mu_{0,n}^{\alpha}(dx^{n})\buildrel
w\over{\Longrightarrow}\mu_{0,n}^{0}(dx^{n})$ where $\nu_{0,n}^{0}\in{\cal
M}_{1}({\cal Y}_{0,n})$ and $\mu_{0,n}^{0}\in{\cal M}_{1}({\cal X}_{0,n})$ are
the marginals of
$({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}^{0})(dx^{n},dy^{n}).$

  * A3)

The sets of measures ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$, and
${\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ are weakly compact.

  * A4)

Let ${\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal Q}^{\bf C1}({\cal
X}_{0,n};{\cal Y}_{0,n-1}),$
$\big{\\{}{\overrightarrow{Q}}_{0,n}^{\alpha}(\cdot|{x^{n}})\big{\\}}_{\alpha\geq
1}\in{\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n}),$ and
$\\{\nu_{0,n}^{\alpha}\\}_{\alpha\geq 1}$ the marginals of
$\big{\\{}({\overleftarrow{P}}_{0,n}\otimes{\overrightarrow{Q}}_{0,n}^{\alpha})(dx^{n},dy^{n})\big{\\}}_{\alpha\geq
1}.$ Then
${\overrightarrow{\Pi}}_{0,n}^{\alpha}(dx^{n},dy^{n})\equiv{\overleftarrow{P}}_{0,n}(dx^{n}|dy^{n-1})\otimes\nu_{0,n}^{\alpha}(dy^{n})\buildrel
w\over{\Longrightarrow}{\overleftarrow{P}}_{0,n}(dx^{n}|dy^{n-1})\otimes\nu_{0,n}^{0}(dy^{n})\equiv{\overrightarrow{\Pi}}_{0,n}^{0}(dx^{n},dy^{n}),$
where $\nu_{0,n}^{0}\in{\cal M}_{1}({\cal Y}_{0,n})$ is the weak limit of
$\nu_{0,n}^{\alpha}\in{\cal M}_{1}({\cal Y}_{0,n})$.

Part B. Let ${\cal X}_{0,n}$ be a compact Polish space and ${\cal Y}_{0,n}$ a
Polish space. Assume ${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in{\cal Q}^{\bf
C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ satisfy the following condition.
CB: For all $h(\cdot){\in}BC({\cal Y}_{0,n})$, the function

$\displaystyle(x^{n},y^{n-1})\longmapsto\int_{{\cal
Y}_{n}}h(y)q_{n}(dy;y^{n-1},x^{n})\in\mathbb{R}$ (14)

is jointly continuous in $(x^{n},y^{n-1})\in{\cal X}_{0,n}\times{\cal
Y}_{0,n-1}$.
The statements of Part A hold by interchanging ${\overleftarrow{Q}}_{0,n}$
with ${\overleftarrow{P}}_{0,n}$, $\nu_{0,n}$ with $\mu_{0,n}$,
${\overrightarrow{\Pi}}_{0,n}$ with ${\overleftarrow{\Pi}}_{0,n}$.

###### Proof:

The proof is quite lengthy and it is based on Prohorov’s theorem relating
tightness and weak compactness of a family of probability measures [13].∎ The
results of Theorem 2 are sufficient to establish lower semicontinuity of
directed information
$I(X^{n}\rightarrow{Y}^{n})\equiv{\mathbb{I}}_{X^{n}\rightarrow{Y}^{n}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$.

######  Theorem 3.

1) Suppose the conditions in Theorem 2, Part A hold. Then
${\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
is lower semicontinuous on ${\overrightarrow{Q}}_{0,n}\in{\cal Q}^{\bf
C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ for fixed
${\overleftarrow{P}}_{0,n}\in{\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal
Y}_{0,n-1})$.
2) Suppose the conditions in Theorem 2, Part B hold. Then
${\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
is lower semicontinuous on ${\overleftarrow{P}}_{0,n}\in{\cal Q}^{\bf
C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$ for fixed
${\overrightarrow{Q}}_{0,n}\in{\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal
X}_{0,n})$.

###### Proof:

Utilizes (11), Theorem 2, and lower semicontinuity of relative entropy.∎ For
capacity problems, it is desirable to identify conditions so that
${\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
as a function of $\overleftarrow{P}_{0,n}$ for fixed
$\overrightarrow{Q}_{0,n}$ is either upper semicontinuous or continuous.

######  Theorem 4.

Consider a forward channel ${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in{\cal
Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n}),$ and a closed family of feedback
channels ${\cal Q}^{c,\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})\subseteq{\cal
Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1}).$ Suppose there exists a family
of measures $\bar{\nu}_{0,n}(dy^{n})$ on $({\cal Y}_{0,n},{\cal B}({\cal
Y}_{0,n}))$ such that
${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\ll{\bar{\nu}}_{0,n}(dy^{n})$ with
Radon-Nikodym derivatives
$\xi_{\bar{\nu}_{0,n}}(x^{n},y^{n})\stackrel{{\scriptstyle\triangle}}{{=}}\frac{{\overrightarrow{Q}}_{0,n}(\cdot|x^{n})}{\bar{\nu}_{0,n}(\cdot)}(y^{n}),$
and
1) the family of Radon-Nikodym derivatives
$\xi_{\bar{\nu}_{0,n}}(x^{n},y^{n})$ is continuous on ${\cal
X}_{0,n}\times{\cal Y}_{0,n},$ and
$\xi_{\bar{\nu}_{0,n}}(x^{n},y^{n})\log\xi_{\bar{\nu}_{0,n}}(x^{n},y^{n})$ is
uniformly integrable over
$\\{\bar{\nu}_{0,n}\otimes{\overleftarrow{P}}_{0,n}:{\overleftarrow{P}}_{0,n}\in{\cal
Q}^{c,\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})\\}$;
2) for a fixed $y^{n}\in{\cal Y}_{0,n},$ the Radon-Nikodym derivative
$\xi_{\bar{\nu}_{0,n}}(x^{n},y^{n})$ is uniformly integrable over ${\cal
Q}^{c,\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1}).$
Then, the directed information
${\mathbb{I}}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
as a functional of
$\\{{\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n}\\}\in{\cal Q}^{c,\bf
C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})\times{\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n})$ is bounded and weakly continuous over ${\cal
Q}^{c,\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$.

###### Proof:

Invoke (11) and generalize related results in [14]. ∎

##  IV Extremum Problems of Directed Information

###  IV-A Existence of Capacity Achieving Distribution

Consider a communication channel with memory and feedback
${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in{\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n})$ and power constraint

$\displaystyle\overleftarrow{\cal{P}}_{0,n}(P)\stackrel{{\scriptstyle\triangle}}{{=}}\big{\\{}{\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in{\cal
Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1}):$
$\displaystyle\int{g}_{0,n}(x^{n},y^{n-1})({\overleftarrow{Q}}_{0,n}\otimes{\overrightarrow{P}}_{0,n})(dx^{n},dy^{n})\leq{P}\big{\\}}$

where for any $n\in\mathbb{N}$, $g_{0,n}:{\cal X}_{0,n}\times{\cal
Y}_{0,n-1}\longmapsto[0,\infty]$ is Borel measurable, and
$\overleftarrow{\cal{P}}_{0,n}(P)$ non-empty. In the absence of any power
constraints the set of input conditional distributions is ${\cal Q}^{\bf
C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$.
The finite horizon maximization of directed information over
$\overleftarrow{\cal{P}}_{0,n}(P)$ or ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal
Y}_{0,n-1})$ (e.g., with or without power constraints) is defined by

$\displaystyle
C^{f}_{0,n}\stackrel{{\scriptstyle\triangle}}{{=}}\sup_{\begin{subarray}{c}{\overleftarrow{P}}_{0,n}(\cdot|y^{n-1})\in\overleftarrow{\cal{P}}_{0,n}(P)\\\
~{}{or}~{}{\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal
Y}_{0,n-1})\end{subarray}}\mathbb{I}_{X^{n}\rightarrow{Y^{n}}}({\overleftarrow{P}}_{0,n},{\overrightarrow{Q}}_{0,n})$
(15)

The next theorem establishes existence of the maximizer.

######  Theorem 5.

Suppose the assumptions of Theorem 2, Part A are satisfied.

  * 1)

The set ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$ is compact.

  * 2)

Suppose $g_{0,n}:{\cal X}_{0,n}\times{\cal Y}_{0,n-1}\longmapsto[0,\infty]$ is
measurable and continuous in $(x^{n},y^{n-1})\in{\cal X}_{0,n}\times{\cal
Y}_{0,n-1}$. Then the set $\overleftarrow{\cal{P}}_{0,n}(P)$ is a closed
subset of ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$.

  * 3)

If in addition the assumptions of Theorem 4 are satisfied (here the assumption
on ${\cal Q}^{\bf C1}({\cal X}_{0,n};{\cal Y}_{0,n-1})$ is satisfied by 1) and
2) ) then $C_{0,n}^{f}$ has a maximum in ${\cal Q}^{\bf C1}({\cal
X}_{0,n};{\cal Y}_{0,n-1})$ (without constraints) or in
$\overleftarrow{\cal{P}}_{0,n}(P)$ (with power constraints).

###### Proof:

1) Utilize the fact that probability measures on compact Polish spaces are
compact. 2) Utilize the fact that closed subset of weakly compact set is
compact. 3) Follows from Weierstrass theorem.∎

###  IV-B Existence of Non-Anticipative Rate Distortion Achieving Distribution

Consider a reconstruction channel
${\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in{\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n})$, a fixed source $\mu_{0,n}(dx^{n})\in{\cal
M}_{1}({\cal X}_{0,n})$, and define the fidelity constraint by

$\displaystyle\overrightarrow{Q}_{0,n}(D)\stackrel{{\scriptstyle\triangle}}{{=}}\big{\\{}{\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in{\cal
Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n}):$
$\displaystyle\int{d}_{0,n}(x^{n},y^{n})({\mu}_{0,n}\otimes{\overrightarrow{Q}}_{0,n})(dx^{n},dy^{n})\leq{D}\big{\\}}$
(16)

where $D\geq{0}$, and for each $n\in\mathbb{N}$, $d_{0,n}:{\cal
X}_{0,n}\times{\cal Y}_{0,n}\longmapsto[0,\infty]$ is Borel measurable, and
$\overrightarrow{Q}_{0,n}(D)$ is non-empty.
The finite horizon minimization of directed information over
$\overrightarrow{Q}_{0,n}(D)$ is defined by

$\displaystyle
R^{c}_{0,n}(D)\stackrel{{\scriptstyle\triangle}}{{=}}\inf_{{\overrightarrow{Q}}_{0,n}(\cdot|x^{n})\in\overrightarrow{Q}_{0,n}(D)}\mathbb{I}_{X^{n}\rightarrow{Y^{n}}}({\mu}_{0,n},{\overrightarrow{Q}}_{0,n})$
(17)

The next theorem establishes existence of the minimizer.

######  Theorem 6.

Let ${\cal X}_{0,n}$ be a Polish space and ${\cal Y}_{0,n}$ a compact Polish
space. Assume $\forall~{}h(\cdot){\in}BC({\cal Y}_{0,n})$, the function

$\displaystyle(x^{n},y^{n-1})\in{\cal X}_{0,n}\times{\cal
Y}_{0,n-1}\longmapsto\int_{{\cal
Y}_{n}}h(y)q_{n}(dy;y^{n-1},x^{n})\in\mathbb{R}$

is continuous jointly in $(x^{n},y^{n-1})\in{\cal X}_{0,n}\times{\cal
Y}_{0,n-1}$.
Then

  * 1)

The set ${\cal Q}^{\bf C2}({\cal Y}_{0,n};{\cal X}_{0,n})$ is compact.

  * 2)

Assume $d_{0,n}:{\cal X}_{0,n}\times{\cal Y}_{0,n}\longmapsto[0,\infty]$ is
measurable and continuous on $y^{n}\in{\cal Y}_{0,n}$. Then
$\overrightarrow{Q}_{0,n}(D)$ is a closed subset of ${\cal Q}^{\bf C2}({\cal
Y}_{0,n};{\cal X}_{0,n})$.

  * 3)

$R_{0,n}^{c}(D)$ has a minimum in $\overrightarrow{Q}_{0,n}(D)$.

###### Proof:

Utilize Theorem 2, Part A, and generalize the derivation in [12] to
$(n+1)-$fold convolution measures. ∎

##  V Conclusion

In this paper we have provided a general framework through which the
properties of mutual information are extended to directed information on
Polish spaces. The existence of extremums to capacity problems with memory and
feedback, and to lossy non-anticipative data compression problems are
discussed.

## References

  * [1] H. Marko, “The bidirectional communication theory–A generalization of information theory,” _IEEE Transactions on Communications_ , vol. 21, no. 12, pp. 1345–1351, Dec. 1973.
  * [2] J. L. Massey, “Causality, feedback and directed information,” in _International Symposium on Information Theory and its Applications (ISITA ’90)_ , Nov. 27-30 1990, pp. 303–305.
  * [3] S. Tatikonda and S. Mitter, “The capacity of channels with feedback,” _IEEE Transactions on Information Theory_ , vol. 55, no. 1, pp. 323–349, Jan. 2009.
  * [4] S. C. Tatikonda, “Control over communication constraints,” Ph.D. dissertation, Mass. Inst. of Tech. (M.I.T.), Cambridge, MA, 2000.
  * [5] J. Chen and T. Berger, “The capacity of finite-state Markov channels with feedback,” _IEEE Transactions on Information Theory_ , vol. 51, no. 3, pp. 780–798, March 2005.
  * [6] R. Venkataramanan, “Information-theoretic results on communication problems with feed-forward and feedback,” Ph.D. dissertation, University of Michigan-Ann Arbor, December 2008.
  * [7] P. A. Stavrou, C. D. Charalambous, and C. K. Kourtellaris, “Causal rate distortion function on abstract alphabets: Optimal reconstruction and properties,” _CoRR_ , vol. abs/1202.0895, 2012. [Online]. Available: http://arxiv.org/abs/1202.0895v1
  * [8] G. Kramer, “Directed information for channels with feedback,” Ph.D. dissertation, Swiss Federal Institute of Technology (ETH), December 1998.
  * [9] ——, “Capacity results for the discrete memoryless network,” _IEEE Transactions on Information Theory_ , vol. 49, no. 1, pp. 4–21, Jan. 2003.
  * [10] T. S. Han and S. Verdu, “Approximation theory of output statistics,” _IEEE Transactions on Information Theory_ , vol. 39, no. 3, pp. 752–772, May 1993.
  * [11] I. Csiszár, “Arbitrarily varying channels with general alphabets and states,” _IEEE Transactions on Information Theory_ , vol. 38, no. 6, pp. 1725–1742, Nov. 1992.
  * [12] ——, “On an extremum problem of information theory,” _Studia Scientiarum Mathematicarum Hungarica_ , vol. 9, pp. 57–71, 1974.
  * [13] P. Dupuis and R. S. Ellis, _A Weak Convergence Approach to the Theory of Large Deviations_. John Wiley & Sons, Inc., New York, 1997.
  * [14] M. Fozunbal, S. McLaughlin, and R. Schafer, “Capacity analysis for continuous-alphabet channels with side information, part I: A general framework,” _IEEE Transactions on Information Theory_ , vol. 51, no. 9, pp. 3075–3085, Sept. 2005.


C4-1 | 0.279834 | 0.399067 | 0.432489 | 500 | 471 | 500 | 422.63 | 992.47 | 1539.73
C5-1 | 0.392415 | 0.564469 | 0.564884 | 500 | 468 | 500 | 443.17 | 971.72 | 1538.01
C6-1 | 0.319871 | 0.505397 | 0.506527 | 382 | 464 | 500 | 429.46 | 963.15 | 1543.40
C7-1 | 0.230476 | 0.494416 | 0.500799 | 71 | 467 | 500 | 421.11 | 952.47 | 1515.98
C1-2 | 0.630014 | 0.925657 | 0.927298 | 82 | 410 | 500 | 387.89 | 963.36 | 1467.46
C2-2 | 0.636132 | 0.952033 | 0.957938 | 103 | 410 | 500 | 398.10 | 951.38 | 1519.20
C3-2 | 0.47998 | 0.967442 | 0.969775 | 40 | 354 | 500 | 376.67 | 929.88 | 1419.33
C4-2 | 0.577446 | 0.895814 | 0.917401 | 73 | 412 | 500 | 385.00 | 990.48 | 1492.62
C5-2 | 0.374383 | 0.946422 | 0.950055 | 89 | 417 | 500 | 396.70 | 1031.74 | 1592.74
C6-2 | 0.555871 | 0.958149 | 0.960983 | 92 | 366 | 500 | 383.10 | 950.24 | 1477.62
C7-2 | 0.530525 | 0.925249 | 0.925615 | 76 | 412 | 500 | 387.90 | 986.33 | 1536.91
Table 4.6:  Comparison of algorithms according to coverage set indicator. Instances | NSGA-II | MOEA/D | Hybrid | NSGA-II | Hybrid | MOEA/D
---|---|---|---|---|---|---
MOEA/D | NSGA-II | NSGA-II | Hybrid | MOEA/D | Hybrid
A1-1 | 0 | 0 | 0 | 0 | 0 | 0
A2-1 | 0 | 0 | 0 | 0 | 0 | 0
A3-1 | 0 | 0 | 0 | 0 | 0 | 0
A4-1 | 0 | 0 | 0 | 0 | 0 | 0
A5-1 | 0 | 0 | 0 | 0 | 0 | 0
A6-1 | 0.043 | 0 | 0 | 0 | 0.043 | 0
A7-1 | 0 | 0 | 0 | 0 | 0 | 0
A1-2 | 0.114 | 0.127 | 0.127 | 0 | 0.114 | 0
A2-2 | 0.227 | 0.063 | 0.0625 | 0 | 0.227 | 0
A3-2 | 0 | 0 | 0 | 0 | 0 | 0
A4-2 | 0.333 | 0 | 0.333 | 0 | 0 | 0
A5-2 | 0.417 | 0 | 0 | 0 | 0.417 | 0
A6-2 | 0 | 0 | 0 | 0 | 0 | 0
A7-2 | 0 | 0.083 | 0.083 | 0 | 0 | 0
B1-1 | 0.408 | 0.097 | 0.101 | 0 | 0.508 | 0.200
B2-1 | 0.524 | 0.024 | 0.094 | 0 | 0.704 | 0
B3-1 | 0.462 | 0.106 | 0.222 | 0 | 0.489 | 0.040
B4-1 | 0.702 | 0.056 | 0.235 | 0 | 0.844 | 0.008
B5-1 | 0.060 | 0.205 | 0.205 | 0 | 0.092 | 0.184
B6-1 | 0.140 | 0.201 | 0.269 | 0 | 0.248 | 0.032
B7-1 | 0.035 | 0.098 | 0.060 | 0 | 0.040 | 0.084
B1-2 | 0.568 | 0.015 | 0.065 | 0 | 0.568 | 0.016
B2-2 | 0.543 | 0.057 | 0.161 | 0 | 0.543 | 0.048
B3-2 | 1 | 0 | 0.091 | 0 | 1 | 0
B4-2 | 0.583 | 0.029 | 0.249 | 0 | 0.597 | 0.016
B5-2 | 0.866 | 0.021 | 0.014 | 0 | 0.866 | 0.020
B6-2 | 1 | 0 | 0.126 | 0 | 1 | 0
B7-2 | 1 | 0 | 0.211 | 0 | 1 | 0
C1-1 | 0.152 | 0.037 | 0.061 | 0 | 0.150 | 0.036
C2-1 | 0.144 | 0.061 | 0.106 | 0 | 0.144 | 0.058
C3-1 | 0.484 | 0 | 0.085 | 0 | 0.484 | 0
C4-1 | 0.258 | 0.053 | 0.244 | 0 | 0.258 | 0.050
C5-1 | 0.028 | 0.060 | 0.006 | 0 | 0.028 | 0.056
C6-1 | 0.058 | 0.078 | 0.013 | 0 | 0.058 | 0.072
C7-1 | 0.592 | 0.002 | 0.105 | 0 | 0.592 | 0.002
C1-2 | 1 | 0 | 0.078 | 0 | 1 | 0
C2-2 | 1 | 0 | 0.320 | 0 | 1 | 0
C3-2 | 1 | 0 | 0.232 | 0 | 1 | 0
C4-2 | 1 | 0 | 0.330 | 0 | 1 | 0
C5-2 | 1 | 0 | 0.091 | 0 | 1 | 0
C6-2 | 1 | 0 | 0.194 | 0 | 1 | 0
C7-2 | 1 | 0 | 0.056 | 0 | 1 | 0

A1A2A3A4A5A6A7B1B2B3B4B5B6B7C1C2C3C4C5C6C7$0$$0.2$$0.4$$0.6$$0.8$InstancesHypervolumeMOEA/D:
1 TW MOEA/D: 2 TW

Figure 4.1: Hypervolume indicator for MOEA/D algorithm according to time
windows (TW)

A1A2A3A4A5A6A7B1B2B3B4B5B6B7C1C2C3C4C5C6C7$0$$0.2$$0.4$$0.6$$0.8$$1$InstancesHypervolumeNSGA-
II: 1 TW NSGA-II: 2 TW

Figure 4.2: Hypervolume indicator for NSGA-II algorithm according to time
windows (TW)

A1A2A3A4A5A6A7B1B2B3B4B5B6B7C1C2C3C4C5C6C7$0$$0.2$$0.4$$0.6$$0.8$$1$InstancesHypervolumeHybrid:
1 TW Hybrid: 2 TW

Figure 4.3: Hypervolume indicator for Hybrid NSGA-II with MOEA/D algorithm
according to time windows (TW)

A1A2A3A4A5A6A7B1B2B3B4B5B6B7C1C2C3C4C5C6C7$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$InstancesHypervolumeNSGA-
IIHybridMOEA/D

Figure 4.4:  Comparison of algorithms for instances with one availability
period according to hypervolume indicator

A1A2A3A4A5A6A7B1B2B3B4B5B6B7C1C2C3C4C5C6C7$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$InstancesHypervolumeNSGA-
IIHybridMOEA/D

Figure 4.5:  Comparison of algorithms for instances with two availability
periods according to hypervolume indicator

According to CPU time indicator, MOEA/D solved instances faster. In the case
where the decision maker is not interested to obtain the whole Pareto front,
MOEA/D may be the best choice to solve the HHCRSP (see Table 4.5). According
to the hypervolume indicator, NSGA-II and the hybrid algorithms outperformed
MOEA/D algorithm. Taking into consideration both hypervolume and Pareto front
size indicators showed that the hybrid algorithm outperformed MOEA/D and NSGA-
II algorithms.

The comparison according to the coverage metric is also carried out (see Table
4.6). This indicator did not differentiate algorithms performances for small
instances A (single or double time windows) and B (single time window) because
the algorithms generated very few non-dominated solutions compared to medium
and large instances. However, For instances $B$ (double time windows) and $C$
(single or double time windows), NSGA-II performs better than MOEA/D. The
percentage of solutions found by MOEA/D and dominated by solutions of NSGA-II
is remarkable. The hybrid algorithm outperformed both NSGA-II and MOEA/D
algorithms. In most of the 42 instances, except instances $B5$-1, $B7$-1,
$C5$-1, and $C6$-1, the percentage of MOEA/D solutions dominated by those of
the hybrid algorithm is greater and significant compared to the proportion of
solutions of the hybrid algorithm that are dominated by those of MOEA/D.

For all instances, Cov(NSGA-II, Hybrid)=0 because the set of solutions found
by NSGA-II are improved by MOEA/D. In the worst case, MOEA/D will not be able
to improve solutions found by NSGA-II , which is the case for instances of set
A with single time window and instances A3-2, A5-2 and A6-2. Accordingly,
Cov(Hybrid, NSGA-II)$>0$ for all instances, except for previously mentioned
instances, which indicate MOEA/D could further improve the quality of
solutions found by NSGA-II. Indeed, Cov(Hybrid, NSGA-II)$>0$ means that hybrid
could reach better solutions, which dominate some solutions found by NSGA-II.
The higher the value of Cov(Hybrid, NSGA-II) , the higher the proportion of
dominated solutions reached by NSGA-II.

In order to study the impact of the number of availability periods on the
quality of solutions, the coverage set metric is computed to compare the
approximated Pareto front found for each instance considering single and
double time windows. Table 4.4 clearly shows the advantage of instances with
double availability periods. A significant improvement is performed to the
approximated Pareto front when double time windows for patient are considered.
For all instances, except $A1,A2,A3,C4$ and $C4$, each solution from the
approximated Pareto front for the instances with single time window is
dominated at least by one solution from the approximated Pareto front for the
instances with double time windows (Cov(2 periods, 1 period)=1). Accordingly,
solutions from the approximated Pareto front for instances with double time
windows, except for previously mentioned instances, are not dominated by any
solution from the set of instances with single time window
($Cov(1\;period,\;2\;periods)=0$).

To sum up, the MOEA/D solves instances faster and is suitable if the decision
maker is not interested in having all Pareto optimal solutions. The NSGA-II
algorithm is very efficient and could found solutions close to the hybrid
algorithm in terms of quality considering hyper-volume indicator (see figures
4.5 and 4.5). However, NSGA-II is not suitable for problems with more than
three objectives. The hybrid algorithm outperformed NSGA-II and MOEA/D
algorithms, which is justified by performance indicators used (hyper-volume,
coverage set and Pareto front size: see tables 4.5 and 4.6). Using multiple
time windows improved solutions quality (see figures 4.3, 4.3 and 4.3) and
these solutions dominate solutions of instances with single availability
period (see Table 4.4).

###  4.3 Conclusion

Home health care companies often deal with conflicting objectives, such as
minimizing the cost while increasing patients’ satisfactions. Most studies
transform multi-objective problems by into a mono-objective case using
scalarazition techniques. The issue is how to assign weights to objective
functions, which may be a confusing task for the decision maker. Consequently,
he needs to be involved a posteriori to select a final preferred solution from
the non-dominated solutions set. In addition, most studies consider only
single time window per patient in which he will be available to be visited by
the assigned caregiver.

This chapter deals with the HHCRSP with multi-objectives and multiple
availability periods of patients. The goal is to minimize the travel and
waiting times as well as to balance caregivers’ workload. Two approaches are
adopted to tackle the multi-objective case: Pareto based, where NSGA-II is
implemented and decomposition based, where MOEA/D is implemented. An efficient
hybrid algorithm is proposed by performing NSGA-II and then MOEA/D
successively, which would improve solutions quality found by NSGA-II.

Performance indicators proved that the hybrid algorithm outperforms MOEA/D and
NSGA-II algorithms in terms of solutions quality while MOEA/D solves instances
faster. MOEA/D is more suitable if the decision maker is not interested in
having all Pareto optimal solutions. Besides, the benefit of using multiple
availability periods for patients is highlighted by the significant
improvement in the quality of the solutions after carrying out a comparison
with single time window per patient.

Future works could be addressed to adapt these approaches to deal with
multiple services operations and even considering the interdependence between
them since patients need several care activities per day. In addition, it
would be interesting to compare the performance of the hybrid algorithm with
some indicators-based approaches.

## General conclusion and perspectives

HHC aims to assist patients at home and to help them to live with greater
independence, avoiding hospitalization or admission to care institutions.
Providing health care services is expected to generate advantages such as, a
decrease in hospital admissions, a decrease in hospitalization duration and
the ability for patients to remain in their homes and receive care and
assistance. HHC companies face two major issues when planning schedules,
namely assigning qualified caregivers to requested services and defining
routes for caregivers to visit patients.

Establishing plannings should be done taking into consideration constraints
such as patients’ availability periods and caregivers’ qualification and
optimizing one or more criteria. In addition, the planning is affected by the
type of the model (deterministic, stochastic, multi-objectives). The
deterministic models are not robust since the uncertainties that may arise are
not considered. In multi-objective models, the decision maker has more choices
between solutions as the objective functions are simultaneously optimized.
From this perspective, the research work in this thesis focuses on modeling
and proposing solution methods to solve the home health care routing and
scheduling problem, which extend the VRP with time windows.

In chapter 1, we analyzed the works carried out in the literature, which cover
a very large variety concerning the constraints considered, the optimized
objectives and the methods used to solve the problem. The first limitation in
previous works is the no-consideration of multiple time windows for patients
as well as most of these studies that consider the synchronization of the
services are limited only to double. The second issue is related to
uncertainty of parameters, which is only dealt with in a few papers. The
predefined schedule should be adapted for any change in practical situations.
Otherwise, there will probably be delays in the services for patients who have
not yet been visited, which will cause their dissatisfaction. The third
limitation relates to the solution approaches used to solve the HHCRSP multi-
objective optimization model. Indeed, in the most cases, this model is solved
using aggregation techniques, but assigning weights to conflicting goals is a
difficult task.

In chapter 2, we have proposed a deterministic version of the HHCRSP that can
deal with an arbitrary number of time windows and services per patient as well
as taking into account of the synchronization of simultaneous services and
skill requirement. We proposed a new mathematical model as well as a GVNS
based heuristic, which is combined with a strategy to solve the model with
large instances. GVNS generates solutions (caregivers’ routes and their
assignment) while the strategy selects, for each patient, a time window and
ensures the synchronization of simultaneous services.

In chapter 3, we have considered the uncertainty of travel and service times.
We proposed two SPR models to cope with the uncertainty of parameters. In the
first one, the recourse is defined as a penalization of tardiness of services
operation and a remuneration for caregivers’ overtime. In the second one, we
assumed that patients’ times are hard/fixed and must be respected. Therefore,
we used another recourse defined as skipping a patient if his time windows
will not be respected. We showed through computational results the adequacy of
the GA to embed the simulation to solve the SPR model.

In chapter 4, we used algorithms designed to approach the Pareto front rather
than using the aggregation techniques. The decision maker will be involved a
posteriori to select a solution from not dominated solutions, which avoid
assigning weights to objective functions. Caregivers’ travel and waiting times
as well the balance of workload are three criteria that are simultaneously
optimized. Approaches based on Pareto and decomposition, with multi-objective
evolutionary algorithms are used to solve approximate Pareto front.
Computational results and performance measures inferred that the MOEA/D
algorithm solved instances faster while the hybrid algorithm found solutions
that better approximate the Pareto front.

Following this works, several research perspectives are available to continue
improving and/or extending our models.

Our proposed models can be extended to cover other important features such as,
considering lunch break for caregivers. Thus, allowing caregivers to take
breaks between the earliest and the latest of the break period where they can
take lunch. Considering the continuity of cares is also an important feature,
which allow patients to be visited by the same caregiver and during
approximately the same time. Our contributions are based on daily planning,
considering medium and long horizon plannings will lead to a better
optimization of scheduling and routing of caregivers as well as to avoid
defining daily caregivers plannings.

In the stochastic models, we considered that the uncertainty of the parameters
related to travel and service times follows the normal law. However, if the
distributions of parameters exposed to the uncertainty are unknown, it would
be better to use the robust optimization. The uncertainty in this model is not
stochastic, but rather deterministic and set-based. In addition, we considered
the uncertainty of of travel and service times, but the demand could also be
exposed to the uncertainties and future works might address this issue.

We used a simulation-based optimization to the solve the SPR model since
computing the expected real value by an explicit mathematical formula is very
complex. The computational results showed that the time resolution of some
instances is relatively long because the simulation requires many iterations
to find a good estimation. As future work, it would be interesting to compute
the expected real value by an explicit mathematical formula or to approximate
it in order to avoid using the simulation. Otherwise, one might think of
machine learning methods in the hope of reducing the number of iterations in
the simulation method to estimate the expected value of each solution.

One of the main problems is the lack of generic benchmark instances that can
be used to compare the performance of new methods and models. In most cases,
especially when new features are considered, researchers randomly generate new
instances to test their models and methods, as the instances in the literature
are designed for classical problems such as TSP, CVRP, VRPTW…etc. This problem
can be tackled by generating new generic reference instances that contain the
features studied in the literature.

## References

  * [1] S. Afifi, D.-C. Dang, and A. Moukrim.  Heuristic solutions for the vehicle routing problem with time windows and synchronized visits.  Optimization Letters, 10(3):511–525, 2016.
  * [2] C. Akjiratikarl, P. Yenradee, and P. R. Drake.  Pso-based algorithm for home care worker scheduling in the uk.  Computers & Industrial Engineering, 53(4):559–583, 2007.
  * [3] H. Allaoua, S. Borne, L. Létocart, and R. W. Calvo.  A matheuristic approach for solving a home health care problem.  Electronic Notes in Discrete Mathematics, 41:471–478, 2013.
  * [4] J. E. Baker.  Adaptive selection methods for genetic algorithms.  In Proceedings of an International Conference on Genetic Algorithms and their applications, pages 101–111. Hillsdale, New Jersey, 1985\.
  * [5] J. F. Bard, Y. Shao, and A. I. Jarrah.  A sequential grasp for the therapist routing and scheduling problem.  Journal of Scheduling, 17(2):109–133, 2014.
  * [6] J. F. Bard, Y. Shao, and H. Wang.  Weekly scheduling models for traveling therapists.  Socio-Economic Planning Sciences, 47(3):191–204, 2013.
  * [7] M. Bazirha, A. Kadrani, and R. Benmansour.  Daily scheduling and routing of home health care with multiple availability periods of patients.  In International Conference on Variable Neighborhood Search, pages 178–193. Springer, 2020.
  * [8] M. Bazirha, A. Kadrani, and R. Benmansour.  Scheduling optimization of the home health care problem with stochastic travel and care times.  In 2020 5th International Conference on Logistics Operations Management (GOL), pages 1–8. IEEE, 2020.
  * [9] M. Bazirha, A. Kadrani, and R. Benmansour.  Stochastic home health care routing and scheduling problem with multiple synchronized services.  Annals of Operations Research, pages 1–29, 2021.
  * [10] M. Bazirha, A. Kadrani, and R. Benmansour.  Optimization of the stochastic home health care routing and scheduling problem with multiple hard time windows.  International Journal of Supply and Operations Management, 9(2):235–250, 2022.
  * [11] S. V. Begur, D. M. Miller, and J. R. Weaver.  An integrated spatial dss for scheduling and routing home-health-care nurses.  Interfaces, 27(4):35–48, 1997.
  * [12] S. Belhaiza, P. Hansen, and G. Laporte.  A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows.  Computers & Operations Research, 52:269–281, 2014.
  * [13] E. J. Beltrami and L. D. Bodin.  Networks and vehicle routing for municipal waste collection.  Networks, 4(1):65–94, 1974.
  * [14] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski.  Robust optimization, volume 28.  Princeton University Press, 2009.
  * [15] D. G. Bernard.  Linear programming under uncertainty.  Management Science, 1:97–206, 1955.
  * [16] S. Bertels and T. Fahle.  A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem.  Computers & operations research, 33(10):2866–2890, 2006.
  * [17] D. Bertsimas, D. B. Brown, and C. Caramanis.  Theory and applications of robust optimization.  SIAM review, 53(3):464–501, 2011.
  * [18] J. Bowers, H. Cheyne, G. Mould, and M. Page.  Continuity of care in community midwifery.  Health care management science, 18(2):195–204, 2015.
  * [19] K. Braekers, R. F. Hartl, S. N. Parragh, and F. Tricoire.  A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience.  European Journal of Operational Research, 248(2):428–443, 2016\.
  * [20] K. Braekers, K. Ramaekers, and I. Van Nieuwenhuyse.  The vehicle routing problem: State of the art classification and review.  Computers & Industrial Engineering, 99:300–313, 2016.
  * [21] O. Bräysy and M. Gendreau.  Vehicle routing problem with time windows, part i: Route construction and local search algorithms.  Transportation science, 39(1):104–118, 2005.
  * [22] O. Bräysy, P. Nakari, W. Dullaert, and P. Neittaanmäki.  An optimization approach for communal home meal delivery service: A case study.  Journal of Computational and Applied Mathematics, 232(1):46–53, 2009.
  * [23] D. Bredström and M. Rönnqvist.  Combined vehicle routing and scheduling with temporal precedence and synchronization constraints.  European journal of operational research, 191(1):19–31, 2008.
  * [24] D. Brockhoff and E. Zitzler.  Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods.  In 2007 IEEE congress on evolutionary computation, pages 2086–2093. IEEE, 2007.
  * [25] E. K. Burke, P. De Causmaecker, G. V. Berghe, and H. Van Landeghem.  The state of the art of nurse rostering.  Journal of scheduling, 7(6):441–499, 2004.
  * [26] P. Cappanera and M. G. Scutellà.  Addressing consistency and demand uncertainty in the home care planning problem.  Flexible Services and Manufacturing Journal, pages 1–39, 2021.
  * [27] P. Cappanera, M. G. Scutellà, F. Nervi, and L. Galli.  Demand uncertainty in robust home care optimization.  Omega, 80:95–110, 2018.
  * [28] J. A. Castillo-Salazar, D. Landa-Silva, and R. Qu.  Workforce scheduling and routing problems: literature survey and computational study.  Annals of Operations Research, 239(1):39–67, 2016.
  * [29] A. Charnes and W. W. Cooper.  Chance-constrained programming.  Management science, 6(1):73–79, 1959.
  * [30] A. Ciré and J. N. Hooker.  A heuristic logic-based benders method for the home health care problem.  manuscript, presented at Matheuristics, 2012.
  * [31] M. Cissé, S. Yalçındağ, Y. Kergosien, E. Şahin, C. Lenté, and A. Matta.  Or problems related to home health care: A review of relevant routing and scheduling problems.  Operations Research for Health Care, 13:1–22, 2017.
  * [32] G. Clarke and J. W. Wright.  Scheduling of vehicles from a central depot to a number of delivery points.  Operations research, 12(4):568–581, 1964.
  * [33] G. Dantzig, R. Fulkerson, and S. Johnson.  Solution of a large-scale traveling-salesman problem.  Journal of the operations research society of America, 2(4):393–410, 1954.
  * [34] L. Davis.  Handbook of genetic algorithms.  1991\.
  * [35] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan.  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  IEEE transactions on evolutionary computation, 6(2):182–197, 2002\.
  * [36] J. Decerle, O. Grunder, A. H. El Hassani, and O. Barakat.  A memetic algorithm for a home health care routing and scheduling problem.  Operations research for health care, 16:59–71, 2018.
  * [37] J. Decerle, O. Grunder, A. H. El Hassani, and O. Barakat.  A memetic algorithm for multi-objective optimization of the home health care problem.  Swarm and evolutionary computation, 44:712–727, 2019.
  * [38] A. Dohn, M. S. Rasmussen, and J. Larsen.  The vehicle routing problem with time windows and temporal dependencies.  Networks, 58(4):273–289, 2011.
  * [39] M. Drexl.  Synchronization in vehicle routing—a survey of vrps with multiple synchronization constraints.  Transportation Science, 46(3):297–316, 2012.
  * [40] P. M. Duque, M. Castro, K. Sörensen, and P. Goos.  Home care service planning. the case of landelijke thuiszorg.  European Journal of Operational Research, 243(1):292–301, 2015\.
  * [41] M. Emmerich, N. Beume, and B. Naujoks.  An emo algorithm using the hypervolume measure as selection criterion.  In International Conference on Evolutionary Multi-Criterion Optimization, pages 62–76. Springer, 2005.
  * [42] F. Errico, G. Desaulniers, M. Gendreau, W. Rei, and L.-M. Rousseau.  A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times.  European Journal of Operational Research, 249(1):55–66, 2016.
  * [43] P. Eveborn, P. Flisberg, and M. Rönnqvist.  Laps care—an operational system for staff planning of home care.  European journal of operational research, 171(3):962–976, 2006\.
  * [44] A. M. Fathollahi-Fard, A. Ahmadi, F. Goodarzian, and N. Cheikhrouhou.  A bi-objective home healthcare routing and scheduling problem considering patients’ satisfaction in a fuzzy environment.  Applied soft computing, page 106385, 2020.
  * [45] D. Favaretto, E. Moretti, and P. Pellegrini.  Ant colony system for a vrp with multiple time windows and multiple visits.  Journal of Interdisciplinary Mathematics, 10(2):263–284, 2007.
  * [46] C. Fikar and P. Hirsch.  Home health care routing and scheduling: A review.  Computers & Operations Research, 77:86–95, 2017.
  * [47] P. M. Francis, K. R. Smilowitz, and M. Tzur.  The period vehicle routing problem and its extensions.  In The vehicle routing problem: latest advances and new challenges, pages 73–102. Springer, 2008.
  * [48] G. Freeman, J. Hughes, et al.  Continuity of care and the patient experience, 2010.
  * [49] S. Frifita and M. Masmoudi.  Vns methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties.  International Transactions in Operational Research, 27(1):291–313, 2020.
  * [50] M. Gamst and T. S. Jensen.  A branch-and-price algorithm for the long-term home care scheduling problem.  In Operations research proceedings 2011, pages 483–488. Springer, 2012.
  * [51] M. R. Garey.  A guide to the theory of np-completeness.  Computers and intractability, 1979.
  * [52] M. Gendreau, G. Laporte, and R. Séguin.  Stochastic vehicle routing.  European Journal of Operational Research, 88(1):3–12, 1996.
  * [53] F. Glover.  Future paths for integer programming and links to artificial intelligence.  Computers & operations research, 13(5):533–549, 1986.
  * [54] D. E. Goldberg and K. Deb.  A comparative analysis of selection schemes used in genetic algorithms.  In Foundations of genetic algorithms, volume 1, pages 69–93. Elsevier, 1991.
  * [55] X. Gong, N. Geng, Y. Zhu, A. Matta, and E. Lanzarone.  A matheuristic approach for the home care scheduling problem with chargeable overtime and preference matching.  IEEE Transactions on Automation Science and Engineering, 18(1):282–298, 2020.
  * [56] L. Grieco, M. Utley, and S. Crowe.  Operational research applied to decisions in home health care: A systematic literature review.  Journal of the Operational Research Society, pages 1–32, 2020.
  * [57] M. H. Hà, T. D. Nguyen, T. N. Duy, H. G. Pham, T. Do, and L.-M. Rousseau.  A new constraint programming model and a linear programming-based adaptive large neighborhood search for the vehicle routing problem with synchronization constraints.  Computers & Operations Research, 124:105085, 2020.
  * [58] M. Hewitt, M. Nowak, and N. Nataraj.  Planning strategies for home health care delivery.  Asia-Pacific Journal of Operational Research, 33(05):1650041, 2016\.
  * [59] G. Hiermann, M. Prandtstetter, A. Rendl, J. Puchinger, and G. R. Raidl.  Metaheuristics for solving a multimodal home-healthcare scheduling problem.  Central European Journal of Operations Research, 23(1):89–113, 2015\.
  * [60] J. H. Holland.  Genetic algorithms.  Scientific american, 267(1):66–73, 1992.
  * [61] A. Ikegami and A. Uno.  Bounds for staff size in home help staff scheduling (< special issue> the 50th anniversary of the operations research society of japan).  Journal of the Operations Research Society of Japan, 50(4):563–575, 2007.
  * [62] H. Ishibuchi and T. Murata.  A multi-objective genetic local search algorithm and its application to flowshop scheduling.  IEEE transactions on systems, man, and cybernetics, part C (applications and reviews), 28(3):392–403, 1998.
  * [63] Y. Kergosien, A. Ruiz, and P. Soriano.  A routing problem for medical test sample collection in home health care services.  In Proceedings of the international conference on health care systems engineering, pages 29–46. Springer, 2014.
  * [64] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.  Optimization by simulated annealing.  science, 220(4598):671–680, 1983.
  * [65] E. Lanzarone, A. Matta, and E. Sahin.  Operations management applied to home care services: the problem of assigning human resources to patients.  IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 42(6):1346–1363, 2012.
  * [66] G. Laporte, F. Louveaux, and H. Mercure.  The vehicle routing problem with stochastic travel times.  Transportation science, 26(3):161–170, 1992.
  * [67] X. Li, P. Tian, and S. C. Leung.  Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm.  International Journal of Production Economics, 125(1):137–145, 2010\.
  * [68] M. Lin, L. Ma, and C. Ying.  Matching daily home health-care demands with supply in service-sharing platforms.  Transportation Research Part E: Logistics and Transportation Review, 145:102177, 2021.
  * [69] R. Liu, X. Xie, V. Augusto, and C. Rodriguez.  Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care.  European Journal of Operational Research, 230(3):475–486, 2013\.
  * [70] R. Liu, B. Yuan, and Z. Jiang.  Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements.  International Journal of Production Research, 55(2):558–575, 2017\.
  * [71] R. Liu, B. Yuan, and Z. Jiang.  A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times.  Flexible Services and Manufacturing Journal, pages 1–23, 2018.
  * [72] Z. Luo, H. Qin, D. Zhang, and A. Lim.  Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost.  Transportation Research Part E: Logistics and Transportation Review, 85:69–89, 2016.
  * [73] L. Malagodi, E. Lanzarone, and A. Matta.  Home care vehicle routing problem with chargeable overtime and strict and soft preference matching.  Health Care Management Science, pages 1–20, 2021.
  * [74] D. S. Mankowska, F. Meisel, and C. Bierwirth.  The home health care routing and scheduling problem with interdependent services.  Health care management science, 17(1):15–30, 2014.
  * [75] M. Marinaki and Y. Marinakis.  A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands.  Expert Systems with Applications, 46:145–163, 2016.
  * [76] P. Matl, R. F. Hartl, and T. Vidal.  Workload equity in vehicle routing problems: A survey and analysis.  Transportation Science, 52(2):239–260, 2018.
  * [77] J. E. Mendoza, L.-M. Rousseau, and J. G. Villegas.  A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints.  Journal of Heuristics, 22(4):539–566, 2016.
  * [78] C. E. Miller, A. W. Tucker, and R. A. Zemlin.  Integer programming formulation of traveling salesman problems.  Journal of the ACM (JACM), 7(4):326–329, 1960.
  * [79] N. Mladenović and P. Hansen.  Variable neighborhood search.  Computers & operations research, 24(11):1097–1100, 1997.
  * [80] S. Nickel, M. Schröder, and J. Steeg.  Mid-term and short-term planning support for home health care services.  European Journal of Operational Research, 219(3):574–587, 2012\.
  * [81] D. C. Paraskevopoulos, G. Laporte, P. P. Repoussis, and C. D. Tarantilis.  Resource constrained routing and scheduling: Review and research prospects.  European Journal of Operational Research, 263(3):737–754, 2017\.
  * [82] V. Pareto.  Cours d’économie politique, volume 1.  Librairie Droz, 1964.
  * [83] S. N. Parragh and K. F. Doerner.  Solving routing problems with pairwise synchronization constraints.  Central European journal of operations research, 26(2):443–464, 2018.
  * [84] M. S. Rasmussen, T. Justesen, A. Dohn, and J. Larsen.  The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies.  European Journal of Operational Research, 219(3):598–610, 2012\.
  * [85] R. Redjem and E. Marcon.  Operations management in the home care services: a heuristic for the caregivers’ routing problem.  Flexible Services and Manufacturing Journal, 28(1-2):280–303, 2016\.
  * [86] A. Rendl, M. Prandtstetter, G. Hiermann, J. Puchinger, and G. Raidl.  Hybrid heuristics for multimodal homecare scheduling.  In International Conference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pages 339–355. Springer, 2012.
  * [87] K.-D. Rest and P. Hirsch.  Daily scheduling of home health care services using time-dependent public transport.  Flexible Services and Manufacturing Journal, 28(3):495–525, 2016\.
  * [88] M. W. Savelsbergh and M. Sol.  The general pickup and delivery problem.  Transportation science, 29(1):17–29, 1995.
  * [89] S. Shahnejat-Bushehri, R. Tavakkoli-Moghaddam, M. Boronoos, and A. Ghasemkhani.  A robust home health care routing-scheduling problem with temporal dependencies under uncertainty.  Expert Systems with Applications, page 115209, 2021.
  * [90] Y. Shi, T. Boudouh, and O. Grunder.  A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times.  Transportation Research Part E: Logistics and Transportation Review, 128:52–95, 2019.
  * [91] Y. Shi, T. Boudouh, O. Grunder, and D. Wang.  Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care.  Expert Systems with Applications, 102:218–233, 2018.
  * [92] M. M. Solomon and J. Desrosiers.  Survey paper—time window constrained routing and scheduling problems.  Transportation Science, 22(1):1–13, Feb. 1988.
  * [93] E. Taillard.  Some efficient heuristic methods for the flow shop sequencing problem.  European journal of Operational research, 47(1):65–74, 1990.
  * [94] R. Tarricone and A. D. Tsouros.  Home care in Europe: the solid facts.  WHO Regional Office Europe, 2008.
  * [95] D. Taş, N. Dellaert, T. van Woensel, and T. De Kok.  The time-dependent vehicle routing problem with soft time windows and stochastic travel times.  Transportation Research Part C: Emerging Technologies, 48:66–83, 2014.
  * [96] D. Taş, M. Gendreau, N. Dellaert, T. Van Woensel, and A. De Kok.  Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach.  European Journal of Operational Research, 236(3):789–799, 2014\.
  * [97] K. Thomsen.  Optimization on home care.  Master’s thesis, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark, 2006.
  * [98] A. Trautsamwieser, M. Gronalt, and P. Hirsch.  Securing home health care in times of natural disasters.  OR spectrum, 33(3):787–813, 2011.
  * [99] A. Trautsamwieser and P. Hirsch.  Optimization of daily scheduling for home health care services.  Journal of Applied Operational Research, 3(3):124–136, 2011.
  * [100] A. Trautsamwieser and P. Hirsch.  A branch-price-and-cut approach for solving the medium-term home health care planning problem.  Networks, 64(3):143–159, 2014.
  * [101] F. Tricoire.  Multi-directional local search.  Computers & operations research, 39(12):3089–3101, 2012.
  * [102] A. Trivedi, D. Srinivasan, K. Sanyal, and A. Ghosh.  A survey of multiobjective evolutionary algorithms based on decomposition.  IEEE Transactions on Evolutionary Computation, 21(3):440–462, 2016\.
  * [103] T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins.  Heuristics for multi-attribute vehicle routing problems: A survey and synthesis.  European Journal of Operational Research, 231(1):1–21, 2013.
  * [104] J. Von Neumann and S. Ulam.  Monte carlo method.  National Bureau of Standards Applied Mathematics Series, 12(1951):36, 1951.
  * [105] J. Wirnitzer, I. Heckmann, A. Meyer, and S. Nickel.  Patient-based nurse rostering in home care.  Operations Research for Health Care, 8:91–102, 2016.
  * [106] B. Yuan, R. Liu, and Z. Jiang.  A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements.  International Journal of Production Research, 53(24):7450–7464, 2015.
  * [107] Q. Zhang and H. Li.  Moea/d: A multiobjective evolutionary algorithm based on decomposition.  IEEE Transactions on evolutionary computation, 11(6):712–731, 2007\.
  * [108] E. Zitzler, D. Brockhoff, and L. Thiele.  The hypervolume indicator revisited: On the design of pareto-compliant indicators via weighted integration.  In International Conference on Evolutionary Multi-Criterion Optimization, pages 862–876. Springer, 2007.
  * [109] E. Zitzler, M. Laumanns, and L. Thiele.  Spea2: Improving the strength pareto evolutionary algorithm.  TIK-report, 103, 2001.
  * [110] E. Zitzler and L. Thiele.  Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach.  IEEE transactions on Evolutionary Computation, 3(4):257–271, 1999\.

  *[HHCRSP]: Home Health Care Routing and Scheduling Problem
  *[VRPTW]: Vehicle Routing Problem with Time Windows
  *[HHC]: Home Health Care
  *[GVNS]: General Variable Neighborhood Search
  *[SPR]: Stochastic Programming with Recourse
  *[GA]: Genetic Algorithm
  *[NSGA-II]: Non-Dominated Sorting Genetic Algorithm II
  *[MOEA/D]: Multi-Objective Evolutionary Algorithm based on Decomposition
  *[]:
  *[VRP]: Vehicle Routing Problem
  *[VNS]: Variable Neighborhood Search
  *[TS]: Tabu Search
  *[SA]: Simulated Annealing
  *[MOEAs]: Multi-Objective Evolutionary Algorithms