TITLE: Topological space, equivalent statements, net, closure, neighborhood
QUESTION [0 upvotes]: Let $(X,\tau)$ be a topological space and $V\subseteq X$. For $x\in X$ are equivalent:
I) $x\in\overline{V}$
II) For every neighborhood $U$ of $x$ is $U\cap V\neq\emptyset$.
III) It exists a net $(x_\lambda)_{\lambda\in\Lambda}$ in $V$ with $x_\lambda\to x$
I want to show, that I) $\Rightarrow$ II) $\Rightarrow$ III) $\Rightarrow$ I)
But I do not really get started... :(
ad I)$\Rightarrow$ II):
Let $U$ be a neighborhood of $x$. Since $x\in\overline{V}$ it is $x$ element of every closed set $A$ which contains $V$.
But I do not see, how I now proof, that $U\cap V\neq\emptyset$.
Can you give me a hint?
ad II)$\Rightarrow$ III)
A net $(x_\lambda)_{\lambda\in\Lambda}$ converges to $x\in V$ iff for all open $O\subseteq V$ with $x\in O$ exists $\lambda_0\in\Lambda$ such that for all $\lambda\geq\lambda_0$ is $x_\lambda\in O$.
ad III) $\Rightarrow$ I)
My problem here is, that I do not see how I get from the open sets to closed sets, so I can conclude $x\in\overline{V}$
I would like to try this again, but at the moment I need some hints.
Thanks in advance

REPLY [2 votes]: My problem here is, that I do not see how I get from the open sets to closed sets

Well, closed sets are complements of open sets and vice versa. :)

I) $\Rightarrow$ II)
Let $x\in\overline{V}$ and assume that $U$ is a neighbourhood of $x$ such that $U\cap V=\emptyset$. Then $V\subseteq X\backslash U$ and since $X\backslash U$ is closed (being a complement of an open subset) then $\overline{V}\subseteq X\backslash U$ and therefore $U\cap\overline{V}=\emptyset$. Since $x\in U$ then $x\not\in\overline{V}$. Contradiction.

II) $\Rightarrow$ III)
Let $$\Lambda=\{U\subseteq X\ |\ U\mbox{ is open and }x\in U\}$$ be ordered by reversed inclusion (i.e. $U< W$ iff $W\subsetneq U$). Obviously it's a directed set. For any $U\in\Lambda$ define $x_U$ to be any element of $U\cap V$ (by assumption this subset is nonempty). Almost by definition $(x_U)_{U\in\Lambda}$ is convergent to $x$.

III) $\Rightarrow$ I)
Let $x\in X$ and $(x_\lambda)_{\lambda\in\Lambda}$ be a net convergent to $x$ with $x_\lambda\in V$ for any $\lambda$.
It is enough to show that for any closed subset $C$ such that $V\subseteq C$ we have that $x\in C$. So assume this is not true, i.e. we have a closed subset $C$ with $V\subseteq C$ and $x\not\in C$. Let $U=X\backslash C$. By definition $U\cap V=\emptyset$. But since $(x_{\lambda})$ converges to $x$ then $x_\theta\in U$ for some $\theta\in\Lambda$. By assumption $x_\theta\in V$ and thus $U\cap V\neq\emptyset$. Contradiction.


text:
\section{Introduction}
\subsection{The problem and its context in Mathematical Physics}
In general relativity, the question of determinism reduces to the mathematical
problem of global uniqueness for solutions of the Einstein equations. This is a consequence of
the central role played by the well posedness results for the Cauchy
problem, first established in the seminal work of Choquet-Bruhat~\cite{Choquet:1952} and Choquet-Bruhat
and Geroch~\cite{Choquet:1969}.

The global uniqueness issue lies beyond the primary difficulty concerning the diffeomorphism
invariance of the equations. It can be conveniently framed by introducing the concept of a
{\em maximal globally hyperbolic development} (MGHD), informally the largest
Lorentzian manifold $({\cal M},g)$ determined, via Einstein's equations, by the initial
data.\footnote{For the precise definitions and a modern account of the Cauchy problem in general
relativity, see~\cite{RingstromCauchy}.} Existence and uniqueness (up to diffeomorphism) of a MGHD
is then the outcome of the well posedness results mentioned above. Remarkably, the study of exact solutions
reveals the possibility of constructing non-isometric extensions of the MGHD. So,
we see that uniqueness of the MGHD is, in fact, a local result: a na\"\i ve version
of  global uniqueness, aiming for full generality, simply fails.

The boundary of the MGHD as a proper submanifold of a larger spacetime,
when such an embedding is possible, is known as the Cauchy horizon. An important class of
examples is provided by the three parameter
[$(M,4\pi e,\Lambda)=$ (mass, charge, cosmological constant)] family of solutions to the Einstein-Maxwell equations
known as the Reissner-Nordstr\"{o}m family.\footnote{Throughout this work we will simply use ``Reissner-Nordst\"om'' to mean any of the anti-de Sitter ($\Lambda<0$), the asymptotically flat ($\Lambda=0$), or the de
Sitter ($\Lambda>0$) Reissner-Nordstr\"{o}m solutions.}
Within a relevant parameter range, and given appropriate initial data, all solutions of this family contain a Cauchy
horizon inside the black hole region.
In fact, all observers (causal curves) entering the black hole region will reach the Cauchy horizon in finite proper
time and will ``safely'' cross such horizon. However, their future history beyond that point (which might continue indefinitely)
cannot be uniquely determined from the initial data (see Figure~\ref{fig23}).

\begin{figure}[h!]
\begin{center}
\psfrag{m}{\tiny MGHD}
\psfrag{e}{\tiny event horizon}
\psfrag{h}{\tiny Cauchy horizon}
\psfrag{s}{\tiny singularity $r=0$}
\psfrag{c}{\tiny causal curve}
\includegraphics[scale=.9]{fig23.eps}
\end{center}
\vspace{-1.5cm}
\caption{Penrose diagram for part of the Reissner-Nordstr\"{o}m solution.}\label{fig23}
\end{figure}

Some early important insights concerning global uniqueness came from an heuristic argument,
complemented with numerical experiments, by Simpson and Penrose~\cite{SimpsonInternal}, who provided
evidence in favor of the instability of the Cauchy horizon of some Reissner-Nordstr\"{o}m solutions with $\Lambda=0$. Later,
Israel and Poisson~\cite{IsraelPoisson} identified the blow up of a scalar invariant known as the Hawking mass as the source of the
instability, in a process known as {\em mass inflation}.
In view of these developments, the expectation became that generic perturbations of such solutions
should turn the Cauchy horizon into a singularity beyond which the spacetime could not be continued in any meaningful way.
This reinstated the belief in global uniqueness as a generic property of reasonable initial value problems
for the Einstein equations, an idea substantiated in Penrose's {\em strong cosmic censorship conjecture},\footnote{For
those wondering about the choice of such a ``baroque name''~\cite{ChruscielSCC}
and not familiar with its history, it might help to note that it is related to
a sibling conjecture, the {\em weak cosmic censorship}, which forbids the generic
existence of {\em naked singularities}.}
see~\cite{PenroseSingularities}, \cite{ChruscielSCC}, \cite{ChristodoulouGlobalnew} and~\cite{DafermosBlack}.

In this series of papers we will study the relation between Cauchy horizon stability and global uniqueness by
considering the full non-linear evolution of an appropriate Einstein-matter
system to the future of the event horizon (the boundary of the black hole region).
Arguably, the simplest formulation of the global uniqueness question within this framework takes the following form:

\begin{Problem}
\label{problema}
  Given spherically symmetric characteristic
  initial data for the Einstein-Maxwell-scalar
  field system with a cosmological constant $\Lambda$,
  with the data on the outgoing initial null hypersurface
  given by a (complete) subextremal Reissner-Nordstr\"{o}m black
  hole event horizon with non-vanishing charge $4\pi e$, and the remaining data otherwise free, study the
  future extendibility of the corresponding MGHD as a  ``suitably regular'' Lorentzian manifold.
\end{Problem}

 Let us take a moment to discuss the choices made. We take characteristic initial data due to the null geometry of event horizons.
Spherical symmetry is compatible with any choice of sign for the cosmological constant, and at the same time allows us to reduce the Einstein
equations to a $1+1$ evolution problem, which is considerably simpler than its higher dimensional counterpart.
The matter model, a self-gravitating real massless scalar field, provides the simplest
non-pathological Einstein-matter system with dynamical degrees of freedom in spherical symmetry,
and admits the entire Reissner-Nordstr\"{o}m family as solutions. Moreover, it exhibits a wavelike behavior reminiscent of the
general Einstein vacuum equations. A non-vanishing charge parameter is needed to exclude the Schwarzschild subfamily,
whose solutions do not contain a Cauchy horizon to start with.

A symmetric model is, a priori, non-generic. Nonetheless, there exists a relation between the spherically symmetric self-gravitating scalar field model
and the problem of vacuum collapse without symmetries, which
has been particularly enlightening and fruitful (see \cite{Christodoulou:2008}).
In fact, recently \cite{LukWeak} explored this relation to obtain the first
promising steps towards the understanding of the
stability of Cauchy horizons without symmetry assumptions. We also note that, in
our framework, the charge is topological, hence non-dynamical.
We refer the reader to the discussion
in~\cite{KommemiGlobal}, where preliminary results for a more realistic matter model are obtained.

The question of the regularity of the possible extensions is of paramount importance and  was
not precisely formulated above. Obtaining a precise formulation is, in fact, one of the challenges of the
problem. The definition of  a ``suitably regular'' extension should, of course, exclude artificial extensions, like, for instance,
taking the disconnected union of the MGHD with another Lorentzian manifold. Having done that, we are still left with several
possibilities. Let us start by considering standard regularity requirements. We will concentrate
on the regularity of the metric, but the regularity requirements for the matter fields,
in our case the scalar field, must also be discussed.

{\em Inextendibility of the metric in $C^2$}: This is motivated by the fact that the Einstein equations are
of second order. Moreover, causality theory (which is extensively used in the proof of the existence and uniqueness of a MGHD) usually assumes
the metric to be $C^2$ (see~\cite{ChruscielGrant}).
It was this criterion that was used
by Ringstr\"om in his seminal work on strong cosmic censorship
for Gowdy symmetry \cite{RingstromGowdy}. Clearly, the existence of $C^2$ extensions would provide
strong evidence against any reasonable form of global uniqueness, unless, for some unlikely and mysterious motive,
the spacetime structure would turn out to be uniquely determined beyond the corresponding Cauchy horizons
(see the discussion in~\cite{ChruscielSCC}). On the other hand, $C^2$-inextendibility does not necessarily provide a
compelling argument in favor of global uniqueness, since there are relevant solutions of the Einstein equations whose regularity is
well below this threshold. For instance, the impulsive wave solutions of Luk and Rodnianski~\cite{LukLocal, LukLocal2},
generalizing the plane gravitational waves of Khan and Penrose~\cite{KhanPenrose} and Szekeres~\cite{SzekeresColliding}, admit a Dirac delta singularity in the curvature along
a null hypersurface, which in no way should be considered as a terminal boundary of spacetime. Another remarkable
example is provided
by  Ori's solution~\cite{OriInner}, where the effect of the pointwise blow-up of the Kretschmann scalar at the Cauchy
horizon, corresponding to infinite tidal forces there, does not necessarily lead to the ``destruction'' of an
observer crossing the horizon; more precisely, a double integral of the Kretschmann scalar remains finite.
Other solutions to the Einstein equations with lower regularity than $C^2$ have been studied in the literature (see for instance \cite{ChristodoulouBounded, LeFloch2007, LeFloch2014}
and references therein). In fact, we will see in this series of papers that there even exist classical solutions of the Einstein equations which
are not necessarily $C^2$.

{\em Inextendibility of the metric in $C^0$}: This was introduced by Christodoulou in his original formulation of the
strong cosmic censorship conjecture~\cite{ChristodoulouGlobalnew}. Its validity would provide overwhelming
evidence in favor of the deterministic nature of general relativity.
It holds for the Schwarzschild solution, and indeed for the generic asymptotically flat solutions of the Einstein-massless scalar field system studied by Christodoulou\footnote{Christodoulou showed that $r=0$ at the future boundary of the black hole region of a generic solution. This suffices to show that there are no spherically symmetric $C^0$ extensions, and it is widely believed (but we are not aware of a formal proof) that in fact there are no $C^0$ extensions whatsoever. In the present work we will only consider the question of existence of spherically symmetric extensions.} in \cite{ChristodoulouNaked}.

It turns out that the two regularity requirements above are insufficient
to capture the full richness of the subject.
In~\cite{Dafermos1}, Dafermos solved many instances of Problem~\ref{problema}
for the $\Lambda=0$ case. His findings were quite remarkable: first, under
the hypothesis of Problem~\ref{problema}, the MGHD can always be extended in a $C^0$
manner; second, if the initial data is sufficiently subextremal and if, in addition, we
assume an appropriate decay
for the free initial data (more precisely, an appropriate decay for the ingoing derivative of the scalar field),
then mass inflation occurs.
Since the Hawking mass is a geometric invariant involving first derivatives of the metric, its blow up excludes the
existence of (spherically symmetric) $C^1$ extensions.

These results led Christodoulou~\cite{Christodoulou:2008} to drop his earlier $C^0$ formulation in favor
of a stronger regularity requirement: the natural inextendibility criterion, from the PDE point of view, would be to exclude extensions which
are solutions of the Einstein equations, as opposed to arbitrary extensions.

