TITLE: Show that there is $C_1,C_2$ s.t. $C_1\log(N)\leq\|D_N\|_{L^1(\mathbb S^1)}\leq C_2\log(N)$ where $D_N$ is the dirichelet kernel.
QUESTION [0 upvotes]: Let $D_N=\frac{\sin(\pi(2N+1)x)}{\sin(\pi x)}$ the dirichlet kernel.
Show that there is $C_1,C_2$ s.t. $$C_1\log(N)\leq\|D_N\|_{L^1(\mathbb S^1)}\leq C_2\log(N)$$
where $\mathbb S^1=\mathbb R/\mathbb Z$ and $$\|D_N\|_{L^1(\mathbb S^1)}=\int_{\mathbb S^1} |D_N(x)|dx.$$
I have no idea on how to proceed. Any idea would be welcome.

REPLY [1 votes]: Upper bound
The contribution of $|x|<1/N$ is $O(1)$. The contribution of $|x|>1/N$ is bounded by $\int_{1/N}^\pi x^{-1}\,dx = O(\log N)$.
Lower bound
Consider the set where $|\sin(\pi(2N+1)x)|\ge 1/\sqrt{2}$. It's a union of some intervals $[a_n, b_n]$. Note that $b_n-a_n = a_{n+1}-b_n$. Also, the denominator on $[a_n, b_n]$ is about constant, $\sim 1/b_n$. And the same can be said about $[b_n,a_{n+1}]$. The conclusion is that integrating $1/|\sin \pi x|$ over $\bigcup_n [a_n,b_n]$ yields $\ge c\int_{a_1}^{\pi}x^{-1}\,dx$ with some $c>0$. This evaluates to $\Omega(\log(1/a_1))=\Omega(\log N)$.


text:
\begin{document}

\title{Inverse Optimal Stopping\\
\bigskip{}
\today}

\author{Thomas Kruse and Philipp Strack}
\begin{abstract}
Let $X$ be a one-dimensional diffusion and $g$ a payoff function
depending on time and the value of $X$. The paper analyzes the inverse
optimal stopping problem of finding a time-dependent function $\pi:[0,T]\to\mathbb{R}$
such that a given stopping time $\tau^{\star}$ is a solution of the
stopping problem $\sup_{\tau}\mathbb{E}\left[g(\tau,X_{\tau})+\pi(\tau)\right]\,.$

Under regularity and monotonicity conditions, there exists a solution
$\pi$ if and only if $\tau^{\star}$ is the first time $X$ exceeds
a time-dependent cut-off $b$, i.e. $\tau^{\star}=\inf\left\{ t\ge0\,|\, X_{t}\ge b(t)\right\} \wedge T\,.$
We prove uniqueness of the solution $\pi$ and derive a closed form
representation. The representation is based on the process $\tilde{X}$
which is a version of the original diffusion $X$ reflected at $b$,
\[
\pi(t)=\mathbb{E}\left[\int_{t}^{T}(\partial_{t}+\mathcal{L}g)(s,\tilde{X}_{s})\mathrm{d}s\,|\,\tilde{X}_{t}=b(t)\right]\,.
\]
The results lead to a new integral equation characterizing the stopping
boundary $b$ of the stopping problem $\sup_{\tau}\mathbb{E}\left[g(\tau,X_{\tau})\right]$.
\medskip{}

\textit{Keywords:} Optimal Stopping, Reflected Stochastic Processes,
Dynamic Mechanism Design, Dynamic Implementability, \medskip{}

\textit{MSC 2010: 91B02, 91A60, 60G40, 62L15}
\end{abstract}

\thanks{{\footnotesize{}\qquad{}Thomas Kruse, University of Duisburg-Essen,
Thea-Leymann-Str. 9, 45127 Essen, Germany. Email: thomas.kruse@univ-evry.fr;}}

