# Attaining mean square boundedness of a marginally stable stochastic linear
system with a bounded control input

Federico Ramponi  ,  Debasish Chatterjee  ,  Andreas Milias-Argeitis  ,  Peter
Hokayem  and  John Lygeros  Automatic Control Laboratory, ETL I28, ETH Zürich,
Physikstrasse 3, 8092 Zürich, Switzerland http://control.ee.ethz.ch
<EMAIL_ADDRESS>
###### Abstract.

In this article we construct control policies that ensure bounded variance of
a noisy marginally stable linear system in closed-loop. It is assumed that the
noise sequence is a mutually independent sequence of random vectors, enters
the dynamics affinely, and has bounded fourth moment. The magnitude of the
control is required to be of the order of the first moment of the noise, and
the policies we obtain are simple and computable.

This research was partially supported by the Swiss National Science
Foundation, grant 200021-122072.

##  1\. Introduction

Stabilization of stochastic linear systems with bounded control inputs has
attracted considerable attention over the years. This is due to the fact that
incorporating bounds on the control is of paramount importance in practical
applications; suboptimal control strategies such as receding-horizon control
[Chatterjee et al., 2009; Hokayem et al., 2009], and rollout algorithms
[Bertsekas, 2000], among others, were designed to incorporate such constraints
with relative ease, and have become widespread in applications. However, the
following question remains open: _when is a linear system with possibly
unbounded additive stochastic noise globally stabilizable with bounded
inputs?_ In this article we shall provide sufficient conditions that give a
positive answer to this question with minimal hypotheses.

Bounded input control has a rich and important history in the control
literature [Yang et al., 1992; Sussmann et al., 1994; Yang et al., 1997; Lin
et al., 1996; Stoorvogel et al., 2007]. The deterministic version of the
bounded input stabilization problem was solved completely in a series of
articles [Yang et al., 1992; Sussmann et al., 1994] culminating in [Yang et
al., 1997]. It was demonstrated in [Yang et al., 1997] that global asymptotic
stabilization of a discrete-time linear system

($(\star)$) $x_{t+1}=Ax_{t}+Bu_{t}$

with bounded feedback inputs is possible if and only if the transition matrix
has spectral radius at most $1$, and the pair $(A,B)$ is stabilizable with
arbitrary controls. Moreover, extensions to the output feedback case have
appeared in [Bao et al., 2000; Chitour and Lin, 2003].

In the presence of affine stochastic noise the linear system ($(\star)$ ‣ 1)
becomes $x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$, where $(w_{t})_{t\in\mathbb{N}_{0}}$ is
a collection of independent (but not necessarily identically distributed)
random vectors in $\mathbb{R}^{d}$ with possibly inter-dependent components at
each time $t$. With an arbitrary noise it is clearly not possible to ensure
mean-square boundedness; for instance, if the noise has a spherically
symmetric Cauchy distribution on $\mathbb{R}^{d}$, then given any initial
condition $x_{0}\in\mathbb{R}^{d}$, the second moment of $x_{1}$ does not even
exist. Similarly, if the second moment of the noise becomes unbounded with
time, it is not possible to control the second moment of the process
$(x_{t})_{t\in\mathbb{N}_{0}}$. It is necessary to assume, at least, that the
noise has bounded variance.

Going beyond this necessary condition, it is not difficult to establish mean-
square boundedness of such a system with bounded controls under the assumption
that $A$ is Schur stable, i.e., all eigenvalues of $A$ are contained in the
interior of the unit disk (the proof of this fact relies on standard Foster-
Lyapunov techniques [Meyn and Tweedie, 1993]). However, to the best of our
knowledge, there is no proof that the same can be ensured for a marginally
stable linear system. Results in this direction were reported in [Stoorvogel
et al., 2007], but to the best of our understanding _conclusive_ proofs of the
facts reported in the present article are still missing in the literature.

In this article, we develop easily computable bounded control policies for the
case when $A$ is marginally stable and $(A,B)$ is stabilizable. Our policy is
not anyway stationary and is in general chosen from the class of finite
$k$-history-dependent and/or non-stationary policies. With respect to the case
when $A$ is orthogonal, it turns out that if the system is reachable in one
step (i.e., $\operatorname{rank}B=$ the dimension of the state space), we do
get stationary feedback policies. In the more general case when the system
($(\star)$ ‣ 1) is reachable in $k$ steps (with arbitrary controls), we
propose a feedback policy for a sub-sampled system derived from the original
one, which, for the actual system, turns out to be a $k$-history-dependent
policy. In fact, in this case we realize our policy as successive
concatenations of a fixed $k$-length policy. In the most general situation we
propose a $k$-history-dependent policy, where $k$ is now the reachability
index of the particular subsystem of $(A,B)$ for which the dynamics matrix is
orthogonal. In all the mentioned cases, the length of the policy is at most
equal to the dimension of the state space; memory requirements for even the
most general case are, therefore, modest.

Note that in our setting we do _not_ assume that the noise is white. For our
purposes the requirements on the noise are rather general, namely, the fourth
moment of the noise should be uniformly bounded, and the noise vectors should
be independent of each other (identical distribution at each time is not
assumed). In particular, we do _not_ assume Gaussian structure of the noise.
It turns out that to ensure stabilization we need the controller to be
sufficiently strong, in the sense that the control input norm bound should be
bigger than a uniform bound on the first moment of the noise.

Section 2 contains a precise statement of our result in the most general
hypotheses ($A$ marginally stable and $(A,B)$ stabilizable), and a brief
sketch of the proof. In Section 3, after some preliminary material, we prove
the attainability of bounded second moment for a random walk, then we
generalize the result under weaker and weaker hypotheses, finally culminating
in the proof of the main theorem of Section 2. Section 4 presents a numerical
example illustrating our results, and Section 5 concludes the article with a
conjecture.

##  2\. Main result

###  2.1. Statement of the theorem

Consider the discrete-time linear system

((2.1)) $x_{t+1}=Ax_{t}+Bu_{t}+w_{t},\qquad x_{0}=x,\quad t\in\mathbb{N}_{0},$

where the following hold: $x\in\mathbb{R}^{d}$ is given; the state $x_{t}$ at
time $t$ takes values in $\mathbb{R}^{d}$; $A\in\mathbb{R}^{d\times d}$, all
the eigenvalues of $A$ lie in the closed unit circle, and those eigenvalues
$\lambda$ such that $|\lambda|=1$ have equal algebraic and geometric
multiplicities; $B\in\mathbb{R}^{d\times m}$, and the control $u_{t}$ at time
$t$ takes values in $\mathbb{R}^{m}$; $(w_{t})_{t\in\mathbb{N}_{0}}$ is an
$\mathbb{R}^{d}$-valued random process with mean zero and
$\mathsf{E}\bigl{[}w_{t}w_{t}^{\scriptscriptstyle{\mathrm{T}}}\bigr{]}=Q_{t}$.

Our objective is to synthesize a $k$-history-dependent control policy111See
§3.1 for definitions of policies. $\pi=(\pi_{t})_{t\in\mathbb{N}_{0}}$,
consisting of successive concatenations of $k$-length sequence
$\tilde{\pi}_{0:k-1}\coloneqq\bigl{[}\tilde{\pi}_{0},\cdots,\tilde{\pi}_{k-1}\bigr{]}$
of maps, $\tilde{\pi}_{i}:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{m}$ for
$i=0,\ldots,k-1$, such that $\pi_{t}:\mathbb{R}^{d\times
k}\longrightarrow\mathbb{R}^{m}$ is measurable,
$u_{t}\coloneqq\pi_{t}\bigl{(}x_{t},x_{t-1},\ldots,x_{t-k+1}\bigr{)}$, the
sequence $(u_{t})_{t\in\mathbb{N}_{0}}$ is bounded, and the state of the
closed-loop system

((2.2))
$x_{t+1}=Ax_{t}+B\pi_{t}\bigl{(}x_{t},x_{t-1},\ldots,x_{t-k+1}\bigr{)}+w_{t},\qquad
x_{0}=x,\quad t\in\mathbb{N}_{0},$

has bounded second-order moment. (To simplify the notation, we fix
$x_{-k+1}=\cdots=x_{-1}=x_{0}$.) The following is our main result:

######  (2.3) Theorem.

Consider the system ((2.1)). Suppose that the pair $(A,B)$ is stabilizable,
and that $\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\bigl{[}\left\lVert
w_{t}\right\rVert^{4}\bigr{]}<\infty$. Then there exist an $R>0$ and a
deterministic $k$-history-dependent policy $(\pi_{t})_{t\in\mathbb{N}_{0}}$,
with $k\leq d$ and $\left\lVert\pi_{t}(\cdot)\right\rVert\leqslant R$ for
every $t$, such that

  1. (P1)

for every fixed $x\in\mathbb{R}^{d}$ the process
$(x_{t})_{t\in\mathbb{N}_{0}}$ that solves the recursion ((2.2)) satisfies
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x}\bigl{[}\left\lVert
x_{t}\right\rVert^{2}\bigr{]}<\infty$, and

  2. (P2)

in the absence of the random noise the origin is asymptotically stable for the
closed-loop system.

###  2.2. Sketch of the proof

Our proof is built in a series of steps, moving from simpler to progressively
more complex systems. The starting point is the $d$-dimensional random walk
$x_{t+1}=x_{t}+u_{t}+w_{t}$. In this case we employ the main result of
[Pemantle and Rosenthal, 1999] to design a policy that guarantees mean-square
boundedness of the closed-loop system. We then consider the system
$x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$, where $u_{t}$ is a $d$-dimensional control
input, $\operatorname{rank}B=d$, and $A$ is orthogonal. With the help of a
time-varying injective linear transformation this case is reduced to the
$d$-dimensional random walk. The third case that we consider is that of the
system $x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$, where $u_{t}\in\mathbb{R}^{m}$ and $A$
is orthogonal. This is reduced to the second case above with the aid of an
injective linear transformation derived from the reachability matrix of the
pair $(A,B)$ (recall that by assumption the reachability matrix has rank $d$).
Finally, the general case when $A$ is just stable and $(A,B)$ stabilizable is
reduced to the third case with the observation that, in view of the stability
hypothesis, $A$ acts as an orthogonal map on its invariant subspace that
corresponds to the eigenvalues that lie on the unit circle.

Arguments for establishing mean-square boundedness of stochastic dynamical
systems typically rely on $L_{1}$-bounded-ness of a Lyapunov-like functional
of the system. The latter can be established in at least three different ways:
The first is via the classical Foster-Lyapunov drift-conditions [Foss and
Konstantopoulos, 2004; Meyn and Tweedie, 1993] and its various refinements;
the second is via excursion-theoretic analysis [Chatterjee and Pal, 2008] that
relies primarily on the existence of certain supermartingales as long as the
process is outside some bounded set; the third is via martingale inequalities
[Pemantle and Rosenthal, 1999], which applies to more general scalar-valued
processes than Markov processes, and in the presence of bounded controls,
provides the basic machinery for establishing our Theorem (2.3).