{\em Christodoulou-Chru\'sciel inextendibility criterion --
  inextendibility as a Lo\-ren\-tzi\-an manifold with Christoffel
symbols in $L^2_{\rm loc}$}:
This is enough to ensure that no extension satisfying the Einstein equations, even in a weak sense,
is possible.  A somewhat different kind of reasoning had already led Chru\'sciel, in~\cite{ChruscielSCC}, to consider
the (slightly stronger) regularity conditions $g\in H^1_{\rm loc}$  and $g^{-1}\in L^{\infty}_{\rm loc}$, as being sufficiently low for the well-posedness of the Einstein equations not to hold.
Indeed, to our knowledge, no well posedness results exist, or are expected to exist, at this level of regularity: the state of the art concerning the Cauchy problem requires
square integrable curvature~\cite{KlainermanL2}. Therefore, the consequences
of a potential failure of the Christodoulou-Chru\'sciel
inextendibility criterion might not be as definite as the consequences of its success: such failure may just mean that the
appropriate regularity for the extension criterion must be made higher.

From the techniques in~\cite{DafermosBlack}, one can easily conclude that, under the conditions
leading to mass inflation identified in~\cite{Dafermos1}, the Christodoulou-Chru\'sciel inextendibility criterion holds (in spherical symmetry).

\bigskip

We now motivate the introduction of a cosmological constant~$\Lambda$ in Problem~\ref{problema}.
It is well known that it plays a fundamental role in modern physics: in cosmology, for instance, a positive $\Lambda$ provides the simplest mechanism to model dark energy,
 while in high energy physics a great deal of attention has been devoted to solutions of
the Einstein equations with $\Lambda<0$. From a purely mathematical point of view, the introduction of this zeroth order term in the
Einstein equations leads
to a whole new range of rich geometrical structures and dynamical behaviors.

Nonetheless, the relevance of considering a cosmological constant in Problem~\ref{problema} is not obvious a priori.
This problem concerns what happens in the interior of a black hole region, whereas the effects of the
cosmological constant are known
to be specially relevant at large scales, in the exterior regions.  It turns out that the question is far more interesting than
originally anticipated. In fact, there was a considerable amount of activity during the 90s concerning the
strong cosmic censorship conjecture with a positive cosmological constant~\cite{BradyCauchy, BradyCauchyMass}. Based on heuristic arguments and perturbative analyses, the initial
expectation became that, close to extremality, mass inflation should fail, i.e.~the Hawking mass should remain bounded, and that
$C^2$ extensions of the spacetime beyond the corresponding Cauchy horizon should exist. In conclusion, the strong cosmic censorship conjecture
was believed to fail for $\Lambda>0$. Later, a perturbative analysis based on a more sophisticated model showed
that the previous results neglected the effects of backscattering; these, when properly taken into account,
would lead to the blow up of curvature scalars. The question of mass inflation was not addressed in the context of this new model.
The main thesis was clear from the title under which these results were presented:
``Cosmic censorship: As strong as ever''~\cite{BradyCosmic} (at least in its $C^2$ inextendibility formulation).

This remained the dominant point of view until, recently,
Dafermos suggested that the
expected curvature blow up might not be related to the blow up of the mass, which, close to extremality, should remain bounded.
The consequences of such {\em no mass inflation} scenario should be considerable and led
Dafermos to conjecture~\cite[Conjecture~4]{DafermosBlack} that
the Christodoulou-Chru\'sciel
inextendibility criterion would fail for positive $\Lambda$. We will show that this is in fact the case
in the context of Problem~\ref{problema}, for any sign of $\Lambda$ (including the $\Lambda=0$ case treated in \cite{Dafermos1}), provided that the free data decays sufficiently fast (see Part~3). It should be noted, however, that we are considering pure Reissner-Nordstr\"{o}m data on the event horizon, which in general will not arise from gravitational collapse; the case $\Lambda > 0$ is special in that this data is expected to be approached exponentially fast (see Section~\ref{section1.3}).

The question of strong cosmic censorship for $\Lambda < 0$ has received less attention in the literature, but it is expected that the mass inflation scenario should hold.

\bigskip

This paper is the first part of a trilogy devoted to the study of Problem~\ref{problema}.
We study the relation between the spherically symmetric
Einstein-Maxwell-scalar field equations with a cosmological constant and the first order PDE system~\eqref{r_u}$-$\eqref{kappa_at_u}, for the quantities~\eqref{nu_0}$-$\eqref{kappa_0}.
We establish its well posedness under the minimal regularity conditions
leading to classical solutions. We also identify the appropriate notion
of maximal solution, from which
the construction of the corresponding MGHD immediately follows, and determine breakdown criteria. In broad terms, these results are widely expected, although
we are unaware of a published proof.
They are also the unavoidable starting point of the analysis;
our main results will depend on a detailed understanding of these fundamentals, and
seemingly minor improvements here will be of paramount importance later on.

In the second paper, we generalize the results of Dafermos concerning the stability of the radius function at the Cauchy horizon
with the inclusion of a cosmological constant (of any sign). More precisely, we show that the radius function is
bounded away from zero. This has the remarkable consequence of allowing the construction of continuous extensions of the metric.
The introduction of the cosmological constant requires a considerable deviation from the original strategy developed by Dafermos,
the main difficulties stemming from the $\Lambda>0$ case. We develop a unified framework that avoids dividing the solution spacetime into red-shift
and blue-shift regions, but instead focuses on the level sets of the radius function, without having to distinguish between the different signs for the cosmological constant.

In the third paper of the series, we analyze the mass inflation scenarios. We start by revisiting Dafermos'
strategy to establish mass inflation, which naturally generalizes to the case of a non-vanishing cosmological constant.
Then we show that under appropriate circumstances (in particular close to extremality), the mass remains bounded. As a consequence,
the Christodoulou-Chru\'sciel inextendibility criterion fails, i.e.\ we can construct extensions of spacetime, across the Cauchy horizon, with continuous metric,
square integrable connection coefficients, and scalar field in $H^1_{\rm loc}$. Finally we prove that, under
slightly stronger conditions, we can bound the gradient of the scalar field. This allows us to construct
(non-isometric) $C^1$ extensions of the metric, which correspond to classical solutions of the Einstein-Maxwell-scalar field equations.
To the best of our knowledge, these are the first results where the generic existence of extensions as solutions is established.

\subsection{The main results}

We summarize the  main results of this trilogy in
\begin{Thm}
\label{thmMain}
Consider, as a reference solution, a subextremal element of the Reissner-Nordstr\"{o}m family with mass $M$, non-vanishing charge $4\pi e$ and cosmological constant $\Lambda$, and let $r_+>0$ be the event horizon radius. Given $0 < U < r_+$, there exists a unique maximal development of the characteristic initial value problem for the spherically symmetric Einstein-Maxwell-scalar field system with metric
\[
g=-\Omega^2(u,v)\,dudv+r^2(u,v)\,\sigma_{\mathbb{S}^2} \label{metric-g}
\]
and scalar field $\phi$, defined on a past set ${\cal P} \subset [0,U] \times [0,+\infty[$, determined by Reissner-Nordstr\"{o}m initial data on the event horizon $\{u=0\}$ and free data on the incoming null direction $\{v=0\}$:
\begin{enumerate}[i)]
\item $r(0,v) = r_+$;
\item $\phi(0,v) = 0$;
\vspace{-3mm}
\item $\Omega^2(0,v) = 4 e^{-\,\frac{2}{r_+^2}\bigl(\frac{e^2}{{r_+}}+\frac{\Lambda}{3}r_+^3-M\bigr)\,v}$;
\item $r(u,0) = r_+-u$;
\item $\phi(\,\cdot\,,0)\in C^1([0,U])$ with $\partial_u \phi(0,0)=0$.
\end{enumerate}

Moreover:
\begin{enumerate}[{\rm (1)}]
\item  {\em Stability of the radius function at the Cauchy horizon.} There exists $U>0$ such that
$$[0,U]\times[0,\infty[\,\subset {\cal P},$$
and $r_0>0$ for which
$$r(u,v)>r_0,\ {\rm for\ all}\ (u,v)\in[0,U]\times[0,\infty[.$$
Consequently, $({\cal M},g,\phi)$ extends, across the Cauchy horizon $\{v=\infty\}$, to $(\hat {\cal M},\hat g,\hat \phi)$, with $\hat g$ and $\hat \phi$ in~$C^0$.
\end{enumerate}
Let\/ $1<\rho<\infty$ be the ratio between the surface gravities of the
Cauchy horizon and of the event horizon of the reference solution.
\begin{enumerate}[{\rm (1)}]\addtocounter{enumi}{+1}
\item {\em Mass inflation.} If $\rho>2$ and
 \begin{equation*}
\partial_u\phi(u,0)\geq cu^s,\ {\it for\ some}\/\
0<s<\frac\rho 2-1,
\end{equation*}
then the renormalized Hawking mass $\varpi$ (see \eqref{bar_rafaeli}) satisfies
\begin{equation*}
\lim_{v\rightarrow\infty}\varpi(u,v)=\infty,\ {\it for\ each}\/\  0<u\leq U.
\end{equation*}
In particular, no (spherically symmetric) $C^1$ extensions across the Cauchy horizon exist.
\item {\em No mass inflation.}  If
\begin{equation*}
|\partial_u\phi(u,0)|\leq cu^s,\ {\rm for\ some}\ s>\frac{7\Psi}9-1,
\end{equation*}
then there exists $C>0$ such that
$$
\left|\varpi(u,v)\right|<C,\ {\rm for\ all}\ (u,v)\in[0,U]\times[0,\infty[.
$$
Consequently, the Christodoulou-Chru\'sciel inextendibility criterion fails, i.e.\
$({\cal M},g,\phi)$ extends across the Cauchy horizon to $(\hat {\cal M},\hat g,\hat \phi)$, with $\hat g$ and $\hat \phi$ in~$C^0$,
Christoffel symbols $\hat\Gamma$ in $L^2_{\rm loc}$, and $\hat\phi$ in $H^1_{\rm loc}$.
\item {\em Classical extensions.} If
\begin{equation*}
|\partial_u\phi(u,0)|\leq cu^s,\ {\rm for\ some}\ s>\frac{13\Psi}9-1,
\end{equation*}
then $({\cal M},g,\phi)$ extends (in a non-unique way), across the Cauchy horizon,
to a spherically symmetric (classical) solution $(\hat {\cal M},\hat g,\hat \phi)$ of the Einstein-Maxwell-scalar field system with
cosmological constant $\Lambda$, with $\hat g$ and $\hat\phi$ in $C^1$.
The Kretschmann scalar is uniformly bounded.
\end{enumerate}
\end{Thm}

In case~(4), and when $\partial_u\phi(\,\cdot\,,0)$ is just $C^0$, the metric does not have to be $C^2$
(see Part~3).

In fact, we can say more about the behavior of the solution at the Cauchy horizon.
For example, suppose that $cu^s\leq\partial_u\phi(u,0)\leq Cu^s$.
Then the behavior of the solution  depends on the value of $s$ as described in Figure~\ref{fig24}.
 We refer to Part~3 for more details.

\newpage

\begin{figure}[h!]
\begin{center}
\psfrag{b}{\tiny $\!\frac 97$}
\psfrag{u}{\tiny $\!\frac 92$}
\psfrag{c}{\tiny $2$}
\psfrag{d}{\tiny $3$}
\psfrag{e}{\tiny $4$}
\psfrag{z}{\tiny $\!\!1$}
\psfrag{g}{\tiny $\!\!\!\frac 49$}
\psfrag{h}{\tiny $\!\!1$}
\psfrag{i}{\tiny $\!\!2$}
\psfrag{j}{\tiny $\!\!3$}
\psfrag{k}{\tiny $s=\frac \Psi 2-1$}
\psfrag{m}{\tiny $s=\Psi-1$}
\psfrag{l}{\tiny $s=\frac{7\Psi}9-1$}
\psfrag{n}{\tiny $s=\frac{13\Psi}9-1$}
\psfrag{r}{\tiny $\Psi$}
\psfrag{s}{\tiny $s$}
\psfrag{o}{\tiny $1$}
\psfrag{p}{\tiny $\!\!0$}
\includegraphics[scale=.7]{fig20.eps}
\end{center}
\begin{center}
\psfrag{e}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!mass inflation}
\psfrag{u}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!mass inflation or}
\psfrag{b}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!no mass inflation}
\psfrag{a}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!no mass inflation}
\psfrag{c}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!no mass inflation}
\psfrag{d}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!Kretschmann bounded}
\psfrag{f}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!Kretschmann unbounded}
\psfrag{v}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!Kretschmann unbounded}
\psfrag{g}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!smooth extension}
\psfrag{h}{\tiny \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!beyond Cauchy horizon}
\includegraphics[scale=1]{fig24.eps}
\end{center}
\vspace{-.5cm}
\caption{Behavior of the solution at the Cauchy horizon.}\label{fig24}
\end{figure}

\subsection{The Strong Cosmic Censorship Conjecture}\label{section1.3}

Strictly speaking, our results do not apply directly to the strong cosmic censorship conjecture since
the data considered on the event horizon does not arise from the gravitational
collapse of generic spacelike initial data. This data is taken from a stationary black hole, and the dynamical features
of our solutions come from the ingoing free data $\phi(\,\cdot\,,0)$.