\thanks{{\footnotesize{}\qquad{}Philipp Strack, University of Califonia,
Berkeley, 513 Evans Hall, Berkeley, 94720 California, USA. Web: \href{http://www.philippstrack.com}{http://www.philippstrack.com},
Email: philipp.strack@gmail.com. }}

\thanks{{\footnotesize{}\qquad{}We would like to thank Stefan Ankirchner,
Dirk Bergemann, Paul Heidhues, David Hobson, Monique Jeanblanc, Daniel
Krähmer, Benny Moldovanu, Jenö Pál, Goran Peskir, Sven Rady, Albert
Shiryaev, Juuso Toikka and seminar audiences in Austin, Bonn, HU Berlin,
Berkeley, Bielefeld, Boston, Caltech, Columbia, Duke, Harvard, Maastricht,
Microsoft Research NE, MIT theory camp, Northwestern, NYU, Paris Evry,
Toronto, University College London, UPenn, Warwick, Yale for many
helpful comments and suggestions. All remaining errors are our own.
Financial support by the Bonn Graduate School of Economics, the Bonn
International Graduate School of Mathematics, the German Research
Foundation (DFG), the Hausdorff Center for Mathematics, the SFB TR
15 and the French Banking Federation through the Chaire ``Markets
in Transition'' is gratefully acknowledged.}}

\maketitle
\newpage{}

\section*{Introduction}

One method to solve optimal stopping problems in a Markovian framework
is to identify the stopping region and its complement the continuation
region. Optimal stopping times are then given as first hitting times
of the stopping region. The \textit{inverse} optimal stopping problem
introduced here consists of modifying the payoff of a stopping problem
in such a way that it is optimal to stop at the first time when a
\textit{given} set is hit. The set of admissible modifications is
restricted by only allowing to add a time-dependent function to the
original payoff.

To fix ideas, consider the continuous-time, finite horizon stopping
problem $\sup_{\tau\in\mathcal{T}}\mathbb{E}\left[g(\tau,X_{\tau})\right]$,
where $\mathcal{T}$ is the set of stopping times with values in $[0,T]$,
$X$ is a one-dimensional diffusion and $g$ is a smooth payoff function.
A deterministic function $\pi:[0,T]\to\mathbb{R}$ is called a transfer.
We say that a set $A\subset[0,T]\times\mathbb{R}$ is implemented
by a transfer $\pi$ if the first time $\tau_{A}$ when $X$ hits
$A$ is optimal in the stopping problem with payoff $g+\pi,$ i.e.
if
\begin{equation}
\tau_{A}\in\argsup_{\tau\in\mathcal{T}}\mathbb{E}\left[g(\tau,X_{\tau})+\pi(\tau)\right].\label{eq:impl_def_intro}
\end{equation}

Inverse optimal stopping problems play an important role in different
economic situations. One example are dynamic principal-agent models:
There is an agent who \textit{privately} observes the stochastic process
$X$ and aims at maximizing her expected payoff $\sup_{\tau\in\mathcal{T}}\mathbb{E}\left[g(\tau,X_{\tau})\right]$
from stopping the process. The principal observes the stopping decision
of the agent, but not the realization of the process. She aims at
inducing the agent to take a particular stopping decision given by
the hitting time $\tau_{A}$. In order to influence the agent's stopping
decision the principal commits to a transfer $\pi$ -- a payment which
is due at the moment when the agent stops. The principal needs to
construct the transfer $\pi$ in such a way that $\tau_{A}$ becomes
optimal in the modified stopping problem $\sup_{\tau\in\mathcal{T}}\mathbb{E}\left[g(\tau,X_{\tau})+\pi(\tau)\right]$.
 For example, the agent could be a firm that has developed a new
technology and now has to decide when to introduce it to the market
place. The firm observes private signals regarding the demand, and
this knowledge changes over time. The principal is a social planner
who also takes the consumer surplus of the new technology into account
and hence prefers a different stopping decision than the firm. The
inverse optimal stopping problem analyzes the question how the planner
can align the preferences of the firm by subsidizing the market entry
through a transfer.   For further examples and applications to revenue
management we refer to \citet{krusestrack2013optimal}, where inverse
optimal stopping problems have been introduced in a discrete-time
framework.

The main result (Theorem \ref{thm:Cut-offs_implementable}) states
that all cut-off regions $A=\left\{ (t,x)\,|\, x\ge b(t)\right\} $
are implementable provided that the boundary $b$ is càdlàg and has
summable downwards jumps. Moreover, we suppose that a so-called single
crossing condition is satisfied. It requires that the expected gain
of waiting an infinitesimal amount of time is non-increasing in the
value of the process $X.$ Formally, we suppose that the function
\begin{equation}
x\mapsto\lim_{h\searrow0}\frac{1}{h}\mathbb{E}\left[g(t+h,X_{t+h}^{t,x})-g(t,x)\right]=(\partial_{t}+\mathcal{L})g(t,x)\label{eq:single_crossing_intro}
\end{equation}
is non-increasing, where $\mathcal{L}$ denotes the generator of the
diffusion $X$. Furthermore, we show that the solution $\pi$ implementing
the cut-off region $A=\left\{ (t,x)|x\ge b(t)\right\} $ admits the
following closed form representation

\begin{equation}
\pi(t)=\mathbb{E}\left[\int_{t}^{T}(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]\,.\label{eq:transfer_intro}
\end{equation}

Here $(\tilde{X}_{s}^{t,b(t)})_{s\geq t}$ denotes the unique process
starting on the barrier $b(t)$ at time $t$ which results from reflecting
the original process $X$ at the barrier $(b(s))_{s\in[t,T]}$ . For
the existence and uniqueness of $\tilde{X}$ for time-dependent barriers
with jumps we refer to \citet{rutkowski1980stochastic}. The proof
of Theorem \ref{thm:Cut-offs_implementable} employs solely probabilistic
arguments. We derive comparison principles for the original process
$X$ and its reflected version $\tilde{X}$. Together with the single
crossing condition they allow to verify that the transfer $\pi$ from
Equation (\ref{eq:transfer_intro}) indeed implements the cut-off
region $A$. This approach requires only weak regularity assumptions
on the model parameters. In particular, the boundary $b$ of the cut-off
region $A$ to be implemented is allowed to have jumps. Moreover,
we do not impose an ellipticity condition on the diffusion $X$.

There is a broad literature on reflected diffusions and their connection
to solutions of linear partial differential equations (PDE) with Neumann
boundary conditions (see e.g. \citet{watanabe1971stochastic}, \citet{karoui1978probleme}
or \citet{chaleyat1980reflexion}). One can use these Feynman-Kac
type formulas to study the Hamilton-Jacobi-Bellman (HJB) equation
associated to the stopping problem (\ref{eq:impl_def_intro}). For
discontinuous barriers $b$, however, the transfer given by Equation
(\ref{eq:transfer_intro}) has jumps (see Proposition \ref{prop:Properties_transfer})
and thus the value function of the stopping problem is discontinuous
as well. Therefore, the value function is only expected to solve the
associated HJB equation in a weak (e.g. viscosity) sense. The purely
probabilistic approach presented here circumvents all the technical
difficulties arising in a PDE characterization of a discontinuous
value function. We give a formal derivation of Equation (\ref{eq:transfer_intro})
based on the HJB equation in Section \ref{sub:Constrained-Processes}.

As shown in \citet{kotlow1973}, \citet{jacka1992finite} and \citet{villeneuve2007threshold}
the single crossing condition (or a weaker version of it) ensures
that the stopping region in stopping problems of the form $v(t,x)=\sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[g(\tau,X_{\tau}^{t,x})\right]$
is of cut-off type, i.e. there exists a barrier $b:[0,T]\to\mathbb{R}$
such that $x\ge b(t)$ if and only if $v(t,x)=g(t,x)$. In Proposition
\ref{prop:only_cut-offs_implementable} we show that this result translates
to implementable regions. We introduce the notion of \textit{strict}
implementability for sets $A\subset[0,T]\times\mathbb{R}$, where
we additionally demand that $A$ coincides with the stopping region
of the problem (\ref{eq:impl_def_intro}). Proposition \ref{prop:only_cut-offs_implementable}
states that under the single crossing condition only cut-off regions
are strictly implementable. Furthermore, we show that if the monotonicity
in Equation (\ref{eq:single_crossing_intro}) is strict, then cut-off
regions with a càdlàg barrier with summable downward jumps are strictly
implementable (Theorem \ref{thm:strict_single_crossing_impl_strong_impl}).
In this way the following characterization of strictly implementable
regions holds up the assumption of right continuity and summable downward
jumps: A region is strictly implementable if and only if it is of
cut-off type.

Furthermore, the transfer implementing a cut-off region is unique
up to an additive constant (Theorem \ref{thm:Uniqueness}). Again
we give a purely probabilistic proof. This result leads to a new characterization
of optimal stopping boundaries (Corollary \ref{cor:appl_opt_stopping}).
If the first hitting time $\tau_{A}$ of a set $A$ is optimal in
the stopping problem $\sup_{\tau\in\mathcal{T}}\mathbb{E}\left[g(\tau,X_{\tau})\right]$
then $A$ is implemented by the zero transfer. Uniqueness of the transfer
implies that
\begin{equation}
\mathbb{E}\left[\int_{t}^{T}(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]=0\label{eq:integral_equation_intro}
\end{equation}
for all $t\in[0,T].$ Remarkably, the nonlinear integral Equation
(\ref{eq:integral_equation_intro}) is not only necessary but also
sufficient for optimality. Therefore it characterizes optimal stopping
boundaries under the single crossing condition. To our knowledge this
is the first result which links reflected (forward) processes to optimal
stopping problems. For future research it is appealing to develop
methods to solve Equation (\ref{eq:integral_equation_intro}) numerically.
These approximation schemes could then for example be used to compute
the optimal exercise boundary for American options or optimal irreversible
investment strategies. In Section \ref{sec:Application-To-Optimal-Stopping}
we discuss the relation to the integral equation derived in \citet{kim1990analytic},
\citet{jacka1991optimal} and \citet{carr2006alternative} (see also
\citet{pevskir2006optimal}).

The paper is organized as follows. In Section \ref{sec:Problem-Formulation}
we set up the model and introduce the notion of implementability.
In Section \ref{sec:Implemtable_implies_cut-off} we show that only
cut-off regions are strictly implementable. Section \ref{sec:Implementability-of-Cut-Off}
is devoted to the converse implication. First we introduce reflected
processes and formally derive the representation (\ref{eq:transfer_intro})
of the transfer (Subsection \ref{sub:Constrained-Processes}). Subsection
\ref{sub:Cut-offs_implementable} contains the main results about
implementability of cut-off regions. In Subsection \ref{sub:Properties-of-the-transfer}
we present the main properties of the transfer and in Subsection \ref{sub:Uniqueness-of-The-transfer}
we provide the uniqueness result. In Section \ref{sec:Application-To-Optimal-Stopping}
we derive and discuss the integral equation (\ref{eq:integraleq}).

\section{Problem Formulation\label{sec:Problem-Formulation}}

\subsection{Dynamics}

In this paper we consider optimal stopping problems with finite time
horizon $T<\infty$. The underlying probability space $(\Omega,\mathcal{F},\mathbb{P})$
supports a one-dimensional Brownian motion $W$. Let $\mathbb{F}=\left(\mathcal{F}_{t}\right)_{t\in[0,T]}$
be the filtration generated by $W$ satisfying the usual assumptions.
We denote the set of $\mathbb{F}$-stopping times with values in $[0,T]$
by $\mathcal{T}$. For $t<T$ we refer to $\mathcal{T}_{t,T}$ as
the subset of stopping times which take values in $[t,T].$ The process
$X$ follows the time-inhomogeneous diffusion dynamics
\begin{equation}
\mathrm{d}X_{t}=\mu(t,X_{t})\mathrm{d}t+\sigma(t,X_{t})\mathrm{d}W_{t}.\label{eq:sde}
\end{equation}
We denote by $\mathcal{L}=\mu\partial_{x}+\frac{1}{2}\sigma^{2}\partial_{xx}$
the infinitesimal generator of $X$. The coefficients $\mu,\sigma:[0,T]\times\mathbb{R}\to\mathbb{R}$
are continuous and Lipschitz continuous in the $x$ variable uniformly
in $t$, i.e. there exists a positive constant $L$ such that
\begin{eqnarray*}
|\mu(t,x)-\mu(t,y)|+|\sigma(t,x)-\sigma(t,y)| & \le & L|x-y|
\end{eqnarray*}
for all $t\in[0,T]$ and $x,y\in\mathbb{R}$. Under this assumption
there exists a unique solution $(X_{s}^{t,x})_{s\ge t}$ to (\ref{eq:sde})
for every initial condition $X_{t}^{t,x}=x$.  Moreover, it follows
that the comparison principle holds true (see e.g. \citet[Proposition 2.18]{karatzas1991brownian}):
The path of the process starting at a lower level $x\le x'$ at time
$t$ is smaller than the path of the process starting in $x'$ at
all later times $s>t$
\begin{equation}
X_{s}^{t,x}\le X_{s}^{t,x'}\qquad\mathbb{P}-a.s.\label{eq:ComparisonPrincipleOriginal}
\end{equation}

\subsection{Payoffs and Transfers}

As long as the process $X$ is not stopped there is a flow payoff
$f$ and at the time of stopping there is a terminal payoff $g$.
The payoffs $f,g:[0,T]\times\mathbb{R}\to\mathbb{R}$ depend on time
and the value of the signal. Thus the expected payoff for using a
stopping time $\tau\in\mathcal{T}_{t,T}$ equals
\[
W(t,x,\tau)=\mathbb{E}\left[\int_{t}^{\tau}f(s,X_{s}^{t,x})\mathrm{d}s+g(\tau,X_{\tau}^{t,x})\right],
\]
given that the signal starts in $x\in\mathbb{R}$ at time $t\in[0,T]$.
We assume that the payoff function $f$ is continuous and Lipschitz
continuous in the $x$ variable uniformly in $t$. Moreover, we suppose
that $g\in C^{1,2}([0,T]\times\mathbb{R})$ with bounded derivatives.

We will analyze how preferences over stopping times change if there
is an additional payoff which only depends on time.
\begin{defn}
A measurable, bounded function $\pi:[0,T]\to\mathbb{R}$ is called
a transfer.
\end{defn}
We define the value function of the stopping problem with payoffs
$f$ and $g$ and an additional transfer $\pi$ by
\begin{equation}
v^{\pi}(t,x)=\sup_{\tau\in\mathcal{T}_{t,T}}\left(W(t,x,\tau)+\mathbb{E}\left[\pi(\tau)\right]\right).\label{eq:stopping_problem_with_transfer}
\end{equation}
Moreover we introduce for every $t\in[0,T]$ the stopping region
\[
D_{t}^{\pi}=\left\{ x\in\mathbb{R}\,|\, v^{\pi}(t,x)=g(t,x)+\pi(t)\right\} .
\]

\subsection{Implementability}

A measurable set $A\subset[0,T]\times\mathbb{R}$ is called \textit{time-closed}
if for each time $t\in[0,T]$ the slice $A_{t}=\{x\in\mathbb{R}\,|\,(t,x)\in A\}$
is a closed subset of $\mathbb{R}$ . Let $X$ start in $x\in\mathbb{R}$
at time $t\in[0,T].$ For a time-closed set $A$ we introduce the
first time when $X$ hits $A$ by
\[
\tau_{A}^{t,x}=\inf\left\{ s\ge t\,|\, X_{s}^{t,x}\in A_{s}\right\} \wedge T.
\]
We now come to the definition of implementability.
\begin{defn}[Implementability]
A time-closed set $A$ is implemented by a transfer $\pi$ if the
stopping time $\tau_{A}^{t,x}$ is optimal in (\ref{eq:stopping_problem_with_transfer}),
i.e. for every $t\in[0,T]$ and $x\in\mathbb{R}$
\[
v^{\pi}(t,x)=W(t,x,\tau_{A}^{t,x})+\mathbb{E}\left[\pi(\tau_{A}^{t,x})\right]\,.
\]

\end{defn}
For a time-closed set $A$ a necessary condition for implementability
is that each slice $A_{t}$ is included in the stopping region $D_{t}^{\pi}$.
Indeed, let $A$ be implemented by $\pi$ and let $t\in[0,T]$ and
$x\in A_{t}$. Then we have $\tau_{A}^{t,x}=t$. Since $\tau_{A}^{t,x}$
is optimal, this implies $v^{\pi}(t,x)=g(t,x)+\pi(t)$ and hence $x\in D_{t}^{\pi}$.
Consequently, we have $A_{t}\subseteq D_{t}^{\pi}$.

Observe that the converse inclusion $D_{t}^{\pi}\subseteq A_{t}$
does not necessarily hold true, since optimal stopping times are in
general not unique. At some point $(t,x)\in[0,T]\times\mathbb{R}$
it might be optimal to stop immediately ($x\in D_{t}^{\pi})$ as well
as to wait a positive amount of time until $X$ hits $A$ ($x\notin A_{t}$).
A particularly simple example is the case where $X$ is a martingale
and $f(t,x)=0$ and $g(t,x)=x$. The optional stopping theorem implies
that all stopping times $\tau\in\mathcal{T}_{t,T}$ generate the same
expected payoff $W(t,x,\tau)=x$. Therefore, every set $A$ is implemented
by the zero transfer. The stopping region consists of the whole state
space $D_{t}^{0}=\mathbb{R}$.

We introduce the notion of strict implementability, where ambiguity
in optimal strategies is ruled out: whenever it is optimal to continue
a positive amount of time it is not optimal to stop.
\begin{defn}[Strict Implementability]
A time-closed set $A$ is strictly implemented by a transfer $\pi$
if $A$ is implemented by $\pi$ and $v^{\pi}(t,x)>g(t,x)+\pi(t)$
for all $x\notin A_{t}$ and $t\in[0,T]$.
\end{defn}
In particular, every strictly implementable set $A$ satisfies $A_{t}=D_{t}^{\pi}$
for the transfer $\pi$. Since the stopping regions $D_{t}^{\pi}$
are closed (see Lemma \ref{lem:continuity} below) the restriction
to time-closed sets is no loss of generality. Any set which is not
time-closed can not be strictly implemented.

Note that the notion of implementability generalizes the notion of
optimal stopping times. If $\tau_{A}^{t,x}$ is an optimal stopping
time in a stopping problem of the form
\[
\sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[\int_{t}^{\tau}f(s,X_{s}^{t,x})\mathrm{d}s+g(\tau,X_{\tau}^{t,x})\right]
\]
 for all $(t,x)\in[0,T]\times\mathbb{R}$, then it is implemented
by the zero transfer.

\subsection{Single Crossing And Cut-Off Regions}

Next we introduce the main structural condition on the payoff functions.
\begin{condition}[Single-Crossing]
\label{def:SingleCrossing}We say that the single crossing condition
is satisfied if the mapping $x\mapsto f(t,x)+(\partial_{t}+\mathcal{L})g(t,x)$
is non-increasing. If this monotonicity is strict, then we say that
the strict single crossing condition holds.
\end{condition}
Moreover, we define a special subclass of time-closed sets.
\begin{defn}
\label{def-cut-off}A time-closed set $A$ is called a cut-off region
if there exists a function $b:[0,T]\to\overline{\mathbb{R}}$ such
that $A_{t}=[b(t),\infty)$. In this case we call $b$ the associated
cut-off and we write
\[
\tau_{A}^{t,x}=\tau_{b}^{t,x}=\inf\{s\ge t\,|\, X_{s}^{t,x}\ge b(s)\}\wedge T
\]
for $(t,x)\in[0,T]\times\mathbb{R}$. We call $\tau_{b}$ a cut-off
rule. We say that a cut-off region $A$ is regular, if the associated
cut-off $b:[0,T]\to\mathbb{R}$ is càdlàg (i.e. is right continuous
and has left limits in $\mathbb{R}$) and has summable downward jumps,
i.e.
\[
\sum_{0\le s\le t}(\Delta b_{s})^{-}<\infty.
\]

\end{defn}

\section{strictly Implementable Regions are Cut-Off Regions\label{sec:Implemtable_implies_cut-off}}

For optimal stopping problems it is well-known that under the single
crossing condition (or a weaker version of it) there exists a cut-off
rule that is optimal (see e.g. \citet{kotlow1973}, \citet{jacka1992finite}
or \citet{villeneuve2007threshold}). In this section we show that
the opposite direction holds more generally for strict implementability:
Only cut-off regions can be strictly implemented.

We first state the following regularity result about $v^{\pi}$.
\begin{lem}
\label{lem:continuity}For every transfer $\pi$ and every $t\in[0,T]$
the mapping $x\mapsto v^{\pi}(t,x)$ is Lipschitz continuous. In particular,
the stopping region $D_{t}^{\pi}$ is closed. \end{lem}
\begin{proof}
Fix $t\in[0,T]$ and $x,y\in\mathbb{R}.$ By Lipschitz continuity
of $f$ and $g$ we have
\begin{eqnarray*}
|v^{\pi}(t,x)-v^{\pi}(t,y)| & \le & \sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[\int_{t}^{\tau}\left|f(s,X_{s}^{t,x})-f(s,X_{s}^{t,y})\right|ds+\left|g(\tau,X_{\tau}^{t,x})-g(\tau,X_{\tau}^{t,y})\right|\right]\\
 & \le & C\mathbb{E}\left[\sup_{s\in[t,T]}\left|X_{s}^{t,x}-X_{s}^{t,y}\right|\right].
\end{eqnarray*}
By the well-known moment estimate for solutions of stochastic differential
equations (see e.g. \citet[Theorem 3.2]{kunita2004stochastic}) there
exists a constant $\tilde{C}$ such that $\mathbb{E}\left[\sup_{s\in[t,T]}\left|X_{s}^{t,x}-X_{s}^{t,y}\right|\right]\le\tilde{C}|x-y|$.
This yields the claim.
\end{proof}
The next result shows that under the single-crossing condition only
cut-off regions are strictly implementable.
\begin{prop}
\label{prop:only_cut-offs_implementable}Assume that the single crossing
condition holds true and let $A$ be strictly implemented by some
transfer $\pi.$ Then $A$ is a cut-off region.\end{prop}
\begin{proof}
Fix $t\in[0,T].$ First observe that the single crossing condition
implies that $x\mapsto v^{\pi}(t,x)-g(t,x)$ is non-increasing. Indeed,
Itô's formula applied to $g(\cdot,X)$ yields
\[
W(t,x,\tau)=\mathbb{E}\left[\int_{t}^{\tau}\left(f(s,X_{s}^{t,x})+(\partial_{t}+\mathcal{L})g(s,X_{s}^{t,x})\right)ds+g(t,x)+\int_{t}^{\tau}g_{x}(s,X_{s}^{t,x})\mu(s,X_{s}^{t,x})dW_{s}\right]
\]
for every $x\in\mathbb{R}$ and $\tau\in\mathcal{T}_{t,T}$. Since
$g_{x}$ is bounded and $\mu$ has linear growth the process $\int_{t}^{\cdot}g_{x}(s,X_{s}^{t,x})\mu(s,X_{s}^{t,x})dW_{s}$
is a martingale. It follows from the comparison principle (\ref{eq:ComparisonPrincipleOriginal})
and the single crossing condition that for $x\le y$
\begin{eqnarray*}
v^{\pi}(t,x)-g(t,x) & = & \sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[\int_{t}^{\tau}\left(f(s,X_{s}^{t,x})+(\partial_{t}+\mathcal{L})g(s,X_{s}^{t,x})\right)\mathrm{d}s+\pi(\tau)\right]\\
 & \ge & \sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[\int_{t}^{\tau}\left(f(s,X_{s}^{t,y})+(\partial_{t}+\mathcal{L})g(s,X_{s}^{t,y})\right)\mathrm{d}s+\pi(\tau)\right]\\
 & = & v^{\pi}(t,y)-g(t,y).
\end{eqnarray*}
This implies that $y\in D_{t}^{\pi}$ if $y\ge x$ and $x\in D_{t}^{\pi}$.
Hence $D_{t}^{\pi}$ is an interval which is unbounded on the right.
By Lemma \ref{lem:continuity} the set $D_{t}^{\pi}$ is closed. Hence
there exists some $b(t)\in\overline{\mathbb{R}}$ such that $D_{t}^{\pi}=[b(t),\infty)$.
This implies that $A$ is a cut-off region since $A_{t}=D_{t}^{\pi}$
by the definition of strict implementability.
\end{proof}

\section{Implementability of Cut-Off Regions\label{sec:Implementability-of-Cut-Off}}

In this section we prove that the converse implication of Proposition
\ref{prop:only_cut-offs_implementable} holds true as well: Every
regular cut-off region is implementable. We derive a closed form representation
for the transfer in terms of the reflected version of $X$ in Subsection
\ref{sub:Constrained-Processes}. In Subsection \ref{sub:Cut-offs_implementable}
we verify that this candidate solution to the inverse optimal stopping
problem indeed implements cut-off regions. The main properties of
the transfer are presented in Subsection \ref{sub:Properties-of-the-transfer}.
In Subsection \ref{sub:Uniqueness-of-The-transfer} we provide a uniqueness
result for transfers implementing a cut-off region.

\subsection{Reflected SDEs and a formal derivation of the candidate transfer\label{sub:Constrained-Processes}}

A solution to a reflected stochastic differential equation (RSDE)
is a pair of processes $(\tilde{X},l)$, where the process $\tilde{X}$
evolves according to the dynamics of the associated SDE (\ref{eq:sde})
below a given barrier $b$ and is pushed below the barrier by the
process $l$ whenever it tries to exceed $b$. Next we give a formal
definition.
\begin{defn}
\label{def:rsde}Let $b$ be a càdlàg barrier, $t\in[0,T]$ a fixed
point in time and $\tilde{\xi}\le b(t)$ a $\mathcal{F}_{t}-$measurable
square-integrable random variable. A pair $(\tilde{X},l)$ of adapted
processes (with càdlàg trajectories) is called a (strong) solution
to the stochastic differential equation (\ref{eq:sde}) reflected
at $b$ with initial condition $(t,\tilde{\xi})$ if it satisfies
the following properties.
\begin{enumerate}
\item $\tilde{X}$ is constrained to stay below the barrier, i.e. $\tilde{X}_{s}\le b(s)$
almost surely for every $s\in[t,T]$.
\item For every $s\in[t,T]$ the following integral equation holds almost
surely
\begin{equation}
\tilde{X}_{s}=\tilde{\xi}+\int_{t}^{s}\mu(r,\tilde{X}_{r})\mathrm{d}r+\int_{t}^{s}\sigma(r,\tilde{X}_{r})\mathrm{d}W_{r}-l_{s}\,.\label{eq:refldiff}
\end{equation}

\item The process $l$ is non-decreasing and only increases when $\tilde{X}_{t}=b(t),$
i.e.
\begin{equation}
\int_{t}^{T}(b(s)-\tilde{X}_{s})\mathrm{d}l_{s}=0\,.\label{eq:minimality}
\end{equation}

\end{enumerate}
\end{defn}
To stress the dependence of $\tilde{X}$ on the initial value we sometimes
write $\tilde{X}^{t,\tilde{\xi}}$.
\begin{rem}
Consider the situation where $b$ has a downward jump at time $t$
and $\tilde{X}$ is above $b(t)$ shortly before time $t$, i.e. $\tilde{X}_{t-}(\omega)\in(b(t),b(t-)]$
for some $\omega\in\Omega$. Since $\tilde{X}_{t}\le b(t)$ the reflected
process $\tilde{X}$ has a downward jump at time $t$ as well. Equation
(\ref{eq:refldiff}) implies that $l$ has an upward jump at time
$t.$ Then Equation (\ref{eq:minimality}) yields that $\tilde{X}$
is on the barrier at time $t$, i.e. $\tilde{X}_{t}=b(t)$. Hence,
the jump of $b$ is rather absorbed by $\tilde{X}$ than truly reflected
(which would mean $\tilde{X}_{t}=2b(t)-\tilde{X}_{t-}$). In this
sense $\tilde{X}$ is the maximal version of $X$ which stays below
$b$. This property is crucial in the proof of Theorem \ref{thm:Cut-offs_implementable}.
Existence and uniqueness of $\tilde{X}$ are established in \citet{rutkowski1980stochastic}.
We also refer to \citet{Slominski20101701} who allow for general
modes of reflection. For results about RSDEs with ``true'' jump
reflections we refer to \citet{chaleyat1980reflexion}.
\end{rem}

\subsubsection*{A formal derivation}

Here we establish the link between inverse optimal stopping problems
and RSDEs and derive the representation of a transfer implementing
a cut-off region. To this end assume that the cut-off region $A=[b(t),\infty)$
is implemented by a transfer $\pi$. Without loss of generality we
assume that $\pi(T)=0$ (else take $\tilde{\pi}(t)=\pi(t)-\pi(T)$).
Since we are only interested in a formal derivation here, we make
some regularity assumptions. We assume that the value function of
the stopping problem (\ref{eq:stopping_problem_with_transfer}) is
smooth ($v^{\pi}\in C^{1,2}([0,T]\times\mathbb{R})$) and that $b$
is continuous such that $\tilde{X}$ is continuous as well. Then $v^{\pi}$
satisfies (see e.g. \citep[Chapter IV]{pevskir2006optimal})
\begin{eqnarray*}
\min\left\{ -(\partial_{t}+\mathcal{L})v^{\pi}-f,v^{\pi}-\left(g+\pi\right)\right\}  & = & 0\\
v^{\pi}(T,\cdot) & = & g(T,\cdot)
\end{eqnarray*}
and $b$ is the free boundary of this variational partial differential
equation. In particular, below the cut-off $b$ the value function
$v^{\pi}$ satisfies the continuation equation
\[
(\partial_{t}+\mathcal{L})v^{\pi}(t,x)=-f(t,x)
\]
for all $x\le b(t).$ On the cut-off, $v^{\pi}$ satisfies the boundary
condition $v^{\pi}(t,b(t))=g(t,b(t))+\pi(t)$ for all $t\in[0,T].$
Moreover, if $b$ is sufficiently regular the smooth fit principle
\[
v_{x}(t,b(t))=g_{x}(t,b(t))
\]
holds for all $t\in[0,T]$ (see e.g. \citet[Section 9.1]{pevskir2006optimal})
Then Itô's formula implies
\begin{eqnarray*}
\mathbb{E}\left[g(T,\tilde{X}_{T}^{t,b(t)})\right] & = & \mathbb{E}\left[v^{\pi}(T,\tilde{X}_{T}^{t,b(t)})\right]\\
 & = & v^{\pi}(t,b(t))+\mathbb{E}\left[\int_{t}^{T}(\partial_{t}+\mathcal{L})v^{\pi}(s,\tilde{X}_{s}^{t,b(t)})ds-\int_{t}^{T}v_{x}(s,\tilde{X}_{s}^{t,b(t)})dl_{s}\right]\\
 & = & g(t,b(t))+\pi(t)-\mathbb{E}\left[\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})ds+\int_{t}^{T}g_{x}(s,\tilde{X}_{s}^{t,b(t)})dl_{s}\right].
\end{eqnarray*}
A further application of Itô's formula yields the following representation
of $\pi$
\begin{eqnarray}
\pi(t) & = & \mathbb{E}\left[g(T,\tilde{X}_{T}^{t,b(t)})+\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})ds+\int_{t}^{T}g_{x}(s,\tilde{X}_{s}^{t,b(t)})dl_{s}\right]-g(t,b(t))\nonumber \\
 & = & \mathbb{E}\left[\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})+(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]\,.\label{eq:candidate_transfer}