##  3\. Proof of the main result

###  3.1. Preliminaries

Let $\mathbb{N}_{0}$ be the set of nonnegative integers $\\{0,1,2,\ldots\\}$.
The standard $2$-norm on Euclidean spaces is denoted by
$\left\lVert\cdot\right\rVert$ and the absolute value on $\mathbb{R}$ by
$\left\lvert{\cdot}\right\rvert$. In a Euclidean space we denote by
${\mathcal{B}}_{r}$ the closed Euclidean ball of radius $r$ centered at the
origin. If $(y_{t})_{t\in\mathbb{N}_{0}}$ is a random process on a probability
space $(\Omega,\mathfrak{F},\mathsf{P})$, taking values in some Euclidean
space, we let $\mathsf{E}_{x}[\varphi(y_{s};s=0,1,\ldots,t)]$ denote the
conditional expectation of a measurable mapping $\varphi$ of the process up to
time $t$, given the initial condition $y_{0}=x$; in particular we define the
$n$-th moment of $y_{t}$ as $\mathsf{E}_{x}[\left\lVert
y_{t}\right\rVert^{n}]$. We denote conditional expectation given a
sub-$\sigma$-algebra $\mathfrak{F}^{\prime}$ of $\mathfrak{F}$ as
$\mathsf{E}[\cdot\,|\,\mathfrak{F}^{\prime}]$. For $r>0$ let
$\operatorname{sat}_{r}:\mathbb{R}^{d}\longrightarrow{\mathcal{B}}_{r}$ be
defined by $\operatorname{sat}_{r}(y)\coloneqq y$ if $y\in{\mathcal{B}}_{r}$
and $\operatorname{sat}_{r}(y)\coloneqq ry/\left\lVert y\right\rVert$
otherwise. Note that $\operatorname{sat}_{r}(\cdot)$ is _not_ the component-
wise saturation function. Given matrices $A\in\mathbb{R}^{d\times d}$ and
$B\in\mathbb{R}^{d\times m}$ we define the $k$-step reachability matrix
${\mathcal{R}}_{k}\coloneqq\left[\begin{array}[]{cccc}B&AB&\cdots&A^{k-1}B\end{array}\right]$.

We specialize the general definition of a policy [Hernández-Lerma and
Lasserre, 1996, Chapter 2] to our setting. A policy
$\pi\coloneqq(\pi_{t})_{t\in\mathbb{N}_{0}}$ is a sequence of measurable maps
$\pi_{t}:\mathbb{R}^{d\times k}\longrightarrow\mathbb{R}^{m}$ for some
$k\in\mathbb{N}$, such that the control at time $t$ is
$\pi_{t}\bigl{(}x_{t},x_{t-1},\ldots,x_{t-k+1}\bigr{)}$. The policy
$\pi=(\pi_{t})_{t\in\mathbb{N}_{0}}$ we have defined is also known as a
deterministic $k$-history-dependent policy in the literature. A special case
of these policies is a deterministic feedback policy or simply a feedback if
$k=1$ in the definition of a deterministic history-dependent policy. Under
deterministic feedback policies the closed-loop system is Markovian
[Hernández-Lerma and Lasserre, 1996, Proposition 2.3.5]. A further special
case is when $\pi_{t}=f$, a fixed measurable mapping
$f:\mathbb{R}^{d}\longrightarrow\mathbb{R}^{m}$ for $t\in\mathbb{N}_{0}$; this
is known as a stationary feedback policy.

######  (3.1) Lemma.

Let $B_{1},\cdots,B_{k}$ be $d\times m$ matrices,
$M\coloneqq\left[\begin{array}[]{ccc}B_{1}&\cdots&B_{k}\end{array}\right]$,
and $\sigma_{d}$ denote the minimum singular value of $M$. If
$\operatorname{rank}M=d$, then for all $r>0$ every vector $v\in\mathbb{R}^{d}$
belonging to ${\mathcal{B}}_{r}$ can be expressed as
$v=\sum_{i=1}^{k}B_{i}u_{i}$, with $u_{i}\in\mathbb{R}^{m}$ and $\left\lVert
u_{i}\right\rVert\leq r\sigma_{d}^{-1}$. In particular, if
$B\in\mathbb{R}^{d\times d}$ and $\operatorname{rank}B=d$, then every vector
$v\in\mathbb{R}^{d}$ belonging to ${\mathcal{B}}_{r}$ can be expressed as
$v=Bu$, where $u\in\mathbb{R}^{d}$, $\left\lVert u\right\rVert\leq
r\sigma_{d}^{-1}$.

###### Proof.

$\operatorname{rank}M=d$ implies that $km\geq d$. Hence,
$M=\left[\begin{array}[]{ccc}B_{1}&\cdots&B_{k}\end{array}\right]\in\mathbb{R}^{d\times
km}$ is a “flat” matrix. Let
$M=USV^{\scriptscriptstyle{\mathrm{T}}}=U\left[\begin{array}[]{cc}\Sigma&0\\\
\end{array}\right]V^{\scriptscriptstyle{\mathrm{T}}}$ be a singular value
decomposition of $M$, where $\Sigma=\mathop{\rm
diag}(\sigma_{1},...,\sigma_{d})$. Since $M$ has full rank, the matrix
$\Sigma$ is invertible. Hence every vector $v\in\mathbb{R}^{d}$ can be
expressed as $v=Mu$, where $u=M^{+}v$ and
$M^{+}=V\left[\begin{array}[]{c}\Sigma^{-1}\\\ 0\\\
\end{array}\right]U^{\scriptscriptstyle{\mathrm{T}}}\in\mathbb{R}^{km\times
d}$ is the Moore-Penrose pseudoinverse of $M$. Since $U,V$ are orthogonal, for
any $\rho>0$ we have $\inf_{\left\lVert u\right\rVert=\rho}\left\lVert
Mu\right\rVert=\inf_{\left\lVert
V^{\scriptscriptstyle{\mathrm{T}}}u\right\rVert=\rho}\left\lVert
U\left[\begin{array}[]{cc}\Sigma&0\\\
\end{array}\right]V^{\scriptscriptstyle{\mathrm{T}}}u\right\rVert=\inf_{\left\lVert\upsilon\right\rVert=\rho}\left\lVert\Sigma\upsilon\right\rVert=\rho\sigma_{d}.$
Hence, the image of ${\mathcal{B}}_{\rho}$ under $M$ contains
${\mathcal{B}}_{\rho\sigma_{d}}$, and if we choose $\rho=r\sigma_{d}^{-1}$,
then the image of ${\mathcal{B}}_{\rho}$ under $M$ contains
${\mathcal{B}}_{r}$. Notice that $\sigma_{d}^{-1}$ is also the greatest
singular value of $M^{+}$, and indeed we have $\sup_{\left\lVert
v\right\rVert=r}\left\lVert M^{+}v\right\rVert=\sup_{\left\lVert
U^{\scriptscriptstyle{\mathrm{T}}}v\right\rVert=r}\left\lVert
V\left[\begin{array}[]{c}\Sigma^{-1}\\\ 0\\\
\end{array}\right]U^{\scriptscriptstyle{\mathrm{T}}}v\right\rVert=\sup_{\left\lVert\nu\right\rVert=r}\bigl{\|}\Sigma^{-1}\nu\bigr{\|}=r\sigma_{d}^{-1}.$
Summing up, every $v\in{\mathcal{B}}_{r}$ can be expressed as $v=Mu$, where
$u\in\mathbb{R}^{km}$ and $\left\lVert u\right\rVert\leq r\sigma_{d}^{-1}$. It
remains to notice that $u$ can be partitioned according to the partition of
$M$, that is
$v=Mu=\left[\begin{array}[]{cccc}B_{1}&B_{2}&\cdots&B_{k}\end{array}\right]\begin{bmatrix}u_{1}^{\scriptscriptstyle{\mathrm{T}}}&\cdots&u_{k}^{\scriptscriptstyle{\mathrm{T}}}\end{bmatrix}^{\scriptscriptstyle{\mathrm{T}}}=\sum_{i=1}^{k}B_{i}u_{i}$
and the bound $\left\lVert u\right\rVert\leq r\sigma_{d}^{-1}$ implies
$\left\lVert u_{i}\right\rVert\leq r\sigma_{d}^{-1}$ for all $i=1\cdots k$. ∎

###  3.2. The $d$-dimensional random walk

At the core of our proof is the $d$-dimensional random walk:

((3.2)) $x_{t+1}=x_{t}+u_{t}+w_{t},\qquad x_{0}=x,\quad t\in\mathbb{N}_{0},$

with the state $x_{t}\in\mathbb{R}^{d}$, the control $u_{t}\in\mathbb{R}^{d}$
with $\left\lVert u_{t}\right\rVert\leqslant r$ for some $r>0$, the noise
process $(w_{t})_{t\in\mathbb{N}_{0}}$ satisfies the following assumption:

######  (3.3) Assumption.

  * $\diamond$

$(w_{t})_{t\in\mathbb{N}_{0}}$ are mutually independent $d$-dimensional random
vectors (not necessarily identically distributed),

  * $\diamond$

$\mathsf{E}[w_{t}]=0$,
$\mathsf{E}\bigl{[}w_{t}w_{t}^{\scriptscriptstyle{\mathrm{T}}}\bigr{]}=Q_{t}$
for all $t\in\mathbb{N}_{0}$,

  * $\diamond$

there exist $C_{4}>0$ such that $\mathsf{E}\bigl{[}\left\lVert
w_{t}\right\rVert^{4}\bigr{]}\leqslant C_{4}$ for all
$t\in\mathbb{N}_{0}$.$\diamondsuit$

Let $C_{1}\coloneqq\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\bigl{[}\left\lVert
w_{t}\right\rVert\bigr{]}$; this is well-defined because by Jensen’s
inequality we have $C_{1}\leqslant\sqrt[4]{C_{4}}$. Let
$(\mathfrak{F}_{t})_{t\in\mathbb{N}_{0}}$ be the natural filtration of the
system ((3.2)). Our proof of Theorem (2.3) relies on the following (immediate)
adaptation of the fundamental result [Pemantle and Rosenthal, 1999, Theorem
1].

######  (3.4) Proposition.