To strengthen the connection with the strong cosmic censorship conjecture in the asymptotically flat case $\Lambda=0$,
Dafermos \cite{Dafermos2} extended his original analysis of \cite{Dafermos1} by considering
data along the event horizon with the widely expected scalar field behavior
prescribed by Price's law (see~\cite{PriceNonshperical}):
a polynomial decay, in the coordinate system of Theorem~\ref{thmMain}, for $\partial_v\phi$
along the event horizon.  Assuming such decay as an upper bound, he showed that the radius function remains
positive at the Cauchy horizon. Moreover, he showed that if the field satisfies an appropriate lower bound, consistent with Price's law,
then mass inflation occurs throughout the entire subextremal range $1<\Psi<\infty$, and the Christodoulou-Chru\'{s}ciel inextendibility criterion holds~\cite{DafermosBlack}.
The relation with the strong cosmic censorship conjecture was later reinforced in~\cite{DafermosProof}, where Dafermos and Rodnianski proved that the polynomial upper bound for the field indeed holds for
large classes of asymptotically flat data. However, the generic validity of the lower bound, under which mass inflation was established in~\cite{Dafermos2}, remains an open problem.

For $\Lambda>0$, it is widely expected (see~\cite{DafermosWavedeSitter, Vasy2014} and references therein) that
the corresponding Price law should guarantee exponential decay of the scalar field along the event horizon,
that is, an exponential approach to the data considered here.
If we take into account the fact that near extremality $\Psi$ is approximately equal to $1$, and so the requirements in $(3)$ and $(4)$ of Theorem~\ref{thmMain}
are satisfied with very mild restriction on the behavior of the free data, then it seems plausible that the no mass inflation scenario, and the existence of
regular extensions, should remain valid when $\Psi$ is close to $1$, and appropriately decaying initial data is considered.
We will address this question in a forthcoming paper.

As mentioned above, for $\Lambda=0$ the expected polynomial decay to
stationarity is enough to exclude the no mass inflation scenario and its surprising consequences. When $\Lambda<0$,
the decay of the field along the event horizon is expected to be slower than polynomial\footnote{Interestingly, the
first spherical harmonic mode of the field decays exponentially along the event horizon; thus, strictly speaking, the decay
is exponential in spherical symmetry.}
 (see~\cite{HolzegelDecay} and~\cite{HolzegelQuasimodes}); moreover,
 the process of gravitational collapse is far less understood.
Thus, one may argue that,
although valid for all signs of cosmological constant, points $(3)$ and $(4)$ of
Theorem~\ref{thmMain} only provide evidence
for the failure of the strong cosmic censorship conjecture in the case where $\Lambda$ is positive.
Nonetheless, the techniques used in our work
and the results we obtain suggest that any difference concerning the
stability of the Cauchy horizon when the cosmological constant $\Lambda$ changes sign
should be due to the behavior of the field under the Price law along the event horizon.

\vspace{3mm}

\noindent {\bf Acknowledgments.} J.~Costa thanks P.~Chru\'{s}ciel and M.~Dafermos for useful discussions concerning the strong cosmic censorship conjecture.

\section{An overview of Part~1}

The structure of the present paper is as follows. We consider a double characteristic initial value problem for the spherically symmetric Einstein-Maxwell-scalar field equations with a cosmological constant $\Lambda$.
This consists of a system of four second order Einstein equations: a wave equation~\eqref{wave_r} for the physical radial coordinate~$r$, a wave equation~\eqref{wave_phi} for the field $\phi$, the
Raychaudhuri equation~\eqref{r_uu} in the incoming null direction $u$, and the Raychaudhuri equation~\eqref{r_vv} in the outgoing null direction $v$; and also a wave equation~\eqref{wave_Omega}
for the metric coefficient $\Omega$ (which is actually implied by the other four equations).

We start by showing that the Einstein equations imply the first order system of PDE~\eqref{r_u}$-$\eqref{kappa_at_u}.
More precisely, this system consists of ten equations for the seven unknowns $r$, $\nu$, $\lambda$, $\varpi$, $\theta$, $\zeta$ and $\kappa$ (with $\nu=\partial_ur$, $\lambda=\partial_vr$,
$\theta=r\partial_v\phi$ and $\zeta=r\partial_u\phi$): two equations for the first partial derivatives of~$r$, two equations which correspond to the wave equation for~$r$,
two equations for the first partial derivatives of the renormalized mass $\varpi$, two equations which correspond to the wave equation for $\phi$, an equation for
a derivative of $\kappa$, and an algebraic restriction equation $\lambda=\kappa(\muu)$ (which can be thought of as the definition of $\kappa$).
The introduction of $\kappa$ allows us to avoid unpleasant denominators which a priori could vanish.
Since there are more equations than unknowns, we solve seven of these equations and treat the remaining three as restrictions, which we later check to be
preserved by the flow.

Our first task is to prove existence of solutions for the first order system (Theorem~\ref{existence}).
The reason why we work with this system and not with the Einstein equations is that we need to prove existence of solutions defined in rectangles $[0,U]\times[0,V]$
for any given $V$ (and suitably small $U$), or any given $U$ (and suitably small $V$); it is not enough to prove such a result for both $U$ and $V$ small.
By working with the first order system we are in fact keeping track of more functions and their derivatives, providing a finer control of $r$, $\Omega$ and $\phi$.
The proof follows a standard Banach Fixed Point Theorem argument. The construction of the contracting operator and the corresponding complete metric space is somewhat subtle, and uses the specific form of our system.

After proving an appropriate uniqueness result, we show that any solution can be extended uniquely to a maximal past set ${\cal P}$ (Theorem~\ref{maximal}).
We then proceed to establish a breakdown criterion for the solution: along all sequences in ${\cal P}$ converging to the boundary of ${\cal P}$,
the radial coordinate $r$ goes to zero and the renormalized mass $\varpi$ goes to $+\infty$ (Theorem~\ref{breakdown}).

We finish Part~1 by showing that, under a stronger regularity condition on the initial data, a solution of the first order system corresponds, in fact, to a solution of the Einstein equations
(Proposition~\ref{einstein-2}). Furthermore, additional regularity for the initial data implies additional regularity for the solutions (Proposition~\ref{regularity} and Remark~\ref{rmk-reg}).

config: arxiv


TITLE: Simplifying expression with absolute value
QUESTION [0 upvotes]: I've come across a past exam paper question, which I have the solutions to, which I have understood until the third part of it. I'll do my best to explain it without writing out the entire question.

Define a sequence by $\left ( a_{n} \right )_{n\in \mathbb{N}}$ by $$a_{1} = 1, $$
  $$a_{n+1} = 1/(1+a_{n}). $$
(c) Use the quadratic equation you've found in (b) to show that $$\left | a_{n+1} - \alpha \right |\leq \alpha \left | a_{n}-\alpha  \right |,\forall n\in\mathbb{N}$$

The quadratic equation is $\alpha =\frac{\sqrt{5}-1}{2}$.
In the solutions it states:

|$a_{n}-\alpha|=|\frac{1}{1+a_{n}}-\alpha|=|\frac{1-\alpha-\alpha a_{n}}{1+a_{n}}|$

But I don't understand where the $\alpha a_{n}$ came from. This is directly followed by:

$≤|1-\alpha-\alpha a_{n}|=|\alpha^{2}-\alpha a_{n}|$

in which I don't understand how these are equal. Any help, or advice, would be much appreciated.

REPLY [1 votes]: By definition $$a_{n+1} = \frac{1}{1+a_n}.$$  Hence $$\left|a_{n+1} - \alpha\right| = \left| \frac{1}{1+a_n} - \alpha \right| = \left| \frac{1}{1+a_n} - \frac{\alpha(1+a_n)}{1+a_n} \right| = \left| \frac{1 - \alpha - \alpha a_n}{1+a_n} \right|.$$  Then since $a_n \ge 0$, $1+a_n \ge 1$, meaning that $$\frac{|1 - \alpha - \alpha a_n|}{|1+a_n|} \le \left|1 - \alpha - \alpha a_n\right|.$$  Then if $\alpha = (\sqrt{5}-1)/2$, it easily follows by direct calculation that $\alpha^2 = 1 - \alpha$.


TITLE: Question about proof of Hessenberg: $\kappa \cdot \lambda = \lambda$
QUESTION [5 upvotes]: The following is a theorem:
(Hessenberg) Let $1 \le \kappa \le \lambda$ where $\lambda$ is an infinite cardinal. Then $\kappa \cdot \lambda = \lambda$.
The proof in the book proceeds by transfinite induction showing $\lambda \cdot \lambda \le \lambda$. I have a question about the induction step. In the proof they define a well-order on $\lambda \times \lambda$ and then show that every proper initial segment of $\lambda \times \lambda$ has cardinality less than $\lambda$. It seems long-ish.
Why can't one argue like this: By the inductive assumption we have $\kappa \cdot \kappa \le \kappa$ for all $\kappa < \lambda$. Hence $\sup (\kappa \cdot \kappa) \le \sup \kappa $. But $\sup \kappa = \lambda$ and $\sup \kappa \cdot \kappa = \lambda \cdot \lambda$ which proves the claim.
Thanks for your help.

REPLY [4 votes]: It doesn't work for successor cardinals. If $\lambda=\mu^+$, then $\sup_{\kappa<\lambda}\kappa=\mu<\lambda$.
For limit cardinals it doesn't work quite so easily either. You'd only have that $\sup_{\kappa<\lambda} \kappa\cdot \kappa=\lambda$, but you don't know if the former is actually $\lambda\cdot\lambda$.

REPLY [3 votes]: Note that you're not exactly arguing about the cardinality as much as you are arguing about the order type of the Hessenberg sum.$\newcommand{\otp}{\operatorname{otp}}$
Furthermore if you have $\otp(\kappa\boxplus\kappa)=\kappa$ (where $\otp$ denotes order-type and $\boxplus$ is the Hessenberg sum) then you get stuck in the successor step:
If $\lambda=\kappa^+$ then your suggestion fails to even go beyond any limit ordinal above $\kappa$.
For limit cardinals you still don't know that $\otp(\kappa\boxplus\lambda)$ is less or more than $\lambda$, and you cannot use that for $\otp(\lambda\boxplus\lambda)=\lambda$.


text:
\section{An Example: Cooperative Exploration}
\label{sec:example_cooperative}

Throughout this section, we refer to the two Markov chains depicted in Figure \ref{fig: cooperative}.  The state space for both chains is $S = \{ 1, \ldots, s\}$, where $s > 1$.  The red chain corresponds to $\ell = 1$ and the blue chain corresponds to $\ell = 2$.  The transition probabilities are as depicted in the figure.  In particular, we assume that chain $1$ has $P(x,x+1) = P(s,1) = 1$  for $x = 1,\ldots,s-1$, and chain $2$ has $P(x,x-1) = P(1,s) = 1$ for $x = 2,\ldots,s$.

We assume the experimenter {\em knows} the transition matrices exactly (as they are deterministic), and thus the only uncertainty in estimating the reward distribution comes from uncertainty regarding the reward distribution of each chain.  We assume each chain {\em only} earns a reward in state $x = 1$.  In particular, chain $\ell$ earns a reward that is Bernoulli($q(\ell)$) in state $1$, for some unknown parameter $q(\ell)$ with $0 < q(\ell) < 1$.  Clearly the stationary distribution of each chain is $\pi(\ell,x) = 1/s$, and so the steady state mean reward of each chain is $\alpha(\ell) = q(\ell)/s$.  Thus the treatment effect is $(q(2) - q(1))/s$.

First, suppose that for $\ell = 1,2$ we wanted to estimate only $\alpha(\ell)$ by running chain $\ell$, i.e., $A_n = \ell$ for all $n$.  Then note that in every $S$ steps, only one observation is received of the reward in state $1$.  Let $\hat{\alpha}_n(\ell)$ denote the maximum likelihood estimate of steady state reward obtained from the first $n$ steps.  Given the structure of this chain, it is straightforward to check that the MLE at time $n > s$ reduces to the sample average of $\lfloor n/s \rfloor$ independent Bernoulli($q(\ell)$) samples.  This estimator has variance that scales as $\Theta(s/n)$.  Thus, any attempt at estimation of the variance of steady state reward by running each chain in isolation will have variance that scales with $s$.

On the other hand, now suppose we use the following sampling policy: the policy always samples chain $1$ when in state $s$;  the policy always samples chain $2$ in states $2, \ldots, s-1$; and in successive visits to state $1$, the policy deterministically alternates between sampling chains $1$ and $2$.