\end{eqnarray}
In Theorem \ref{thm:Cut-offs_implementable} below we verify that
Equation (\ref{eq:candidate_transfer}) indeed leads to a transfer
$\pi$ implementing $A$. The proof does neither rely on any analytic
methods nor on results from the theory of partial differential equations.
Instead we employ purely probabilistic arguments based on the single
crossing condition and comparison results for SDEs and RSDEs. This
methodology requires weak regularity assumptions on the model parameters.
In particular there is no ellipticity condition on $\sigma.$

\subsubsection*{Properties of RSDEs}

The next proposition proves auxiliary results about RSDEs which we
will use in the proof of Theorem \ref{thm:Cut-offs_implementable}.
There is a broad literature on RSDEs including comparison results
(see e.g. \citet{bo2007strong}). To the best of our knowledge the
comparison principles for RSDE with càdlàg barriers and summable downward
jumps as needed for our result have not been shown before. While all
results follow by standard arguments we give a proof in the Appendix
for the convenience of the reader. For the existence and uniqueness
result we refer to \citet{rutkowski1980stochastic}.
\begin{prop}
\label{prop:refldiff}For every regular
\footnote{see Definition \ref{def-cut-off}
} cut-off $b$ there exists a unique solution $\tilde{X}$ to the RSDE
(\ref{eq:refldiff}). The process $l$ is given by
\begin{equation}
l_{s}=\sup_{t\le r\le s}(\tilde{\xi}+\int_{t}^{r}\mu(u,\tilde{X}_{u})\mathrm{d}u+\int_{t}^{r}\sigma(u,\tilde{X}_{u})\mathrm{d}W_{u}-b(r))^{+}.\label{eq:loctime}
\end{equation}
Moreover, $\tilde{X}$ satisfies
\begin{enumerate}
\item \label{enu:momest1}(Square Integrability) $\mathbb{E}\left[\sup_{t\leq s\leq T}(\tilde{X}_{s}^{t,\xi})^{2}\right]<\infty$
for all $t\in[0,T]$.
\item \label{enu:minimality}(Minimality) $\tilde{X}_{s}^{t,\xi}1_{\{s<\tau_{b}\}}=X_{s}^{t,\xi}1_{\{s<\tau_{b}\}}$
a.s. for all $s\in[t,T]$.
\item \label{enu:compprinc}(Comparison Principle for the Reflected Process)If
$\xi_{1}\le\xi_{2}$ a.s., then for $s\in[t,T]$ we have $\tilde{X}_{s}^{t,\xi_{1}}\le\tilde{X}_{s}^{t,\xi_{2}}$
a.s.
\item \label{enu:momest2}(Moment Estimate) For $\xi_{1},\xi_{2}\in L^{2}(\mathcal{F}_{t})$
there exists a constant $K>0$ such that $\mathbb{E}\left[\sup_{t\le r\le s}|\tilde{X}_{r}^{t,\xi_{1}}-\tilde{X}_{r}^{t,\xi_{2}}|^{p}|\mathcal{F}_{t}\right]\le K|\xi_{1}-\xi_{2}|^{p}$
a.s. for all $s\in[t,T]$ and $p=1,2.$
\item \label{enu:comprinc2}(Comparison Principle for the Original Process)
$\tilde{X}_{s}^{t,\xi}\leq X_{s}^{t,\xi}$ a.s. for all $s\in[t,T]$.
\item \label{enu:conv}(Left continuity) Let $t\in[0,T]$ and $x\le b(t)\wedge b(t-)$.
Then $\tilde{X}_{t}^{s,y\wedge b(s)}\to x$ in $L^{2}$ for $s\nearrow t$
and $y\to x$.
\end{enumerate}
\end{prop}
Using similar arguments as in \citet[Chapter V Section 6]{protter2005stochastic}
one can show that $\tilde{X}$ satisfies the strong Markov property.
For $s\ge t$ we define the transition kernel $\tilde{P}_{t,s}$ by
\[
\tilde{P}_{t,s}\varphi(t,x)=\mathbb{E}\left[\varphi(s,\tilde{X}_{s}^{t,x})\right]
\]
for any Borel measurable, bounded function $\varphi:[0,T]\times\mathbb{R}\to\mathbb{R}$.
Then $\tilde{X}$ satisfies for any stopping time $\tau\in\mathcal{T}$
and $u\ge0$
\begin{equation}
\mathbb{E}\left[\varphi(\tau+u,\tilde{X}_{\tau+u})\,|\,\mathcal{F}_{\tau}\right]=\tilde{P}_{\tau,\tau+u}\varphi(\tau,\tilde{X}_{\tau}).\label{eq:strong_markov}
\end{equation}
Moreover, uniqueness of solutions of RSDEs implies the following flow
property of $\tilde{X}$. For $t\le r\le s$ and $x\in\mathbb{R}$
we have a.s.
\begin{equation}
\tilde{X}_{s}^{t,x}=\tilde{X}_{s}^{r,\tilde{X}_{r}^{t,x}}.\label{eq:flow_prop}
\end{equation}

\subsection{Regular Cut-Off Regions are Implementable\label{sub:Cut-offs_implementable}}

In this section we prove our main theorem stating that every regular
cut-off region is implemented by the transfer derived in Subsection
\ref{sub:Constrained-Processes}.
\begin{thm}
\label{thm:Cut-offs_implementable}Assume that the single crossing
condition is satisfied. Let $A$ be a regular cut-off region with
boundary $b$. Then it is implemented by the transfer
\begin{equation}
\pi(t)=\mathbb{E}\left[\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})\mathrm{+(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})d}s\right]\,.\label{eq:DefinitionPayment-2}
\end{equation}
\end{thm}
\begin{proof}
First observe that the cut-off rule $\tau_{b}^{t,x}$ is a stopping
time for all $(t,x)\in[0,T]\times\mathbb{R}$. Indeed, since $X$
has continuous paths and $b$ is right-continuous, the Début-theorem
(see e.g. \citet[Chapter IV, Section 50]{dellacherie1978probabilities})
implies $\tau_{b}^{t,x}\in\mathcal{T}_{t,T}$.

Let $\pi$ be given by Equation (\ref{eq:DefinitionPayment-2}). For
the boundedness and measurability of $\pi$ we refer to Proposition
\ref{prop:Properties_transfer}. We set $h=f+(\partial_{t}+\mathcal{L})g$.
As in the proof of Proposition \ref{prop:only_cut-offs_implementable}
we have
\[
W(t,x,\tau)=g(t,x)+\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})ds\right].
\]
Note that we can write $\pi$ in terms of the transition function
$\tilde{P}$ of $\tilde{X}$ as follows
\[
\pi(t)=\int_{t}^{T}\tilde{P}_{t,s}h(t,b(t))\mathrm{d}s.
\]
The strong Markov property (Equation (\ref{eq:strong_markov})) of
$\tilde{X}$ implies
\[
\tilde{P}_{\tau,\tau+u}h(\tau,b(\tau))=\mathbb{E}\left[h(\tau+u,\tilde{X}_{\tau+u}^{\tau,b(\tau)})\,|\,\mathcal{F}_{\tau}\right]
\]
 for any stopping time $\tau\in\mathcal{T}$ and $u\ge0$. Hence we
have
\begin{equation}
\pi(\tau)=\mathbb{E}\left[\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s|\mathcal{F}_{\tau}\right]\,.\label{eq:pitau}
\end{equation}

Fix $t\in[0,T]$ and $x\ge b(t)$. Let $\tau\in\mathcal{T}_{t,T}$
be an arbitrary stopping time. The comparison principle between the
original and the reflected process (Property (\ref{enu:comprinc2}))
implies $X_{s}^{t,x}\ge X_{s}^{t,b(t)}\ge\tilde{X}_{s}^{t,b(t)}$
a.s. for every $s\in[t,T].$ From the flow property (Equation (\ref{eq:flow_prop}))
and the comparison principle for reflected processes (Property (\ref{enu:compprinc}))
follows that $\tilde{X}_{s}^{t,b(t)}=\tilde{X}_{s}^{\tau,\tilde{X}_{\tau}^{t,b(t)}}\le\tilde{X}_{s}^{\tau,b(\tau)}$
a.s. for every $s\in[\tau,T]$. Therefore the single crossing condition
implies
\begin{eqnarray*}
\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right] & = & \mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s\right]\\
 & \le & \mathbb{E}\left[\int_{t}^{\tau}h(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s+\int_{\tau}^{T}h(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]\\
 & = & \pi(t).
\end{eqnarray*}
This implies $W(t,x,\tau)+\mathbb{E}\left[\pi(\tau)\right]\le W(t,x,t)+\pi(t)$.
Hence $\tau_{b}^{t,x}=t$ is optimal in (\ref{eq:stopping_problem_with_transfer})
as claimed.

In the second step fix $x<b(t)$ and let $\tau\in\mathcal{T}_{t,T}$
be an arbitrary stopping time. To shorten notation we write $\tau_{b}=\tau_{b}^{t,x}$.
First, we prove that the stopping $\min\{\tau,\tau_{b}\}$ performs
at least as well as $\tau.$ By (\ref{eq:pitau}) we have
\begin{eqnarray*}
\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\pi(\tau)\right] &  & =\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\mathbb{E}\left[\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s\,|\,\mathcal{F}_{\tau}\right]\right]=\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s\right].
\end{eqnarray*}
 This leads to
\begin{flalign*}
\mathbb{E} & \left[1_{\{\tau_{b}<\tau\}}\left(\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right)\right]\\
 & =\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\left(\int_{t}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau_{b}}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s\right)\right].