Let $(\xi_{t})_{t\in\mathbb{N}_{0}}$ be a sequence of nonnegative random
variables on some probability space $(\Omega,\mathfrak{F},\mathsf{P})$, and
let $(\mathfrak{F}_{t})_{t\in\mathbb{N}_{0}}$ be any filtration to which
$(\xi_{t})_{t\in\mathbb{N}_{0}}$ is adapted. Suppose that there exist
constants $b>0$, and $J,M<\infty$, such that $\xi_{0}\leqslant J$, and for all
$t$:

((3.5))
$\displaystyle\mathsf{E}\bigl{[}\xi_{t+1}-\xi_{t}\big{|}\mathfrak{F}_{t}\bigr{]}\leqslant-b\quad\text{on
the event }\\{\xi_{t}>J\\},\quad\text{and}$ ((3.6))
$\displaystyle\mathsf{E}\bigl{[}\left\lvert{\xi_{t+1}-\xi_{t}}\right\rvert^{4}\big{|}\xi_{0},\ldots,\xi_{t}\bigr{]}\leqslant
M.$

Then there exists a constant $c=c(b,J,M)>0$ such that
$\displaystyle{\sup_{t\in\mathbb{N}_{0}}\mathsf{E}\bigl{[}\xi_{t}^{2}\bigr{]}\leqslant
c}$.

######  (3.7) Lemma.

Consider the system ((3.2)), and define $\xi_{t}\coloneqq\left\lVert
x_{t}\right\rVert$, $t\in\mathbb{N}_{0}$. There exists a constant $b>0$, such
that for any $r>C_{1}$ condition ((3.5)) holds in closed-loop with the control
$u_{t}=-\operatorname{sat}_{r}(x_{t})$.

###### Proof.

Fix $t\in\mathbb{N}_{0}$ and $r>C_{1}$. We have

$\displaystyle\mathsf{E}\bigl{[}\xi_{t+1}-\xi_{t}\big{|}\mathfrak{F}_{t}\bigr{]}$
$\displaystyle=\mathsf{E}\bigl{[}\left\lVert x_{t+1}\right\rVert-\left\lVert
x_{t}\right\rVert\big{|}\mathfrak{F}_{t}\bigr{]}=\mathsf{E}\bigl{[}\bigl{\|}x_{t}+u_{t}+w_{t}\bigr{\|}-\left\lVert
x_{t}\right\rVert\big{|}\mathfrak{F}_{t}\bigr{]}$
$\displaystyle=\mathsf{E}\bigl{[}\left\lVert
x_{t}-\operatorname{sat}_{r}(x_{t})+w_{t}\right\rVert-\left\lVert
x_{t}\right\rVert\big{|}\mathfrak{F}_{t}\bigr{]}$
$\displaystyle\leqslant\mathsf{E}\bigl{[}\left\lVert
x_{t}-\operatorname{sat}_{r}(x_{t})\right\rVert+\left\lVert
w_{t}\right\rVert-\left\lVert
x_{t}\right\rVert\big{|}\mathfrak{F}_{t}\bigr{]}.$

Let $J=r$ and $b\coloneqq r-C_{1}$. On the set $\\{\left\lVert
x_{t}\right\rVert>J\\}$ we have $\left\lVert
x_{t}-\operatorname{sat}_{r}(x_{t})\right\rVert-\left\lVert
x_{t}\right\rVert=-r$. From the above we get, on the set $\\{\left\lVert
x_{t}\right\rVert>J\\}$,

$\displaystyle\mathsf{E}\bigl{[}\xi_{t+1}-\xi_{t}\big{|}\mathfrak{F}_{t}\bigr{]}$
$\displaystyle\leqslant\mathsf{E}\bigl{[}\left\lVert
x_{t}-\operatorname{sat}_{r}(x_{t})\right\rVert+\left\lVert
w_{t}\right\rVert-\left\lVert
x_{t}\right\rVert\big{|}\mathfrak{F}_{t}\bigr{]}$
$\displaystyle=-r+\mathsf{E}\bigl{[}\left\lVert w_{t}\right\rVert\bigr{]}$
$\displaystyle\leqslant-b,$

where $b$ is positive by our hypothesis. The assertion follows. ∎

######  (3.8) Lemma.

Consider the system ((3.2)) and define $\xi_{t}\coloneqq\left\lVert
x_{t}\right\rVert$, $t\in\mathbb{N}_{0}$. Then for the closed-loop system with
$u_{t}=-\operatorname{sat}_{r}(x_{t})$ there exists a constant $M=M(C_{4})>0$
such that ((3.6)) holds.

###### Proof.

Fix $r>C_{1}$. Applying the triangle inequality successively, we have

$\left\lvert{\xi_{t+1}-\xi_{t}}\right\rvert^{4}=\left\lvert{\left\lVert
x_{t+1}\right\rVert-\left\lVert
x_{t}\right\rVert}\right\rvert^{4}\leqslant\left\lVert
x_{t+1}-x_{t}\right\rVert^{4}=\left\lVert
u_{t}+w_{t}\right\rVert^{4}\leqslant\bigl{(}r+\left\lVert
w_{t}\right\rVert\bigr{)}^{4},$

which leads to

$\mathsf{E}\bigl{[}\left\lvert{\xi_{t+1}-\xi_{t}}\right\rvert^{4}\,\big{|}\,\xi_{0},\ldots,\xi_{t}\bigr{]}\leqslant\mathsf{E}\bigl{[}\bigl{(}r+\left\lVert
w_{t}\right\rVert\bigr{)}^{4}\big{|}\xi_{0},\ldots,\xi_{t}\bigr{]}=\mathsf{E}\bigl{[}\bigl{(}r+\left\lVert
w_{t}\right\rVert\bigr{)}^{4}\bigr{]}.$

Since the fourth moment of $w_{t}$ is uniformly bounded, expanding the right-
hand side above and applying Jensen’s inequality shows that there exists some
$M=M(C_{4})>0$ such that $\mathsf{E}\bigl{[}\bigl{(}r+\left\lVert
w_{t}\right\rVert\bigr{)}^{4}\bigr{]}\leqslant M$. The assertion follows. ∎

######  (3.9) Proposition.

For $r>0$ consider the system ((3.2)) under the deterministic stationary
feedback policy $u_{t}=-\operatorname{sat}_{r}(x_{t})$:

((3.10)) $x_{t+1}=x_{t}-\operatorname{sat}_{r}(x_{t})+w_{t},\qquad
x_{0}=x,\quad t\in\mathbb{N}_{0}.$

Then for every $r>C_{1}$ the system ((3.10)) satisfies
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x}\bigl{[}\left\lVert
x_{t}\right\rVert^{2}\bigr{]}\leqslant c$ for some $c=c(x,C_{1})<\infty$.

###### Proof.

Let $r=C_{1}+b$ for some $b>0$ and $J\coloneqq\max\bigl{\\{}r,\left\lVert
x\right\rVert\bigr{\\}}$. Lemma (3.7) guarantees that ((3.5)) holds, and Lemma
(3.8) shows that there exists an $M>0$ such that ((3.6)) holds. The assertion
now is an immediate consequence of Proposition (3.4). ∎

###  3.3. The case of $A$ orthogonal

Next we establish part (P1) of the main theorem in the particular case of $A$
being orthogonal.

######  (3.11) Lemma.

Consider the system $y_{t+1}=Ay_{t}+u_{t}+w_{t}$, where $y_{t}$ and $u_{t}$
take values in $\mathbb{R}^{d}$, $A$ is orthogonal, and
$(w_{t})_{t\in\mathbb{N}_{0}}$ satisfies Assumption (3.3). There exist a
constant $r>0$ and a deterministic stationary policy $\pi=(f,f,\cdots)$ such
that $\left\lVert f(y)\right\rVert\leqslant r$ for all $y\in\mathbb{R}^{d}$
and $t\in\mathbb{N}_{0}$, and the closed-loop system

((3.12)) $y_{t+1}=Ay_{t}+f(y_{t})+w_{t}$

under this policy satisfies
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x}\bigl{[}\left\lVert
y_{t}\right\rVert^{2}\bigr{]}<\infty$.

###### Proof.

Consider the process $(z_{t})_{t\in\mathbb{N}_{0}}$ defined by
$z_{t}\coloneqq(A^{\scriptscriptstyle{\mathrm{T}}})^{t}\ y_{t}$. The second
moment of $z_{t}$ is the same as that of $y_{t}$ due to orthogonality of $A$:

$\mathsf{E}_{x}\bigl{[}\left\lVert
z_{t}\right\rVert^{2}\bigr{]}=\mathsf{E}_{x}\bigl{[}\left\lVert(A^{\scriptscriptstyle{\mathrm{T}}})^{t}\
y_{t}\right\rVert^{2}\bigr{]}=\mathsf{E}_{x}\bigl{[}y_{t}^{\scriptscriptstyle{\mathrm{T}}}A^{t}(A^{\scriptscriptstyle{\mathrm{T}}})^{t}y_{t}\bigr{]}=\mathsf{E}_{x}\bigl{[}y_{t}^{\scriptscriptstyle{\mathrm{T}}}y_{t}\bigr{]}=\mathsf{E}_{x}\bigl{[}\left\lVert
y_{t}\right\rVert^{2}\bigr{]}.$

Now we have