Suppose for simplicity that this chain starts at $X_0 = 1$.  Then in every four periods, this chain obtains one independent sample each of a reward from chain 1 in state 1 (i.e., Bernoulli($q(1)$), and a reward from chain 2 in state 1 (i.e., Bernoulli($q(2)$).  Thus the maximum likelihood estimator of $\alpha(\ell)$ will have variance that scales as $\Theta(4/n)$, and in particular, does {\em not} grow with $s$.  In particular, the improvement in variance under this policy relative to the preceding approach can be made unboundedly large by increasing $s$.

This example illustrates the surprising insight that by {\em cooperatively exploring} using {\em both} chains together, substantial benefits in estimation variance can be achieved relative to the variance of estimation with each chain in isolation.  In this example, both approaches to estimation will be consistent.

However, the state-dependent sampling policy leads to a substantial reduction in variance, because it benefits from cooperative exploration: for each chain $\ell =1,2$, the {\em other} chain is used to drive the system back to where samples are most needed to reduce variance.  By contrast, running each chain in isolation forces the experimenter to wait $s$ time steps between successive observations of the random reward in state $1$.  When $s$ becomes larger, the long run average time spent in state 1 approaches $1/2$ for the state-dependent sampling policy, but approaches zero for either chain in isolation.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.3\textwidth]{cooperative.png}
    \caption{The two Markov chains described in Appendix \ref{sec:example_cooperative}.  Chain $1$ is red, and chain $2$ is blue.  Rewards are only earned in state $1$ for each chain; in particular, the reward distribution in state 1 is Bernoulli($q(\ell)$) for chain $\ell$.}
    \label{fig: cooperative}
\end{figure}

\section{Proofs: Section \ref{sec:tar}}
\label{sec:tar_proofs}

\begin{proof}[Proof of Proposition \ref{prop: policy limits}]
Relations (\ref{eq: kappa eq 2}) and (\ref{eq: kappa eq 3}) are obvious. As for (\ref{eq: kappa eq 1}), note that
\begin{align}
&\frac{1}{n}\Gamma_n(1,y)+\frac{1}{n} \Gamma_n(2,y)\\
=&\frac{1}{n}\sum_{j=\newrj{0}}^{n-1}I(X_j=y)\\
=&\frac{1}{n}\sum_{j=1}^{n}I(X_j=y)+\frac{1}{n}\big(I(X_0=y)-I(X_n=y)\big)\\
=& \frac{1}{n}\sum_{j=1}^{n}I(X_j=y)+O_p\left(\frac{1}{n}\right)\\
=& \sum_{\ell=1}^{2} \sum_{x\in S} \frac{1}{n} \sum_{j=1}^{n} I(X_{j-1}=x, A_{j-1}=\ell, X_j=y)+O_p\left(\frac{1}{n}\right)\\
=& \sum_{\ell=1}^{2}\sum_{x\in S} \frac{1}{n}\Gamma_n(\ell,x)P(\ell,x,y)\\
&+\sum_{\ell=1}^{2}\sum_{x\in S}\bigg\{ \frac{1}{n} \sum_{j=1}^{n} I(X_{j-1}=x, A_{j-1}=\ell)[I(X_j=y)-P(\ell,x,y)]\bigg\}+O_p\left(\frac{1}{n}\right).\label{eq: gamma eq 4}
\end{align}
(Here we use the notation that $f(n) =O_p(1/n)$ to denote stochastic boundedness of $n f(n)$: for all $\epsilon > 0$, there exists deterministic $M$ such that $P(|n f(n)| > M) < \epsilon$ for all $n$.)

Let $W_j = I(X_{j-1}=x, A_{j-1}=\ell)[I(X_j=y)-P(\ell,x,y)]$.  This is a martingale difference sequence adapted to  $\mathcal{G}_{j}$.  In particular, as a result the $W_j$ are {\em orthogonal} in the sense that for $j < k$, there $E\{_j W_k\} = 0$.  (This result follows by conditioning on $\mathcal{G}_j$ and nesting conditional expectations: $E\{W_j W_k\} = E\{E\{W_k | \mathcal{G}_j\} W_j\} = 0$.)  Using orthogonality of the martingale differences implies that
\begin{align}
    &E\bigg\{\bigg(\frac{1}{n}\sum_{j=1}^{n} I(X_{j-1}=x, A_{j-1}=\ell)[I(X_j=y)-P(\ell,x,y)]\bigg)^2\bigg\}\\
    =&E\bigg\{\frac{1}{n^2} \Gamma_{n}(\ell,x)\big(P(\ell,x,y)-P^2(\ell,x,y)\big)\bigg\} \rightarrow  0
\end{align}
as $n\rightarrow \infty$. Therefore, by Chebyshev's inequality
\begin{align}\label{eq: convergence P(l) martingale}
    \frac{1}{n}\sum_{j=1}^{n} I(X_{j-1}=x, A_{j-1}=\ell)[I(X_j=y)-P(\ell,x,y)]\xrightarrow{p} 0
\end{align}
as $n\rightarrow \infty$. Taking the limits in (\ref{eq: gamma eq 4}) yields (\ref{eq: kappa eq 1}).
\end{proof}

\begin{proof}[Proof of Proposition \ref{prop: P convergence}]
We start by proving \eqref{eq:P_convergence}.  We recall that
\begin{align}
    \hat{P}_n(\ell,x,y)=\frac{\sum_{j=0}^{n-1} I(X_j=x, A_j=\ell, X_{j+1}=y)}{\max\{\Gamma_n(\ell,x), 1\}}
\end{align}
As in the proof of Proposition \ref{prop: policy limits},
\begin{align}
    &\frac{1}{n}\sum_{j=0}^{n-1}I(X_j=x, A_j=\ell, X_{j+1}=y)\\
    =& \bigg\{\frac{1}{n}\sum_{j=0}^{n-1}I(X_j=x, A_j=\ell)[I(X_{j+1}=y)-P(\ell,x,y)]\bigg\}+\frac{1}{n}\Gamma_n(\ell,x)P(\ell,x,y)
\end{align}
Therefore,
\begin{align}
   \hat{P}_n(\ell,x,y)=&\frac{\bigg\{\frac{1}{n}\sum_{j=0}^{n-1}I(X_j=x, A_j=\ell)[I(X_{j+1}=y)-P(\ell,x,y)]\bigg\}}{\frac{1}{n}\max\{\Gamma_n(\ell,x),1\}}
   \\ & +\frac{\Gamma_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}}P(\ell,x,y)\\
    =& \frac{o_p(1)}{\frac{1}{n}\max\{\Gamma_n(\ell,x),1\}}+\frac{\Gamma_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}}P(\ell,x,y) \qquad \text{from (\ref{eq: convergence P(l) martingale})}\\
    \xrightarrow{p}& P(\ell,x,y)\label{eq: convergence to P}
\end{align}
as $n\rightarrow \infty$, where the convergence in (\ref{eq: convergence to P}) holds
because $\gamma(\ell,x)$ are almost surely positive.

We now prove \eqref{eq:pi_convergence}.
Let $\mu_n$ denote the law of $\hat{\pi}_n$, and view it as a probability measure on vectors in the probability simplex on the state space $S$, denoted $\Delta(S)$.  The set $\Delta(S)$ is compact, and so by Prohorov's theorem there exists a deterministic subsequence $n_k$ such that $\mu_{n_k}$ converges weakly to a probability measure $\mu$ on $\Delta(S)$, with associated random variable $\pi'(\ell)$.  Since $\hat{P}_n(\ell) \xrightarrow{p} P(\ell)$ by \eqref{eq: convergence to P}, and $P(\ell)$ is deterministic, it follows by Slutsky's theorem that:
\[ \hat{\pi}_{n_k}(\ell) \hat{P}_{n_k}(\ell) \Rightarrow \pi'(\ell) P(\ell). \]

Since the policy limits are almost surely positive, $J$ is almost surely finite.  Thus, for all sufficiently large $k$ there holds $\hat{\pi}_{n_k}(\ell) \hat{P}_{n_k}(\ell) = \hat{\pi}_{n_k}(\ell)$.   It follows that $\pi'(\ell) = \pi'(\ell) P(\ell)$, so that $\pi'(\ell) = \pi(\ell)$ almost surely.  In other words, the measure $\mu$ is the Dirac measure that places probability one on $\pi(\ell)$.  Since this is the case for every convergent subsequence of $\{\mu_n\}$, we conclude that $\hat{\pi}_n(\ell) \Rightarrow \pi(\ell)$.  Since $\pi(\ell)$ is deterministic, we conclude that $\pi_n(\ell) \xrightarrow{p} \pi(\ell)$ as $n \to \infty$, as required.
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:consistency}]
Since the policy limits of $A$ are almost surely positive, it is straightforward to show that for each $\ell,x$, $\hat{r}_n(\ell,x) \xrightarrow{p} r(\ell,x)$ as $n \to \infty$.  The result then follows from Proposition \ref{prop: P convergence}.
\end{proof}

\section{Proofs: Section \ref{sec:var}}
\label{sec:var_proofs}

\begin{proof}[Proof of Theorem \ref{thm:CLT}]
We begin by showing that for $\ell = 1,2$ and $n \geq J$, there holds:
\begin{equation}
    \big(\hat{\pi}_n(\ell)-\pi(\ell)\big)r(\ell)=\hat{\pi}_n(\ell)\big(\hat{P}_n(\ell)-P(\ell)\big)\tilde{g}(\ell).
\end{equation}
To see this, observe that for $n\ge J$,
\begin{align}
    \hat{\pi}_n(\ell)-\pi(\ell)=\hat{\pi}_n \hat{P}_n(\ell)-\hat{\pi}_n(\ell)P(\ell)+\hat{\pi}_n(\ell)P(\ell)-\pi(\ell)P(\ell)
\end{align}
so rearranging the terms we get,
\begin{align}
    \big(\hat{\pi}_n(\ell)-\pi(\ell)\big)\big(I-P(\ell)\big)=\hat{\pi}_n(\ell)\big(\hat{P}_n(\ell)-P(\ell)\big).
\end{align}
Because $\Pi(\ell)$ has identical elements down each column,
\begin{align}
   \big (\hat{\pi}_n(\ell)-\pi(\ell)\big)\Pi(\ell)=0,
\end{align}
and hence
\begin{align}
    \big(\hat{\pi}_n(\ell)-\pi(\ell)\big)\big(I-P(\ell)+\Pi(\ell)\big)=\hat{\pi}_n(\ell)\big(\hat{P}_n(\ell)-P(\ell)\big).
\end{align}
Recall that we defined $\tilde{g}(\ell) = \big(I-P(\ell)+\Pi(\ell)\big)^{-1}r(\ell)$; thus
\begin{align}
\big(\hat{\pi}_n(\ell)-\pi(\ell)\big)r(\ell)=\hat{\pi}_n(\ell)\big(\hat{P}_n(\ell)-P(\ell)\big)\tilde{g}(\ell),
\end{align}
as desired.

Now for $\ell=1,2$, and $x\in S$, define
\begin{align}
    r(\ell,x,y)=&\int_{\mathbb{R}}zF(dz, x,y,\ell).

\end{align}

Recall that $\hat{\alpha}_n = \hat{\pi}_n(2) \hat{r}_n(2) - \hat{\pi}_n(1) \hat{r}_n(1)$. We can write:
\begin{align}
\hat{\pi}_n(\ell)&\hat{r}_n(\ell)-\pi(\ell)r(\ell)\\
    &=\big(\hat{\pi}_n(\ell)-\pi(\ell)\big)r(\ell)+\hat{\pi}_n(\ell)\big(\hat{r}_n(\ell)-r(\ell)\big)\\
    &=\hat{\pi}_n(\ell)\big(\hat{P}_n(\ell)-P(\ell)\big)\tilde{g}(\ell)+\hat{\pi}_n(\ell)\big(\hat{r}_n(\ell)-r(\ell)\big)\\
    &= \sum_{x\in S} \hat{\pi}_n(\ell,x) \frac{\sum_{j=1}^{n} I(X_{j-1}=x, A_{j-1}=\ell)\big[\tilde{g}(\ell,X_j)-\big(P(\ell)\tilde{g}(\ell)\big)(X_{j-1})]}{\max\{\Gamma_n(\ell,x),1\}}\nonumber\\&+ \sum_{x\in S} \hat{\pi}_n(\ell,x) \frac{\sum_{j=0}^{n-1} I(X_j=x, A_j=\ell)\big(R_{j+1}-r(\ell,x)\big)}{\max\{\Gamma_n(\ell,x),1\}}\\

    &= \sum_{x\in S}\hat{\pi}_n(\ell,x)\frac{\sum_{j=1}^{n}D_j(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}}\label{eq:trans_to_Dj}
\end{align}
where
\begin{align}
\label{eq:Dj(l,x)}
    D_j(\ell,x):= I(X_{j-1}=x, A_{j-1}=\ell)\big[\tilde{g}(\ell,X_j)-\big(P(\ell)\tilde{g}(\ell)\big)(X_{j-1})+R_j-r(\ell,X_{j-1})\big].
\end{align}
Note that for each $\ell,x$, $D_j(\ell,x)$ is a martingale difference sequence adapted to $\mathcal{G}_j$.

For deterministic $w(\ell)=(w(\ell,x): x\in S), \ell=1,2$, consider
\begin{align}
    T_n&=
    \frac{1}{\sqrt{n}}\sum_{j=1}^{n} \sum_{\ell=1}^{2} \sum_{x\in S} D_j(\ell,x)w(\ell,x)\\
    &\triangleq \frac{1}{\sqrt{n}} \sum_{j=1}^{n} D_j,
 \end{align}
where
\begin{align}
    D_j=\sum_{\ell=1}^{2} \sum_{x\in S} D_{j}(\ell,x)w(\ell,x).
\end{align}
The $D_j$'s are martingale differences adapted to $(\mathcal{G}_j: j\ge 0)$. Since they are bounded by $2\max\{|\tilde{g}(\ell,x)|: x\in S, \ell=1,2\}<\infty$ (since $r(\ell,x)$ is finite), the following conditional Lindeberg's condition holds (Eq. (3.7) of \cite{hall1980martingale}):
\begin{align}
    \text{for all } \epsilon>0, \quad \sum_{j=1}^{n}\frac{1}{n}E\{D_j^2I(|D_j|> \epsilon)|\mathcal{G}_{j-1}\}\xrightarrow{p} 0.
\end{align}

Furthermore,
\begin{align}\label{eq: D j variance}
    \frac{1}{n} \sum_{j=1}^{n} E\{D_j^2|\mathcal{G}_{j-1}\}&=\frac{1}{n}\sum_{\ell=1}^{2}\sum_{x\in S} \sum_{j=0}^{n-1} I(X_j=x, A_j=\ell)\sigma^2(\ell,x)w^2(\ell,x)\\%Also, is it clear that the conditional variances are RHS?
    &=\sum_{\ell=1}^{2}\sum_{x\in S} \sigma^2(\ell,x)w^2(\ell,x)\frac{\Gamma_n(\ell,x)}{n}\\
    &\xrightarrow{p} \sum_{\ell=1}^{2} \sum_{x\in S} \sigma^2(\ell,x)w^2(\ell,x)\gamma(\ell,x)\triangleq\eta^2,