\end{flalign*}
By construction of the reflected process $\tilde{X}$ we have $\tilde{X}_{\tau_{b}}^{t,x}=b(\tau_{b})$.
The comparison principle between the original and the reflected process
(Property (\ref{enu:comprinc2})) and the flow property of reflected
processes (Equation (\ref{eq:flow_prop})) imply almost surely
\[
\tilde{X}_{s}^{\tau_{b},b(\tau_{b})}=\tilde{X}_{s}^{\tau_{b},\tilde{X}_{\tau_{b}}^{t,x}}=\tilde{X}_{s}^{t,x}\le X_{s}^{t,x}
\]
for $s\ge\tau_{b}$. Since $\tilde{X}_{\tau}^{\tau_{b},b(\tau_{b})}\le b(\tau)$
we have on the set $\{\tau>\tau_{b}\}$
\[
\tilde{X}_{s}^{\tau,b(\tau)}\ge\tilde{X}_{s}^{\tau,\tilde{X}_{\tau}^{\tau_{b},b(\tau_{b})}}=\tilde{X}_{s}^{\tau_{b},b(\tau_{b})}
\]
for all $s\ge\tau$. These two inequalities combined with the monotonicity
of $h$ yield that
\begin{flalign*}
\mathbb{E} & \left[1_{\{\tau_{b}<\tau\}}\left(\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right)\right]\\
 & \le\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\left(\int_{t}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau_{b}}^{\tau}h(s,\tilde{X}_{s}^{\tau_{b},b(\tau_{b})})\mathrm{d}s\right)+\int_{\tau}^{T}h(s,\tilde{X}_{s}^{\tau_{b},b(\tau_{b})})\mathrm{d}s\right]\\
 & =\mathbb{E}\left[1_{\{\tau_{b}<\tau\}}\left(\int_{t}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau_{b})\right)\right]\,.
\end{flalign*}
Consequently using the stopping time $\min\{\tau,\tau_{b}\}$ is at
least as good as using $\tau$
\begin{flalign*}
W(t,x,\tau)+\mathbb{E}\left[\pi(\tau)\right] & =g(t,x)+\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right]\\
 & \le g(t,x)+\mathbb{E}\left[\int_{t}^{\tau\wedge\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\min\{\tau,\tau_{b}\})\right]\\
 & =W(t,x,\min\{\tau,\tau_{b}\})+\mathbb{E}\left[\pi(\min\{\tau,\tau_{b}\})\right].
\end{flalign*}
Thus it suffices to consider stopping rules $\tau\leq\tau_{b}$. In
this case we have
\begin{flalign*}
\mathbb{E} & \left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right]\\
 & =\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau}^{\tau_{b}}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s+\int_{\tau_{b}}^{T}h(s,\tilde{X}_{s}^{\tau,b(\tau)})\mathrm{d}s\right].
\end{flalign*}
From the comparison principle for reflected processes (Property (\ref{enu:compprinc}))
and the flow property Equation (\ref{eq:flow_prop}) follows $\tilde{X}_{s}^{t,x}=\tilde{X}_{s}^{\tau,\tilde{X}_{\tau}^{t,x}}\le\tilde{X}_{s}^{\tau,b(\tau)}$
for all $s\ge\tau.$ By the minimality property of reflected processes
(Property (\ref{enu:minimality})) we have that $X_{s}^{t,x}=\tilde{X}_{s}^{t,x}$
for all $s<\tau_{b}$. Similar considerations as above yield
\[
\tilde{X}_{s}^{\tau_{b},b(\tau_{b})}=\tilde{X}_{s}^{\tau_{b},\tilde{X}_{\tau_{b}}^{t,x}}=\tilde{X}_{s}^{t,x}=\tilde{X}_{s}^{\tau,\tilde{X}_{\tau}^{t,x}}\le\tilde{X}_{s}^{\tau,b(\tau)}
\]
a.s. for $s\ge\tau_{b}$. The monotonicity of $h$ implies
\begin{flalign*}
\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau)\right] & \le\mathbb{E}\left[\int_{t}^{\tau}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\int_{\tau_{b}}^{T}h(s,\tilde{X}_{s}^{\tau_{b},b(\tau_{b})})\mathrm{d}s\right]\\
 & =\mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau_{b})\right]
\end{flalign*}
and hence $W(t,x,\tau)+\mathbb{E}\left[\pi(\tau)\right]\le W(t,x,\tau_{b})+\mathbb{E}\left[\pi(\tau_{b})\right]$.
This completes the proof of implementability.\end{proof}
\begin{example}
Assume that $X=\sigma W$ is a Brownian motion with volatility $\sigma>0$.
Further suppose that there is no flow payoff $f=0$ but only a final
payoff of the form $g(t,x)=x^{2}$. Then the single crossing condition
is satisfied and the transfer from Theorem \ref{thm:Cut-offs_implementable}
does not depend on the boundary $b$:
\[
\pi(t)=\sigma^{2}(T-t).
\]
Indeed, $-\pi$ is (up to a constant) the increasing part of the Doob-Meyer
decomposition of the submartingale $g(\cdot,X).$ Hence, the process
$g(\cdot,X)+\pi$ is a martingale and therefore every region $A$
is implemented by $\pi$. The stopping region (and thus the only strictly
implementable region) of the stopping problem with payoff $g+\pi$
is the whole state space $D_{t}^{\pi}=\mathbb{R}$.

In Proposition \ref{prop:only_cut-offs_implementable} we showed that
strictly implementable regions are necessarily of cut-off type. The
next result establishes the converse direction. Under the strict single
crossing condition cut-off regions are strictly implementable. \end{example}
\begin{thm}
\label{thm:strict_single_crossing_impl_strong_impl}If the strict
single crossing condition holds true, then a regular cut-off region
with barrier $b$ is strictly implemented by the transfer from Equation
(\ref{eq:DefinitionPayment-2}).\end{thm}
\begin{proof}
We use the same notation as in the proof of Theorem \ref{thm:Cut-offs_implementable}.
Let $t\in[0,T]$ and $x<b(t)$. Then the right-continuity of $b$
and $\tilde{X}$ and the strict monotonicity of $h$ imply that
\[
\mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,\tilde{X}_{s}^{t,x})\mathrm{d}s\right]>\mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]
\]
 Consequently we have