((3.13)) $\begin{split}z_{t+1}&=(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
y_{t+1}=(A^{\scriptscriptstyle{\mathrm{T}}})^{t}\
y_{t}+(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
u_{t}+(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
w_{t}=z_{t}+\bar{u}_{t}+\bar{w}_{t},\end{split}$

where the mapping
$u_{t}\longmapsto\bar{u}_{t}\coloneqq(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
u_{t}$ is isometric and invertible, and $(\bar{w}_{t})_{t\in\mathbb{N}_{0}}$
defined by $\bar{w}_{t}\coloneqq(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
w_{t}$, is a sequence of zero-mean, independent (although in general not
identically distributed) random vectors, with fourth moment given by
$\mathsf{E}\bigl{[}\left\lVert\bar{w}_{t}\right\rVert^{4}\bigr{]}=\mathsf{E}\bigl{[}\bigl{\|}(A^{\scriptscriptstyle{\mathrm{T}}})^{t+1}\
w_{t}\bigr{\|}^{4}\bigr{]}=\mathsf{E}\bigl{[}\left\lVert
w_{t}\right\rVert^{4}\bigr{]}\leqslant C_{4}.$ Due to Proposition (3.9), there
exists a constant $r$ such that the closed-loop system ((3.13)) under the
policy $\bar{u}_{t}=-\operatorname{sat}_{r}(z_{t})\eqqcolon\bar{f}(z_{t})$ has
bounded second moment. Consequently, the original system ((3.12)) has bounded
second moment under the policy

$u_{t}=A^{t+1}\bar{u}_{t}=A^{t+1}\bar{f}(z_{t})=-A^{t+1}\operatorname{sat}_{r}\left((A^{\scriptscriptstyle{\mathrm{T}}})^{t}\
y_{t}\right)\eqqcolon f_{t}(y_{t}).$

Noting that for any orthogonal matrix $A$ we have
$\operatorname{sat}_{r}(Ay)=A\operatorname{sat}_{r}(y)$, we arrive at
$u_{t}=f_{t}(y_{t})=-A\operatorname{sat}_{r}(y_{t})\eqqcolon f(y_{t}),$ which
is indeed a stationary feedback. Moreover, since $\left\lVert
A\operatorname{sat}_{r}(y_{t})\right\rVert\leq r$, we have $\left\lVert
f(y_{t})\right\rVert\leq r$. ∎

In the following we will consider a nonstationary policy obtained by
successive concatenations of a $k$-length policy $(f_{0},f_{1},\cdots
f_{k-1})$ acting on the “sub-sampled” process $(x_{nk})_{n\in\mathbb{N}_{0}}$.
More precisely, our policy has the form $u_{t}=Bf_{t\ {\bf mod}\ k}(x_{(t\div
k)k})$ where the “$\div$” symbol denotes integer division and “${\bf mod}$”
its remainder. In words, we break the time line into segments of length $k$,
and within each segment we let the controls be given by $f_{0},f_{1},\cdots
f_{k-1}$, applied in this order always to the first state observed in the
segment. For example, $x_{1}=x_{0}+Bf_{0}(x_{0})+w_{0}$,
$x_{2}=x_{1}+Bf_{1}(x_{0})+w_{1}$, …, $x_{k}=x_{k-1}+Bf_{k-1}(x_{0})+w_{k-1}$,
$x_{k+1}=x_{k}+Bf_{0}(x_{k})+w_{k}$, $x_{k+2}=x_{k+1}+Bf_{1}(x_{k})+w_{k+1}$,
and so on.

######  (3.14) Lemma.

Consider the system

((3.15)) $x_{t+1}=Ax_{t}+Bu_{t}+w_{t},$

where $x_{t}$ takes values in $\mathbb{R}^{d}$, $u_{t}$ takes values in
$\mathbb{R}^{m}$, $A$ is orthogonal, the pair $(A,B)$ is reachable in $k$
steps (i.e., $\operatorname{rank}{\mathcal{R}}_{k}=d$, where
${\mathcal{R}}_{k}=\left[\begin{array}[]{cccc}B&AB&\cdots&A^{k-1}B\end{array}\right]$),
and $(w_{t})_{t\in\mathbb{N}_{0}}$ satisfies Assumption (3.3). Then there
exist a constant $\rho>0$ and a policy $\pi=(f_{0},f_{1},\cdots
f_{k-1},f_{0},f_{1},\cdots)$ such that $\left\lVert
f_{i}(x)\right\rVert\leq\rho$ for all $x\in\mathbb{R}^{d}$, and the closed-
loop system

((3.16)) $x_{t+1}=Ax_{t}+Bf_{t\ {\bf mod}\ k}(x_{(t\div k)k})+w_{t}$

under this policy satisfies
$\sup_{t\in\mathbb{N}_{0}}\mathsf{E}_{x}\bigl{[}\left\lVert
x_{t}\right\rVert^{2}\bigr{]}<\infty$.

###### Proof.

Let $\tau\in\mathbb{N}_{0}$ and consider the evolution of ((3.15)) from time
$\tau k$ to time $(\tau+1)k$:

((3.17)) $\begin{split}x_{(\tau+1)k}&=A^{k}\ x_{\tau
k}+{\mathcal{R}}_{k}\begin{bmatrix}u_{(\tau+1)k-1}\\\ \vdots\\\ u_{\tau
k}\end{bmatrix}+\sum_{i=0}^{k-1}A^{k-1-i}w_{\tau k+i}=\bar{A}x_{\tau
k}+\bar{u}_{\tau}+\tilde{w}_{\tau},\end{split}$

where $\tilde{w}_{\tau}\coloneqq\sum_{i=0}^{k-1}A^{k-1-i}w_{\tau k+i}$ is a
random vector with mean zero and bounded fourth moment. Since
${\mathcal{R}}_{k}$ has full rank, Lemma (3.1) implies that for arbitrary
$r>0$, any $\bar{u}_{\tau}$ in ${\mathcal{B}}_{r}$ can be expressed as
$\bar{u}_{\tau}=\sum_{i=0}^{k-1}A^{k-1-i}Bu_{\tau k+i}$, where $\left\lVert
u_{\tau k+i}\right\rVert\leq r\sigma_{d}^{-1}$ and $\sigma_{d}$ is the
smallest singular value of ${\mathcal{R}}_{k}$. But from Lemma (3.11) we know
that there exists a particular $r>0$ such that, under the stationary policy
$\bar{u}_{\tau}=f(x_{\tau k})=-\bar{A}\operatorname{sat}_{r}(x_{\tau k})$, the
“sub-sampled” system ((3.17)) has bounded second moment, and
$\left\lVert\bar{u}_{\tau}\right\rVert\leq r$. Therefore, if we choose
$\rho=r\sigma_{d}^{-1}$, there exists a constant $c=c(x,C_{1},C_{4})>0$ such
that $\sup_{\tau\in\mathbb{N}_{0}}\mathsf{E}_{x}\bigl{[}\left\lVert x_{\tau
k}\right\rVert^{2}\bigr{]}\leqslant c$. It follows from the system dynamics
that for $n=0,\ldots,k-1$,

$\displaystyle\mathsf{E}_{x}\bigl{[}\left\lVert x_{\tau
k+n}\right\rVert^{2}\bigr{]}$ $\displaystyle\leqslant
2\bigl{(}c+n^{2}r^{2}\sigma_{1}(B)^{2}\bigl{)}+k\max_{n=0,\ldots,k-1}\operatorname{tr}Q_{\tau
k+n}$ $\displaystyle\leqslant
2\bigl{(}c+n^{2}r^{2}\sigma_{1}(B)^{2}\bigl{)}+k\sqrt{C_{4}},$

where the last step follows from Jensen’s inequality. Since the right-hand
side above constitutes a uniform bound, this proves the assertion. ∎

######  (3.18) Remark.

The actual policy for ((3.15)) is $\begin{bmatrix}u_{(\tau+1)k-1}\\\ \vdots\\\
u_{\tau
k}\end{bmatrix}=-{\mathcal{R}}_{k}^{+}\bar{A}\operatorname{sat}_{r}(x_{\tau
k}).$ The proof above shows that all the inputs
$u_{(\tau+1)k-1},\cdots,u_{\tau k}$ can be computed at time $\tau k$ in order
to counteract the future effect of the current state, i.e. $\bar{A}x_{\tau
k}$, and ignoring the effect of the noise for the following $k$ steps. In the
particular case when $B\in\mathbb{R}^{d\times d}$ has full rank, $m=d$, and
obviously $k=1$, the above policy is stationary, and in particular it has the
form: $u_{t}=f(x_{t})=-B^{-1}A\operatorname{sat}_{r}(x_{t}).$ Once again we
have $\left\lVert u_{t}\right\rVert\leq r\sigma_{d}^{-1}$, where this time
$\sigma_{d}$ is the smallest singular value of $B$. $\vartriangleleft$

###  3.4. Proof of Theorem (2.3)

###### Proof.

Consider the system ((2.1)), with $(A,B)$ stabilizable and
$(w_{t})_{t\in\mathbb{N}_{0}}$ with bounded fourth moment. If $A$ is Schur
stable (that is, all the eigenvalues of $A$ belong to the interior of the unit
disk), the system with zero input has bounded second moment and is
asymptotically stable, and there is nothing to prove. Otherwise, there exists
a change of base in the state-space that brings the original pair $(A,B)$ to a
new pair $\bigl{(}\tilde{A},\tilde{B}\bigr{)}$, where $\tilde{A}$ is in real
Jordan form [Horn and Johnson, 1990, p. 150]. In particular, choosing a
suitable ordering of the Jordan blocks, we can ensure that the pair
$\bigl{(}\tilde{A},\tilde{B}\bigr{)}$ has the form
$\left(\bigl{[}\begin{smallmatrix}A_{11}&0\\\
0&A_{22}\end{smallmatrix}\bigr{]},\bigl{[}\begin{smallmatrix}B_{1}\\\
B_{2}\end{smallmatrix}\bigr{]}\right)$, where $A_{11}$ is Schur stable, and
$A_{22}$ has its eigenvalues on the unit circle. Due to the stability
hypothesis (the algebraic and geometric multiplicities of the eigenvalues of
$A_{22}$ are equal), $A_{22}$ is therefore block-diagonal with elements on the
diagonal being either $\pm 1$ or $2\times 2$ rotation matrices. As a
consequence, $A_{22}$ is orthogonal. Moreover, since $(A,B)$ is stabilizable,
the pair $(A_{22},B_{2})$ must be reachable in a number of steps $k\leq d$
which depends on the dimension of $A_{22}$ and the structure of
$(A_{22},B_{2})$, since it contains precisely the modes of $A$ which are not
asymptotically stable. Summing up, we can reduce the original system
$x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$ to the form
$\Bigl{[}\begin{smallmatrix}x^{(1)}_{t+1}\\\
x^{(2)}_{t+1}\end{smallmatrix}\Bigr{]}=\Bigl{[}\begin{smallmatrix}A_{11}x^{(1)}_{t}\\\
A_{22}x^{(2)}_{t}\end{smallmatrix}\Bigr{]}+\Bigl{[}\begin{smallmatrix}B_{1}\\\
B_{2}\end{smallmatrix}\Bigr{]}u_{t}+\Bigl{[}\begin{smallmatrix}w^{(1)}_{t}\\\
w^{(2)}_{t}\end{smallmatrix}\Bigr{]},$ where $A_{11}$ is Schur stable,
$A_{22}$ is orthogonal, $(A_{22},B_{2})$ is reachable, and
$\Bigl{(}\Bigl{[}\begin{smallmatrix}w^{(1)}_{t}\\\
w^{(2)}_{t}\end{smallmatrix}\Bigr{]}\Bigr{)}_{t\in\mathbb{N}_{0}}$ is derived
from $(w_{t})_{t\in\mathbb{N}_{0}}$ by means of linear transformations. We
know that since $A_{11}$ is Schur stable, the noise
$\bigl{(}w^{(1)}_{t}\bigr{)}_{t\in\mathbb{N}_{0}}$ has bounded second moment,
and the control inputs $(u_{t})_{t\in\mathbb{N}_{0}}$ are bounded, then the
$x^{(1)}$ sub-system is mean-square bounded under any Markovian control
[Chatterjee et al., 2009, §4]. Therefore, if under some bounded policy the
$x^{(2)}$ sub-system is mean-square bounded, the original system will also be
mean-square bounded under the same policy. Thus, at least for the proof of
(P1), it suffices to restrict our attention to the subsystem described by the
pair $\bigl{(}A_{22},B_{2}\bigr{)}$. Suppose that this subsystem is reachable
in a certain number $k\leq d$ of steps.

The proof of (P1) coincides with the proof of Lemma (3.14), where we obtain
$\rho=r\sigma_{d}^{-1}$ for $r>C_{1}$ and $\sigma_{d}$ is the smallest
singular value of ${\mathcal{R}}_{k}$. (Here,
${\mathcal{R}}_{k}=\left[\begin{array}[]{cccc}B_{2}&A_{22}B_{2}&\cdots&A_{22}^{k-1}B_{2}\end{array}\right]$.)
As the control authority required in the claim of the theorem, we choose
precisely $R=\rho$.

To prove (P2), notice that for the closed-loop “sub-sampled” system without
noise under the policy
$u_{t}=-{\mathcal{R}}_{k}^{+}\bar{A}\operatorname{sat}_{r}\bigl{(}x_{t}^{(2)}\bigr{)}$,
where $\bar{A}=A_{22}^{k}$, it holds:

((3.19)) $x_{(\tau+1)k}^{(2)}=\bar{A}x_{\tau
k}^{(2)}-\bar{A}\operatorname{sat}_{r}\bigl{(}x_{\tau k}^{(2)}\bigr{)}.$

As long as $x_{\tau k}^{(2)}$ is outside ${\mathcal{B}}_{r}$, $\left\lVert
x_{(\tau+1)k}^{(2)}\right\rVert=\left\lVert x_{\tau k}^{(2)}\right\rVert-r$.
Hence, in a finite number of steps it must hold $\left\lVert x_{\tau
k}^{(2)}\right\rVert<r$. When for some $\bar{\tau}$ we have $\left\lVert
x_{(\bar{\tau}-1)k}^{(2)}\right\rVert<r$, by the definition of
$\operatorname{sat}_{r}(\cdot)$ we have $x_{\bar{\tau}k}^{(2)}=0$, and
consequently $x_{\tau k}^{(2)}=0$ for all $\tau\geq\bar{\tau}$. Hence, the
state of the closed-loop “sub-sampled” system converges to zero in finite time
for any initial condition. Then, according to the chosen policy, for all
$\tau\geq\bar{\tau}$ we have $\begin{bmatrix}u_{(\tau+1)k-1}\\\ \vdots\\\
u_{\tau k}\end{bmatrix}=-{\mathcal{R}}_{k}^{+}\bar{A}x_{\tau k}^{(2)}=0$ and
$\bar{u}_{\tau}={\mathcal{R}}_{k}\begin{bmatrix}u_{(\tau+1)k-1}\\\ \vdots\\\
u_{\tau k}\end{bmatrix}=0,$ and consequently, for $\tau\geq\bar{\tau}$ and
$\tau k\leq t<(\tau+1)k$ we also have $x_{t}^{(2)}=0$, that is,
$x_{t}^{(2)}=0\;\;\forall\,t\geq\bar{\tau}k$, which proves (P2) for the
subsystem $\bigl{(}A_{22},B_{2}\bigr{)}$ of our system ((2.1)).

Finally, to extend the result (P2) to the general case (where $A=\mathop{\rm
diag}(A_{11},A_{22})$), it suffices to note that, since for $t\geq\bar{\tau}k$
it also holds $u_{t}=0$, from the time $\bar{\tau}k$ onwards the subsystem
$(A_{11},B_{1})$ is in open loop. Since we imposed $A_{11}$ to be Schur
stable, the state $x^{(1)}_{t}$ of the latter converges to zero as
$t\rightarrow\infty$. This proves the theorem. ∎

##  4\. Numerical Example

An example follows, which shows that our nonlinear policy is readily
computable, and effective in bounding the state of a stable linear system in
the mean square. We executed $1000$ runs of simulation of the system
$x_{t+1}=Ax_{t}+Bu_{t}+w_{t}$, where
$A=\left[\begin{smallmatrix}\cos{\varphi_{1}}&-\sin{\varphi_{1}}&0&0\\\
\sin{\varphi_{1}}&\cos{\varphi_{1}}&0&0\\\ 0&0&0.5&0\\\
0&0&0&0.9\end{smallmatrix}\right]$, $B=\left[\begin{smallmatrix}1\\\ 0\\\ 0\\\
0\end{smallmatrix}\right]$, with $\varphi_{1}=0.8$,
$x_{0}=\left[\begin{array}[]{cccc}10&20&30&40\end{array}\right]^{\top}$, and
where $w_{t}$ is a Gaussian white noise with variance $I_{4}$. This system is
marginally stable and, as is easily seen, the $2$-dimensional subsystem with
eigenvalues on the unit circle is reachable in $2$ steps, whereas the
$2$-dimensional Schur-stable subsystem is not reachable at all. The control
authority $R$ was chosen approximately equal to $3.6$ according to a rough
estimate of $C_{1}=\mathsf{E}_{x}\bigl{[}\left\lVert
w_{t}\right\rVert\bigr{]}$. It should be noticed that smaller values of $R$
are also sufficient to stabilize the system.

Figure 4.1. Empirical average of $||x_{t}||^{2}$ over $1000$ runs.

Figure 4.1 shows the empirical average of $||x_{t}||^{2}$ over the $1000$
runs, respectively with disabled control, with the chosen control authority,
and with one tenth of the chosen control authority.

##  5\. A Conjecture

We conjecture that if the noise has bounded variance, then _given any
arbitrary positive uniform upper-bound_ on the norm of the control, there
exists a _stationary feedback policy_ such that the closed-loop system is
mean-square bounded. It appears to us that a proof of this conjecture will
require substantially new and nontrivial techniques.

## References

  * [1]
  * Bao et al. [2000] Bao, X., Lin, Z. and Sontag, E. D. [2000], ‘Finite gain stabilization of discrete-time linear systems subject to actuator saturation’, Automatica 36(2), 269–277.
  * Bertsekas [2000] Bertsekas, D. P. [2000], Dynamic Programming and Optimal Control, Vol. 1, 2 edn, Athena Scientific.
  * Chatterjee et al. [2009] Chatterjee, D., Hokayem, P. and Lygeros, J. [2009], ‘Stochastic receding horizon control with bounded control inputs—a vector-space approach’, IEEE Transactions on Automatic Control .  Under review. http://arxiv.org/abs/0903.5444.
  * Chatterjee and Pal [2008] Chatterjee, D. and Pal, S. [2008], ‘An excursion-theoretic approach to stability of stochastic hybrid systems’, http://arxiv.org/abs/0901.2269.
  * Chitour and Lin [2003] Chitour, Y. and Lin, Z. [2003], ‘Finite gain $l_{p}$ stabilization of discrete-time systems subject to actuator saturation: The case of $p=1$’, IEEE Transactions on Automatic Control 48(12), 2196–2198.
  * Foss and Konstantopoulos [2004] Foss, S. and Konstantopoulos, T. [2004], ‘An overview of some stochastic stability methods’, Journal of Operations Research Society of Japan 47(4), 275–303.
  * Hernández-Lerma and Lasserre [1996] Hernández-Lerma, O. and Lasserre, J. B. [1996], Discrete-Time Markov Control Processes: Basic Optimality Criteria, Vol. 30 of Applications of Mathematics, Springer-Verlag, New York.
  * Hokayem et al. [2009] Hokayem, P., Chatterjee, D. and Lygeros, J. [2009], On stochastic receding horizon control with bounded control inputs, in ‘IEEE Conference on Decision and Control and Chinese Control Conference’, Shanghai, China.  http://arxiv.org/abs/0902.3944.
  * Horn and Johnson [1990] Horn, R. A. and Johnson, C. R. [1990], Matrix Analysis, Cambridge University Press, Cambridge.
  * Lin et al. [1996] Lin, Z., Saberi, A. and Stoorvogel, A. A. [1996], ‘Semi-global stabilization of linear discrete-time systems subject to input saturation via linear feedback—an ARE-based approach’, IEEE Transactions on Automatic Control 41(8), 1203–1207.
  * Meyn and Tweedie [1993] Meyn, S. P. and Tweedie, R. L. [1993], Markov Chains and Stochastic Stability, Springer-Verlag, London.
  * Pemantle and Rosenthal [1999] Pemantle, R. and Rosenthal, J. S. [1999], ‘Moment conditions for a sequence with negative drift to be uniformly bounded in $L^{r}$’, Stochastic Processes and their Applications 82(1), 143–155.
  * Stoorvogel et al. [2007] Stoorvogel, A. A., Saberi, A. and Weiland, S. [2007], On external semi-global stochastic stabilization of linear systems with input saturation, in ‘American Control Conference’, pp. 5845–5850.
  * Sussmann et al. [1994] Sussmann, H. J., Sontag, E. D. and Yang, Y. [1994], ‘A general result on the stabilization of linear systems using bounded controls’, IEEE Transactions on Automatic Control 39(12), 2411–2425.
  * Yang et al. [1997] Yang, Y., Sontag, E. D. and Sussmann, H. J. [1997], ‘Global stabilization of linear discrete-time systems with bounded feedback’, Systems & Control Letters 30(5), 273–281.
  * Yang et al. [1992] Yang, Y., Sussmann, H. J. and Sontag, E. D. [1992], Stabilization of linear systems with bounded controls, in M. Fliess, ed., ‘Proceedings of the Nonlinear Control Systems Design Symposium’, IFAC Publications, pp. 15–20.


11institutetext: Indian Institute of Science Education and Research (IISER)
Pune 22institutetext: Indian Institute of Technology (IIT) Madras
22email<EMAIL_ADDRESS>
22email<EMAIL_ADDRESS>
# The Connected Domination Number of Grids ††thanks: This research was
supported by the first author’s INSPIRE fellowship from Department of Science
and Technology (DST), Govt. of India

Adarsh Srinivasan 11 0000-0003-0288-4818 N S Narayanaswamy 22
0000-0002-8771-3921

###### Abstract

Closed form expressions for the domination number of an $n\times m$ grid have
attracted significant attention, and an exact expression has been obtained in
2011 [7]. In this paper, we present our results on obtaining new lower bounds
on the connected domination number of an $n\times m$ grid. The problem has
been solved for grids with up to $4$ rows and with $6$ rows and the best
currently known lower bound for arbitrary $m,n$ is
$\left\lceil\frac{mn}{3}\right\rceil$ [11]. Fujie [4] came up with a general
construction for a connected dominating set of an $n\times m$ grid. In this
paper, we investigate whether this construction is indeed optimum. We prove a
new lower bound of
$\left\lceil\frac{mn+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil}{3}\right\rceil$
for arbitrary $m,n\geq 4$.

###### Keywords:

Connected Dominating Set Maximum Leaf Spanning Tree Grid Graph Connected
Domination Number

##  1 Introduction

In this paper, we study the Minimum Connected Dominating Set (Min-CDS) problem
in grid graphs. Given a connected graph $G=(V,E)$, a _connected dominating
set_ (CDS) is a subset $S$ of $V$ which induces a connected subgraph in $G$
such that every vertex of $G$ is either in $S$ or adjacent to a vertex in $S$.
The Min-CDS problem asks for a CDS of minimum size. This is a well studied
problem in combinatorial optimisation. The _connected domination number_ of
$G$ is the minimum size of a connected dominating set of $G$. This problem is
equivalent to the Maximum Leaf Spanning Tree (MLST) problem, which is the
problem of finding a spanning tree of $G$ with maximum number of leaves. A
graph has a spanning tree with $k$ leaves if and only if it has a connected
dominating set of size $|V|-k$. These problems are known to be NP-complete [6,
ND2, Appendix 2], and have been widely studied and have applications in areas
such as networking, circuit layout, etc (See [15] for example). A common theme
in the study of any NP-complete problem is to consider the problem in special
classes of inputs with more structure than the general case and try to
understand whether the problem remains NP-complete or admits a polynomial time
solution. Min-CDS is known to be NP-complete when it is restricted to planar
bipartite graphs of maximum degree $4$ [9]. It is also known to be NP-complete
for unit disk graphs [10] and subgraphs of grid graphs [2, Theorem 6.1]. When
viewed in terms of approximation algorithms, the minimum connected dominating
set and maximum leaf spanning tree problems are not equivalent. The MLST
problem is MAX-SNP-hard which makes a Polynomial Time Approximation Scheme
(PTAS) unlikely [5], but linear time $3$-approximation algorithms [12] and
$2$-approximation algorithms [13] exist. A PTAS exists for the Min-CDS problem
on unit disk graphs [3, 8]. The complexity of this problem for complete grid
graphs remains unknown.

By comparison, the computation of the domination number of an $n\times m$ grid
graph is a well studied problem. Chang [1] devoted their PhD thesis to
calculating the domination number of grids and Gonçalves et al [7] solved this
problem in 2011 by proving it to be
$\left\lfloor\frac{(n+2)(m+2)}{5}\right\rfloor-4$ for $16\leq m\leq n$. Hence
it is natural to ask the following questions about the connected domination
number of grid graphs:

  * •

Can we come up with a closed form expression for the connected domination
number of an $n\times m$ grid?

  * •

Can we design an algorithm that takes $n,m$ as input, with run-time polynomial
in $n,m$ that outputs the domination number of an $n\times m$ grid?

An answer for the first question would imply an answer for the second one, but
not vice versa. A partial answer can be obtained by showing lower and upper
bounds on the connected domination number. Upper bounds can be obtained using
constructions or heuristic algorithms. Fujie [4] came up with a general
construction of a spanning tree of a grid with a large number of leaves which
leads to an upper bound on the connected domination number. Li and Tolouse
[11] determined the optimum maximum leaf spanning tree for grid graphs with up
to 4 rows and with 6 rows. The only known general lower bound is
$\left\lceil\frac{mn}{3}\right\rceil$. This was obtained by Li and Tolouse
using an easy counting argument and by Fujie using a mathematical programming
approach.

In this paper, we come up with improved lower bounds on the connected
domination number of a grid. We show a lower bound of
$\left\lceil\frac{mn+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil}{3}\right\rceil$
for arbitrary $m,n\geq 4$ (Theorem 2.3). To our knowledge, this is the first
non-trivial result of this kind. Our proof also leads to some insight on the
structure of the optimum connected dominating set of a grid.

###  1.1 Preliminaries and Terminology

We first introduce the definitions and notations that we will use in the rest
of the paper. For all definitions and notations not defined here, we refer to
[14]. Let $G=(V,E)$ be a connected graph. A leaf refers to a vertex of degree
$1$ in $G$. The open neighbourhood of a subset $S$ of $V$ in $G$ is defined to
be the set of all vertices adjacent to a vertex in $S$ which are not in $S$
and denoted by $N_{G}(S)$. The closed neighbourhood of $S$ in $G$, $N_{G}[S]$
is defined to be $N_{G}(S)\cup S$. $G[S]$ denotes the subgraph of $G$ induced
by $S$. A set $S$ is called a connected dominating set of $G$ if $N_{G}[S]=V$
and $G[S]$ is a connected subgraph of $G$. The size of the minimum connected
dominating set of $G$ is called its connected domination number and is denoted
by $\gamma_{c}(G)$. The maximum leaf number of $G$ is the number of leaves in
the maximum leaf spanning tree of $G$. The connected domination number and the
maximum leaf number add up to $|V|$. A connected dominating set of $G$ can be
obtained by deleting the leaves of a spanning tree of $G$.

The notation $[i]$ denotes the set $\\{1,2,\dots,i\\}$. The $n\times m$ grid
graph $G_{n,m}$ is the graph with the vertex set $[n]\times[m]$ with two
vertices $(i_{1},j_{1})$ and $(i_{2},j_{2})$ being adjacent if and only if
$|i_{i}-i_{2}|+|j_{1}-j_{2}|=1$. It can also be defined as a unit disk graph
in which the disks have the integer points mentioned as centers and radius
$1/2$. For the reminder of the paper, we just use $G$ instead of $G_{n,m}$
without any ambiguity. We assume whenever necessary that $G$ is embedded in a
larger grid graph. Specifically, we embed $G$ in $G^{\prime}$ which is a grid
graph with two additional rows and columns. The vertex set of $G^{\prime}$ is
$\\{0,1,\dots,n+1\\}\times\\{0,1,\dots,m+1\\}$ with the same incidence
relation as $G$.

$S$ is a connected dominating set of $G$. $l$ is the number of leaves in the
graph $G[S]$. It has no relation to the number of leaves in the corresponding
spanning tree of $G$. For any $v\in G$ we define the _loss function_ of that
vertex to be $\ell(v)=|N[v]\cap S|-1$. The loss function of the set $S$ is
defined to be $\ell(S)=\sum_{v\in N_{G^{\prime}}[S]}\ell(v)$. The _boundary_
of $G_{n,m}$ is defined to be the set of points in $G_{n,m}$ which have three
neighbours or less in $G_{n,m}$ (excluding the points themselves). The _excess
function_ $e(S)$ is defined to be the number of points in $S$ present in the
boundary of $G$. These definitions are inspired by similar definitions in [7].

##  2 Bounds on the connected domination number

###  2.1 Known upper bounds

Upper bounds for $\gamma_{c}(G)$ can be easily obtained by constructing
spanning trees for $G$ with a large number of leaves, which leads to an upper
bound for the maximum leaf number of $G$, and a corresponding lower bound on
the connected domination number. Fujie gave a construction of a spanning tree
with a large number of leaves [4, Lemma 2]. We reproduce their construction
here:

Let $D_{1}$ be a CDS of $G_{n,m}$ with the following vertices-

$\displaystyle(1,2),(2,2),\dots,(n,2)$
$\displaystyle(1,m-1),(2,m-1),\dots(n,m-1)$
$\displaystyle(2,3),(2,4),\dots,(2,m-2)$ $\displaystyle(i,3k+2)\text{ for
}i=3,4,\dots,n,k=1,2,\dots,\left\lfloor\frac{m-4}{3}\right\rfloor$

Let $D_{2}$ be a CDS with the following vertices-

$\displaystyle(2,1),(2,2),\dots,(2,m)$
$\displaystyle(n-1,1),(n-1,2),\dots(n-1,m)$
$\displaystyle(3,2),(4,2),\dots,(m-2,2)$ $\displaystyle(3k+2,i)\text{ for
}k=1,2,\dots,\left\lfloor\frac{n-4}{3}\right\rfloor,i=3,4,\dots,m$

Hence, we have the following upper bound on $\gamma_{c}(G)$:

$\gamma_{c}(G)\leq\min\left\\{2n+(m-4)+\left\lfloor\frac{m-4}{3}\right\rfloor(n-2),2m+(n-4)+\left\lfloor\frac{n-4}{3}\right\rfloor(m-2)\right\\}$
(1)

Fig. 1 describes an example for the constructions for the graph $G_{7,11}$.

Figure 1: $D_{1}$ and $D_{2}$ for $G_{7,11}$ (Black vertices present in CDS)

###  2.2 New lower bounds

Proving lower bounds would require combinatorial arguments, which will be the
main contribution of this paper. In [7] the authors introduced a combinatorial
parameter called the loss function to prove lower bounds on the domination
number of a grid. The loss and excess functions which we have defined are
inspired by that definition. Using these parameters, we prove a sequence of
lower bounds on $|S|$, each an improvement on the previous one, culminating in
theorem 2.3.

Our approach is to obtain lower bounds in $\ell(S)$ and $e(S)$ parametrized by
$l$ and then combine them to obtain absolute lower bounds on $\ell(S)+e(S)$.
This will, in turn lead to lower bounds on $|S|$.

$G[S]$ can be divided into a number of horizontal and vertical line segments,
with each vertical line segment connected to at least one horizontal line
segment and vice versa as the graph is connected. The vertices, called _joins_
where a horizontal line segment meets a vertical line segment can be of degree
$2$, $3$ or $4$. When the join is of degree $2$, we refer to the horizontal
line segment and vertical line segment that meet at the vertex as a _bend_.

Let $d_{3}$ and $d_{4}$ be the number of vertices in $G[S]$ with degree $3$
and $4$ respectively and $d_{2}$ be the number of bends. Note that here
$d_{2}$ counts only those degree $2$ vertices which form a bend. We make the
following observation on the number of leaves in $G[S]$:

###### Lemma 1

For any CDS $S$ of $G$: $l\leq d_{3}+2d_{4}+2$

###### Proof

The well known handshake lemma states that for a graph $G=(V,E)$ $\sum_{v\in
V}\delta(v)=2|E|$. We apply this for $G[S]$. The number of vertices of degree
$2$ is $|S|-d_{3}-d_{4}-l$ and as $G[S]$ is connected, the number of edges in
$G[S]$ is at least $|S|-1$.

$\displaystyle 3d_{3}+4d_{4}+2(|S|-d_{3}-d_{4}-l)+l=2|E|\geq 2(|S|-1)$
$\displaystyle\implies l\leq d_{3}+2d_{4}+2$

∎

We now relate the parameters $\ell(S)$ and $e(S)$ to the size of a connected
dominating set:

###### Lemma 2

For any $m,n\geq 3$, $G_{n,m}$ has a minimum CDS that does not contain any
corner of $G_{n,m}$

###### Proof

Consider a CDS $S$ of $G_{n,m}$ which contains the corner point $(1,1)$. As
$G[S]$ is a connected subgraph, $S$ must contain either $(1,2)$ or $(2,1)$.
There exists a maximal horizontal or vertical line segment in $G[S]$
containing $(1,1)$. Assume $G[S]$ contains the path $(1,1),(1,2),\dots,(1,k)$
As $G[S]$ is connected, one of these points must contain a neighbour in $S$.
Let $(1,i)$ be the first such point with a neighbour $(2,i)$. Now, for all
$j<i$, we replace $(1,j)$ in $S$ with $(2,j)$ to obtain a new CDS of $G$ with
the same number of points. As $n,m\geq 4$, $(2,1)$ which replaces $(1,1)$ is
not a corner point. We perform a similar procedure with the path
$(1,1),(2,1),\dots,(k,1)$ if $S$ does not contain the point $(1,2)$, and
repeat this for all four corner points of $G$ to obtain a new CDS for
$G_{n,m}$ with the same number of points as $S$. ∎

###### Lemma 3

For a CDS $S$ of $G$: $nm=5|S|-\ell(S)-e(S)$

###### Proof

For a set $S$ which dominates $G$, consider the set $N_{G^{\prime}}[S]$, which
is its closed neighbourhood in $G^{\prime}$. Any point in $S$ dominates $5$
points including itself, and for each $v\in N_{G^{\prime}}[S]$, the number of
points which dominate $v$ is $1+\ell(v)$. Hence,
$|N_{G^{\prime}}[S]|=5|S|-\ell(S)$.

As no point in $S$ is a corner point of $G$ (see previous lemma), every point
in the boundary of $G$ dominates exactly one point in $G^{\prime}$ outside
$G$. Thus the number of points in $N_{G^{\prime}}[S]$ outside $G$ is $e(S)$.
Hence, $mn=|N_{G^{\prime}}[S]|-e(S)$ and this proves the lemma.∎

PQR

PQRST

P

Figure 2: The three different types of joins

###### Lemma 4

$\ell(S)\geq 2|S|-l+d_{2}+3d_{3}+6d_{4}$ and $e(S)\geq 4$ if $m,n\geq 4$

###### Proof

Consider the four corners of the grid, the points $(1,1),(n,1),(1,m)$ and
$(n,m)$. These points have to be dominated by a point in $S$, and all their
neighbours in $G$ are in the boundary of $G$. As both $n$ and $m$ are greater
than or equal to $4$, two corner points cannot be dominated by the same point
in $S$, and hence $e(S)\geq 4$.

For any point $v$ in $S$ which is not a leaf in $G[S]$, $\ell(v)\geq 2$. This
is because it has at least $2$ neighbours in $S$. If $v$ is a leaf,
$\ell(v)=1$. Hence, if $l$ is the number of leaves of $S$, $\ell(S)\geq
2|S|-l$. In addition to this, consider a vertex of degree $3$ as in Fig. 2.
The loss function of the point $P$ is at least $3$ and the loss function of
$Q$ and $R$ is at least $1$. For the vertex of degree $4$ shown, the loss
function of $P$ is at least $4$ and the loss functions of $Q,R,S$ and $T$ are
each at least $1$. For the bend shown, the loss function of the point $P$ is
at least $1$. Hence, $\ell(S)\geq 2|S|-l+d_{2}+3d_{3}+6d_{4}$. ∎

Putting these observations together, we get our first bound on $e(S)+\ell(S)$:

######  Lemma 5 (Parametrized bound 1)

Consider any CDS $S$ for $G$, with $G[S]$ having $l$ leaves. Then
$\ell(S)+e(S)\geq 2|S|+2l-2$.

###### Proof

This follows from the fact that $\ell(S)+e(S)\geq 2|S|-l+3d_{3}+6d_{4}+4$
(lemma 4) and $d_{3}+2d_{4}\geq l-2$ (lemma 1). ∎

From this bound it is easy to derive the already known lower bound of
$\left\lceil\frac{mn}{3}\right\rceil$ for $\gamma_{c}(G)$:

######  Theorem 2.1 (Bound 1)

For any CDS $S$ of $G$:

$|S|\geq\left\lceil\frac{mn}{3}\right\rceil$

###### Proof

As $S$ must have at least $2$ leaves, $\ell(S)+e(S)\geq 2|S|+2$. We can now
use this in lemma 3:

$\displaystyle mn\leq 5|S|-2|S|-2=3|S|-2$
$\displaystyle\implies|S|\geq\left\lceil\frac{mn}{3}\right\rceil$

∎

We have not used any structural information on $G[S]$ yet. Specifically, we
have not used the fact that it might contain bends. Next, we use the fact that
the connected dominating set must contain a certain minimum number of joins to
show a new bound on $\ell(S)+e(S)$. We first prove the following simple lemma
on the structure of $G[S]$. We say that the horizontal line segments _span_
the height of the graph if the subgraph induced by their closed neighbourhood
contains a point from every row of $G$ and we say that the vertical line
segments _span_ the width of the graph if the subgraph induced by their closed
neighbourhood contains a point from every column of $G$.

###### Lemma 6

$G[S]$ either has at least $\left\lceil\frac{n}{3}\right\rceil$ horizontal
line segments which span the width of $G$ or
$\left\lceil\frac{m}{3}\right\rceil$ vertical line segments which span the
height of $G$.

###### Proof

Any horizontal line segment dominates an area that spans at most three rows.
Hence, if $S$ has less than $\left\lceil\frac{n}{3}\right\rceil$ horizontal
line segments, there exists at least one row which is not dominated by any of
the points in the horizontal line segments. The rows not dominated by
horizontal line segments must be dominated by the vertical line segments. Any
vertical line segment can dominate an area which spans at most $3$ columns and
hence there must be at least $\left\lceil\frac{m}{3}\right\rceil$ vertical
line segments in $S$. Similarly, if $S$ has less than
$\left\lceil\frac{m}{3}\right\rceil$ vertical line segments, it must have at
least $\left\lceil\frac{n}{3}\right\rceil$ horizontal line segments. ∎

We use this lemma to prove the following bound on the number of joins in
$G[S]$.

###### Lemma 7

Let $d_{2}$, $d_{3}$ and $d_{4}$ denote the number of bends, joins of degree
$3$ and joins of degree $4$ respectively.

$d_{2}+d_{3}+d_{4}\geq\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil$

###### Proof

Either the horizontal line segments dominate an area that spans the entire
height of the graph or the vertical line segments dominate an area that spans
the width of the graph. We assume the latter without loss of generality. Each
of these vertical line segments must be connected to a point in the previous
or next column in the grid. Hence, each of these must contain either a bend, a
degree $3$ join or a degree $4$ join. From the previous lemma, we know that
there are at least $\left\lceil\frac{m}{3}\right\rceil$ vertical line segments
and the result follows. ∎

We use these two lemmas to obtain two new lower bounds on $\ell(S)+e(S)$
parametrized by the number of leaves, which we can then combine to obtain an
improved lower bound for $|S|$.

######  Lemma 8 (parametrized bound 2)

Consider any CDS $S$ for $G$, with $G[S]$ having $l$ leaves. Then
$\ell(S)+e(S)\geq 2|S|+\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil+l$

###### Proof

We know that $e(S)\geq 4$ and $\ell(S)\geq 2|S|-l+3d_{3}+6d_{4}+d_{2}$, and
because $d_{2}+d_{3}+d_{4}\geq\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil$,

$\ell(S)\geq
2|S|-l+\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil+2d_{3}+5d_{4}\geq
2|S|-l+\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil+2(d_{3}+2d_{4}+2)-4$

We now use the fact that $l\leq d_{3}+2d_{4}+2$ to prove the lemma ∎

######  Lemma 9 (parametrized bound 3)

Consider any CDS $S$ for $G$, with $G[S]$ having $l$ leaves. Then
$\ell(S)+e(S)\geq 2|S|+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil+2-l$

###### Proof

We can assume without loss of generality that the vertical lines span the
width of the grid. Every vertical line must contain a join. Hence, at least
$\left\lceil\frac{m}{3}\right\rceil-d_{3}-d_{4}$ of them must have one or more
bends. A vertical line with only one bend must also contain a leaf. This
implies that the number of bends is at least
$2\left(\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-d_{3}-d_{4}\right)-l$.
We use this in our estimation of $\ell(S)$:

$\displaystyle\ell(S)\geq$ $\displaystyle 2|S|-l+d_{2}+3d_{3}+6d_{4}$
$\displaystyle\geq$ $\displaystyle
2|S|-l+3d_{3}+6d_{4}+2\left(\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-
d_{3}-d_{4}\right)-l$ $\displaystyle\geq$ $\displaystyle
2|S|+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil+d_{3}+2d_{4}+2-2l-2$
$\displaystyle\geq$ $\displaystyle
2|S|+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-l-2$

Using the fact that $e(S)\geq 4$, the result follows.∎

Combining the previous two parametrized bounds leads to the following lower
bound on $|S|$ which is an improvement over the currently known bound of
$|S|\geq\left\lceil\frac{mn}{3}\right\rceil$:

######  Theorem 2.2 (Bound 2)

For a CDS $S$ of $G$:

$|S|\geq\left\lceil\frac{mn+\left\lceil\frac{3}{2}\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil\right\rceil+1}{3}\right\rceil$

###### Proof

The lower bound in lemma 8 increases with $l$ and the bound in lemma 9
decreases with $l$. As they both lower bound $\ell(S)+e(S)$, $\ell(S)+e(S)$ is
always greater than or equal to
$2|S|+\left\lceil\frac{3}{2}\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil\right\rceil+1$.
From Lemma 3,

$mn=5|S|-\ell(S)-e(S)\geq
5|S|-\left(2|S|+\left\lceil\frac{3}{2}\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil\right\rceil+1\right)$

This means that $3|S|\geq
mn+\left\lceil\frac{3}{2}\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil\right\rceil+1$
which proves the theorem.∎

This bound can be further improved by counting the number of bends in $G[S]$
more carefully. In the proof of lemma 9, we used the fact that the number of
bends is at least $2\left(\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-
d_{3}-d_{4}\right)-l$. In the following lemma, we improve on that:

###### Lemma 10

Consider a CDS $S$ of $G$. The number of bends in $S$ is at least
$2\left(\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-l+1\right)$.

###### Proof

We first assume that $G[S]$ has no vertices of degree $4$. If it does, we can
just treat a vertex of degree $4$ as two vertices of degree $3$. Hence, the
number of vertices of degree $3$ has to be at least $l-2$. As before, we can
assume without loss of generality that the vertical lines dominate an area
that spans the width of the grid and that there are
$\left\lceil\frac{m}{3}\right\rceil$ vertical lines. Some of these lines have
one or more degree $3$ vertices and some of them have bends.

Observe that a vertical line with only one join must contain a leaf. Every
join in a vertical line must be paired with another join or be paired with a
leaf as shown in Fig. 3.

Figure 3:

Out of all the vertices of degree $3$, let $t_{1}$ be the number of vertices
not paired with a bend or a degree $3$ vertex, $t_{2}$ be the number of bend-
degree $3$ vertex pairs, and $t_{3}$ be the number of degree $3$ vertex-
degree $3$ vertex pairs. Hence, it is clear that out of the vertical lines, at
most $(l-2)-t_{3}$ contain vertices of degree $3$. Hence there are at least
$\left(\left\lceil\frac{m}{3}\right\rceil-(l-2)+t_{3}\right)$ vertical lines
without vertices of degree $3$ and these vertical lines contain at most
$l-t_{1}$ leaves. Consider such a vertical line. It can have only one bend if
and only if it has a leaf and hence there can be at most $(l-t_{1})$ of such
columns. We have already counted $t_{2}$ bends. Hence, we can bound the number
of bends:

$\displaystyle d_{2}$ $\displaystyle\geq
2\left(\left\lceil\frac{m}{3}\right\rceil-(l-2)+t_{3}-(l-t_{1})\right)+t_{2}+(l-t_{1})$
$\displaystyle=2\left\lceil\frac{m}{3}\right\rceil-3l+4+t_{1}+t_{2}+2t_{3}$

$t_{1}+t_{2}+2t_{3}\geq l-2$ as every vertex of degree $3$ belongs in at least
one of the three categories mentioned and the lemma follows. ∎

We now have the necessary material to prove the main result of our paper.

######  Theorem 2.3 (Main Theorem)

For a CDS $S$ of $G$:

$|S|\geq\left\lceil\frac{mn+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil}{3}\right\rceil$

###### Proof

$\displaystyle\ell(S)\geq$ $\displaystyle 2|S|-l+d_{2}+3d_{3}+6d_{4}$
$\displaystyle\geq$ $\displaystyle
2|S|-l+3d_{3}+6d_{4}+6+2\left(\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-l+1\right)-6$
$\displaystyle\geq$ $\displaystyle
2|S|+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil-4$

We have used the fact that $d_{3}+2d_{4}+2\geq l$. As $e(S)\geq 4$,
$\ell(S)+e(S)\geq 2|S|+2\left\lceil\frac{\min\\{m,n\\}}{3}\right\rceil$, the
theorem follows. ∎

###  2.3 Gap between lower and upper bounds

In this section, we compare the gap between the lower and upper bounds
obtained. To do that, we have to consider this case by case, for reminders $n$
and $m$ leave on division by $3$. We assume $m\leq n$. Let $L$ denote the
lower bound obtained in theorem 2.3. We let $L=\frac{mn}{3}+\frac{2m}{9}$,
omitting the ceiling functions as they would only increase $L$ by at most $2$.
Out of the two CDS’s we constructed in section 2.1, $D_{1}$ and $D_{2}$, the
upper bound is given by the construction of smaller size. If $m$ is divisible
by $3$, $|D_{1}|\leq|D_{2}|$, and the gap between the lower and upper bounds
is $\frac{m}{9}$. If $m$ is not divisible by $3$ and $n$ is however, then
$|D_{2}|\leq|D_{1}|$ and the gap is $\frac{n}{3}-\frac{2m}{9}$. Similarly, we
can analyse the other cases using Table 1 and Table 2. The new lower bound is
closest to the constructions in the case that $m$ is divisible by $3$.

$m\mod{3}$ | $|D_{1}|$ | $|D_{1}|-\frac{mn}{3}$ | $|D_{1}|-L$
---|---|---|---
$0$ | $\frac{mn}{3}+\frac{m}{3}$ | $\frac{m}{3}$ | $\frac{m}{9}$
$1$ | $\frac{mn}{3}+\frac{m}{3}+\frac{2n}{3}-\frac{4}{3}$ | $\frac{m}{3}+\frac{2n}{3}-\frac{4}{3}$ | $\frac{m}{9}+\frac{2n}{3}-\frac{4}{3}$
$2$ | $\frac{mn}{3}+\frac{m}{3}+\frac{n}{3}-\frac{2}{3}$ | $\frac{m}{3}+\frac{n}{3}-\frac{2}{3}$ | $\frac{m}{9}+\frac{n}{3}-\frac{2}{3}$
Table 1: Gaps between $|D_{1}|$ and $L$ $n\mod 3$ | $|D_{2}|$ | $|D_{2}|-\frac{mn}{3}$ | $|D_{2}|-L$
---|---|---|---
$0$ | $\frac{mn}{3}+\frac{n}{3}$ | $\frac{n}{3}$ | $\frac{n}{3}-\frac{2m}{9}$
$1$ | $\frac{mn}{3}+\frac{n}{3}+\frac{2m}{3}-\frac{4}{3}$ | $\frac{n}{3}+\frac{2m}{3}-\frac{4}{3}$ | $\frac{n}{3}+\frac{4m}{9}-\frac{4}{3}$
$2$ | $\frac{mn}{3}+\frac{m}{3}+\frac{n}{3}-\frac{2}{3}$ | $\frac{m}{3}+\frac{n}{3}-\frac{2}{3}$ | $\frac{m}{9}+\frac{n}{3}-\frac{2}{3}$
Table 2: Gaps between $|D_{2}|$ and $L$

##  3 Conclusions and further research

In this paper, we come up with improved lower bounds on the connected
domination number of a grid. The question of finding a closed form expression
however, remains open. We have broadly used the following approach to prove
lower bounds on $|S|$. Using the fact that $G$ is a grid graph, we obtained
some structural results for any connected set that dominates $G$, which lead
to lower bounds on the number of bends, vertices of degree $3$ and vertices of
degree $4$ in $G[S]$. We then used lemma 4 to get lower bounds on $|S|$. This
approach however, does not capture the full picture. Consider Fujie’s
construction detailed in section 2.1. There are no bends or vertices of degree
$4$ and the number of vertices of degree $3$ is
$\left\lceil\frac{m}{3}\right\rceil$ or $\left\lceil\frac{n}{3}\right\rceil$,
and our techniques have already accounted for this. There is still a gap
between our lower bound and this upper bound because
$e(S)=\left\lceil\frac{m}{3}\right\rceil+2$ and
$\left\lceil\frac{n}{3}\right\rceil+2$ for these constructions, while we have
used a lower bound of $4$ for $e(S)$. While this is the best possible lower
bound for $e(S)$ separately, it might be possible to obtain better lower
bounds for $\ell(S)+e(S)$ by trying to lower bound the sum of two quantities,
rather than lower bound each quantity separately as we have done.

An approach to this problem which we have not pursued here would be to design
an algorithm or an approximation algorithm that returns the size of the
minimum connected dominating set of an $n\times m$ grid in time polynomial in
$n$ and $m$. It is important to note that an approximation algorithm would
lead to an _upper bound_ on the connected domination number of the grid, while
our work has focused on lower bounds. The constructions described in section
2.1 for example, would lead to a trivial approximation algorithm. The gap
between our current lower and upper bounds is linear in $m$ and $n$, which
means that this would be asymptotically better than any
$(1+\epsilon)$-approximation algorithm (the input size is $O(mn)$). A non-
constructive approach to obtaining upper bounds, for example using the
probabilistic method could also be tried.

Our approach has been completely analytical. In [7] the authors used a
computational approach to answer the analogous questions about the domination
number of grids, using dynamic programming algorithms to calculate the minimum
value of a similar loss function near the boundary of the grid. The connected
dominating set problem is one of a more ‘global’ nature than the dominating
set problem, as it involves connectivity as a constraint. This entails a very
different set of challenges and a computational approach to the problem would
likely require new techniques.

## References

  * [1] Chang, T.: Domination Numbers of Grid Graphs. PhD Thesis, University of South Florida (1992)
  * [2] Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86(1), 165 – 177 (1990). https://doi.org/10.1016/0012-365X(90)90358-O
  * [3] Du, H., Ye, Q., Zhong, J., Wang, Y., Lee, W., Park, H.: Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks. Theoretical Computer Science 447, 38–43 (2012). https://doi.org/10.1016/j.tcs.2011.10.010
  * [4] Fujie, T.: An exact algorithm for the maximum leaf spanning tree problem. Computers & Operations Research 30(13), 1931 – 1944 (2003). https://doi.org/10.1016/S0305-0548(02)00117-X
  * [5] Galbiati, G., Maffioli, F., Morzenti, A.: A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters 52(1), 45 – 49 (1994). https://doi.org/10.1016/0020-0190(94)90139-2
  * [6] Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1979)
  * [7] Gonçalves, D., Pinlou, A., Rao, M., Thomassé, S.: The domination number of grids. SIAM Journal on Discrete Mathematics 25(3), 1443–1453 (2011). https://doi.org/10.1137/11082574
  * [8] Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation schemes for NP-and PSPACE-hard problems for geometric graphs. Journal of algorithms 26(2), 238–274 (1998). https://doi.org/10.1006/jagm.1997.0903
  * [9] Li, B.P., Toulouse, M.: Variations of the maximum leaf spanning tree problem for bipartite graphs. Information Processing Letters 97(4), 129 – 132 (2006). https://doi.org/10.1016/j.ipl.2005.10.011
  * [10] Lichtenstein, D.: Planar formulae and their uses. SIAM journal on computing 11(2), 329–343 (1982). https://doi.org/10.1137/0211025
  * [11] Lie, P., Toulouse, M.: Maximum leaf spanning tree problem for grid graphs. JCMCC. The Journal of Combinatorial Mathematics and Combinatorial Computing 73 (2010), http://www.cs.umanitoba.ca/~lipakc/gridgraph-aug6-08.pdf
  * [12] Lu, H.I., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. Journal of algorithms 29(1), 132–141 (1998). https://doi.org/10.1006/jagm.1998.0944
  * [13] Solis-Oba, R., Bonsma, P., Lowski, S.: A 2-approximation algorithm for finding a spanning tree with maximum number of leaves. Algorithmica 77(2), 374–388 (2017). https://doi.org/10.1007/s00453-015-0080-0
  * [14] West, D.B.: Introduction to Graph Theory. Prentice Hall, 2 edn. (September 2000)
  * [15] Wu, J., Li, H.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications. p. 7–14. DIALM ’99, Association for Computing Machinery, New York, NY, USA (1999). https://doi.org/10.1145/313239.313261