\end{align}
since $A$ is assumed to be a TAR policy. We therefore conclude that (by Corollary (3.1) of \cite{hall1980martingale})
\begin{align}
    T_n
    &\Rightarrow \sum_{\ell=1}^{2} \sum_{x\in S} \sigma(\ell,x)w(\ell,x)\sqrt{\gamma(\ell,x)}G(\ell,x)\quad (stably)
\end{align}
as $n\rightarrow \infty$.\footnote{If a sequence of random variables $Y_n$ on a probability space $(\Omega, \mathcal{F}, P)$ converges weakly to $Y$, we say the convergence is {\em stable} if for all continuity points $y$ of the cumulative distribution function of $Y$ and for all measurable events $E$, the limit $\lim_{n \to \infty} P(\{Y_n \leq y\} \cap E) = Q_y(E)$ exists, and if $Q_y(E) \to P(E)$ as $y \to \infty$.}

Stable weak convergence implies that the following convergence of characteristic functions holds as well:
\begin{align}
    &E\bigg\{\exp\big(iT_n

+i\sum_{\ell=1}^2\sum_{x\in S}\tilde{w}(\ell,x)\gamma(\ell,x)\big)\bigg\}\\
    \rightarrow &E\bigg\{\exp\big(i\sum_{\ell=1}^{2}\sum_{x\in S} w(\ell,x)G(\ell,x)\sigma(\ell,x)\sqrt{\gamma(\ell,x)}+i\sum_{\ell=1}^{2} \sum_{x\in S}\tilde{w}(\ell,x)\gamma(\ell,x)\big)\bigg\}
\end{align}
as $n\rightarrow \infty$, for any deterministic choice of $\tilde{w}(\ell)=(\tilde{w}(\ell,x): x\in S), j=1,2$. The Cramer-Wold device therefore implies that
\begin{align}\label{eq: cramer wold weak convergence}
\left(\frac{\sum_{j = 1}^n D_j(\ell,x)}{\sqrt{n}} , \gamma(\ell,x): x\in S, \ell = 1,2\right)

    \Rightarrow \left(\sigma(\ell,x)\sqrt{\gamma(\ell,x)}G(\ell,x), \gamma(\ell,x): x\in S, \ell=1,2\right)
\end{align}
as $n\rightarrow \infty$. Consequently, since the $\gamma(\ell,x)$'s are almost surely  positive,
\begin{align}
\left(\frac{\sum_{j= 1}^n D_j(\ell,x)}{\sqrt{n}\gamma(\ell,x)}: x\in S, \ell=1,2\right)\Rightarrow   \left(\frac{\sigma(\ell,x)G(\ell,x)}{\sqrt{\gamma(\ell,x)}}: x\in S, \ell=1,2\right)
\end{align}
as $n\rightarrow \infty$. Because $\frac{\Gamma_n(\ell,x)}{n\gamma(\ell,x)}\xrightarrow{p} 1$ as $n\rightarrow \infty$, Slutsky's lemma implies that
\begin{align}
    &\sqrt{n}\left(\frac{\sum_{j = 1}^n D_j(\ell,x)}{\Gamma_n(\ell,x)}: x\in S, \ell=1,2\right)\\
    \Rightarrow& \bigg(\frac{\sigma(\ell,x)G(\ell,x)}{\sqrt{\gamma(\ell,x)}}: x\in S, \ell=1,2\bigg)\label{eq: Slutsky 1}
\end{align}
as $n\rightarrow \infty$. Finally, Result 2, (\ref{eq: Slutsky 1}), and another application of Slutsky's lemma imply that
\begin{align}
    &\sqrt{n}\left[\sum_{x\in S} \hat{\pi}_n(1,x)\frac{\sum_{j = 1}^n D_j(1,x)}{\Gamma_n(1,x)}-\sum_{x\in S}\pi_{n}(2,x)\frac{\sum_{j = 1}^n D_j(2,x)}{\Gamma_n(2,x)}\right]\\
    \Rightarrow& \sum_{x\in S}\frac{\pi(1,x)\sigma(1,x)G(1,x)}{\sqrt{\gamma(1,x)}}-\sum_{x\in S}\frac{\pi(2,x)\sigma(2,x)G(2,x)}{\sqrt{\gamma(2,x)}}
\end{align}
as $n\rightarrow \infty$, proving the Theorem.
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:var_lowerbound}]
Note that the Skorohod representation theorem together with Fatou's lemma applied to \eqref{eq:CLT} yields the following:
\begin{equation}
\label{eq:fatou_var_lowerbound}
    \liminf_{n\rightarrow \infty} n \Var(\hat{\alpha}_n - \alpha)  \ge \sum_{\ell=1,2}\sum_{x\in S}\pi^2(\ell,x)\sigma^2(\ell,x) E\left\{\frac{1}{\gamma(\ell,x)}\right\}.
\end{equation}
Using Jensen's inequality on the right hand side of \eqref{eq:fatou_var_lowerbound}, we obtain the result in \eqref{eq:var_lowerbound}, as required.  (Note that $E\{\gamma(\ell,x)\} > 0$ for all $\ell,x$ since we assumed the policy limits are almost surely positive.)
\end{proof}

\begin{proof}[Proof of Corollary \ref{cor:asymptotic_var_constant_TAR}]

First we show the following limits hold:
\begin{align}
\lim_{n \to \infty}& E \left\{ \sup_{\ell = 1,2; x \in S} \left| \frac{\hat{\pi}_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}/n} - \frac{\pi(\ell,x)}{\gamma(\ell,x)} \right| \right\} = 0; \label{eq:pi_over_gamma_limit1}\\
\lim_{n \to \infty}& E \left\{ \sup_{\ell = 1,2; x \in S} \left| \frac{\hat{\pi}_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}/n} - \frac{\pi(\ell,x)}{\gamma(\ell,x)} \right|^2 \right\} = 0.\label{eq:pi_over_gamma_limit2}
\end{align}
We know from Proposition \ref{prop: P convergence} that $\hat{\pi}_n \xrightarrow{p} \pi_n$ for all $\ell,x$.  Further, we know from the definition of policy limits that $\Gamma(\ell,x)/n \xrightarrow{p} \gamma(\ell,x)$ for all $\ell,x$.  Thus the vector $(\hat{\pi}_n, \Gamma_n/n)$ converges in probability to the vector $(\pi, \gamma)$.  Use the Skorohod representation theorem to construct a joint probability space on which these limits hold almost surely.  Then note that each of the terms inside the expectations are bounded in
\eqref{eq:pi_over_gamma_limit1}-\eqref{eq:pi_over_gamma_limit2}, so the desired results hold by the bounded convergence theorem.

For the next steps, we use the same definitions as in the proof of Theorem \ref{thm:CLT}, and refer the reader there for the relevant notation.  In particular, we define $D_j(\ell,x)$ as in that proof, and use the relationship in \eqref{eq:trans_to_Dj}.  We make the following two definitions:
\begin{align*}
 Y_n(\ell) &= \hat{\pi}_n(\ell) \hat{r}_n(\ell) - \pi(\ell)r(\ell) = \sum_{j = 1}^n \sum_{x \in S} \frac{\hat{\pi}_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}/n} \cdot \frac{D_j(\ell,x)}{n};\\
 Z_n(\ell) &= \sum_{j = 1}^n \sum_{x \in S} \frac{\pi(\ell,x)}{\gamma(\ell,x)} \cdot \frac{D_j(\ell,x)}{n}.
\end{align*}

Note that $\hat{\alpha}_n - \alpha = Y_n(2) - Y_n(1)$.  The main remaining step in our proof is to show that we can compute the scaled asymptotic variance of $Z_n(2) - Z_n(1)$, and to use this to upper bound the scaled asymptotic variance of $Y_n(2) - Y_n(1)$.

We now show the following limit holds:
\begin{equation}
\label{eq:Zn_var_limit}
\lim_{n \to \infty} \Var(\sqrt{n} (Z_n(2) - Z_n(1))) = \sum_{x \in S} \frac{\pi^2(\ell,x) \sigma^2(\ell,x)}{\gamma(\ell,x)}.
\end{equation}
Observe that $Z_n(\ell)$ is a weighted sum of martingale differences; thus we use orthogonality of martingale differences again.  In particular, $E\{Z_n(\ell)\} = 0$ for all $n$.  Thus $\Var(\sqrt{n} (Z_n(2) - Z_n(1))) = n E\{ (Z_n(2) - Z_n(1))^2 \}$.  Observe that:
\[ Z_n(1) Z_n(2) = \sum_{j = 1}^n \sum_{k = 1}^n \sum_{x,y \in S} \frac{\pi(1,x) \pi(2,y)}{\gamma(1,x)\gamma(2,y)} \frac{D_j(1,x)D_k(2,y)}{n}. \]
We show that $E\{D_j(1,x) D_k(2,y) \} = 0$.  If $j = k$, then the product $D_j(1,x) D_j(2,y) = 0$ since only one of the two chains $\ell = 1,2$ can be run at time $k$.  If $j > k$, then the tower property of conditional expectations is applied  as usual to give:
\[ E\{ E\{ D_j(1,x) | \mathcal{G}_k \} D_k(2,x) \} = 0. \]
The same holds of course if $j < k$.  Thus we have $E\{Z_n(1) Z_n(2)\} = 0$ for all $n$.  Finally, using \eqref{eq: D j variance} with $w(1,x) = \pi(1,x)/\gamma(1,x)$ and $w(2,x) = 0$, together with the Skorohod representation theorem and the bounded convergence theorem, it follows that:
\[ E \{ n Z_n(1)^2 \} \to \sum_{x \in S} \frac{\pi^2(1,x) \sigma^2(1,x)}{\gamma(1,x)}. \]
(Use of bounded convergence here requires assuming boundedness of rewards.)  An analogous result holds for the limit of $E \{ n Z_n(2)^2\}$.  Combining these steps, we obtain \eqref{eq:Zn_var_limit}.

Finally, we can establish the following upper bound:
\begin{equation}
\label{eq:var_limsup}
\limsup_{n \to \infty} n \Var(\hat{\alpha}_n - \alpha_n) \leq \sum_{\ell = 1,2} \sum_{x \in S} \frac{\pi^2(\ell,x) \sigma^2(\ell,x)}{\gamma(\ell,x)}.
\end{equation}

To prove this we upper bound the variance of $Y_n(2) - Y_n(1)$ in terms of the variance of $Z_n(2) - Z_n(1)$.  Note that $\Var(Y_n(2) - Y_n(1)) \leq E\{ (Y_n(2) - Y_n(1))^2 \}$.  Further, because $D_j(\ell,x)$ are bounded, there exist constants $M_1,M_2$ such that:
\begin{multline*}
(Y_n(2) - Y_n(1))^2 \leq (Z_n(2) - Z_n(1))^2 +M_1 \sup_{\ell = 1,2; x \in S} \left| \frac{\hat{\pi}_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}/n} - \frac{\pi(\ell,x)}{\gamma(\ell,x)} \right| \\
+  M_2 \sup_{\ell = 1,2; x \in S} \left| \frac{\hat{\pi}_n(\ell,x)}{\max\{\Gamma_n(\ell,x),1\}/n} - \frac{\pi(\ell,x)}{\gamma(\ell,x)} \right|^2.
\end{multline*}
Taking expectations on both sides, and applying Steps 2 and 3, establishes \eqref{eq:var_limsup}.  Combining \eqref{eq:var_limsup} with \eqref{eq:var_lowerbound} yields the desired result (note that $E\{\gamma(\ell,x)\} = \gamma(\ell,x)$ since the policy limits are almost surely constant).
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm: stationary optimality}]
First, we show that \eqref{eq:MLE_opt1}-\eqref{eq:MLE_opt2} has a unique optimal solution $\kappa^*$, with entries that are all positive.  It is straightforward to see that the solution to this problem will be  positive in all coordinates, since the objective function approaches infinity as any $\kappa(\ell,x)$ approaches zero (as all $\sigma(\ell,x)$ are positive).  Further, note that the objective function is strictly convex and $\mathcal{K}$ is convex and compact, and thus there must be a unique solution $\kappa^* \in \mathcal{K}$ to the optimization problem \eqref{eq:MLE_opt1}-\eqref{eq:MLE_opt2}.

Next, we show that the limit inferior of the scaled asymptotic variance of the MLE under any TAR policy with positive policy limits is bounded below by the optimal value of \eqref{eq:MLE_opt1}-\eqref{eq:MLE_opt2}.  This follows by applying Corollary \ref{cor:var_lowerbound}.  In particular, from Remark \ref{rem:markov_TAR}, we know $\gamma$ is a probability measure over the set $\mathcal{K}$ (cf.~Definition \ref{def: mathcal K}).  The set $\mathcal{K}$ is convex and compact, and so $\kappa=E\{\gamma\}\in \mathcal{K}$. In particular, as a consequence by applying \eqref{eq:var_lowerbound} we conclude that the optimal value of \eqref{eq:MLE_opt1}-\eqref{eq:MLE_opt2} is a lower bound to $\liminf_{n \to \infty} \Var(\hat{\alpha}_n - \alpha)$.

Finally, the fact that \eqref{eq:Astar_var} holds follows from Corollary \ref{cor:asymptotic_var_constant_TAR}.  The stationary Markov policy $A^*$ defined via \eqref{eq:Markov_from_kappa} has the constant policy limit $\kappa^*$ (cf.~Remark \ref{rem:markov_TAR}), so it is efficient.  The theorem follows.
\end{proof}