\begin{eqnarray*}
\mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,X_{s}^{t,x})\mathrm{d}s+\pi(\tau_{b})\right] & = & \mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,\tilde{X}_{s}^{t,x})\mathrm{d}s+\int_{\tau_{b}}^{T}h(s,\tilde{X}_{s}^{\tau_{b},b(\tau_{b})})\mathrm{d}s\right]\\
 & > & \mathbb{E}\left[\int_{t}^{\tau_{b}}h(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s+\int_{\tau_{b}}^{T}h(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]\\
 & = & \pi(t).
\end{eqnarray*}
 This implies $v^{\pi}(t,x)>\pi(t)+g(t,x)$ and hence $A$ is strictly
implemented by $\pi.$
\end{proof}
In general the distribution of the reflected process $\tilde{X}$
is not explicitly known. Hence, one has to fall back to numerical
methods to approximate the transfer from Theorem \ref{thm:Cut-offs_implementable}.
For example one could use discretization schemes for the RSDE (\ref{eq:refldiff})
and Monte Carlo simulations to evaluate the expectation in Equation
(\ref{eq:DefinitionPayment-2}) (see e.g. \citet{saisho1987stochastic},
\citet{bossy2004symmetrized} or \citet{onskog2010weak}). If $X$
evolves according to a Brownian motion, then the distribution of $\tilde{X}$
is available in closed form.
\begin{example}
\label{exa:BM}First assume that $X$ evolves according to a Brownian
motion with volatility $\sigma>0$ and drift $\mu\in\mathbb{R}$
\[
dX_{t}=\mu dt+\sigma dW_{t}.
\]
For regular cut-offs $b$ the reflected version $(\tilde{X},l)$ of
$X$ is given by
\begin{eqnarray*}
\tilde{X}_{s}^{t,x} & = & X_{s}^{t,x}-\sup_{t\le r\le s}\left(X_{r}^{t,x}-b(r)\right)^{+}\\
l_{s} & = & \sup_{t\le r\le s}\left(X_{r}^{t,x}-b(r)\right)^{+}
\end{eqnarray*}
If $b(t)=b$ is constant and $X$ has vanishing drift ($\mu=0)$ we
have
\[
\tilde{X}_{s}^{t,b(t)}=b+\sigma(W_{s}-W_{t})-\sigma\sup_{t\le r\le s}\left(W_{r}-W_{t}\right).
\]
It follows from the reflection principle for the Brownian motion (see
e.g. \citet[Chapter 2 Section 8A]{karatzas1991brownian}) that
\[
\tilde{X}_{s}^{t,b(t)}\sim b-\sigma\left|W_{s-t}\right|.
\]
This leads to the following representation of the transfer from Theorem
\ref{thm:Cut-offs_implementable}
\[
\pi(t)=\int_{t}^{T}\int_{0}^{\infty}\sqrt{\frac{2}{\pi(s-t)}}e^{-\frac{x^{2}}{2(s-t)}}h(s,b-\sigma x)dxds
\]
where $h=f+(\partial_{t}+\mathcal{L})g$.
\end{example}

\subsection{Properties of the Transfer\label{sub:Properties-of-the-transfer}}

The next proposition summarizes properties of transfer implementing
a cut-off region.
\begin{prop}
\label{prop:Properties_transfer}Let $b:[0,T]\to\mathbb{R}$ be a
regular cut-off. The transfer $\pi$ from Equation (\ref{eq:DefinitionPayment-2})
satisfies the following properties
\begin{enumerate}
\item $\pi$ is càdlàg. In particular $\pi$ is bounded and measurable.
\item $\pi$ is continuous at $t\in[0,T]$ if $b$ is continuous at $t$
or if $b$ has a downward jump at $t$.
\item $\pi$ has no upward jumps.
\item If $\pi$ has a downward jump at $t\in[0,T]$, then $b$ has an upward
jump at $t$.
\item $\pi$ converges to $0$ at time $T$: $\lim_{t\nearrow T}\pi(t)=0$.
\end{enumerate}
\end{prop}
\begin{proof}
As in the proof of Theorem \ref{thm:Cut-offs_implementable} we introduce
the function $h(t,x)=f(t,x)+\left(\partial_{t}+\mathcal{L}\right)g(t,x)$.
By assumption $h$ is Lipschitz continuous and has linear growth in
$x$. The transfer $\pi$ is given by
\[
\pi(t)=\mathbb{E}\left[\int_{t}^{T}h(s,\tilde{X}_{s}^{t,b(t)})ds\right].
\]
We first show that $\pi$ is right-continuous. For $t\in[0,T]$ and
$\epsilon>0$ we have
\[
\left|\pi(t)-\pi(t+\epsilon)\right|\le\mathbb{E}\left[\int_{t}^{t+\epsilon}\left|h(s,\tilde{X}_{s}^{t,b(t)})\right|ds\right]+\mathbb{E}\left[\int_{t+\epsilon}^{T}\left|h(s,\tilde{X}_{s}^{t,b(t)})-h(s,\tilde{X}_{s}^{t+\epsilon,b(t+\epsilon)})\right|ds\right].
\]
It follows from the linear growth of $h$ and Property (\ref{enu:momest1})
of $\tilde{X}$ from Proposition \ref{prop:refldiff} that $\mathbb{E}\left[\int_{t}^{t+\epsilon}\left|h(s,\tilde{X}_{s}^{t,b(t)})\right|ds\right]\to0$
as $\epsilon\to0$. Moreover, the Lipschitz continuity of $h$ implies
\[
\mathbb{E}\left[\int_{t+\epsilon}^{T}\left|h(s,\tilde{X}_{s}^{t,b(t)})-h(s,\tilde{X}_{s}^{t+\epsilon,b(t+\epsilon)})\right|ds\right]\le C\mathbb{E}\left[\sup_{s\in[t+\epsilon,T]}\left|\tilde{X}_{s}^{t,b(t)}-\tilde{X}_{s}^{t+\epsilon,b(t+\epsilon)}\right|\right]
\]
for some constant $C>0$. By the flow property (Equation (\ref{eq:flow_prop}))
we have $\tilde{X}_{s}^{t,b(t)}=\tilde{X}_{s}^{t+\epsilon,\tilde{X}_{t+\epsilon}^{t,b(t)}}$.
Property (\ref{enu:momest2}) from Proposition \ref{prop:refldiff}
yields
\[
\mathbb{E}\left[\sup_{s\in[t+\epsilon,T]}\left|\tilde{X}_{s}^{t,b(t)}-\tilde{X}_{s}^{t+\epsilon,b(t+\epsilon)}\right|\right]\le\tilde{C}\mathbb{E}\left[\left|\tilde{X}_{t+\epsilon}^{t,b(t)}-b(t+\epsilon)\right|\right].
\]
Right continuity of $\tilde{X}$ and $b$ then implies $\pi(t+)=\pi(t)$.
\footnote{Here and in the sequel we use the notation $\pi(t+)=\lim_{\epsilon\searrow0}\pi(t+\epsilon)$
and $\pi(t-)=\lim_{\epsilon\searrow0}\pi(t-\epsilon)$ for the one-sided
limits.
}

Concerning the left-hand limits of $\pi$ we show that
\begin{equation}
\pi(t-)=\mathbb{E}\left[\int_{t}^{T}h(s,\tilde{X}_{s}^{t,b(t)\wedge b(t-)})ds\right].\label{eq:Left-continuity}
\end{equation}
for all $t\in(0,T].$ Equation (\ref{eq:Left-continuity}) implies
all remaining claims of Proposition \ref{prop:Properties_transfer}.
If $b$ is continuous at $t$ or has a downward jump ($b(t)\le b(t-)$),
then Equation (\ref{eq:Left-continuity}) yields continuity of $\pi$
at $t$: $\pi(t-)=\pi(t)$. Monotonicity of $h$ and the comparison
principle for the reflected process imply $\pi(t-)\ge\pi(t),$ i.e.
$\pi$ has no upward jumps. If $\pi$ has a downward jump at time
$t$ ($\pi(t-)>\pi(t)$), then Equation (\ref{eq:Left-continuity})
yields that $b$ has necessarily an upward jump ($b(t)>b(t-)$). Moreover,
it follows from Equation (\ref{eq:Left-continuity}) that $\pi(T-)=0$.
To prove Equation (\ref{eq:Left-continuity}) let $t\in(0,T]$ and
$\epsilon>0$. Then consider
\begin{eqnarray*}
\left|\pi(t-\epsilon)-\mathbb{E}\left[\int_{t}^{T}h(s,\tilde{X}_{s}^{t,b(t)\wedge b(t-)})ds\right]\right| & \le & \mathbb{E}\left[\int_{t-\epsilon}^{t}\left|h(s,\tilde{X}_{s}^{t-\epsilon,b(t-\epsilon)})\right|ds\right]\\
 &  & +\mathbb{E}\left[\int_{t}^{T}\left|h(s,\tilde{X}_{s}^{t-\epsilon,b(t-\epsilon)})-h(s,\tilde{X}_{s}^{t,b(t)\wedge b(t-)})\right|ds\right].
\end{eqnarray*}
By Property (\ref{enu:conv}) from Proposition \ref{prop:refldiff}
we have $\tilde{X}_{s}^{t-\epsilon,b(t-\epsilon)}\to\tilde{X}_{s}^{t,b(t)\wedge b(t-)}$
in $L^{2}$ as $\epsilon\searrow0$. Lipschitz continuity and linear
growth of $h$ then imply that $\mathbb{E}\left[\int_{t-\epsilon}^{t}\left|h(s,\tilde{X}_{s}^{t-\epsilon,b(t-\epsilon)})\right|ds\right]\to0$
and $\mathbb{E}\left[\int_{t}^{T}\left|h(s,\tilde{X}_{s}^{t-\epsilon,b(t-\epsilon)})-h(s,\tilde{X}_{s}^{t,b(t)\wedge b(t-)})\right|ds\right]\to0$
for $\epsilon\searrow0$. This yields the claim.
\end{proof}

\subsection{Uniqueness of The Transfer \label{sub:Uniqueness-of-The-transfer}}

To prove a uniqueness result for the transfer from Theorem \ref{thm:Cut-offs_implementable}
we need the following auxiliary result about cut-off stopping times.
\begin{lem}
\label{lem:convergence_stopp_times}Let $b:[0,T]\to\mathbb{R}$ be
bounded from below. Then we have $\tau_{b}^{t,x}\nearrow T$ a.s.
for $x\searrow-\infty$ and for every $t\in[0,T].$\end{lem}
\begin{proof}
Fix $t\in[0,T]$. By \citet[Lemma 3.7]{kunita2004stochastic} there
exists a constant $C>0$ such that
\[
\mathbb{E}\left[\sup_{t\le s\le T}\left(\frac{1}{1+(X_{s}^{t,x})^{2}}\right)^{2}\right]\le C\left(\frac{1}{1+x^{2}}\right)^{2}.
\]
Then Fatou's Lemma implies
\[
\mathbb{E}\left[\liminf_{x\to-\infty}\sup_{t\le s\le T}\left(\frac{1}{1+(X_{s}^{t,x})^{2}}\right)^{2}\right]\le\liminf_{x\to-\infty}\mathbb{E}\left[\sup_{t\le s\le T}\left(\frac{1}{1+(X_{s}^{t,x})^{2}}\right)^{2}\right]\le\liminf_{x\to-\infty}C\left(\frac{1}{1+x^{2}}\right)^{2}=0.
\]
Consequently we have $\limsup_{x\to-\infty}\inf_{t\le s\le T}|X_{s}^{t,x}|=\infty$
a.s.  Together with the comparison principle for $X$ this yields
$\limsup_{x\to-\infty}\sup_{t\le s\le T}X_{s}^{t,x}=-\infty$ a.s.
It follows that $\tau_{b}^{t,x}\nearrow T$ for $x\searrow-\infty.$\end{proof}
\begin{thm}
\label{thm:Uniqueness}Let $A$ be a regular cut-off region with boundary
$b$. Assume that $A$ is implemented by two transfers $\pi$ and
$\hat{\pi}$ satisfying $\lim_{t\nearrow T}\pi(t)=\lim_{t\nearrow T}\hat{\pi}(t)$.
Then $\pi(t)=\hat{\pi}(t)$ for all $t\in[0,T)$.\end{thm}
\begin{proof}
Fix $t\in[0,T).$ To shorten notation we set $v=v^{\pi}$ and $\hat{v}=v^{\hat{\pi}}.$
By Lemma \ref{lem:continuity} the functions $v$ and $\hat{v}$ are
Lipschitz continuous in the $x$ variable. Similar considerations
yield that the function $x\mapsto W(t,x,\tau)$ is Lipschitz continuous
for every $\tau\in\mathcal{T}_{t,T}$. In particular, these functions
are absolutely continuous. Appealing to the envelope theorem from
\citet[Theorem 1]{milgrom2002envelope} yields that
\[
v_{x}(t,x)=W_{x}(t,x,\tau_{b}^{t,x})=\hat{v}_{x}(t,x)
\]
for Lebesgue almost every $x\in\mathbb{R}$. Integrating from $x<b(t)$
to $b(t$) gives
\[
v(t,b(t))-v(t,x)=\hat{v}(t,b(t))-\hat{v}(t,x)
\]
or equivalently

\[
\pi(t)-\hat{\pi}(t)=\mathbb{E}\left[\pi(\tau_{b}^{t,x})-\hat{\pi}(\tau_{b}^{t,x})\right].
\]
Since $\pi$ and $\hat{\pi}$ are bounded we can appeal to Lemma \ref{lem:convergence_stopp_times}
to obtain
\[
\pi(t)-\hat{\pi}(t)=\lim_{x\to-\infty}\mathbb{E}\left[\pi(\tau_{b}^{t,x})-\hat{\pi}(\tau_{b}^{t,x})\right]=0,
\]
 where we used the dominated convergence theorem.
\end{proof}

\section{Application To Optimal Stopping\label{sec:Application-To-Optimal-Stopping}}

From Theorem \ref{thm:Uniqueness} we derive a probabilistic characterization
of optimal stopping times for stopping problems of the form
\begin{equation}
v(t,x)=\sup_{\tau\in\mathcal{T}_{t,T}}\mathbb{E}\left[\int_{t}^{\tau}f(s,X_{s}^{t,x})ds+g(\tau,X_{\tau}^{t,x})\right]\,,\label{eq:optstop}
\end{equation}
where $f,g$ and $X$ satisfy the single crossing condition. We say
that a stopping time $\tau\in\mathcal{T}_{t,T}$ is optimal in (\ref{eq:optstop})
for $(t,x)\in[0,T]\times\mathbb{R}$ if
\[
v(t,x)=\mathbb{E}\left[\int_{t}^{\tau}f(s,X_{s}^{t,x})ds+g(\tau,X_{\tau}^{t,x})\right].
\]

\begin{cor}
\label{cor:appl_opt_stopping}Assume that the single crossing condition
is satisfied and let $b:[0,T]\to\mathbb{R}$ be a regular cut-off.
The stopping time $\tau_{b}^{t,x}$ is optimal in (\ref{eq:optstop})
for all $(t,x)\in[0,T]\times\mathbb{R}$, if and only if $b$ satisfies
the nonlinear integral equation
\begin{equation}
\mathbb{E}\left[\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})+(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]=0\label{eq:integral_equation_reflected}
\end{equation}
for all $t\in[0,T].$\end{cor}
\begin{proof}
First assume that (\ref{eq:integral_equation_reflected}) holds true
for every $t\in[0,T]$. Then Theorem \ref{thm:Cut-offs_implementable}
implies that the cut-off region with boundary $b$ is implemented
by the zero transfer. This means that $\tau_{b}^{t,x}$ is optimal
in (\ref{eq:optstop}) for every $(t,x)\in[0,T]\times\mathbb{R}$.

For the converse direction assume that $\tau_{b}^{t,x}$ is optimal
in (\ref{eq:optstop}) for every $(t,x)\in[0,T]\times\mathbb{R}$.
Then the cut-off region with boundary $b$ is implemented by the zero
transfer $\hat{\pi}=0$. By Theorem \ref{thm:Cut-offs_implementable}
it is also implemented by the transfer $\pi(t)=\mathbb{E}\left[\int_{t}^{T}f(s,\tilde{X}_{s}^{t,b(t)})+(\partial_{t}+\mathcal{L})g(s,\tilde{X}_{s}^{t,b(t)})\mathrm{d}s\right]$.
By Proposition \ref{prop:Properties_transfer} the transfer $\pi$
satisfies $\lim_{t\nearrow T}\pi(t)=0$. Then Theorem \ref{thm:Uniqueness}
implies that $\pi(t)=\hat{\pi}(t)=0$ for all $t\in[0,T].$
\end{proof}
In the literature on optimal stopping there is a well known link between
optimal stopping boundaries and a nonlinear integral equation differing
from Equation (\ref{eq:integral_equation_reflected}). It was established
by \citet{kim1990analytic}, \citet{jacka1991optimal} and \citet{carr2006alternative}
who considered the optimal exercise of an American option. For a more
general framework and an overview we refer the reader to \citet{pevskir2006optimal}.
In \citet[Chapter IV, Section 14]{pevskir2006optimal} the authors
derive the integral equation
\begin{equation}
\mathbb{E}\left[\int_{t}^{T}\left(f(s,X_{s}^{t,b(t)})+(\partial_{t}+\mathcal{L})g(s,X_{s}^{t,b(t)})\right)\mathbf{1}_{\{X_{s}^{t,b(t)}\le b(s)\}}\mathrm{d}s\right]=0\label{eq:integraleq}
\end{equation}
as a \textit{necessary} optimality condition for a stopping boundary
$b$. To verify that a solution to Equation (\ref{eq:integraleq})
indeed yields an optimal stopping time the authors proceed as follows.
First, it is shown that an optimal stopping time $\tau_{b}$ exists
and that the associated boundary $b$ necessarily satisfies Equation
(\ref{eq:integraleq}). In a second step the authors verify that Equation
(\ref{eq:integraleq}) has at most one solution which consequently
has to coincide with $b$. This verification step, however, is carried
out only for specific examples. These examples include the cases of
American (\citet{peskir2005american}) or Russian (\citet{peskir2005russian})
option payoffs where the price process $X$ evolves according to a
geometric Brownian motion.

To relate the two integral equations consider the case of a constant
barrier $b(t)=b\in\mathbb{R}$ and $X$ a Brownian motion. In this
case it follows from the reflection principle (see also Example \ref{exa:BM})
that for all $x\leq b$
\[
\mathbb{P}\left[\tilde{X}_{s}^{t,b(t)}\leq x\right]=2\,\mathbb{P}\left[X_{s}^{t,b(t)}\leq x\right]
\]
 and thus Equation (\ref{eq:integraleq}) and Equation (\ref{eq:integral_equation_reflected})
have the same solutions.

As the distribution of the random variable $\tilde{X}_{s}^{t,b(t)}$
depends on the whole barrier $(b(r))_{t\le r\le s}$ from time $t$
to $s$, Equation (\ref{eq:integral_equation_reflected}) is arguably
easier to check than (\ref{eq:integraleq}). For general diffusion
processes and payoffs, however, Equation (\ref{eq:integraleq}) does
not provide a \textit{sufficient} condition for optimality. This is
illustrated by the next simple example.
\begin{example}
Consider the static case, i.e. assume that $\mu=\sigma=0$ and hence
$X_{s}^{t,x}=x$ for all $s\ge t$ and $x\in\mathbb{R}$. Then every
strictly decreasing function $b$ satisfies Equation (\ref{eq:integraleq})
since $1_{\{X_{s}^{t,b(t)}\le b(s)\}}=0$ for all $s>t.$ But clearly
not every strictly decreasing barrier is optimal in (\ref{eq:optstop})
for an arbitrary choice of $f$ and $g$. Choose for example $f(t,x)=-x$
and $g(t,x)=0$, where the unique optimal stopping barrier is given
by $b(t)=0$.

By contrast Equation (\ref{eq:integral_equation_reflected}) leads
to the following characterization of the optimal stopping boundary
under the single crossing condition. Since $\tilde{X}_{s}^{t,b(t)}=b(s)$
for all $s\in[t,T]$, Equation (\ref{eq:integral_equation_reflected})
is satisfied by a function $b$ if and only if $f(t,b(t))+g_{t}(t,b(t))=0$
for all $t\in[0,T]$. In the case $f(t,x)=-x$ and $g(t,x)=0$, this
condition indeed yields the stopping barrier $b(t)=0.$
\end{example}

\section{Appendix}
\begin{proof}[Proof of Proposition \ref{prop:refldiff}]
Existence and uniqueness of $(\tilde{X},l)$ follow from \citet{rutkowski1980stochastic}.
See also \citet[Theorem 3.4]{Slominski20101701} for the time-homogeneous
case. By construction of $(\tilde{X},l)$ we also have (\ref{enu:momest1}).

We next show (\ref{enu:minimality}). Note that the solution to the
unreflected SDE (\ref{eq:sde}) solves the reflected SDE for $s<\tau_{b}$.
As the solution to the reflected SDE is unique (\ref{enu:minimality})
follows.

To prove (\ref{enu:compprinc}) and (\ref{enu:momest2}) we consider
without loss of generality only the case $t=0$. For $\xi_{1},\xi_{2}\in\mathbb{R}$
we write $(\tilde{X}^{i},l^{i})=(\tilde{X}^{0,\xi_{i}},l^{0,\xi_{i}})$,
($i=1,2$) and introduce the processes $D_{t}=\tilde{X}_{t}^{1}-\tilde{X}_{t}^{2}$
and $\Gamma_{t}=\sup_{s\le t}\max(0,D_{s})^{2}$. Applying the Meyer-Itô
formula \citet[Theorem 71, Chapter 4]{protter2005stochastic} to the
function $x\mapsto\max(0,x)^{2}$ yields
\begin{equation}
\begin{split}\max(0,D_{s})^{2}= & \max(0,D_{0})^{2}+2\int_{0}^{s}1_{\{D_{r-}>0\}}D_{r-}\mathrm{d}D_{r}+\int_{0}^{s}1_{\{D_{r-}>0\}}\mathrm{d}\left[D\right]{}_{r}^{c}\\
 & +\sum_{0<r\le s}\left(\max(0,D_{r})^{2}-\max(0,D_{r-})^{2}-1_{\{D_{r-}>0\}}D_{r-}\Delta D_{r}\right).
\end{split}
\label{eq:maxdelta0}
\end{equation}
Since $D$ only jumps when $b$ has a downward jump and since $\tilde{X}^{i}$
jumps to the barrier we have $-\left(\Delta b(r)\right)^{-}\le\Delta D_{r}\le0$
on the set $\left\{ D_{r-}>0\right\} $. Moreover, $D$ has bounded
paths. Since $b$ has summable downward jumps we have $\sum_{0<r\le s}1_{\{D_{r-}>0\}}\left|D_{r-}\Delta D_{r}\right|<\infty$
a.s. Hence, we can rewrite Equation \ref{eq:maxdelta0} as follows
\begin{equation}
\begin{split}\max(0,D_{s})^{2}= & \max(0,D_{0})^{2}+2\int_{0}^{s}1_{\{D_{r}>0\}}D_{r}\mathrm{d}D_{r}^{c}+\int_{0}^{s}1_{\{D_{r-}>0\}}\mathrm{d}\left[D\right]{}_{r}^{c}\\
 & +\sum_{0<r\le s}\left(\max(0,D_{r})^{2}-\max(0,D_{r-})^{2}\right).
\end{split}
\label{eq:maxdelta}
\end{equation}
Regarding the jump terms in Equation (\ref{eq:maxdelta}), assume
that there exists $r\in(0,s]$ such that $\max(0,D_{r})^{2}>\max(0,D_{r-})^{2}.$
This implies $D_{r}>0$ and $D_{r}>D_{r-}$. Since $\tilde{X}^{i}$
jumps if and only if $l^{i}$ jumps ($i=1,2)$ we obtain $\tilde{X}_{r}^{1}>\tilde{X}_{r}^{2}$
and $l_{r}^{2}-l_{r-}^{2}>l_{r}^{1}-l_{r-}^{1}$. It follows that
$l_{r}^{2}-l_{r-}^{2}>0,$ since $l^{1}$ is non-decreasing. Hence,
$l^{2}$ jumps at $r$, which implies that $\tilde{X}_{r}^{2}=b(r)$.
Thus, we obtain the contradiction $\tilde{X}_{r}^{1}>b(r).$ Therefore
we have
\[
\sum_{0<r\le s}\left(\max(0,D_{r})^{2}-\max(0,D_{r-})^{2}\right)\le0.
\]
For the last integral in Equation (\ref{eq:maxdelta}) the Lipschitz
continuity of $\sigma$ implies
\[
\int_{0}^{s}1_{\{D_{r}>0\}}d\langle D\rangle_{r}^{c}=\int_{0}^{s}1_{\{D_{r}>0\}}(\sigma(r,\tilde{X}_{r}^{1})-\sigma(r,\tilde{X}_{r}^{2}))^{2}\mathrm{d}r\le L^{2}\int_{0}^{s}\max(0,D_{r})^{2}\mathrm{d}r\le L^{2}\int_{0}^{s}\Gamma_{r}dr.
\]
The first integral of Equation (\ref{eq:maxdelta}) decomposes into
the following terms, which we will consider successively. By the Lipschitz
continuity of $\mu$ we have
\[
2\int_{0}^{s}1_{\{D_{r}>0\}}D_{r}(\mu(r,\tilde{X}_{r}^{1})-\mu(r,\tilde{X}_{r}^{2}))\mathrm{d}r\le2L\int_{0}^{s}\max(0,D_{r})^{2}\mathrm{d}r\le L\int_{0}^{s}\Gamma_{r}dr.
\]
Next, we have
\[
-2\int_{0}^{s}1_{\{D_{r}>0\}}D_{r}\mathrm{d}l_{r}^{1,c}\le0
\]
 and
\[
2\int_{0}^{s}1_{\{D_{r}>0\}}D_{r}\mathrm{d}l_{r}^{2,c}=2\int_{0}^{s}1_{\{\tilde{X}_{r}^{1}>b(r)\}}D_{r}\mathrm{d}l_{r}^{2,c}=0.
\]
Moreover, it follows from the Burkholder-Davis-Gundy inequality, the
Lipschitz continuity of $\sigma$ and Young's inequality that
\begin{eqnarray*}
\mathbb{E}\left[\sup_{s\le t}\int_{0}^{s}1_{\{D_{r}>0\}}D_{r}(\sigma(r,\tilde{X}_{r}^{1})-\sigma(r,\tilde{X}_{r}^{2}))\mathrm{d}W_{r}\right] & \le & C\mathbb{E}\left[\sqrt{\int_{0}^{t}1_{\{D_{r}>0\}}D_{r}^{4}\mathrm{d}r}\right]\\
 & \le & C\mathbb{E}\left[\sqrt{\Gamma_{t}\int_{0}^{t}\Gamma_{r}dr}\right]\\
 & \le & \frac{1}{2}\mathbb{E}\left[\Gamma_{t}\right]+\frac{1}{2}C^{2}\mathbb{E}\left[\int_{0}^{t}\Gamma_{r}dr\right].
\end{eqnarray*}
Putting everything together, we obtain
\[
\mathbb{E}\left[\Gamma_{t}\right]\le\Gamma_{0}+K\int_{0}^{t}\mathbb{E}\left[\Gamma_{r}\right]dr
\]
for some constant $K>0.$ Then Gronwall's lemma yields
\begin{equation}
\mathbb{E}\left[\sup_{s\le t}\max(0,\tilde{X}_{s}^{1}-\tilde{X}_{s}^{2})^{2}\right]=\mathbb{E}[\Gamma_{t}]\le C\Gamma_{0}=C\max(0,\xi_{1}-\xi_{2})^{2}\label{eq:supmax}
\end{equation}
for some constant $C>0$. If $\xi_{1}\le\xi_{2}$ this directly yields
(\ref{enu:compprinc}). For (\ref{enu:momest2}) observe that we have
\[
\mathbb{E}\left[\sup_{s\le t}(\tilde{X}_{s}^{1}-\tilde{X}_{s}^{2})^{2}\right]\le\mathbb{E}\left[\sup_{s\le t}\max(0,\tilde{X}_{s}^{1}-\tilde{X}_{s}^{2})^{2}\right]+\mathbb{E}\left[\sup_{s\le t}\max(0,\tilde{X}_{s}^{2}-\tilde{X}_{s}^{1})^{2}\right].
\]
Then Inequality (\ref{eq:supmax}) yields $\mathbb{E}\left[\sup_{s\le t}(\tilde{X}_{s}^{1}-\tilde{X}_{s}^{2})^{2}\right]\le\tilde{C}(\xi_{1}-\xi_{2})^{2}$.
The case $p=1$ follows from Jensen's inequality. Claim (\ref{enu:comprinc2})
follows by performing similar arguments with $D=\tilde{X}^{t,\xi}-X^{t,\xi}$.

In order to prove Equation (\ref{eq:loctime}), we set
\begin{equation}
Y_{s}=Y_{s}^{t,\xi}=\int_{t}^{s}\mu(u,\tilde{X}_{u}^{t,\xi})du+\int_{t}^{r}\sigma(u,\tilde{X}_{u-}^{t,\xi})\mathrm{d}W_{u},\quad\hat{l}_{s}=\sup_{t\le r\le s}(\xi+Y_{r}-b(r))^{+}\label{eq:yappendix}
\end{equation}
and $\hat{X}=\xi+Y_{s}-\hat{l}_{s}.$ Then it is straightforward to
show that $(\hat{X},\hat{l})$ is a solution to the Skorokhod problem
associated with $Y$ and barrier $b$ (cf. \citet[Definition 2.5]{Slominski20101701}).
Since $(\tilde{X},l)$ is also a solution, we obtain Equation (\ref{eq:loctime})
by uniqueness of solutions to the Skorokhod problem (cf. \citet[Proposition 2.4]{Slominski20101701}).

Finally we prove Claim (\ref{enu:conv}). To this end let $x\le b(t)\wedge b(t-)$
and $t_{n}\nearrow t$ and $x_{n}\to x$ as $n\to\infty.$ We write
$\tilde{X}^{n}=\tilde{X}^{t_{n},x_{n}\wedge b(t_{n})}$ and $Y^{n}=Y^{t_{n},x_{n}\wedge b(t_{n})}$
(see Equation (\ref{eq:yappendix}) for the definition of $Y$). Then
we have
\begin{eqnarray*}
|\tilde{X}_{t}^{n}-x| & = & |x_{n}\wedge b(t_{n})-x+Y_{t}^{n}-\sup_{t_{n}\le r\le t}(x_{n}\wedge b(t_{n})+Y_{r}^{n}-b(r))^{+}|\\
 & \le & |x_{n}\wedge b(t_{n})-x|+\sup_{t_{n}\le r\le t}(x_{n}\wedge b(t_{n})-b(r))^{+}+2\sup_{t_{n}\le r\le t}|Y_{r}^{n}|.
\end{eqnarray*}
Squaring this inequality and taking expectations yields
\[
\mathbb{E}\left[|\tilde{X}_{t}^{n}-x|^{2}\right]\le3|x_{n}\wedge b(t_{n})-x|^{2}+3\sup_{t_{n}\le r\le t}\left((x_{n}\wedge b(t_{n})-b(r))^{+}\right)^{2}+6\mathbb{E}\left[\sup_{t_{n}\le r\le t}|Y_{r}^{n}|^{2}\right].
\]
The first two terms converge to $0$ for $n\to\infty$ since $b$
is càdlàg and $x\le b(t)\wedge b(t-)$. Regarding the last term, observe
that Jensen's and the Burkholder-Davis-Gundy inequality yields
\begin{eqnarray*}
\mathbb{E}\left[\sup_{t_{n}\le r\le t}|Y_{r}^{n}|^{2}\right] & \le & C\int_{t_{n}}^{t}\mathbb{E}\left[\mu(s,\tilde{X}_{s}^{n})^{2}+\sigma(s,\tilde{X}_{s}^{n})^{2}\right]ds
\end{eqnarray*}
for some constant $C>0$ (not depending on $n$). It remains to prove
that $\mathbb{E}\left[\mu(s,\tilde{X}_{s}^{n})^{2}+\sigma(s,\tilde{X}_{s}^{n})^{2}\right]$
is a bounded sequence. To this end assume without loss of generality
that $\tilde{X}^{0}=\tilde{X}^{0,b(0)}$, then the linear growth of
$\mu$ and $\sigma$, the Markov property of $\tilde{X}^{0}$ and
Claim (\ref{enu:momest2}) imply
\begin{eqnarray*}
\mathbb{E}\left[\mu(s,\tilde{X}_{s}^{n})^{2}+\sigma(s,\tilde{X}_{s}^{n})^{2}\right] & \le & C_{1}\left(1+\mathbb{E}\left[(\tilde{X}_{s}^{n}-\tilde{X}_{s}^{0})^{2}+(\tilde{X}_{s}^{0})^{2}\right]\right)\\
 & \le & C_{2}\left(1+\mathbb{E}\left[(\tilde{X}_{t_{n}}^{0}-x_{n}\wedge b(t_{n}))^{2}+(\tilde{X}_{s}^{0})^{2}\right]\right)
\end{eqnarray*}
for some $C_{1},C_{2}>0$. This is a bounded sequence by Claim (\ref{enu:momest1}),
which yields $\mathbb{E}[\sup_{t_{n}\le r\le t}|Y_{r}^{n}|^{2}]\to0$
as $n\to\infty.$
\end{proof}
\bibliographystyle{economic/ecta}
\bibliography{delstop}

\end{document}

config: arxiv


TITLE: Construction of $R$-graph from a directed graph
QUESTION [0 upvotes]: Let $G$ be a finite directed graph with vertex set $V$ and an edge set $E$. In this paper https://arxiv.org/pdf/1209.2578.pdf, another graph is constructed from $G$ called $R$-graph by the following way:

On page 2, line-5 of the paper whose link is given above, Authors choose a partition $\{E^{-}, E^+\}$ of $E$.
In page 2, line-13, for any $q, r \in V$, Authors choose a relation $\mathcal R(q, r) \subset E^{-}(q, r) \times E^+(q, r)$

I have doubts about this partition and relation.  Whether this partition $\{E^{-}, E^+\}$, and relation $\mathcal R(q, r)$ are fixed or for any partition $\{E^{-}, E^+\}$ and relation $\mathcal R(q, r)$, we can construct $R$-graph?

Thanks in advance for your kind help.

REPLY [2 votes]: Krieger is simply defining his notion of $\mathcal{R}$-graph. It is an object $\mathcal{G}_{\mathcal{R}}(\mathfrak{P},\mathcal{E}^-,\mathcal{E}^+)$, where $\mathfrak{P}$ is the vertex set of a finite directed graph with edge set $\mathcal{E}$, $\{\mathcal{E}^-,\mathcal{E}^+\}$ is a partition of $\mathcal{E}$, the graph satisfies certain conditions, and $\mathcal{R}$ is a relation on the edges that also satisfies certain conditions.
Specifically, for $\mathfrak{q},\mathfrak{r}\in\mathfrak{P}$ we define $\mathcal{E}^-(\mathfrak{q},\mathfrak{r})$ to be the set of edges in $\mathcal{E}^-$ from $\mathfrak{q}$ to $\mathfrak{r}$ and $\mathcal{E}^+(\mathfrak{q},\mathfrak{r})$ to be the set of edges in $\mathcal{E}^+$ from $\mathfrak{r}$ to $\mathfrak{q}$. For each $\mathfrak{q},\mathfrak{r}\in\mathfrak{P}$ we require that either both of these sets be empty or both be non-empty, and we further require that the directed graph $\langle\mathfrak{P},\mathcal{E}^-\rangle$ (and hence also ($\langle\mathfrak{P},\mathcal{E}^+\rangle$) be strongly connected.
The relation $\mathcal{R}$ is the union of relations $\mathcal{R}(\mathfrak{q},\mathfrak{r})\subseteq\mathcal{E}^-(\mathfrak{q},\mathfrak{r})\times\mathcal{E}^+(\mathfrak{q},\mathfrak{r})$ for $\mathfrak{q},\mathfrak{r}\in\mathfrak{P}$.
And that’s it: any object satisfying those conditions is an $\mathcal{R}$-graph in the sense of this definition. If you change any of the parameters — the vertex set $\mathfrak{P}$, the edge set $\mathcal{E}$, the partition of the edge set, or the relation $\mathcal{R}$ — you have either a different $\mathcal{R}$-graph, if the various structural conditions are still met, or something that is not an $\mathcal{R}$-graph.


TITLE: Proof of Riemann Hypothesis
QUESTION [0 upvotes]: This proof was released this year:
http://arxiv.org/abs/1508.00533
Where is the mistake? I just found it and was wondering how obviously wrong it is.

REPLY [5 votes]: The proof of lemma 2.1 (the first thing the author proves at all) is false (though I didn't check if the claim of the lemma is possibly correct for other reasons):
Let $R_n(s):= \frac{1+(-1)^n}{n^{s}}$. This $R$ has sufficiently similar properties as the series remainder term, at least as far as they were used in the alleged proof:
First of all, $$\tag1\lim_{n\to\infty}R_n(s)=0.$$
Next, $$R_n(s)-R_{n-1}(s)=\frac{1+(-1)^n}{n^{s}}-\frac{1-(-1)^n}{(n-1)^{s}}=\begin{cases}-\frac{2}{(n-1)^s}&n\text{ odd}\\\hphantom{-}\frac2{n^s}&n\text{ even}\end{cases}$$ and
$$R_n(s)-R_{n+1}(s)=\frac{1+(-1)^n}{n^{s}}-\frac{1-(-1)^n}{(n+1)^{s}}=\begin{cases}-\frac{2}{(n+1)^s}&n\text{ odd}\\\hphantom{-}\frac2{n^s}&n\text{ even}\end{cases}$$
so that
$$\frac{R_n(s)-R_{n-1}(s)}{R_n(s)-R_{n+1}(s)}=\begin{cases}\left(1+\frac2{n-1}\right)^s&n\text{ odd}\\1&n\text{ even} \end{cases}$$
and $$\tag2 \lim_{n\to\infty}\frac{R_n(s)-R_{n-1}(s)}{R_n(s)-R_{n+1}(s)}=1.$$
It appears that the author thinks that $(1)$ and $(2)$ (or maybe even $(2)$ alone) imply
$$ \lim_{n\to\infty}\frac{-R_{n-1}(s)}{R_n(s)}= \lim_{n\to\infty}\frac{-R_{n+1}(s)}{R_n(s)}=1.$$
However, with $R$ as defined by me, these limits do not even exist.


TITLE: Heat equation with heat radiation and heat transfer
QUESTION [1 upvotes]: If I want to calculate steady temperature distribution on a one-dimensional stick,
and I need to consider both the heat radiation and heat transfer,
then my equation will be in the form:
$$
\frac{\partial ^2 T}{\partial x^2}=A(T^4-T_{env}^4) + B(T-T_{env}).
$$
$T_{env}$ is the environment temperature which varies at different places.
Is there any algorithm that can solve this kind of equation numerically?
Most of numerical algorithms focus on equation like $H\phi=a\phi$.

REPLY [1 votes]: Suppose you have 5 cells with 1 ghost cell (related to your particular boundary conditions, whatever they may be) on either side. In this case, you can write your steady-state heat equation as
\begin{align}
T_0-2T_1+T_2 &= dx^2\,f(T_1)\\
T_1-2T_2+T_3 &= dx^2\,f(T_2)\\
T_2-2T_3+T_4 &= dx^2\,f(T_3)\tag{1}\\
T_3-2T_4+T_5 &= dx^2\,f(T_4)\\
T_4-2T_5+T_6 &= dx^2\,f(T_5)\\
\end{align}
where
$$
f(T_i)=A\left(T_i^4-T_{ext}^4\right) + B\left(T_i-T_{ext}\right)\tag{2}
$$
Equation (1) can be expressed as the matrix operation
$$
\left(\begin{array}{ccccc}1 & -2 & 1 & 0 & 0 &0&0\\
0 & 1 & -2 & 1 & 0 &0&0\\
0 & 0 & 1 & -2 & 1  &0&0\\
0& 0 & 0 & 1 & -2 & 1 &0\\
0&0& 0 & 0 & 1 & -2 & 1 \\
\end{array}\right)\left(\begin{array}{c}T_0\\T_1\\T_2\\T_3\\T_4\\T_5\\T_6\end{array}\right)=dx^2\left(\begin{array}{c}f(T_0)\\f(T_1)\\f(T_2)\\f(T_3)\\f(T_4)\\f(T_5)\\f(T_6)\end{array}\right)
$$
This means that your equation really takes the form,
$$
\mathbb A\mathbf T=\mathbf b
$$
where $\mathbb A$ is a tridiagonal matrix, $\mathbf T$ are your temperatures and $\mathbf b=f(\mathbf T)$ a vector of Equation (2). This is effectively a system of linear equations.
Thus, you want to look at iterative solver methods such as

Gauss-Seidel method
Successive over-relaxation method
Conjugate gradient

Note that (a) this is an incomplete list and (b) each of these, as well as the others not mentioned, have its downsides and upsides. You'll likely want to spend some time looking at each one to choose the optimal one for you.


TITLE: Linear independent or linear dependent?
QUESTION [0 upvotes]: I am not sure to say if the following set is independent:
$$ \{1, \sin x, \cos x\}$$
I would say they are independent because after an analysis of the coefficients in the linear combination equal zero, the only setting possible are when they are all equal zero.
How should I prove this?

REPLY [0 votes]: Consider the function $f(x) = a + b\sin x + c \cos x$, which is infinitely continuously differentiable.
Linearly independence of the set in question is the same as showing that $f(x) \equiv 0$ if and only $a = b =c =0$.
Suppose that $f(x) \equiv 0$. Then derivatives of all orders are identically zero.
To see that $b$ and $c$ must be zero, note that $0 = f'(0) = b$ and $0 =f''(0) = -c$, but then these two conditions together with the assumption that imply that $a = 0$.
Hence, it follows that $f(x) = 0$ for all x implies that $a = b = c = 0$. This proves linearly independence of the set in question.


TITLE: Prove that $\mathcal{B}$ is a basis for $\mathcal{L}(V , W)$
QUESTION [0 upvotes]: Let $V$ and $W$ two vector spaces on a field $K$ and let ${\{{\phi}_i\}}_{i = 1}^n$ and ${\{w_j\}}_{j = 1}^m$ be two basis for $V^*$ and $W$ respectively. Defining, for each $(\phi , w) \in V^* \times W$,
$$
\begin{array}{llccl}
{\Psi}_{(\phi , w)} & : & V & \to & W
\\
& & v & \mapsto & \phi(v) w\mbox{,}
\end{array}
$$
is $\mathcal{B} = {\{{\Psi}_{({\phi}_i , w_j)}\}}_{(i , j) \in \{1 , \ldots , n\} \times \{1 , \ldots , m\}}$ a basis for the vector space $\mathcal{L}(V , W)$ formed by the linear maps between $V$ y $W$? Thank you very much in advance.

REPLY [3 votes]: Take $T\colon V \to W$ linear. Assume $(v_1,\ldots,v_n)$ is the basis of $V$ dual to $(\phi_1,\ldots,\phi_n)$. For each $v \in V$, we have $v= \sum_{j=1}^n \phi_j(v)v_i$, by definition of dual basis. Then $$T(v) = \sum_{j=1}^n \phi_j(v) T(v_j) = \sum_{i=1}^m \sum_{j=1}^n \phi_j(v)a_{ij}w_i,$$where $[T]_{(v_i),(w_j)} = (a_{ij})$ is the matrix of $T$ with respect to these bases. Well, this writes as $$T(v) = \sum_{i=1}^m \sum_{j=1}^n a_{ij} \Psi_{(\phi_j ,w_i)}(v),$$so $$T = \sum_{i=1}^m \sum_{j=1}^n a_{ij} \Psi_{(\phi_j,w_i)}$$and we conclude that $(\Psi_{(\phi_i,w_j)})_{(i,j) \in \{1,\ldots,n\}\times \{1,\ldots,m\}}$ is a spanning set for ${\rm Lin}(V,W)$. If you already know that $\dim {\rm Lin}(V,W) = nm$, we're done.
Otherwise, you have to check for linear independence directly. One does this as follows: Assume that $$\sum_{i=1}^m \sum_{j=1}^n a_{ij} \Psi_{(\phi_j,w_i)} = 0.$$We must check that $a_{ij} = 0$ for all possibilities of $i$ and $j$. Evaluate the above expression in $v_k$: $$0
 =\sum_{i=1}^m \sum_{j=1}^n a_{ij} \phi_j(v_k)w_i = \sum_{i=1}^m \sum_{j=1}^n a_{ij}\delta_{jk}w_i = \sum_{i=1}^m a_{ik}w_i,$$and linearly independence of $(w_i)_{i=1}^m$ gives $a_{ik} = 0$. But $k$ was also arbitrary, so we're done.


TITLE: Finding the $2\times 2$ determinant using row operations and upper triangular matrix.
QUESTION [1 upvotes]: Calculate $\begin{vmatrix}
3 &-5 \\
 2&6
\end{vmatrix}$.

I want to use row operations, and so what I did first was interchange the rows, which multiplies the determinant by $-1$. Then I wanted the $2$ to be a leading one, so I multiplied the first row by $\frac{1}{2}$, which multiplies the determinant by $\frac{1}{2}$. Then I eliminate the $3$ in the second row. I get the resulting determinant:
$-\frac{1}{2}\begin{vmatrix}
1&3 \\
 0&-14
\end{vmatrix}$
So then the determinant is $7$. However, I know this is wrong. Could someone please tell me what I did wrong to get an incorrect determinant?

REPLY [2 votes]: You took the $2$ out by taking $1/2$ out, i.e., you actually used $(2a) = 1/2*a$.

REPLY [2 votes]: Along those lines, what you should have done was:\begin{align}\begin{vmatrix}3&-5\\2&6\end{vmatrix}&=-\begin{vmatrix}2&6\\3&-5\end{vmatrix}\\&=-2\begin{vmatrix}1&3\\3&-5\end{vmatrix}\\&=-2\begin{vmatrix}1&3\\0&-14\end{vmatrix}\\&=28.\end{align}

REPLY [1 votes]: It's important to know what types of operations change the determinant. Replacing a row after you've scaled it will scale the determinant. So you should replace a row you didn't scale. For example:$$\underbrace{\begin{bmatrix}
3&-5\\
2&6
\end{bmatrix}\sim\begin{bmatrix}
0&-14\\
2&6
\end{bmatrix}}_{R_1-\frac{3}{2}R_2\implies R_1}$$
Which has determinant $28.$
Now, you swapped two rows, so you are right to change the sign. But when you multiplied by $\frac{1}{2}$ you then need to multiply by 2 to get the correct determinant in the end.


text:
\begin{document}

\maketitle
\section{Abstract:}
In 1966, Galli proposed a question: whether every connected graph has a vertex that is common to all it longest paths. The answer to that is negative. Another related question was raised in 1995 at British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? In this paper it is shown that the answer to that question is \textbf{yes}.\\
\\
Keywords: longest path, intersection of longest paths.
\section{Introduction:}
In 1966, during a colloquium on graph theory, Galli[1] asked whether every longest path in a connected graph have a vertex in common. A few years later, Walther[2] answered this question negatively by exhibiting a counter example on 25 vertices. Another question was asked in 1995, whether every three longest path in a connected graph has a vertex in common[3]. The only known progress in this problem were obtained by Axenovich[4], who proved the problem for outer-planar graphs, and by Rezende, Fernansex, Martin, Wakabayashi[5], who proved that in a connected graph in which all non-trivial blocks are Hamiltonian, then any three paths have a common vertex.\\
\\

In this paper, I show that for a 2-dimensional connected graph, any three longest paths share a common vertex.\\
\section{The proof:}

\textbf{Theorem:} Any three longest paths in a connected graph has a common vertex. \\
\\
\textbf{proof:}\\
Let \textbf{\textit{G}} be a \textit{connected graph} in a 2-dimensional plane. Let the length of the longest path in \textbf{\textit{G}} be \(n\).
Suppose \(P_1,P_2,P_3\) are paths in \textbf{\textit{G}} of length \(n\) and \(P_i=\langle p_{i1},p_{i2},...,p_{in}\rangle\). \\
\\
\textbf{Lemma 1:} Any two longest paths in \textbf{\textit{G}} has at least one common vertex.\\
\\
proof:\\
Consider two longest paths \(P_i\) and \(P_j\). Lets assume they don't have a common vertex. Since \textbf{\textit{G}} is connected, there is a path \(P^\prime\)  connecting \(p_{ik}\) and \(p_{jk^\prime}\) for some \(k,k^\prime \in \{1,2,...,n\}\) such that \(P^\prime\) shares no vertex with \(P_i\cup P_j\) other than \(p_{ik}\) and \(p_{jk^\prime}\). Say \(P^\prime = \langle p_{ik},v_1,v_2,...,v_b,p_{jk^\prime}\rangle\).\\
\\
Without loss of generality we can assume \(k,k^\prime\geq\lceil\frac{n}{2}\rceil\) (we can always reverse the numbering). Then we can construct a new path \(P^*=\langle p_{i1},p_{i2},...,p_{ik},v_1,v_2,...,v_b,p_{jk^\prime},...,p_{j1}\rangle\)\\
\\
Clearly \(P^*\) has a length of at least \(n+1\) which contradicts the assumption that \textbf{\textit{G}} has no path of length greater that \(n\).\\
\\
Hence, any two longest path in a connected graph must have at least one vertex in common. \\
\\
\textbf{Lemma 2:}
If the length of the longest path in a connected graph is even, then either the longest path is unique or any two longest paths have more than one vertex in common.\\
\\
proof:\\
Assume the contrary, that there are two longest paths \(P_i\) and \(P_j\) of length \(2m\) and have only one vertex in common. Say \(p_{ik}=p_{jk^\prime}\) for some \(k,k^\prime \in \{1,2,...,2m\}\). Without loss of generality, we can assume that \(k,k^\prime\geq m\).\\
\\
case 1: If \(k\) or \(k^\prime\) is greater than \(m\).\\
\\
Suppose \(k>m\). The path form \(p_{i1}\) to \(p_{ik}\)(or \(p_{jk^\prime}\)) along \(P_i\)  has at least \(m+1\) vertices and path from \(p_{ik}\)(or \(p_{jk^\prime}\)) to \(p_{j1}\) along \(P_j\) has at least \(m\) vertices. So, this path \(\langle p_{i1},p_{i2},...,p_{ik}(or\;p_{jk^\prime}),p_{jk^\prime - 1},...,p_{j1}\rangle\) has a length of a least \(2m+1\),  which is a contradiction.\\
\\
case 2: If \(k=k^\prime=m\).\\
\\
Consider the path from \(p_{in}\) to \(p_{ik}\)(or \(p_{ik^\prime}\)) along \(P_i\) and then to \(p_{jn}\) along \(P_j\). Clearly, this path \(\langle p_{in},p_{in-1},...,p_{ik}(or\;p_{jk^\prime}),p_{jk^\prime+1},...,p_{jn}\rangle\) has a length of \(2m+1\). Which is a contradiction. \\
\\
Hence, in a connected graph with even longest path length, either the longest path is unique or any two longest paths have more than one common vertex. \\
\\
\subsection{Case 1:}
Suppose \(P_i\) and \(P_j\) are two longest paths in a connected graph \textbf{\textit{G}}. If \(p_{ik}=p_{jk^\prime}\) (i,e., if \(P_i\) and \(P_j\) share a vertex) for some \(k,k^\prime\in\{1,2,...,n\}\), then \(k=k^\prime\).\\
\\
Assuming the above statement to be true, we proceed as following:\\
\\

\textbf{Lemma 3:}
Suppose \(P_1,P_2,P_3\) are three longest paths in a graph \textbf{\textit{G}}. Let \(\{p_{2t_1},p_{2t_2},...,p_{2t_a}\}\) be the common vertices of \(P_1\) and \(P_2\) and let \(\{p_{2r_1},p_{2r_2},...,p_{2r_b}\}\) be the common vertices of \(P_2\) and \(P_3\) where \(t_i,r_j\in\{1,2,...,n\}\) and \(t_1<t_2<...<t_a\) and \(r_1<r_2<...<r_b\). Then there are no \( p,q\in \{1,2,...,a\}\) and \(s\in\{1,2,...,b\}\) such that \(t_p<r_s<t_q\).\\
\\
proof:\\
Note:  We know that \(p_{2t_1}=p_{1t_1},p_{2t_2}=p_{1t_2},...,p_{2t_a}=p_{1t_a}\) and \(p_{2r_1}=p_{3r_1},p_{3r_2}=p_{3r_2},...,p_{2r_b}=p_{3r_b}\).
Assume there are such \(p,q\in\{1,2,...,a\}\) and \(s\in\{1,2,...,b\}\) such that \(t_p<r_s<t_q\). Without loss of generality, we can assume there are no intersections of \(P_2\) with \(P_1\) and \(P_3\) between the points \(p_{2t_p}\) and \(p_{2tq}\) other than \(p_{2r_u}\) and assume \(p_{2t_p}\) is not common to all the three paths. Now consider the path from \(p_{31}\) to \(p_{2r_s}\) along \(P_3\). It is clear from lemma 3 that \(\;\mid\mid\langle p_{31},p_{32},...,p_{2r_s}\rangle\mid\mid=r_s\). Now walk up from \(p_{2r_s}\) to \(p_{2t_p}\) along \(P_2\), \(\mid\mid\langle p_{2r_s-1},...,p_{2t_p}\rangle\mid\mid=r_s-t_p\). Then from \(p_2t_p\) to \(p_2t_q\) along \(P_1\), \(\mid\mid\langle p_{1t_p-1},...,p_{2t_q}\rangle\mid\mid=t_q-t_p\). Then from \(p_2t_q\) to \(p_{1n}\) along \(P_1\), \(\mid\mid\langle p_{2t_q+1},...,p_{1n}\rangle\mid\mid=n-t_q\) (we can walk this path because \(t_q\) is the largest index we have walked this far, hence vertices \(p_{1t_q+1},...,p_{1n}\) has not been walked on before).
So, the total path length is \(r_s+(r_s-t_p)+(t_q-t_p)+(n-t_q)=n+2(r_s-t_p)>n\), which contradicts the assumption that the largest path length is \(n\). Hence there are no \( p,q\in \{1,2,...,a\}\) and \(s\in\{1,2,...,b\}\) such that \(t_p<r_s<t_q\).\\
\\
This implies either three paths intersect at the same vertices, or \(t_1<t_2<...<t_a<r_1<r_2<...<r_b\)\\
\\
We work with the later scenario.\\
\\

Suppose \(P_1,P_2,P_3\) are three longest paths in a graph \textbf{\textit{G}}. We assume that the do not have a common vertex. Let \(\{p_{2t_1},p_{2t_2},...,p_{2t_a}\}\) be the common vertices of \(P_1\) and \(P_2\) and let \(\{p_{2r_1},p_{2r_2},...,p_{2r_b}\}\) be the common vertices of \(P_2\) and \(P_3\) where \(t_i,r_j\in\{1,2,...,n\}\) and \(t_a<r_b\). \\
Call \(\mid\mid\langle p_{11},p_{12}...,p_{2t_a}\rangle\mid\mid=\mid\mid\langle p_{21},p_{22},...,p_{2t_a}\rangle\mid\mid=x\) and  \(\mid\mid\langle p_{2r_1+1},p_{2r_1+2}...,p_{2n}\rangle\mid\mid=\mid\mid\langle p_{3r_1+1},p_{3r_1+2},...,p_{3n}\rangle\mid\mid=y\). Then \(\mid\mid\langle p_{2t_a+1},p_{2t_a+2}...,p_{2r_1}\rangle\mid\mid=n-x-y\). \\
Now consider the path \(\langle p_{1n},p_{1n-1}...,p_{2t_a}\rangle\), then from here, take the path \(\langle p_{2t_a+1},p_{2t_a+2}...,p_{2r_1}\rangle\) and then \(\langle p_{3r_1+1},p_{3r_1+2}...,p_{3n}\rangle\). The path length is \((n-x)+(n-x-y)+(n-y)=3n-2(x+y)\)\\
But \(3n-2(x+y)\leq n\Rightarrow n\leq x+y\), which is a contradiction because \(x+y<\mid\mid p_2\mid\mid\).\\
Hence, they must share a common vertex.
\subsection{Case 2:}
Assuming the statement of case 1 is false.\\
\\
We will be using a lemma 1 from Axenovich's paper, which is
\begin{figure}[H]
    \centering
    \includegraphics[width=\linewidth]{4.PNG}
    \caption{Lemma 1 of Axenovich's paper}

\end{figure}
The paths \(P_1\) and \(P_2\) would have a configuration similar to this:
\begin{figure}[H]
    \centering
    \includegraphics[width=1\textwidth]{graph1.png}
    \caption{}

\end{figure}
If we stretch \(P_1\) straight, and represent the intersections by lines connecting the common vertices on the paths, then it would look like this:
\begin{figure}[H]
    \centering
    \includegraphics[width=1\textwidth]{graph2.png}
    \caption{}

\end{figure}
Now we introduce a third path of same length \(P_3\) and examine how it interacts with \(P_1\) and \(P_2\). \\
\\
From lemma 1, we know that \(P_3\) will intersect both \(P_1\) and \(P_2\) at some point. So, \(P_3\) will jump from \(P_1\) to \(P_2\). To avoid \(Q_2\) configuration, we see that \(P_3\) can jump from \(P_1\) to \(P_2\) only in the following 12 fashion:
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{graph3.png}
    \caption{}
    \includegraphics[width=.5\textwidth]{graph4.png}
    \caption{}
    \includegraphics[width=.5\textwidth]{graph5.png}
    \caption{}
    \end{figure}
Every other possible fashion of intersection is similar to one of these. Figure 3 is equivalent to figure 7, figure 4 is equivalent to figure 8 and figure 6 is equivalent to figure 9.
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{graph6.png}
    \caption{}
     \includegraphics[width=.5\textwidth]{graph7.png}
     \caption{}
    \end{figure}
\begin{figure}[H]
    \centering

    \includegraphics[width=.5\textwidth]{graph8.png}
    \caption{}
    \end{figure}

Note: Whatever may the choice for \(y\) be, the segment \(\langle x,y\rangle\) of \(P_3\) doesn't intersect with any other path. (We can always find such a segment of \(P_3\) as \(P_3\) jumps from \(P_1\) to \(P_2\) at some point.)

Consider this path: start at \(x\) i.e., the bottom of the yellow line connecting \(P_3\) and \(P_1\), jump from \(P_3\) to \(P_1\), now, move right, to the closest black line connecting \(P_1\) and \(P_2\), jump to \(P_2\) from \(P_1\), then walk towards \(y\) on \(P_2\) and then jump from \(P_2\) to \(P_3\) and move towards \(x\).
\\
Example:
\begin{figure}[H]
    \centering
    \includegraphics[width=\linewidth]{graph12.png}
    \caption{}
    \label{}
\end{figure}

We can always walk such a path, as the segment of \(P_3\) doesn't intersect with anything, and segments of \(P_1\) and \(P_2\) don't intersect due to construction.
We get a cycle which satisfies the properties of \(Q_1\).
rename \(P_2\) as \(P_0\) and \(P_3\) as \(P_2\). And segment of \(P_0,P_1,P_2\) as \(S_0,S_1,S_2\) respectively. Clearly interior of \(S_0\) and interior of \(S_2\) do not contain any vertices of \(P_1\) and interior of \(S_1\) and interior of
\(S_2\) do not contain any vertices of \(P_0\).
\begin{figure}[H]
    \centering
    \includegraphics[width=\linewidth]{graph13.png}
    \caption{}
    \label{}
\end{figure}

Hence, we can't avoid both \(Q_1\) and \(Q_2\) configuration simultaneously if we want \(P_1,P_2,P_3\) not to have a common vertex. And hence, \(P_1,P_2,P_3\) must have a common vertex.
\section{Acknowledgements:}
I thank Jui Koley (Sarojini Naidu College for Women, Kolkata, India), for motivating me to do this research and I would like to  thank Simion De (Indian Statistical Institute, Kolkata, India) for cross checking my proof.
\section{References:}
{[1]} Galli,T., \textit{Problem 4}, in: \textit{Theory of Graphs} (1968), p. 362.\\
\\
{[2]}  Walther, H.,. Combinatorial Theory 6 (1969), pp. 1–6.\\
\\
{[3]} Research problems, Discrete Mathematics 167/168 (1997), pp. 605–615, 15th
British Combinatorial Conference.\\
\\
{[4]} Axenovich, M.,\textit{ When do three longest paths have a common vertex?}, Discrete
Mathematics, Algorithms and Applications 1 (2009), pp. 115–120.\\
\\
{[5]} Susanna F. de Rezende  Cristina G. Fernandes
Daniel M. Martin  Yoshiko Wakabayashi., \textit{Intersection of Longest Paths in a Graph}.

\end{document}


TITLE: Example of Devil's nested radicals
QUESTION [2 upvotes]: Let the following nested radical :
$$\sqrt{665+2x}=x$$
There is a hidden quadratic equation and the result is :
$$x=\sqrt{666}+1$$
So we see the number $666$ appear .
My question :
Do you know (more or less trivial) nested radical where the devil's number appear ?
Can we build it as in my example ?
Thanks in advance and have fun .
Ps: I don't speak about Galois's theory .

REPLY [2 votes]: Setting aside the fact that "the Number of the Beast" might be 616, or perhaps both 616 and 666 based on different spellings of "(Emperor) Nero", we can render 666 from an appropriate combination of the seemingly innocuous numbers 3 and 15:
$\sqrt{(15+\sqrt3)\sqrt3}$
To wit:
$\sqrt{(15+\sqrt3)\sqrt3}=\sqrt{(15\sqrt3)+\sqrt9}$
Then apply the identity
$\sqrt{a+\sqrt b}=\sqrt{(a+\sqrt{a^2-b})/2}+\sqrt{(a-\sqrt{a^2-b})/2}$
where here $a^2=675$ and $b=9$:
$\sqrt{(15+\sqrt3)\sqrt3}=\sqrt{(15\sqrt3+\sqrt{666})/2}+\sqrt{(15\sqrt3-\sqrt{666})/2}$.
The number 616 actually has this beat.  Start with just $2\sqrt7$ and use the same identity as above, with $25^2=625$:
$2\sqrt7=\sqrt{25+\sqrt9}=\sqrt{(25+\sqrt{616})/2}+\sqrt{(25-\sqrt{616})/2}$.


TITLE: Is $[0,\frac{1}{2})$ open in $[0,1]$ w.r.t usual metric d?
QUESTION [1 upvotes]: Question:

Consider $[0,1]$ as a metric space, with metric the restriction $d$ on
  $[0,1]$. Show that w.r.t this metric $[0,\frac{1}{2})$ is open in
  $[0,1]$

There is a solution which says:
'$[0,\frac{1}{2})$ = $[0,1]$ $\cap$ $(-\frac{1}{2}, \frac{1}{2})$'
Firstly, could some explain this to me? I understand how it is an intersection, but $(-\frac{1}{2}, \frac{1}{2})$ is not in $[0,1]$ so how can we use it as an open interval?
My solution was:
$[0,1] \setminus [0,\frac{1}{2})$ = $[\frac{1}{2}, 1]$ which is a closed interval and thus $[0,\frac{1}{2})$ is open. Does this work?

REPLY [4 votes]: The solution given uses the fact that $[0,1]$ is a subspace of $\mathbb{R}$ and inherits its topology from it. As such, a subset $X \subset [0,1]$ is open iff there exists an open subset $U \subset \mathbb{R}$ such that $U \cap [0,1] = X$. In this case, $U = (-1/2, 1/2)$ is open in $\mathbb{R}$, thus $X = U \cap [0,1] = [0, 1/2)$ is open in $[0,1]$.
Since we're dealing with metric spaces, it's also easier to just notice that $[0,1/2)$ is an open ball in $[0,1]$, with center $0$ and radius $1/2$. So by definition of the topology of $[0,1]$, it is open.
Your solution uses the fact that $[1/2,1]$ is closed in the space $[0,1]$, something that you have not proven. Indeed, you only know that $[1/2, 1]$ is closed in $\mathbb{R}$.
You can again argue that $[1/2,1]$ is the closed ball with center $1$ and radius $1/2$, and is thus closed. But another general fact is that if $E \subset \mathbb{R}$ is closed, then the closed subsets of $E$ are exactly the closed subsets of $\mathbb{R}$ which are contained in $E$. In your case $[0,1]$ is closed, so a subset $F \subset [0,1]$ is closed in $[0,1]$ iff it is closed in $\mathbb{R}$.

REPLY [0 votes]: In my opinion, the correct answer here is that in $([0,1],d)$ the set
$$
B^{[0,1]}_{\frac12}(0) = \{x \in [0,1] \mid d(x,0) < \tfrac12\} = [0,\tfrac12)
$$
is open by definition.
Your answer only works if you have a clear reason why $[\tfrac12, 1]$ is closed in $[0,1]$.
Their answer is a lot like 'my' answer: the set $(-\tfrac12,\tfrac12)$ is equal to $B^{\mathbb R}_{\frac12}(0)$ in $\mathbb R$, and -- as long as $x$ is an element of a subset $X$ of $\mathbb R$ -- we always have the equality
$$
B^{\mathbb R}_{\epsilon}(x) \cap X = B^X_{\epsilon}(x).
$$

REPLY [0 votes]: Definition: A subset $A$ of the metric space $([0,1],d)$ is open in $([0,1],d)$ if there is an open subset $B$ of the metric space $(\mathbb R,d)$ such that
$A=[0,1] \cap B$
In your question: $A=[0,\frac{1}{2})$ and $B=(-\frac{1}{2}, \frac{1}{2})$


TITLE: How to find the Most likelihood estimator for
QUESTION [1 upvotes]: $f\left( x\right) =\begin{cases}e^{-\left( x-\theta \right) },  x \ge \theta\\
0\end{cases}$
We want to find the estimator for $\theta$. I already have the solution but I don't understand it.
They first write this $ f(x;\theta) = e^{(\theta-x)} \cdot 1_{(x \ge 0)}$ I don't understand why and what it means so I would like clarifications on that.
Then they find the joint mass function (I am not going to enter into details here because I  know what's going on mostly $f(x;\theta) = \exp \left\{ n\theta -\sum ^{n}_{i=1}x_{i}\right\} \cdot 1_{\left( x_{1}\ge 0\right) }$. Now why is it $x_1$ under the $1$ instead of $x_i$ ? Why do we take the smallest value?
They than proceed in saying that: "The maximum likelihood estimator for $\theta$ is simply the value of θ that maximizes this function. Now,
seen as a function of θ, it is increasing up to the point θ = $x_{(1)}$, after which it becomes 0. So it's at this point that it's maximized, which means that $\widehat {\theta } =  X_1$"
I don't understand their statement, how is $\theta$ going to equal the smallest value if $n$ is increasing?

REPLY [2 votes]: First, your question has a typo: $f(x,\theta)$ should be $\exp(\theta-x)1_{x\ge\theta}.$
The notation $1_{x_i\ge\theta}$ is read as indicator that $x_i>\theta.$ It means the following:
$$1_{x_i\ge\theta}=\begin{cases}1\hspace{2cm}\text{if }x_i\ge\theta
\\0\hspace{2cm}\text{otherwise.}\end{cases}$$
Let us study the joint distribution now. It is known that joint of independent random variables becomes product of their distributions. Then the joint is
$$f(x_1,...,x_n;\theta)=\displaystyle\exp(n\theta-\sum_{i=1}^n x_i)\prod_{i=1}^n1_{x_i\ge\theta}.$$
Look at the product $\prod_{i=1}^n1_{x_i\ge\theta}.$ It can be $1$ or $0.$ When is it $0?$ Whenever any one of the $x_i$'s is less than $\theta.$ So the product is $1$ if and only if all the $x_i$'s are larger than $\theta,$ that is, if and only if $x_{(1)}=\min x_i\ge\theta.$
We have now answered the question of how $x_{(1)}$ comes up. Now look at the joint likelihood as a function of $\theta.$ $\exp(n\theta)$ is increasing. If $\theta<x_{(1)},$ likelihood function is positive and increasing in $\theta,$ and if $\theta>x_{(1)},$ likelihood becomes zero. To maximize the likelihood, we take $\theta=x_{(1)}.$


TITLE: Do laws of black hole mechanics depend on dimensionality?
QUESTION [1 upvotes]: Unfortunately I'm not very familiar with the proof methods of the laws of black hole mechanics/thermodynamics. Do they hold in any number of dimensions? Are there any "hidden" assumptions? I'm thinking natural assumptions like asymptotic flatness (which would not hold for AdS black holes), or cosmic censorship (which I believe is violated in $D\geq 5$). Or are the laws simply general statements about event horizons?

REPLY [1 votes]: The mass-energy, radius, entropy, lifetime etc. are related with power laws whose exponents depend on not only $D$ but in some cases also the geometry. For example, which $p$ gives the entropy-energy relation $S\propto E^p$? If the universe is otherwise Minkowski, $p=\frac{D}{D-2}$; if it's anti-de Sitter, $p=\frac{D-2}{D-1}$. As explained here, the former indicates quantum gravity is non-renormalisable while the latter motivates interest in the AdS/CFT correspondence.