\section{Pseudocode for \OnlineETI}
\label{sec:online_pseudocode}

The pseudocode for \OnlineETI is prsented as Algorithm \ref{alg: reg cycle}.

\begin{algorithm}[ht]
\caption{\OnlineETI (Online Experimentation with Temporal Interference)}\label{alg: reg cycle}
\begin{algorithmic}[1]

\Procedure{Experiment}{initial state $x_0$}
\State Set initial state $X_0 = x_0$
\State Initialization: For $\ell = 1,2$, $x,y \in S$, set ${\hat{P}}_0(\ell,x,y)=\frac{1}{|S|}$; $\Gamma_0(\ell,x)=0$; $\Phi_0(\ell,x,y)=0$;
\State \indent $\Theta_0(\ell,x)=0$; $\Psi_0(\ell,x)=0$; $\Upsilon_0(\ell,x,y)=0$; $\hat{r}_0(\ell,x)=0$; $\hat{s}_0(\ell,x,y)=0$;
\State \indent $\hat{t}_0(\ell,x,y)=0$; $\hat{\pi}_0(\ell, x)=0$; $\hat{p}_0(\ell,x)=0.5$
\For{$n = 1, 2, \ldots$}
\State Set $A_{n-1} = \ell$ with probability $\hat{p}_{n-1}(\ell,x)$, i.e.:
\State \indent $A_{n-1} = 1$ if $U_{n-1} \leq \hat{p}_{n-1}(1,x)$, and $A_{n-1} = 2$ otherwise
\State Run chain $A_{n-1}$, and obtain reward $R_n$ and new state $X_n$

\State For all $\ell = 1,2$, $x,y \in S$:
\State \indent $\Gamma_n(\ell,x)\gets \Gamma_{n-1}(\ell,x)+I(X_{n-1}=x, A_{n-1}=\ell)$
\State \indent $\Phi_n(\ell,x, y)\gets  \Phi_{n-1}(\ell,x, y)+I(X_{n-1}=x, X_{n}=y, A_{n-1}=\ell)$
\State \indent $\Theta_n(\ell,x)\gets \Theta_{n-1}(\ell,x)+I(X_{n-1}=x, A_{n-1}=\ell)R_{n}$
\State \indent $\Psi_n(\ell,x,y)=\Psi_{n-1}(\ell,x,y)+I(X_{n-1}=x, X_{n}=y, A_{n-1}=\ell)R_{n}$
\State \indent $\Upsilon_n(\ell,x,y)\gets \Upsilon_{n-1}(\ell,x,y)+I(X_{n-1}=x, X_{n}=y, A_{n-1}=\ell)R_{n}^2$
\State \indent $\hat{P}_n(\ell,x,y)\gets \frac{\Phi_n(\ell,x,y)}{\max\{\Gamma_n(\ell,x), 1\}}$
\If{for both $\ell = 1,2$, $\hat{P}_n(\ell)$ is irreducible}
\State Set $\hat{\pi}_n(\ell)$ to be the unique steady state distribution of $\hat{P}_n(\ell)$
\State For $\ell =1,2$ and $x,y \in S$:
\State \indent $\hat{\Pi}_n(\ell)\gets e\hat{\pi}_n(\ell)$
\State \indent $\hat{\tilde{g}}_n(\ell,x)\gets \big(I-\hat{P}_n(\ell) + \hat{\Pi}_n(\ell)\big)^{-1}\hat{r}_n(\ell)$
\State \indent$\hat{r}_n(\ell,x)\gets \frac{\sum_{y\in S}\Psi_n(\ell,x,y)}{\max\{\Gamma_n(\ell,x), 1\}}$
\State \indent$\hat{s}_n(\ell,x,y)\gets \frac{\Psi_n(\ell,x,y)}{\max\{\Phi_n(\ell,x, y), 1\}}$
\State \indent$\hat{t}_n(\ell,x,y)\gets \frac{\Upsilon_n(\ell,x,y)}{\max\{\Phi_n(\ell,x, y), 1\}}$
\State \indent$\hat{\sigma}_n^2(\ell,x)\gets \sum_{y\in S} \hat{P}_n(\ell,x,y)[\hat{\tilde{g}}_n(\ell,y)$ $-$ $\sum_{z\in S}\hat{P}_n(\ell,x,z)\hat{\tilde{g}}_n(\ell,z)]^2$
\State \indent\ \  $+$ $\sum_{y\in S}\hat{P}_n(\ell,x,y)\big(\hat{t}_n(\ell,x,y)-\hat{s}_n(\ell,x,y)^2\big)$
\State Choose any $\hat{\kappa}_n$ in $\arg\inf_{\hat{\kappa}\in \mathcal{K}}\sum_{\ell=1}^{2} \sum_{x\in S} \frac{\hat{\pi}_n^2(\ell,x)\hat{\sigma}_n^2(\ell,x)}{\hat{\kappa}_n(\ell,x)}$
\State For all $x \in S$, $M_n(x) \gets \Gamma_n(1,x) + \Gamma_n(2,x)$
\If{$\hat{\kappa}_n(1,x) + \hat{\kappa}_n(2,x) > 0$ and $M_n(x) > 0$}
\State $\hat{p}_n(\ell,x) \gets (1-M_n(x)^{-1/2})\left(\frac{\hat{\kappa}_n(\ell,x)}{\hat{\kappa}_n(1,x)+\hat{\kappa}_n(2,x)}\right)$
\State \indent $+\frac{1}{2}M_n(x)^{-1/2}$ for $\ell = 1,2$, $x \in S$
\Else
\State $\hat{p}_n(\ell,x) = 0.5$ for $\ell = 1,2$, $x \in S$
\EndIf
\State $\hat{\alpha}_n \gets \hat{\pi}_n(2)\hat{r}_n(2)-\hat{\pi}_n(1)\hat{r}_n(1)$
\Else
\State $\hat{p}_n(\ell,x) \gets 0.5$
\State $\hat{\alpha}_n \gets 0$
\EndIf
\EndFor

\EndProcedure
\end{algorithmic}
\end{algorithm}

\section{Proofs: Section \ref{sec:online}}
\label{sec:proofs_online}

\begin{proof}[Proof of Theorem \ref{thm: alg efficiency}]

We establish that for \OnlineETI there holds:
\begin{align}
    \frac{1}{n} \Gamma_n(\ell,x)\xrightarrow{p} \kappa^*(\ell, x),
\end{align}
where $\kappa^*$ is the solution to \eqref{eq:MLE_opt1}-\eqref{eq:MLE_opt2}.

First, note that the forced exploration (i.e., the $M_n(x)^{-1/2}$ term in the definition of $\hat{p}_n(\ell,x)$) ensures that $\Gamma_n(\ell,x) \to \infty$ almost surely for all $\ell,x$.  To see this, note first that as long as $M_n(x) \to \infty$ almost surely, it must be the case that $\Gamma_n(\ell,x) \to \infty$ for $\ell = 1,2$ almost surely as well, due to the forced exploration term, the fact that $\sum_{k \geq 1} k^{-1/2}$ diverges, and the Borel-Cantelli Lemma.  Since the state space is finite, almost surely, there exists at least one state $x'$ that is visited infinitely often.  Thus almost surely, all states reachable from $x'$ in one step under either $P(1)$ or $P(2)$ must be visited infinitely often as well.  The same argument applies to those states, and so on.  Since the state space is finite, and both $P(1)$ and $P(2)$ are irreducible, this process exhausts all the states, and we conclude $M_n(x) \to \infty$ almost surely for all $x \in S$.

Next we show that for all $\ell,x,y$, $\hat{P}_n(\ell,x,y)$ converges to $P(\ell,x,y)$ almost surely.  For each $\ell,x$, it is convenient to define $T_m(\ell,x) = \inf \{ n : \Gamma_n(\ell,x) = m \}$.  By the standard strong law of large numbers, it follows that $\hat{P}_{T_m(\ell,x)}(\ell,x,y)  \to P(\ell,x,y)$ almost surely;
this is because $\hat{P}_{T_m(\ell,x)}(\ell,x,y)$ is the sample average of $m$ independent Bernoulli random variables, each with success probability $P(\ell,x,y)$.  Now observe that for $n$ such that $T_m(\ell,x) \leq n < T_{m+1}(\ell,x)$, $\hat{P}_n(\ell,x,y) = \hat{P}_{T_m(\ell,x)}(\ell,x,y)$; i.e., between successive visits to state $x$ in which policy $\ell$ is sampled, $\hat{P}_n(\ell,x,y)$ remains constant.  It follows therefore that $\hat{P}_n(\ell,x,y) \to P(\ell,x,y)$ almost surely as well.

We now use a compactness argument analogous to that used to establish \eqref{eq:pi_convergence} to show that $\hat{\pi}_n(\ell) \to \pi(\ell)$ almost surely.  Let $J$ be the first $n$ at which $\hat{P}_n(\ell)$ is irreducible for both $\ell = 1,2$.  The time $J$ is almost surely finite, because both chains are sampled with equal probability until time $J$, and because $P(\ell)$ is irreducible for $\ell = 1,2$.  Thus for the remainder of our argument, we condition on the almost sure event $J < \infty$.  Next, consider any subsequence $\{n_k\}$ along which, almost surely, $\hat{\pi}_{n_k}(\ell) \to \pi'(\ell)$.  (Note that in general, this is a random subsequence.)  Since $\hat{\pi}_{n_k}(\ell) \hat{P}_{n_k}(\ell) = \hat{\pi}_{n_k}(\ell)$ for all $k$, almost sure convergence of $\hat{P}_n(\ell)$ implies that $\pi'(\ell) P(\ell) = \pi'(\ell)$.  Thus $\pi'(\ell) = \pi(\ell)$ almost surely.  Since this is almost surely true for every convergent subsequence, we conclude that $\hat{\pi}_n(\ell) \to \pi(\ell)$ almost surely, as required.

Because rewards are bounded, and thus in particular have finite moments, an argument analogous to that above for $\hat{P}_n$ establishes that almost surely we have:
\[ \hat{r}_n(\ell,x) \to r(\ell,x) \]
and
\[ \hat{t}_n(\ell,x,y) - \hat{s}_n^2(\ell,x,y)^2 \to \Var(R_1 | A_0 = \ell, X_0 = x, X_1 = y). \]

When $J < \infty$, since each $\hat{P}_n(\ell)$ is irreducible, it follows that $\big(I-\hat{P}_n(\ell) + \hat{\Pi}_n(\ell)\big)^{-1}$ exists.  By continuity, conditioning on $J < \infty$, we have:
\[ \hat{\tilde{g}}(\ell,x) \to \tilde{g}(\ell,x) \]
almost surely as well, and thus:
\[ \hat{\sigma}^2(\ell,x) \to \sigma^2(\ell,x) \]
almost surely.

We now establish almost sure convergence of $\hat{\kappa}_n$ to $\kappa^*$.  To do this, for a distribution $\tilde{\pi}$ on the state space $S$ and a nonnegative vector $\tilde{\sigma}$, define the correspondence $K(\tilde{\pi},\tilde{\sigma})$ to be the set of minimizers of $\sum_{\ell = 1,2} \sum_{x \in S} \tilde{\pi}^2(\ell,x)\tilde{\sigma}^2(\ell,x)/\kappa(\ell,x)$ over $\kappa \in \mathcal{K}$; recall that $\mathcal{K}$ is compact so this correspondence is nonempty everywhere.  Further, observe that if $\tilde{\pi}$ and $\tilde{\sigma}$ are positive in all coordinates, then the minimizer is unique, i.e., $K$ is a function.
Then by Lemma \ref{lem:maximizer} below, $K$ is continuous in $\tilde{\pi}$ and $\tilde{\sigma}$ when they are both positive in all coordinates.  Since $\hat{\pi}_n(\ell) \to \pi(\ell)$ and $\hat{\sigma}_n^2(\ell,x) \to \sigma^2(\ell,x)$ almost surely, and both limits are positive in all coordinates, it follows that $K(\hat{\pi}_n, \hat{\sigma}_n) \to K(\pi, \sigma) = \kappa^*$ almost surely, and thus $\hat{\kappa}_n \to \kappa^*$ almost surely.

In particular, we thus know that almost surely, $\hat{\kappa}_n(\ell,x) > 0$ for all sufficiently large $n$.  As a result, it follows that $\hat{p}_n(\ell,x) \to p^*(\ell,x)$ almost surely, where:
\[ p^*(\ell,x) = \frac{\kappa^*(\ell,x)}{\kappa^*(1,x) + \kappa^*(2,x)}. \]

To complete the proof, we require some additional notation.  We define the following stochastic matrix:
\[ Q(x,y) = p^*(1,x) P(1,x,y) + p^*(2,x) P(2,x,y). \]
Note that this matrix is irreducible, and because $\kappa^* \in \mathcal{K}$, we can easily see that $Q$ has the unique stationary distribution given by:
\[ \zeta^*(x) = \kappa^*(1,x) + \kappa^*(2,x). \]
(See also the discussion in Remark \ref{rem:markov_TAR}.)

In addition, we define:
\[ \hat{Q}_n(x,y) = \frac{\sum_{j = 1}^n I(X_{j-1} = x, X_j = y)}{\max\{M_n(x),1\}}. \]
Observe that $\hat{Q}_n$ is a stochastic matrix.

We now show that $\hat{Q}_n \xrightarrow{p} Q$.  We rewrite $\hat{Q}_n(x,y)$ as follows:
\begin{equation}
\label{eq:hatQrewrite}
 \hat{Q}_n(x,y) = \sum_{\ell = 1,2} \hat{P}_{n}(\ell,x,y) \cdot \frac{\sum_{j = 1}^n I(X_{j-1} = x, A_{j-1} = \ell)}{\max\{M_n(x),1\}}.
\end{equation}

For each $x$ and $m$, let $S_m(x) = \inf \{ n \geq 0 : M_n(x) = m \}$; this is the time step at which the $m$'th visit to $x$ takes place.  Further, define $\tilde{A}_m = A_{S_m(x)}$; this is the policy sampled at the $m$'th visit to $x$.  Let $\mathcal{H}_m(x) = \sigma((X_j, U_j, V_j, j < S_m(x); X_{S_m(x)}))$ be the sigma field generated by randomness up to the $m$'th visit to $x$, but prior to the policy being chosen.  Finally, let $\hat{q}_m(\ell,x) = \hat{p}_{S_m(x)}(\ell,x)$.  Now observe that when $M_n(x) = m \geq 1$, we have:
\begin{align*}
 \frac{\sum_{j = 1}^n I(X_{j-1} = x, A_{j-1} = \ell)}{\max\{M_n(x),1\}} &= \frac{\sum_{i = 1}^m I(\tilde{A}_i = \ell)}{m}\\
 &=  \frac{\sum_{i = 1}^m I(\tilde{A}_i = \ell) - \hat{q}_i(\ell,x)}{m} + \frac{\sum_{i = 1}^m \hat{q}_i(\ell,x)}{m}.
\end{align*}
 The terms in the first sum on the right hand side of the previous expression form a martingale difference sequence adapted to $\mathcal{H}_i$.  Thus using orthogonality of martingale differences, we have:
 \[ \frac{1}{m^2}E\left \{ \left( \sum_{i = 1}^m I(\tilde{A}_i = \ell) - \hat{q}_i(\ell,x)\right)^2 \right \} \leq \frac{1}{4m}, \]
 which approaches zero as $m \to \infty$.  By Chebyshev's inequality, it follows that:
 \[ \frac{\sum_{i = 1}^m I(\tilde{A}_i = \ell) - \hat{q}_i(\ell,x)}{m} \xrightarrow{p} 0 \]
 as $m \to \infty$.  On the other hand, note that since $M_n(x) \to \infty$ almost surely, we also know that $S_m(x) \to \infty$ as $m \to \infty$ almost surely.  Thus it follows that:
 \[ \frac{\sum_{i = 1}^m \hat{q}_i(\ell,x)}{m} \to p^*(\ell,x) \]
almost surely as $m \to \infty$, and thus in probability as well.  Combining these insights, we conclude that:
\[  \frac{\sum_{j = 1}^n I(X_{j-1} = x, A_{j-1} = \ell)}{\max\{M_n(x),1\}} \xrightarrow{p} p^*(\ell,x) \]
as $n \to \infty$, and so returning to \eqref{eq:hatQrewrite}, we find that:
\[ \hat{Q}_n(x,y) \xrightarrow{p} \sum_{\ell=1,2} p^*(\ell,x) P(\ell,x,y)  = Q(x,y). \]

Next, observe that:
\begin{align*}
\frac{M_n(x)}{n} &= \frac{\sum_{j = 1}^n I(X_j = x)}{n} + \frac{I(X_0 = x) - I(X_n = x)}{n} \\
&= \left( \sum_{y \in S} \hat{Q}_n(x,y) \cdot \frac{\max\{M_n(y),1\}}{n} \right) + O_p\left(\frac{1}{n}\right).
\end{align*}

Since $M_n(x) \to \infty$ almost surely, in what follows we condition on $M_n(x) \geq 1$ for all $x$ and thus ignore the ``$\max$'' on the right hand side in the preceding expression.  Note that for all $n$, $\sum_{x \in S} M_n(x) = n$.  Thus using a compactness argument analogous to that used to establish \eqref{eq:pi_convergence}, it follows that:
\[ \frac{M_n(n)}{n} \xrightarrow{p} \zeta^*(x). \]

We can now complete the proof of the theorem.  We have:
\begin{align}
    \frac{1}{n} \Gamma_n(\ell,x)=& \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x, A_j=\ell) \nonumber\\
    =& \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x) p^*(\ell,x)+\frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x) \big(\hat{p}_j(\ell,x)-p^*(\ell,x)\big)\nonumber\\
    &+\frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x)\big(I(A_j=\ell)-\hat{p}_j(\ell,x)\big)\label{eq: Gamma for algorithm conv}
\end{align}
Because $I(X_j=x)\big(I(A_j=\ell)-\hat{p}_j(\ell, x)\big)$ is a martingale difference measurable with respect to $\mathcal{G}_j$, orthogonality of martingale differences implies that
\begin{align}
    E\bigg\{\bigg(&\frac{1}{n}\sum_{j=1}^{n} I(X_j=x)\big(I(A_j=\ell)-\hat{p}_j(\ell,x)\big)\bigg)^2\bigg\}\\
    &\leq  E\bigg\{\frac{1}{4} \cdot \frac{1}{n^2} \Gamma_{n}(\ell,x) \bigg\} \leq \frac{1}{4n}\\
    &\rightarrow  0
\end{align}
as $n\rightarrow \infty$. Therefore, by Chebyshev's inequality
\begin{align}\label{eq: convergence P(l) martingale 2}
    \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x)\big(I(A_j=\ell)-\hat{p}_j(
\ell,x)\big)\xrightarrow{p} 0
\end{align}
as $n\rightarrow \infty$. Also, since $\hat{p}_n(\ell,x) \to p^*(\ell,x)$ almost surely, we have:
\begin{align}\label{eq: constant c 1 x}
    \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x) \big(\hat{p}_j(\ell,x)-p^*(\ell,x)\big)\xrightarrow{p} 0.
\end{align}
Finally,
\[ \frac{1}{n} \sum_{j=0}^{n-1} I(X_j=x) p^*(\ell,x) = \frac{p^*(\ell,x) M_n(\ell,x)}{n} \xrightarrow{p} p^*(\ell,x) \zeta^*(\ell,x). \]
Combining the preceding results, we conclude that as $n \to \infty$ in (\ref{eq: Gamma for algorithm conv}), we have
\begin{equation}\label{eq: Gamma n with constant c}
    \frac{1}{n} \Gamma_n(\ell,x)\xrightarrow{p} \zeta^*(\ell,x)p^*(\ell,x) = \kappa^*(\ell,x)
\end{equation}
as $n\rightarrow \infty$, completing the proof of the theorem.
\end{proof}

\begin{lemma}
\label{lem:maximizer}
Suppose that the set $X$ is compact, the set $\Theta$ is open, and the real-valued function $f(\theta,x)$ is  continuous on the domain $\Theta \times X$.  Suppose further that for every $\theta \in \Theta$, there exists a unique $x^*(\theta) = \arg \min_{x \in X} f(\theta,x)$.  Then $x^*(\theta)$ is continuous in $\theta$.
\end{lemma}

\begin{proof}
Suppose that $\theta^{(n)} \to \theta$.  For all $n$ we have:
\begin{equation}
    \label{eq:f_lowerbound}
    f(\theta^{(n)}, x^*(\theta^{(n)})) \leq f(\theta^{(n)}, x^*(\theta)).
\end{equation}
Since $X$ is compact, let $\{n_k\}$ be a subsequence such that $x^*(\theta^{(n_k)}) \to x'$ as $k \to \infty$.   Taking limits on both sides of \eqref{eq:f_lowerbound} along the sequence $\{n_k\}$, we obtain:
\[ f(\theta, x') \leq f(\theta, x^*(\theta)). \]
Since $x^*(\theta)$ is unique, this is only possible if $x' = x^*(\theta)$.  Since every convergent subsequence must have the limit $x'$, we conclude that $x^*(\theta^{(n)}) \to x^*(\theta)$ as $n \to \infty$, as required.
\end{proof}


TITLE: Question about factoring/condensing equation rules
QUESTION [0 upvotes]: I have the equation $x^2 - 6x = 72$ and then $x^2 - 6x - 72 = 0$ that's supposed to turn into $(x-12)(x+6)$. 72/6 = 12. So could just do that with any equation that? Divide the end thing with the middle coefficient of x to get the thing for the first set of parentheses? Or is it just a coincidence?

REPLY [1 votes]: This is a coincidence.
When the solutions are $a,b$:

the middle term is $-a-b$ (here it is $-(-6)-12 = -6)$)
the end term is $ab$ (here: $-6\times 12 = -72$).

The formula
$$
-\frac{a+b}{ab}
$$is not a solution in general.

This is a coincidence because here you have $-a-b = a$.


TITLE: For what values will f(x) be necessarily one-one?
QUESTION [2 upvotes]: Let $g:\mathbb{R}\to\mathbb{R}$ be a differentiable function such that
  $|g'(x)|\le M$ for all $x\in \mathbb{R}$. For what values of
  $\epsilon$ will the function $f(x)=x+\epsilon g(x)$ will be
  necessarily one-one?

Not getting any idea how to proceed, maybe Mean value theorem will work.

REPLY [2 votes]: Yes, well Rolle's theorem is enough.
Let $a, b$ be such that $f(a)=f(b)$. There there is a $c\in [a, b]$ such that $f'(c)=1+\epsilon g'(c)=0$. Since $|g'(c)|\leq M$. Then if $|\epsilon|<\frac{1}{M}$ you are good.

REPLY [0 votes]: The other answers are totally correct...
Next time, when you have no idea how to proceed, try a few simple cases! Let $M=1$ and let $g(x)=x$, or $g(x)=-x$, or $g(x)=\sin(x)$. Then try $\epsilon=0$, $\epsilon=1/2$, $\epsilon=1$, and $\epsilon=2$.
For each of these choices, write down $f(x)$. Graph it if you like. Is $f$ one-to-one? Now that you've looked at these cases, what patterns do you notice? Try $M=2$ or $M=1/2$. How do you need to adjust $g$ and $\epsilon$?
Keep going until you have a hypothesis. Then try to prove your hypothesis. You'll find it much easier to select the right tools when you know what the answer is!


TITLE: Is this function, $f$, a homomorphism under addition and subtraction?
QUESTION [1 upvotes]: Allow me to construct $f$
$\textbf{Lemma}$: For all $x \in [0,1]$, there exists a sequence $\{b_k\}_{k=1}^\infty$ such that
$$\forall k \in \mathbb{N}, b_k \in \{0,1\}$$
And
$$x = \sum_{k=1}^\infty \frac{b_k}{2^k}$$
$\textbf{Proof}$: For any number $x \in [0,1]$, it has a base 2 form (binary) consisting of only $0$ before the Radix point. For example,
$$1.0_{10} = 0.11\bar 1_2$$
$$0.5_{10} = 0.10\bar 0_2$$
$$0.0_{10} = 0.00\bar 0_2$$
Consider the sequence $\{b_k\}_{k=1}^\infty$, where $b_k$ is the value at the $k$th location past the Radix point of $x$'s base 2 form.
Because $b_k$ is a bit in a base 2 number, for all $k \in \mathbb{N}$, $b_k \in \{0, 1\}$. In addition, because of the method used to convert base 2 numbers to base 10, and $x \in [0,1]$
$$x = \sum_{k=1}^\infty \frac{b_k}{2^k}$$
And our lemma is true.
Using this Lemma, we construct a sequence of functions
$$\{b_k(x)\}_{k=1}^\infty:\ [0,1] \rightarrow \{0, 1\}$$
Such that for some $x \in [0,1]$ and some corresponding $\{b_k\}_{k=1}^\infty$ as defined in our lemma, $b_k(x) = b_k$.
Notice that for all $x \in [0,1]$,
$$x = \sum_{k=1}^\infty \frac{b_k(x)}{2^k}$$
We will now use this function $b_k(x)$ to construct $f:\ [0,1] \rightarrow [0,1]$
Define
$$f(x) := \sum_{k=1}^\infty \frac{2b_k(x)}{3^k}$$
Is this function a homomorphism under addition and subtraction? That is for $x,y \in [0,1]$, does
$$(x+y) \in [0,1] \Rightarrow f(x + y) = f(x) + f(y)$$
$$(x-y) \in [0,1] \Rightarrow f(x - y) = f(x) - f(y)$$
The purpose of this is to show that $f$ is continuous. If $f$ is homomorphic, it is not too hard to prove. I have tried to prove it is continuous without this assumption but keep getting stuck.
The function intrigued me and can be thought of as first converting $x$ to binary, replacing the 1's with 2's, and then converting it from ternary to decimal.

REPLY [2 votes]: This map is not additive (even when restricted to cases it is well-defined).
Consider $x = y  = 1/3$.  Then
$$
x = y = 1/3 = 0.\overline{01}_2
\\
x+y = 2/3 = 0.\overline{10}_2
\\
f(x) = f(y) = 0.\overline{02}_3 = 1/4
\\
f(x+y) = 0.\overline{20}_3 = 3/4
$$
and $f(x+y) \ne f(x)+f(y)$.

Is $f$ continuous?  Yes, it is continuous at the points with unique binary expansion.  For counterexample we have to look at a point with two different binary expansions.
$$
1/2 = 0.1\overline{0}_2 = 0.0\overline{1}_2 .
$$
So conider a sequence $a_n$,
$$
a_{2n} = 0.10^n1\overline{0}_2,\\
a_{2n+1} = 0.1^n\overline{0}_2 .
$$
where $0^n$ means $n$ zeros in a row, $1^n$ means $n$ ones in a row.
Then $a_n$ converges to $1/2$, with terms alternately above and below $1/2$.
But $f(a_n)$ does not converge.  The even terms $f(a_{2n})$ converge
to $2/3$ from above.  The odd terms $f(a_{2n+1})$ converge
to $1/3$ from below.


TITLE: Discrete Probability: You are given a string of length n, in which each character is a uniformly random element of {a.b.c}
QUESTION [0 upvotes]: Question: A string $s_1s_2\ldots s_n$ is a palindrome if $s_1s_2\ldots s_{n-1}s_n = s_ns_{n-1}...s_2s_1 $; i.e reading the string from left to right gives the same result as reading the string from right to left.
Let $n \ge 3$, be an odd integer. You are given a string of length $n$, in which each character is a uniformly random element of $\{a,b,c\}$. The characters are independent of each other. What is the probability that this bitstring is a palindrome?

Answer: $(1/3)^{(n-1)/2}$

Attempt:
I took $n=3$, with a string aba to make a palindrome. For the first character a, I have 3 options and must choose one of them. For b, I have 2 options and I must choose 1. And for a, I have 1 option and must pick 1 to make it a palindrome.
I used the binomial for all three cases and got
$$
Pr(A_1) = \binom{3}{1}*(1/3)^1*(1 - 1/3)^2 = 4/9\\
Pr(A_2) = \binom{2}{1}*(1/2)^1*(1-1/2)^1 = 1/2\\
Pr(A_3) = \binom{1}{1}*(1/2)^1*(1/2)^0 = 1/2
$$
Finally,
$$Pr(A) = (4/9)*(1/2)*(1/2) = 1/9 = (1/3)^{(n+1)/2}
\quad {\text for } \quad n=3$$
But according to the answer, it should be $Pr(A) = 1/3$. Where did I go wrong?

REPLY [1 votes]: The idea is, out of $n = 2k+1$ positions, you pick the first $k+1$, then fix the last $k$ to be exactly like the first $k$ in reverse order. The number of such strings is $3^{k+1}$. The total number of string in question is $3^n=3^{2k+1}$, so the probability would be
$$
3^{k+1}/3^n = 3^{k+1-(2k+1)} = 3^{-k}.
$$


TITLE: Optimal Control Problem with Fraction Objective
QUESTION [0 upvotes]: $\mu$ and $\lambda$ are two positive constants and $\mu > \lambda$. $c$ and $b$ are two positive constants and $c < b$. How to solve the following optimization problem?
\begin{align}
\max_{T\ge 0, H_t} & \, \frac{W_0}{M_0} \\
s.t. & \, \frac{dW_t}{dt} = \mu W_t - \mu H_t, H_t \ge W_t + c, W_T = 0. \\
     & \frac{dM_t}{dt} = \lambda M_t - \lambda H_t, H_t \ge M_t + b, M_T = 0.
\end{align}

REPLY [0 votes]: Using a state space formulation with the state vector, $x_t$, as $\begin{bmatrix} W_t \\ M_t \end{bmatrix}$ and $H_t$ as the input, $u_t$,
$$\begin{bmatrix}
\dot{W_t} \\
\dot{M_t} \\
\end{bmatrix} = \begin{bmatrix} \mu & 0 \\ 0 & \lambda \end{bmatrix} \begin{bmatrix} W_t \\ M_t \end{bmatrix} + \begin{bmatrix} -\mu \\ -\lambda \end{bmatrix} H_t \\
\dot{x}_t = Ax_t + Bu_t$$
Taking its Laplace transform,
$$sX(s) - x_0 = AX(s) + BU(s) \\
X(s)(sI - A) = BU(s) + x_0 \\
X(s) = (sI - A)^{-1}(BU(s) + x_0) \\
x_t = \mathcal{L}^{-1}[(sI-A)^{-1}(BU(s) + x_0)] \\
\begin{bmatrix} W_t \\ M_t \end{bmatrix} =  \begin{bmatrix} -\mu e^{\mu t}* H_t + e^{\mu t}W_0 \\ -\lambda e^{\lambda t}*H_t + e^{\lambda t}M_0
\end{bmatrix}$$
A little algebra gives us
$$W_0 = (W_t  + \mu e^{\mu t} * H_t )e^{-\mu t}\\
M_0 = (M_t + \lambda e^{\lambda t} * H_t )e^{-\lambda t}
$$
Using $W_T = M_T = 0$, we get
$$W_0 = (\mu e^{\mu T} * H_T) e^{-\mu T} \\
M_0 = (\lambda e^{\lambda T} * H_T) e^{-\lambda T}$$
Since $e^{\mu T}, e^{\lambda T}$ and $H_T$ are constants for a particular $T$, their convolution w.r.t time yields $te^{\mu T}H_T $ and $te^{\lambda t}H_T $.
Therefore, the objective function becomes $\frac{W_0}{M_0} = \frac{\mu}{\lambda}$, which is independent of $T, H_t$.


TITLE: Selection vs Grouping
QUESTION [0 upvotes]: Question 1: The total number of different combinations of these letters can be made from letters of the word 'MISSISSIPPI"?
Question 2: How many different words can be formed with the letters of the word 'MISSISSIPPI'?
My question: What is the difference between above two questions which would then help me understand how to calculate the answers?
I understand question 1 involves selecting from set of alike and different objects and question 2 involves group. I want to understand why.

REPLY [0 votes]: A combination refers to the selection of a subset of the elements in some specified collection, usually a set.  In this case, you are selecting a subset of a multiset since some of the letters in MISSISSIPPI are repeated.  In a combination, what matters are which objects are selected, not the order in which they are selected.
A word is a sequence of characters from some specified alphabet.  The order of the letters in the string matters, so IMSS is considered to be different from MISS.


TITLE: Do all holomorphic functions on $\{z^2 + w^2 = 1\}$ extend to $\mathbb{C}^2$?
QUESTION [4 upvotes]: Let
$$X = \{(z, w) \in \mathbb{C}^2 : z^2 + w^2 = 1\}.$$
Is there a holomorphic function $f : X \to \mathbb{C}$ which do not extend to a holomorphic function on all of $\mathbb{C}^2$?

I tried to find an example of the form $f(z, w) = \frac{1}{g(z, w)}$, where $g(z, w)$ is a holomorphic function which has zeros, but none that lie in $X$. But I couldn't find any.

REPLY [2 votes]: Here is one reason that you could not find a counterexample. Say you have $\psi(z,w)$ a holomorphic function on $\mathbb{C}^2$ that has no zeroes on $\{\phi=0\}$, that is $\phi$ and $\psi$ have no common zeroes.  Then take $\frac{1}{\psi(z,w)}$ and somehow get a contradiction. Now it turns out that if two $\phi$, $\psi$ have no common zeroes then there exist other two functions $a$, $b$ such that
$$a \phi + b \psi = 1$$
Therefore, on $\{\phi=0\}$ we have $\frac{1}{\psi} = b$, which extends. Uff...
Now, a general approach to the extension of functions from $\{\phi=0\}$ to the whole space.
Let $f$ be holomorphic on $X=\{\phi=0\}$. There exists an open cover $(U_n)_n$ of the whole space $\mathbb{C}^2$ and a family of holomorphic maps $F_n$ on $U_n$ such that
$$F_n\ _{\mid X\cap U_n} = f_{\mid X\cap U_n}$$
that is, $F_n$ locally extends $f$ from $X\cap U_n$ to $U_n$. Now, the problem is that $F_n$ do not piece together to form a function on $\mathbb{C}^2$. In other words,
$$F_m\ _{U_m \cap U_n} \not= F_n\ _{U_m \cap U_n}$$
just yet. However,
$$F_m\ _{U_m \cap U_n\cap X} = F_n\ _{U_m \cap U_n\cap X}$$
Now, if for a holomorphic function $G$ on $U$ open subset of $\mathbb{C}^2$ we have
$$G_{\mid U \cap \{\phi=0\}} = 0$$
then
$$G = \phi\cdot H$$
for some holomorphic function on $U$ ( the converse is obvious). This is not difficult to prove, but requires an argument. Let's leave it for now.
In any case, we have
$$(F_m - F_n)_{\mid U_m \cap U_n} = \phi\cdot G_{m n}$$
for some function $G_{mn} \colon U_{mn} \to \mathbb{C}$, holomorphic.
Now, we would like to write
$$G_{mn} = H_m- H_n$$
for some functions $H_\colon U_m \to \mathbb{C}$. That would give us
$$F_m - F_n = \phi( H_m - H_n)$$
and so
$$F_m - \phi \cdot H_m = F_n - \phi \cdot H_n$$
on $U_m\cap U_n$
and so
$$\tilde F_n \colon = F_n - \phi \cdot H_n$$
piece together into a function on $\mathbb{C}^2$ that restricts to $f$.
How to get the $H_n$'s?  We have
$$G_{mn}+ G_{nk}+ G_{km}= 0$$ on $U_m\cap U_n\cap U_k$ so they form a cocycle (Cech cohomology). Now, every cocycle is in fact a coboundary ( this follows from some existence result for the $\bar \partial $ problem).
Recommended text: Hormander, Several Complex Variables
Note: this result holds in general: if $X$ is a complex submanifold of $\mathbb{C}^n$, and $f\colon X\to \mathbb{C}$ is holomorphic, then there exists $F\colon \mathbb{C}^n$ that restricts to $f$. The proof is similar, but there are complications. It would be essentially the same if $X$ was the zero set of $\phi$, with $0$ a regular value.  In codimension larger than $1$  one deals with "sheaves of (ideals of) holomorphic functions", and some discipline is required.
Why is this more complicated than the smooth case? There we have the partition of $1$, something that does not exists in the holomorphic case.


TITLE: Euler-Mascheroni constant: understanding why $\lim_{m\rightarrow \infty} \sum_{n=1}^{m} (\ln (1 + \frac{1}{n})-\frac{1}{n+1})= 1 - \gamma$
QUESTION [3 upvotes]: I am trying to understand why the Euler-Mascheroni constant $\displaystyle \gamma = \lim_{n \rightarrow \infty} \left ( \sum_{k=1}^n \frac{1}{k} - \ln n \right )$ is equal to $1 - \displaystyle \int_{1}^{\infty} \frac{t-[t]}{t^2}\; \mathrm{d}t$ where $[t]$ is the floor function.
There has been an answered question here already:
Integral form for the euler-mascheroni gamma constant using floor function
However, there is one line I do not understand and will appreciate help on explaining why the following equality is true:
$$ \lim_{m\rightarrow \infty} \sum_{n=1}^{m} (\ln (1 + \frac{1}{n})-\frac{1}{n+1})= 1 - \gamma $$

REPLY [5 votes]: However, there is one line I do not understand and will appreciate help on explaining why the following equality is true: $$\lim_{m\to\infty} \sum_{n=1}^m \left( \ln \left(1 + \tfrac{1}{n}\right) - \frac{1}{n+1}\right) = 1-\gamma$$

Observe that $\ln \left(1 + \frac{1}{n}\right) = \ln (n+1) - \ln n \implies \displaystyle\sum_{n=1}^m \ln \left(1 + \frac{1}{n}\right) = \ln (m+1)$ (it telescopes).
Therefore $$\sum_{n=1}^m \left(\ln \left(1 + \tfrac{1}{n}\right) - \frac{1}{n+1}\right) = \ln (m+1) - \sum_{n=1}^{m+1} \frac{1}{n} + 1$$
and $$\ln (m+1) - \sum_{k=1}^{m+1} \frac{1}{n} \to -\gamma$$ as $m\to\infty$ by definition.


TITLE: What is the difference between $\{1, 2\}\cup\{3\}$ and $\{1, 2, 3\}$?
QUESTION [3 upvotes]: I have a simple question related to set theory.
Is there any difference between the following two sets?
What is the difference between $\{1, 2\}\cup\{3\}$ and $\{1, 2, 3\}$?

REPLY [3 votes]: The way that we show two sets are equal is by showing that every thing in one set is in the other set, and vice versa.
i.e. $$A=B \text{ if and only if } A\subseteq B \text{ and }B\subseteq A$$
Since union is defined to be the set of elements in both sets in the union, it is obvious in your situation that the two sets in question are equal.


TITLE: Sum of squares of characters
QUESTION [2 upvotes]: Given a finite Abelian group $G$, I am interested in the sum $$ \sum_{\chi} \chi^2(g) $$ for some element $g \in G$ and the sum runs over the characters of $G$.
I tried using the identity $\chi^2(g) = \chi(g^2)$ and changing the above into a usual character sum. Is this correct or am I missing something?

REPLY [1 votes]: In general, the Second Orthogonality Relation tells you for a general finite group $G$ and $g,h \in G$
$$\sum_{\chi \in Irr(G)}\chi(g)\overline{\chi(h)}= 0 \text{  if  }g \nsim h \text{  and  } = |C_G(g)| \text{  if  } g \sim h. $$
(Here $\sim$ denotes conjugation) Hence if $G$ is abelian and $\chi$ linear, we have
$$\sum_{\chi \in Irr(G)} \chi^2(g)=\sum_{\chi \in Irr(G)}\chi(g)\overline{\chi(g^{-1})}=0 \text{  if  } g \neq g^{-1} \text{and  } =|G| \text{  if } g^2=1.$$
If you want to do some calculations: see for example here (character table of $C_6$), and try an element of order $2$ and of order $3$).
There is even a generalization to groups $G$ not necessarily being abelian. If $g \in G$ and $g \sim g^{-1}$, then $g$ is called a real element. The trivial element (identity) is obviously real, also all elements of order $2$ of the center $Z(G)$. One has
$$\sum_{\chi \in Irr(G)} \chi^2(g)=0 \text{  if  } g \text{  is not real  } \text{  and  } =|C_G(g)| \text{ if } g \text { is real  }.$$
If $|G|$ is odd, then $G$ does not contain any non-trivial real elements. See also here.