text:
\begin{document}
\begin{abstract}
A variation of Dyck paths allows for down-steps of arbitrary length, not just one. This is motivated by ideas due to Emeric Deutsch.  We use the adding-a-new-slice technique and the kernel method to compute the number of maximal runs of up-step runs of length 1
and a subclass of Deutsch paths satisfying a condition that was stipulated by R. Stanley for Dyck paths.
	\end{abstract}

\maketitle

\section{Introduction}

A Dyck path consists of up-steps $(1,1)$ and down-steps $(1,-1)$. They start at the origin, end at the origin and never go below the $x$-axis.
\begin{center}

\begin{tikzpicture}[scale=0.35]

	\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (20.0,5.0);
	\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,2) to (5,1) to (6,0)to (7,1)to (8,0)to (9,1)to (10,2)to (11,3)to (12,4)to (13,3)to (14,4)to (15,5)to (16,4)to (17,3)to (18,2)to (19,1)to (20,0);
\end{tikzpicture}
\end{center}
The path in the example is a Dyck path of length 20, and has 4 `mountains', i.e. a maximal sequence of up-steps followed by a maximal sequence of down-steps.
Sometimes we also allow a path to end at a level different from zero. To emphasize the fact that the end-level is unspecified, we use the word \emph{open}.
In \cite{BF}, this is called a \emph{meander}, whereas the version that returns to the $x$-axis is called an \emph{excursion}.

Deutsch paths are like Dyck paths, but extra down-steps of the form $(1,-j)$, for any $j\ge2$, are also allowed.
They were analyzed recently in \cite{Prodinger-Deutsch}. Here, we want to enumerate them in a different manner
which is quite versatile when certain parameters of Deutsch paths should be analyzed.

We decompose a Deutsch path into maximal runs of up- resp.\ down-steps. First, we restrict our attention to the instance when the path ends with down-steps. If a path is closed (=ends on the $x$-axis), this happens anyway (except for the empty path), but for open-ended paths, the last step of the path might be an up-step.

The technique we are using can be found in \cite{FP}.

We consider two applications:
It is well-known that the $n$-th Catalan number $C_n =\frac{1}{n+1}\binom{2n}{n}$
enumerates Dyck paths of
length $2n$. In \cite{Stanley}, Stanley lists a variety of other combinatorial interpretations of the Catalan
numbers, one of them being the number of Dyck paths from $(0, 0)$ to $(2n+2, 0)$ such that any
maximal sequence of consecutive $(1,-1)$ steps ending on the $x$-axis has odd length. At this
point it is interesting to note that there are more subclasses of Dyck paths, also enumerated
by Catalan numbers, that are defined via parity restrictions on the length of the returns to the
$x$-axis as well (see, e.g., \cite{Stanley}). This restriction of Dyck paths that leads again to Catalan numbers
was further investigated in  \cite{HP}. In this paper, we consider Deutsch paths with the property
that each maximal run of down-steps to the $x$-axis starts at an odd level. Unfortunately, in this context,
this does not lead to any known or  nice numbers.

In the last section, we count the number of maximal sequences of up-steps consisting of only one up-step in Deutsch paths.

In the paper \cite{Estland}, the authors counted the number of maximal runs of up-steps of length one in Dyck paths. This was greatly extended in \cite{HHP};
the method of choice in the first incarnation of this paper was indeed the adding-a-new-slice technique combined with the kernel method.  We keep our analysis in the instance of Deutsch paths  simple and only consider the basic case, leaving more general considerations for later.

\section{Enumeration of Deutsch paths by the adding-a-new-slice technique}

We consider a generating function $F_k(z,u)$, where $k$ is the number of `mountains' (runs of up-steps, followed by runs of down-steps), $z$ marks the length of the path and $u$ is used to remember the last level reached (coefficient of $u^j$). To be more precise, the coefficient of $z^nu^j$ in $F_k(z,u)$, for which we write
$[z^nu^j]F_k(z,u)$ is the number of Deutsch paths with $k$ mountains, length $n$, and ending on level $j$.

The extra down-steps require some preparations. If one want to go down by $h\ge1$ levels, and do this in $n\ge1$ steps, it can be done in
\begin{equation*}
[z^h]\Bigl(\frac{z}{1-z}\Bigr)^n=[z^{h-n}](1-z)^{-n}=\binom{h-1}{h-n}
\end{equation*}
ways. (The notation of $[z^h]f(z)$ refers, as just said, to the coefficient of $z^n$ in a generating function $f(z)$.)
To understand this, we are looking at the coefficient of $z^h$ in
\begin{equation*}
\underbrace{(z+z^2+\cdots)(z+z^2+\cdots)\dots(z+z^2+\cdots)}_{n \text{ copies}},
\end{equation*}
and any choice of $i_1+\cdots+i_n=h$ is a possibility to go down by $h$ levels in $n$ steps.
 If one wants to keep $n$ variable, using a generating function, we get, using the binomial theorem,
\begin{equation}\label{down-h}
\sum_{n=1}^{h}\binom{h-1}{h-n}z^n=z(1+z)^{h-1}.
\end{equation}
This will also be used later. And now, for modeling a new mountain,  we have to compute this:
\begin{equation*}
\sum_{k>i}z^{k-i}\sum_{0\le j<k}u^jz(1+z)^{k-1-j}=\frac{z^2(1+z)^{i+1}}{(1-z-z^2)(1+z-u)}-\frac{z^2u^{i+1}}{(1-zu)(1+z-u)}.
\end{equation*}
Consequently we have
\begin{equation*}
F_{k+1}(z,u)=\frac{z^2(1+z)}{(1-z-z^2)(1+z-u)}F_k(z,1+z)-\frac{z^2u}{(1-zu)(1+z-u)}F_k(z,u).
\end{equation*}
With
\begin{equation*}
\Phi(z,u):=\sum_{k\ge0}F_k(z,u),
\end{equation*}
(arbitrary number of mountains) this leads to
\begin{equation*}
	\Phi(z,u)-1=\frac{z^2(1+z)}{(1-z-z^2)(1+z-u)}\Phi(z,1+z)-\frac{z^2u}{(1-zu)(1+z-u)}\Phi(z,u)
\end{equation*}
or
\begin{equation*}
	\frac{z(u-u_1)(u-u_2)}{(1-zu)(1+z-u)}\Phi(z,u)=1+\frac{z^2(1+z)}{(1-z-z^2)(1+z-u)}\Phi(z,1+z),
\end{equation*}
with
\begin{equation*}
	u_{1,2}=\frac{1+z\pm\sqrt{1-2z-3z^2}}{2z}.
\end{equation*}
A naive approach to solve this functional equation would be to plug in $u=1+z$ and solve. However, this leads to a void equation. The kernel method is a way to still use
the idea of plugging in, but first a `bad' factor has to be removed from numerator and denominator. One of two factors $(u-u_1(z))$, $(u-u_2(z))$ is bad, since, when appearing in the denominator, does not lead to a valid power series expansion around $(0,0)$. In this instance, $u-u_2(z)\sim u-z+\cdots$ and this is the bad factor. Rephrasing, setting
$u:=u_2(z)$ leads to an equation, since the bad factor must be cancelled from both, numerator and denominator.

As it was shown already in \cite{Prodinger-Deutsch}, we are in the Motzkin world.
Recall that the generating function of Motzkin-paths (Dyck paths, but horizontal steps are also allowed) is given by
\begin{equation*}
M(z)=\frac{1-z-\sqrt{1-2z-3^2}}{2z^2}.
\end{equation*}
Now we use arguments from the kernel method \cite{kernel}, as just recapitulated.
The factor $(u-u_2)$ must also be a factor of the right-hand side, otherwise there would not be a power series expansion around
$z=0$. This leads to
\begin{equation*}
\frac{1+\frac{z^2(1+z)}{(1-z-z^2)(1+z-u)}\Phi(z,1+z)}{u-u_2}=-\frac1{1+z-u}.
	\end{equation*}
	Further simplification leads to
\begin{equation*}
	\Phi(z,u)=-\frac{(1-zu)}{z(u-u_1)}=\frac{1-zu}{zu_1(1-u/u_1)}.
\end{equation*}
	Setting $u=0$ means that the path ends on the $x$-axis:
\begin{equation*}
	\Phi(z,0)=\frac{1}{zu_1}=\frac{1+z-\sqrt{1-2z-3z^2}}{2z(1+z)}=
	1+{z}^{2}+{z}^{3}+3{z}^{4}+6{z}^{5}+15{z}^{6}+36{z}^{7}+\cdots.
\end{equation*}
The coefficients of this series are sometimes called \emph{Riordan numbers}, see A005043 in \cite{OEIS}.
As an illustration, we provide the 6 Deutsch paths (returning to the $x$-axis) of length 5:
\begin{center}
	\begin{tikzpicture}[scale=0.35]
		\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,4.0);

		\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,4) to (5,0);
	\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
	\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,3.0);

	\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,2) to (5,0);
\end{tikzpicture}
	\begin{tikzpicture}[scale=0.35]
		\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,3.0);

		\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,1) to (5,0);
	\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
	\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,2.0);

	\draw[thick] (0,0) to (1,1) to (2,2) to (3,1) to (4,2) to (5,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
	\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,2.0);

	\draw[thick] (0,0) to (1,1) to (2,2) to (3,0) to (4,1) to (5,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
	\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (5.0,2.0);

	\draw[thick] (0,0) to (1,1) to (2,0) to (3,1) to (4,2) to (5,0);
\end{tikzpicture}

\end{center}

\medskip

	As seen  already in \cite{Prodinger-Deutsch}, the substitution $z=\dfrac{v}{1+v+v^2}$ makes everything prettier:
\begin{equation*}
	\Phi(z,0)=\frac{1+v+v^2}{1+v}.
\end{equation*}
The function
\begin{equation*}
\Phi(z,u)\frac1{1-zu}
\end{equation*}
describes Deutsch paths that can also end with up-steps. And if one replaces now $u:=1$, we get so-called open Deutsch paths, that can end at any level:
\begin{equation*}
	\Phi(z,1)\frac1{1-z}=\frac{1}{z(u_1-1)}=1+v+v^2,
\end{equation*}
which also enumerates Motzkin paths. This was explained via a bijection in \cite{Prodinger-Deutsch}. Let us emphasize that $	\Phi(z,1)$ is
the generating function of open Deutsch paths ending with down-steps, and $\frac1{1-z}$ is the generating function of a possible sequence of up-steps at the end.

\section{Deutsch paths satisfying a  condition by Stanley}
As mentioned above, the function
\begin{equation*}
\Phi(z,u)\frac1{1-zu}
\end{equation*}
describes Deutsch paths that can also end with up-steps. Consequently,
\begin{equation*}
\mathcal{G}(z,u)=	\Phi(z,u)\frac{zu}{1-zu}=\frac{u}{u_1(1-u/u_1)}=\sum_{k\ge1}\frac{u^k}{u_1^k}
\end{equation*}
is the generating function of paths (`good' paths) ending with an up-step. From this we see that the good paths ending on level $k$ have
generating function $1/u_1^k$.

In the spirit of Stanley, we now compute good Deutsch paths, ending on the odd level $2k+1$, and return after that for the \emph{first time} in a series of down-steps to the $x$-axis:
\begin{equation*}
z\sum_{k\ge0}\frac{1}{u_1^{2k}}\cdot z(1+z)^{2k} =\frac{z^2}{1-(1+z)^2/u_1^2}.
\end{equation*}
To clarify, the first $z$ in this formula is responsible for a first extra up-step, making sure that returns to the $x$-axis occur only at the end.
The other factor $z$ belongs to $z(1+z)^{2k}$ and originates from formula \eqref{down-h}.

The final step is to consider an arbitrary sequence of such paths, viz.
\begin{equation*}
\dfrac{1}{1-\frac{z^2}{1-(1+z)^2/u_1^2}}=\frac{3+z-\sqrt{1-2z-3z^2}}{2(1+z)}=\frac{1+2v+2v^2}{(1+v)^2}.
\end{equation*}
This series is
\begin{equation*}
1+{z}^{2}+2 {z}^{4}+2 {z}^{5}+7 {z}^{6}+14 {z}^{7}+37 {z}^{8}+90
 {z}^{9}+233 {z}^{10}+\cdots,
\end{equation*}
and the coefficients do not bare any significance to Motzkin numbers.

For interest, here are the $7$ objects of length $6$, satisfying the Stanley-condition that each down-run to the $x$-axis starts at an odd level.

\begin{center}
\begin{tikzpicture}[scale=0.35]
\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,1.0);

\draw[thick] (0,0) to (1,1) to (2,0) to (3,1) to (4,0) to (5,1) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,3.0);

\draw[thick] (0,0) to (1,1) to (2,0) to (3,1) to (4,2) to (5,3) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]
\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,3.0);

\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,0) to (5,1) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]

\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,5.0);
\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,4) to (5,5) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]

\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,3.0);
\draw[thick] (0,0) to (1,1) to (2,2) to (3,1) to (4,2) to (5,3) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]

\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,3.0);
\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,2) to(5,3) to (6,0);
\end{tikzpicture}
\begin{tikzpicture}[scale=0.35]

\draw[step=1.cm,black,dotted] (-0.0,-0.0) grid (6.0,3.0);
\draw[thick] (0,0) to (1,1) to (2,2) to (3,3) to (4,2) to (5,1) to (6,0);
\end{tikzpicture}

\end{center}
The first and the last   are Dyck-paths, and 2 is indeed the Catalan number $C_2$.

	\section{Counting runs of single up-steps}

The approach is quite similar to the previous sections; however, we use a third variable, $t$, to count the up-runs of length one.

We have to compute this (for $t=1$, it coincides with the previous computation):
\begin{equation*}
	\sum_{k>i+1}z^{k-i}\sum_{0\le j<k}u^jz(1+z)^{k-1-j}+tz\sum_{0\le j\le i}u^jz(1+z)^{i-j},
\end{equation*}
which leads to
	\begin{equation*}
		F_{k+1}(z,u)=\alpha F_k(z,u)+\beta F_k(z,1+z)
	\end{equation*}
	with
	\begin{equation*}
\alpha={\dfrac {{z}^{2}u \left( -zu+tzu-t \right) }{ ( 1-zu ) 			( 1+z-u ) }}
	\quad\text{and}\quad\beta=-{\dfrac {{z}^{2} ( 1+z )  ( -z-{z}^{2}+tz+t{z}^{2}-t) }{( 1-z-{z}^{2} )  ( 1+z-u )  }}.
	\end{equation*}
	This leads to
	\begin{equation*}
		\Phi(z,u)-1=\alpha\Phi(z,u)+\beta\Phi(z,1+z)
	\end{equation*}
	or
	\begin{equation*}
		\frac{z(1+z^2-tz^2)(u-u_1)(u-u_2)}{(1-zu)(1+z-u)}\Phi(z,u)=1+\beta\Phi(z,1+z),
	\end{equation*}

	The two roots are now
	\begin{equation*}
		u_{1,2}={\frac {-t{z}^{2}+z+1+{z}^{2}\pm\sqrt {{t}^{2}{z}^{4}+2 t{z}^{3}-
					2 t{z}^{2}+2 t{z}^{4}-{z}^{2}-2 z-2 {z}^{3}+1-3 {z}^{4}}}{2z
				( 1+{z}^{2}-t{z}^{2}) }}.
	\end{equation*}
	Simplification, after dividing out the factor $u-u_2$ from the equation, leads to
\begin{equation*}
\Phi(z,u)=\frac{(1-zu)}{z(1+z^2-tz^2)(u_1-u)}.
\end{equation*}
This time, we confine ourselves to the instance $u=0$, i.e., Deutsch paths returning to the $x$-axis. We get
\begin{align*}
	\Phi(z,&0)=\frac{1}{z(1+z^2-tz^2)u_1}\\&
={\frac {-t{z}^{2}+z+1+{z}^{2}-\sqrt {{t}^{2}{z}^{4}+2 t{z}^{3}-2
			 t{z}^{2}+2 t{z}^{4}-{z}^{2}-2 z-2 {z}^{3}+1-3 {z}^{4}}}{2z
		( 1+z )  ( {z}^{2}-t{z}^{2}+1 ) }}\\&
=1+t{z}^{2}+{z}^{3}+ ( {t}^{2}+2 ) {z}^{4}+ ( 3+3 t) {z}^{5}+ ( 7+7 t+{t}^{3} ) {z}^{6}+
( 17+13 t+6 {t}^{2} ) {z}^{7}+\cdots.
\end{align*}
Once one has this generating function, one can state many results as a corollary. We will only provide one such result, namely,  the average of the parameter labelled by the variable $t$. So, we differentiate $\Phi(z,0)$ w.r.t. $t$ and then set $t:=1$.
This leads to
\begin{equation*}
\frac{v^2}{(1-v)(1+v)^2(1+v+v^2)}.
\end{equation*}
We prefer the factored form since the term $1+v+v^2$ immediately reminds us of the Motzkin-world.

One could even read off the coefficients from this, but this would lead to a sum, so we refrain from doing this. However, we are interested in asymptotics. We will use singularity analysis, as is now customary, see \cite{FS}. In particular Example VI.3. on page 396 discusses the basics of the asymptotics of Motzkin numbers.

The relevant singularity is at $z=\frac13$, and we find, as $z\to\frac13$ (the square root vanishes at this value, and it is the closest value to the origin with this property).
Since
\begin{equation*}
v=\frac{1-z-\sqrt{1-2z-3z^2}}{2z},
\end{equation*}
the singularity translates into $v=1$, and one can compute a local expansion:
\begin{equation*}
v\sim 1-\sqrt{3}\sqrt{1-3z} \quad \Longleftrightarrow\quad 1-v \sim -\sqrt{3}\sqrt{1-3z}.
\end{equation*}

Furthermore,
\begin{equation*}
\frac{v^2}{(1-v)(1+v)^2(1+v+v^2)}\sim\frac{1}{12(1-v)}  \sim \frac{\sqrt3}{36\sqrt{1-3z}}.
\end{equation*}
Therefore
\begin{equation*}
[z^n]	\frac{v^2}{(1-v)(1+v)^2(1+v+v^2)}\sim [z^n]\frac{\sqrt3}{36\sqrt{1-3z}}\sim\frac{\sqrt3}{36}3^n\frac1{\sqrt{\pi n}}.
	\end{equation*}
The table on page 388 in \cite{FS} is particularly useful to translate from local expansions to asymptotics of coefficients.

This needs to be divided by the total number of such paths (the coefficient of $z^n$ in $\Phi(z,0)$), viz.
\begin{equation*}
[z^n]\frac{1+v+v^2}{1+v}\sim[z^n]\Big(\frac32-\frac{3\sqrt3}{4}\sqrt{1-3z}\Big)\sim \frac{3\sqrt3}{8}3^n\frac1{\sqrt{\pi} n^{3/2}}.
	\end{equation*}
The quotient is
\begin{equation*}
\sim\frac{2n}{27}=0.074 n.
\end{equation*}
So, a Deutsch path of length $n$ has about $0.074 n$ up-runs of length 1. Many such results could be derived with some patience and a computer.

\section{Concluding remarks}

We have demonstrated the usefulness of the adding-a-new-slice technique \cite{FP} in the instance of the relatively new class of Deutsch paths,
introduced in \cite{Prodinger-Deutsch}. Whenever it is possible to describe how a new mountain is created, a functional equation can be written.
A variation of the idea of Deutsch paths is to use down-steps $-1,-3,-5,-7,\dots$  instead of $-1,-2,-3,-4,\dots$, as done here.
This situation was analyzed in \cite{Prodinger-special}, but not with the adding-a-new-slice method. This is probably possible, but instead of a quadratic
equation with 2 factors, a cubic equation with 3 factors will play a role, and either one or two of them (depending on the model) need to be cancelled out.

\medspace

\textsc{Acknowledgment.} The insightful comments of one referee resulted in a much more elaborate and hopefully clearer exposition of this material.

config: arxiv


text:
\begin{document}
\title{Dirichlet problems on graphs with ends}
\subjclass[2010]{Primary: 31C20; Secondary: 05A99, 31C05}
\keywords{Discrete, Subharmonic, Potential Theory, Dirichlet Problem}

\author{Tony L. Perkins }
\address{ Department of Mathematics,  Spring Hill College, 4000 Dauphin Street, Mobile, Alabama 36608-1791}
\date{\today}

\begin{abstract}
In classical potential theory, one can solve the Dirichlet problem on unbounded domains such as the upper half plane.  These domains have two types of boundary points; the usual finite boundary points and another point at infinity.  W. Woess has solved a discrete version of the Dirichlet problem on the ends of graphs analogous to having multiple points at infinity and no finite boundary. Whereas C. Kiselman has solved a similar version of the Dirichlet problem on graphs analogous to bounded domains.  In this work, we combine the two ideas to solve a version of the Dirichlet problem on graphs with finitely many ends and boundary points of the Kiselman type.
\end{abstract}

\maketitle
\thispagestyle{empty}

\section{Introduction}
Let $D\subset\mathbb{R}^n$ be an open set and take a function $f\colon \partial D\rightarrow \mathbb{R}$.  The Dirichlet problem on $D$ with boundary data $f$ is to find a unique function $h$ which is harmonic on $D$, continuous on $\overline{D}$, and agrees with $f$ on the boundary, i.e. $h|_{\partial D}=f$.  Various methods, such as that of Perron, allow one to always find a harmonic function $h$ which is associated to $f$ in a natural way.  The main challenge is to determine when (or where) this $h$ matches $f$ on $\partial D$.  Given the way we've defined the Dirichlet problem the continuity of $f$ is clearly necessary.  For bounded open sets $D$, the uniqueness criteria follows from the maximum principle for harmonic functions.  However for unbounded domains uniqueness is non-trivial.

Consider the example of the upper half plane $\mathbb{H}=\{(x,y)\in \mathbb{R}^2\colon y\ge 0\}$.  If one wants to solve the Dirichlet problem on $\mathbb{H}$, we have trouble with uniqueness.  Indeed, the functions $f_1(x,y)=y$ and $f_2(x,y)=0$ are harmonic and identically equal to $0$ on the boundary of the upper half plane. In classical potential theory, to obtain uniqueness one adds a point at infinity, $\hat{\mathbb{H}}=\mathbb{H}\cup \{\infty\}$, and then considers the Dirichlet problem on $\hat{\mathbb{H}}$ with boundary $\partial\hat{\mathbb{H}}=\partial\mathbb{H}\cup\{\infty\}$.
Using Perron's method, to each $f\colon \partial \hat{\mathbb{H}}\rightarrow \mathbb{R}$, we can find a corresponding function $h\colon \hat{\mathbb{H}}\rightarrow \mathbb{R}$ which is harmonic.  To ensure that this $h$ equals $f$ on $\partial \hat{\mathbb{H}}$ all that is required of $f$ is to be continuous and bounded on $\partial \hat{\mathbb{H}}$, where continuous on $\partial\hat{\mathbb{H}}$ means that $f$ is continuous on $\partial \mathbb{H}$ and continuous at the point infinity.

In discrete potential theory, one often studies the Dirichlet problem on directed graphs.  Here one considers an arbitrary at most countable set $X$ as the vertex set.  Weighted directed edges are provided by a structure function $\lambda:X\times X \rightarrow \mathbb{R}$, where $\lambda\ge 0$, and $\lambda(x,y)>0$ denotes the existence of a directed edge from $x$ to $y$ with edge weight equal to $\lambda(x,y)$  ($\lambda(x,y)=0$ implies that there is no edge from $x$ to $y$), and with the additional condition $\sum_{y\in X} \lambda(x,y)=1$, the graph has the structure of a Markov chain.

Considering the domain as a Markov chain allows one to attack these types of problems with either probability or analysis.  This is of course true for the classical setting as well, e.g. \cite{D01}.  Here we take the analytic approach.

In \cite{K05} Kiselman defines the boundary of $X$ as
\[\partial{X} = \{x_0\in X\colon \lambda(x_0,x_0)=1\}\equiv \{x_0\in X \colon \lambda(x_0,y)=0 \text{ for all } y\in X\setminus\{x_0\}\}\]
and studies the Dirichlet problem in this setting.  To obtain uniqueness results, he considers only finite graphs.

However in probability one often studies a {\it reversible} Markov chain, i.e. $\lambda(x,y)>0 \iff \lambda(y,x)>0$.  In this setting Kiselman type boundary points trivially become isolated points of the graph.  Thus the only interesting formulation of a Dirichlet problem is a problem at infinity.  The principle works in this setting are those of \cite{CSW93,W88, W96}, where they solve a Dirichlet problem where the boundary points are the ends of the graph.

The primary goal of this paper is to begin the study of discrete Dirichlet problems with mixed boundary type, i.e. a graph with both Kiselman type boundary points and ends.  As a motivational example we look at the following simple `discretized' version of the upper half plane.
\begin{ex}
Consider the set $X=\mathbb{Z}^2 \cap \mathbb{H}$.  Define
\[\lambda((x_1,y_1), (x_2,y_2)) =
\begin{cases}
1/4 &\colon  (x_2-x_1)^2 + (y_2-y_1)^2=1 \text{ and } y_1 \neq 0 \\
1 &\colon x_1=x_2, y_1=y_2 \text{ and } y_1=0 \\
0 &\colon \text{ otherwise.}
\end{cases}\]
Then $\partial X = \mathbb{Z}^2 \cap \{y=0\}$ is a boundary set.  It is easy to check that the functions $f_1(x,y)=y$ and $f_2(x,y)=0$ are harmonic and identically equal to $0$ on $\partial X$.
\end{ex}

So uniqueness remains of principal concern.  However in $\hat{X}$, the end compactification of $X$, we add a single point at infinity.  Therefore $\hat{X}$ has the interesting structure of both a Kiselman type boundary and one end.

To study the Dirichlet problem on graphs of this type we introduce the notion of a quasi-reversible graph (reversible except for some Kiselman type boundary points).  We prove (Theorem \ref{T:max-prnc}) a maximum principle with regard to a boundary of mixed type, from which follows (Theorem \ref{T:unique}) a uniqueness result that holds for all connected quasi-reversible graphs.

It is a remarkable property of these mixed boundary problems that one-ended graphs are already non-trivial; a stark contrast to the setting in \cite{CSW93, W96}.  In the last section, we show (Theorem \ref{T:exists}) there exists a unique solution to Dirichlet problems of mixed boundary types on one ended graphs.  Finally we are able to extend the previous result to show (Theorem \ref{T:exists2}) there also exists a unique solution on graphs with finitely many ends.  Analogously to the classical setting we require the boundary data to be continuous at infinity.

The Dirichlet problem, i.e.\ harmonic interpolation, on graphs has applications to coverage problems on topological sensor networks, \cite[pp 62--63]{G10} and shape description problems in digital image analysis \cite{K05, W05}.

\section{Preliminaries}\label{S:basic}
Introductions to various aspects of discrete potential theory can be found in \cite{BLS07, S94, W94}. The basic structure we will be working over can be thought of as a directed graph with weights on the edges, which is also known as a network.  The weights will be assumed to be non-negative and can be thought of as transition probabilities.  Therefore another interpretation, e.g. \cite{W94}, is as a random walk on a graph or a Markov chain.

We start by considering an arbitrary at most countable set $X$.  This is the domain of our harmonic functions and can be thought of as the vertices of a graph.

A function $f:X\times X\rightarrow \mathbb{C}$ is called a \emph{structure function} if the set $\{y\colon f(x,y)\neq 0\}$ is finite for all $x\in X$, thereby ensuring that our graph is locally finite.  A common operation one takes on structure functions is given by
\[(f\diamond g)(x,y) := \sum_{\zeta \in X} f(x,\zeta)g(\zeta,y) \qquad (x,y\in X). \]
In fact we are interested in a particular type of structure function called a \emph{weight function} which has the additional properties $\lambda \colon X\times X \rightarrow \mathbb{R}$, with $\lambda \ge 0$ and $\sum_{\zeta\in X} \lambda(x,\zeta) = 1$ for all $x\in X$.

We think of $\lambda(x,y)$ as defining a weight on a directed edge from $x$ to $y$ with the interpretation of $\lambda(x,y)=0$ as meaning that there is no edge.  For us the domain $X$ and the weight $\lambda$ are fixed, hence we will often refer to the graph $X$ without ambiguity. Also note that $\lambda$ need not be symmetric.

\subsection{The Laplacian and harmonic functions}\label{SS:lap_sub}

The Laplacian $\Delta$ at a point $x\in X$ is defined with respect to $\lambda$ on functions $f\colon X \rightarrow \mathbb{R}$ by
\[\Delta f(x) = \sum_{\zeta \in X} \lambda(x,\zeta)[f(\zeta)-f(x)].\]

A function $f\colon X \rightarrow \mathbb{R}$ is said to be \emph{harmonic} if $\Delta f(x)=0$ for every $x\in X$ and \emph{subharmonic} if $\Delta f(x)\ge 0$ for every $x\in X$.  Some simple arithmetic shows that subharmonicity is equivalent to the property that
\[f(x) \le \sum_{\zeta \in X} \lambda(x,\zeta)f(\zeta) \qquad (x\in X).\]

Notice that constant functions are always harmonic, no matter what weight $\lambda$ is under consideration.
\begin{nt}
The set of harmonic and subharmonic functions on $X$ will be denoted by $H(X)$ and $S(X)$, respectively.
\end{nt}

Some properties of subharmonic functions and their relationship to other functions on graphs can be found \cite{BP14}.

\subsection{Kiselman's Boundary}\label{SS:Kiselman}
In \cite{K05}, Kiselman introduces the following notion of boundary on the directed graph $X$.  The boundary of $X$, denoted by $\partial X$, is the set
\begin{align*}
\partial X &= \{x\in X\colon \lambda(x,y)=0 \text{ for all } y \in X\setminus\{x\} \}\\
&= \{x\in X\colon \lambda(x,x)=1 \}.
\end{align*}
The Kiselman boundary can be thought of intuitively as the stable equilibria of the Markov process, those states from which a random walk can not escape.

Its complement $X^\circ = X \setminus \partial X$ is the \emph{interior} of $X$. We note that a point $x$ has a neighbor different from $x$ if and only if $x$ is in the interior. Given a point $a \in X$ we define $N_0(a) = \{a\}$ and then inductively
\[N_{k+1}(a) = \{y\colon \lambda(x, y) > 0 \text{ for some } x \in N_k(a)\}\qquad (k \in \mathbb{N}).\]
The union of all the $N_k(a)$ will be called the \emph{component} of $a$ and be denoted by $C(a)$. Clearly $C(a) = \{a\}$ if and only if $a$ is a boundary point.  We shall say that $X$ is \emph{boundary connected} if $C(a)$ intersects $\partial X$ for every $a \in X^\circ$. (In particular $\partial X$ is nonempty if $X$ is boundary connected and
nonempty.) We shall say that $X$ is \emph{connected} if $C(a) = X$ for all $a \in X^\circ$. It is possible that $\partial X$ may be empty.

It is useful to observe that for any function $f$ on $X$ we have
\begin{equation*}\sum_{\zeta \in X} \lambda(x , \zeta) f(\zeta) = \sum_{\zeta \in C(x)} \lambda(x , \zeta) f(\zeta)=\sum_{\zeta \in N_1(x)} \lambda(x , \zeta) f(\zeta),
\end{equation*}
as $\lambda(x, \eta)=0$ for all $\eta \in X\setminus N_1(x)$ by definition.

Kiselman (see \cite{K05}) provides some maximum principles for subharmonic functions on directed graphs, which can be traced back to \cite{LT69}.
\begin{prp}[Kiselman]\label{P:max1}
If $X$ is finite and boundary connected, then $\sup_{X}u = \sup_{\partial X}u$ for all subharmonic functions $u$ on $X$. The converse holds.
\end{prp}

Later in Section \ref{S:max_nn-cnst}, Proposition \ref{P:max1} of Kiselman is generalized by our Theorem \ref{T:max-prnc} to include the ends of a graph.

\begin{prp}[Kiselman]\label{P:max2}
If $X$ is connected (finite or infinite), then a subharmonic function which attains its supremum at an interior point must be constant.  The converse holds.
\end{prp}

\begin{nt}
For $k= 1, 2, \cdots$, we take $\lambda^{\diamond k}$ as the $\diamond$ product of $\lambda$ $k$ times, i.e. $\lambda^{\diamond k} = \lambda \diamond \lambda\diamond \lambda\cdots \diamond \lambda$.

Take $\omega_x^0(\zeta)= \delta(x,\zeta)$, $\omega_x^1(\zeta)=\lambda(x,\zeta)$, and $\omega_x^k(\zeta)=\lambda^{\diamond k}(x,\zeta)$.  In a slight abuse of notation for any function $g$ on $X$, we let $\omega_x^k(g)$ denote
\[\omega_x^k(g) := \sum_{\zeta \in X}\lambda^{\diamond k}(x,\zeta)g(\zeta).\]
\end{nt}

We see how this notation is useful in the following technical lemma.
\begin{lma}\label{L:mono}
If $g$ is a subharmonic function on $X$ then $\{\omega_x^k(g)\}_{k=0}^\infty$ is an increasing sequence, i.e. $\omega_x^k(g) \le \omega_x^{k+1}(g)$ for all $x\in X$ and all $k\in \mathbb{N}$.
\end{lma}
\begin{proof}
First observe that
\[\omega_x^0(g)=g(x)\le \sum_{\zeta\in X} \lambda(x,\zeta) g(\zeta) = \omega_x^1(g),\]
holds for any subharmonic $g$ and any $x\in X$ by the definitions. We may repeat the substitution at $\zeta$ inside the summation as
\[g(x)\le \sum_{\zeta\in X} \lambda(x,\zeta) g(\zeta)\le \sum_{\zeta\in X} \lambda(x,\zeta)\left(\sum_{\eta\in X} \lambda(\zeta,\eta) g(\eta)\right).\]
The summations are all finite by hypothesis (the graph is locally finite) and so we swap the order of summation
\[\omega_x^0(g)\le\omega_x^1(g) \le \sum_{\eta\in X}\left(\sum_{\zeta\in X} \lambda(x,\zeta) \lambda(\zeta,\eta)\right) g(\eta) = \sum_{\eta\in X}(\lambda\diamond \lambda)(x,\eta) g(\eta) = \omega_x^2(g).\]
Clearly this process may be repeated.  Therefore $\{\omega_x^k(g)\}_{k=0}^\infty$ is an increasing sequence.
\end{proof}

\subsection{The ends of a graph}

We define a {\it ray} in  an undirected infinite graph $X$ as a one way infinite cycle-free (undirected) path $\pi = x_0x_1x_2\ldots$ in $X$. For directed graphs, we will require rays to be directed; that is, $\lambda(x_i, x_{i+1}) > 0$ for all $i \geq 0$.

Following \cite{W96}, consider any finite subgraph $A$ of $X$.  Then $X\setminus A$ breaks into finitely many connected components, one of which must contain infinitely many of the points of $\pi$.  In this case we say $\pi$ is said to {\it end} in that component.  Given two rays $\pi$ and $\pi'$ we say that they are {\it equivalent} if $\pi$ and $\pi'$ end in the same component of $X\setminus A$ for every finite $A\subset X$.  An {\it end} of a graph is precisely one such equivalence class of rays.

We let $\partial_{end}X$ denote the collection of ends of $X$ and take $\hat{X}=\partial_{end}X \cup X$.  The boundary of $\hat{X}$ is given by $\partial \hat{X}=\partial_{end}X \cup \partial X$ where
\[\partial X = \{x\in X\colon \lambda(x,x)=1\}.\]  This is the boundary from which we wish to extend harmonic functions.  First we will want to discuss the class of subharmonic functions on $\hat{X}$.
\begin{df}
The set of \emph{subharmonic functions} on $\hat{X}$ is denoted $S(\hat{X})$. A function $f\colon\hat{X}\rightarrow \mathbb{R}$ is said to be in $S(\hat{X})$ if $f|_X\in S(X)$ and
\[ \limsup_{i\rightarrow \infty}f(x_i) \le f(\omega),\]
where $\pi = x_0x_1x_2\ldots $ is in $\omega$.
\end{df}
Of course, each subharmonic function $f$ on $X$ naturally extends to $\hat{X}$ in the following way:
\[f(\omega) = \sup\{ \limsup_{i\rightarrow \infty}f(x_i)\colon \pi = x_0x_1x_2\ldots  \text{ in } \omega \}.\]
Consequently, the class of harmonic functions on $\hat{X}$ is \[H(\hat{X}) = S(\hat{X})\cap (-S(\hat{X})),\]
where $-S(\hat{X})=\{-f\colon f\in S(\hat{X})\}$.

The Dirichlet problem on $\hat{X}$ can now be phrased: for any $f\colon \partial \hat{X} \rightarrow \mathbb{R}$ there is a unique $h\in H(\hat{X})$ such that $h|_{\partial\hat{X}}=f$.

\section{Maximum principles and uniqueness for the Dirichlet problem.}\label{S:max_nn-cnst}

In this section we prove a maximum principle for a class of graphs.  This will be used to supply the ``uniqueness" part of the Dirichlet problem.

\begin{df}
Given a non-constant subharmonic function $f$, we call a finite sequence $\{x_i\}_{i=0}^k \subset X$ such that $f(x_i)< f(x_{i+1})$, $x_{i+1}\in N_1(x_i)$ and $f(x_{i+1}) = \max\{f(y)\colon y\in N_1(x_i)\}$ a \emph{maximally increasing path} for $f$. Note that such a path is cycle-free. Consequently, we define {\em a maximally increasing ray} for $f$ to be an infinite sequence $\{x_i\} \subset X$ such that every finite subsequence is a maximally increasing path for $f$.
\end{df}

\begin{lma}[K{\"o}nig's Infinity Lemma] Let $V_0, V_1, \ldots$ be an infinite sequence of disjoint non-empty finite sets, and let $X$ be an undirected graph on their union. Assume that every vertex $v \in V_n$ has a neighbor $g(v)$ in $V_{n-1}$. Then $X$ contains a ray $v_0v_1\ldots$ with $v_n \in V_n$ for all $n$.
\end{lma}

\begin{thm}\label{T:max_incr}
Suppose $(X,\lambda)$ is a reversible infinite connected graph.  Given any non-constant subharmonic function $f$ there exists a maximally increasing ray for $f$.
\end{thm}
\begin{proof}
Suppose $f$ is a non-constant subharmonic function.  Then as $X$ is connected there exists two points $a,b\in X$ such $a\neq b$, $\lambda(a,b)>0$, consequently $\lambda(b,a)>0$, and $f(a)< f(b)$.  Take $x_0=a$ and $x_1\in X$ such that $f(x_1) = \max\{f(y)\colon y\in N_1(x_0)\}$.  As $b\in N_1(x_0)$ we have that $f(x_0)<f(b)\le f(x_1)$.

We proceed to built the sequence inductively.  Suppose we have a maximally increasing path $\{x_i\}_{i=0}^k$ with $f(x_i)< f(x_{i+1})$, $x_{i+1}\in N_1(x_i)$ and $f(x_{i+1}) = \max\{f(y)\colon y\in N_1(x_i)\}$.  We will now find the next term.  Since $\lambda\ge 0$ and $\sum_{y\in X}\lambda(x_k,y)=1$, we think of subharmonicity as averaging the values of $f$ over the nearest neighbors with weights $\lambda$.  By construction we have that $\lambda(x_{k-1}, x_k)>0$.  Hence the reversibly condition implies that the average $\sum_{y\in X}\lambda(x_k,y)f(y)$ includes the $x_{k-1}$ term as $\lambda(x_k,x_{k-1})>0$.  Since $f(x_{k-1})<f(x_k)$ and $f$ is subharmonic, there must be a point $c\in N_1(x_k)$ such that $f(x_k)<f(c)$.  Take $x_{k+1}$ to be a point in $N_1(x_k)$ with $f(x_{k+1})=\max\{f(y)\colon y\in N_1(x_k)\}$ and we have that $f(x_k)<f(c)\le f(x_{k+1})$. This guarantees that $x_{i+1}$ is distinct from $\{x_i\}_{i=0}^k$, so $\{x_i\}_{i=0}^{k+1}$ is a maximally increasing (cycle-free) path. Whence, given any maximally increasing path of length $k$, we can always extend it to a maximally increasing path of length $k+1$. By induction and K{\"o}nig's Infinity Lemma, $X$ contains a maximally increasing ray for $f$.
\end{proof}

Recall that a graph is reversible whenever $\lambda(x,y)>0 \iff \lambda(y,x)>0$. With the next definition we take a weaker form of reversible by allowing some Kiselman type boundary points.
\begin{df}
We say that a graph is {\it quasi-reversible} if $\lambda(x,y)>0$ implies that either $\lambda(y,x)>0$ or $\lambda(y,y)=1$, that is, the graph is reversible everywhere except the boundary points.
\end{df}
Observe that Example 1 is of this type.

\begin{thm}[Maximum Principle]\label{T:max-prnc}
Let $X$ be a connected quasi-regular graph.  Then  for all $f\in S(\hat{X})$ we have
\[\sup\{f(x)\colon x\in \hat{X}\} = \sup\{f(y)\colon y\in \partial \hat{X}\}.\]
\end{thm}
\begin{proof}
Let $M=\sup\{f(x)\colon x\in \hat{X}\}$.

We start with the easy case when the supremum occurs at a point. If there is a point $x_0\in \partial \hat{X}$ such that $f(x_0)=M$, we are done.  Suppose otherwise, that there is a point $x_0\in \hat{X}^\circ=X^\circ$, so that $f(x_0)=M$.  Consequently by Proposition \ref{P:max2}, the function $f$ must therefore be constant on $X$ as the graph is connected, which trivially implies the result.

Now we consider what happens when the supremum does not occur at a point.  In this case, there is a sequence $\{x_i\}\subset \hat{X}$ such that $f(x_i)<f(x_{i+1})$ with $\lim_{i\rightarrow \infty}f(x_i)=M$.  If $|\{x_i\}\cap \partial\hat{X}|=\infty$, we are done.  Hence without loss of generality we will assume that $\{x_i\}\subset \hat{X}^\circ$.

Our strategy will be to start a directed path at each $x_i$ (or some other point $y$ where $f(y)=f(x_i)$) on which $f$ is strictly increasing.  This path will either terminate at a boundary point of $X$ or be a ray (an infinite cycle free one way directed path) on which $f$ is strictly increasing.  We will then use this path to conclude the result.

To construct such a path we mimic the previous Theorem \ref{T:max_incr}.   Pick any $x_i$ from $\{x_i\}$.  It may be the case that $f$ is locally constant around $x_i$, that is, $f(x_i)=f(y)$ for all $y$ adjacent to $x_i$.  However since $f$ is non-constant and we are working on a connected quasi-reversible graph, we can find a $y_0$ such that $f(x_i)=f(y_0)$ such that $f$ is not locally constant around $y_0$.  Hence there is a $z$ adjacent to $y_0$ such that $f(z)\neq f(y_0)$.  If $f(z)>f(y_0)$, then take $y_1=z$.  If $f(z)<f(y_0)$, then subharmonicity demands the existence of a $z'$ adjacent to $y_0$ with $f(z')>f(y_0)$; in this case take $y_1=z'$.

If $y_1 \not\in\partial X$, we can find (using subharmonicity and that $f(y_0)<f(y_1)$) a $y_2$ adjacent to $y_1$ such that $f(y_2)>f(y_1)$; otherwise we allow the path to terminate at the point $y_1\in \partial X$.  Using induction we obtain a cycle-free directed path starting at $y_0$ (where $f(x_i)=f(y_0)$) along which $f$ is strictly increasing where the path is either $(1)$ finite with terminal point in $\partial X$ or $(2)$ a ray.

In the first case, we have the path $y_0y_1 \ldots y_m$ where $y_m\in \partial X$ and $f(y_i)<f(y_{i+1})$ and where $\lambda(y_i, y_{i+1})>0$.  Hence
\[f(x_i)=f(y_0)\le f(y_m) \le \sup\{f(y) \colon y\in \partial X\}\le \sup\{f(y) \colon y\in \partial \hat{X}\}.\]

While in the second case, we've constructed a ray $\pi = y_0y_1 \ldots $ with $f(y_i)<f(y_{i+1})$ where $\lambda(y_i, y_{i+1})>0$ and $f(x_i)=f(y_0)$.  Therefore $\pi$ must be in some end $\omega\in\partial_{end}X$, and so
\[f(x_i)=f(y_0)\le \lim_{y_i\in \pi}f(y_i) \le f(\omega) \le \sup\{f(y) \colon y\in \partial \hat{X}\}.\]

Thus in either case we have that $f(x_i)\le \sup\{f(y) \colon y\in \partial \hat{X}\}$. We simply take the supremum over all $x_i \in \{x_i\}$ to see
\[M = \sup\{f(x_i)\colon x_i\in\{x_i\} \} \le \sup\{f(y) \colon y\in \partial \hat{X}\}\]
which is the desired result.
\end{proof}

\begin{thm}[Uniqueness]\label{T:unique}
Let $X$ be connected and quasi-reversible.  If there exists a solution to the Dirichlet problem on $\hat{X}$, then it is unique.
\end{thm}
\begin{proof}
Let $f\colon \partial\hat{X}\rightarrow \mathbb{R}$.  We seek to show that there is at most one solution to the Dirichlet problem, that is a harmonic $h$ such that $h|_{\partial\hat{X}}=f$.

Suppose $h$ and $h'$ are harmonic and equal to $f$ on $\partial\hat{X}$.  Then $h-h'$ and $h'-h$ are subharmonic and equal to $0$ on $\partial\hat{X}$.  Hence by Theorem \ref{T:max-prnc}
\[\sup\{h(x)-h'(x)\colon x\in \hat{X}\} = \sup\{h'(x)-h(x)\colon x\in \hat{X}\}= \sup\{0\colon y\in \partial\hat{X}\}=0.\]
Therefore $h-h'\le 0$ and $h'-h\le 0$ on $\hat{X}$, and so they are equal.
\end{proof}

\section{Existence for graphs with one end.}
The following trivial observation will be useful.
\begin{lma}\label{L:ext_by_zero}
If $f\colon \partial X \rightarrow \mathbb{R}$ is non-negative, then the extension of $f$ by $0$ to all of $X$ is subharmonic on $X$.
\end{lma}
\begin{proof}
Suppose that $f\ge 0$ and define an extension of $f$ by $0$ as
\[\tilde{f}(x) = \begin{cases} f(x) & \colon x\in \partial X\\ 0 &\colon \text{ else.}\end{cases}\]

Now we observe that $\tilde{f}\in S(X)$. Suppose $x_0 \notin \partial X$.  Then $\tilde{f}(x_0)=0$, and as $\tilde{f}\ge 0$ everywhere, we have $\tilde{f}(x_0) \le \sum_{\zeta\in X} \lambda(x_0,\zeta)\tilde{f}(\zeta)$.
So $\tilde{f}$ is subharmonic at $x_0$.  If $x_1 \in \partial X$, by definition $\lambda(x_1,y)=\delta(x_1,y)$, the Kronecker delta.  Hence $\tilde{f}$ is harmonic at $x_1$.  Thus $\tilde{f}$ is subharmonic on $X$.
\end{proof}

\begin{thm}
For every non-negative bounded function $f\colon \partial X\rightarrow \mathbb{R}$ there is a bounded harmonic function $h\colon X\rightarrow \mathbb{R}$ such that $h=f$ on ${\partial X}$.  Furthermore $h$ is given by
\[h(x) = \lim_{k\rightarrow \infty} \omega_x^k(f)\]
for all $x\in X$.
\end{thm}
\begin{proof}
By Lemma \ref{L:ext_by_zero} the extension $\tilde{f}$ of $f$ by $0$ is subharmonic.  Therefore by Lemma \ref{L:mono} $\{\omega_x^k(\tilde{f})\}_{k=0}^\infty$ is an increasing sequence.  Since $f$ is bounded above, we have $f\le M$ for some positive constant $M$.  This shows that the sequence $\{\omega_x^k(\tilde{f})\}_{k=0}^\infty$ is bounded above by
\[\omega_x^k(\tilde{f}) = \sum_{\eta\in X} \lambda^{\diamond k}(x,\eta)\tilde{f}(\zeta)\le \sum_{\eta\in X} \lambda^{\diamond k}(x,\eta)M = M,\]
for all $x\in X$ and every $k$.
Thus this is a bounded increasing sequence and hence converges.  Let $h(x) = \lim_k \omega_x^k(\tilde{f})$.  Now we will check that $h$ is harmonic.

Since $\lambda(x,\zeta)$ is non-zero for only finitely many $\zeta$, we have
\begin{align*}\sum_{\zeta \in X}\lambda(x,\zeta)h(\zeta) & = \sum_{\zeta \in X}\lambda(x,\zeta)\lim_{k\rightarrow \infty} \omega_\zeta^k(\tilde{f}) \\& = \sum_{\zeta \in X}\lambda(x,\zeta)\lim_{k\rightarrow \infty} \left(\sum_{\eta\in X}\lambda^{\diamond k}(\zeta, \eta)\tilde{f}(\eta)\right) \\& = \lim_{k\rightarrow \infty} \sum_{\eta\in X}\left( \sum_{\zeta \in X}\lambda(x,\zeta)\lambda^{\diamond k}(\zeta, \eta)\right)\tilde{f}(\eta) \\& =
\lim_{k\rightarrow \infty} \sum_{\eta\in X}\lambda^{\diamond (k+1)}(x, \eta)\tilde{f}(\eta) \\& = \lim_{k\rightarrow \infty}\omega_x^{k+1}(\tilde{f}) = h(x).
\end{align*}
Hence $h$ is harmonic on $X$.

As $\tilde{f}(x)=f(x)$ for all $x\in \partial X$ and $\tilde{f}$ is harmonic at every point $x\in \partial X$ , we have that $\omega_x^{\diamond k}(\tilde{f})=f(x)$ for all $k$.  Hence $h=f$ on $\partial X$.
\end{proof}

For the remainder of the paper we will only consider graphs with finitely many ends, which we will denote $\omega$.  Modeling our work after classical potential theory, we must require the boundary data $f\colon \partial \hat{X}\rightarrow \mathbb{R}$ to be ``continuous at infinity".   Hence we make the following definitions:
\begin{df}
A sequence $\{x_n\}\subset \hat{X}$ is said to \emph{converge} to $x\in \hat{X}$, if for all $Y\subset X$ finite, there exists an $N>0$ such that for all $n>N$, $x_n$ and $x$ lie in the same connected component of $\hat{X}\setminus Y$.

Observe that the ends of the graph are the only limit points.  Hence by this definition a sequence can only converge if $x\in \partial_{end}X$.  We say that a function $f\colon \partial \hat{X}\rightarrow \mathbb{R}$ is \emph{continuous} at $\omega\in \partial_{end} X$, if $\lim_{x_n\rightarrow \omega}f(x_n)=f(\omega)$ for every $\{x_n\}\subset\partial\hat{X}$ converging to $\omega$.  If such an $f$ is continuous at every end, then it is said to be \emph{continuous at infinity}.
\end{df}

Note that in particular, if $\partial X$ is itself finite, then every function $f$ on $\partial X$ is necessarily continuous at infinity.  Furthermore that any harmonic function on $\hat{X}$ must necessarily be continuous at infinity as both $h$ and $-h$ are in $S(\hat{X})$.

Also note that if $X$ is a graph with one end $\omega$, then a function $f\colon \partial \hat{X}\rightarrow \mathbb{R}$ is {\it continuous at infinity}, whenever the set
\[\{x\in \partial X\colon |f(x)-f(\omega)|>\varepsilon\}\]
is finite for every $\varepsilon>0$.

In \cite{CSW93, W96} the solvability of the Dirichlet problem is characterized by two properties of the Green's function, which we will briefly recall.

The \emph{Green's function} on $X$ is defined by
\[G(x,y) = \sum_{k=0}^\infty \lambda^{\diamond k}(x,y), \]
for $x, y\in X$.  The Green's function is said to be \emph{transient} whenever $G(x,y)<\infty$ for all $x\in X^\circ$ and $y\in X$.  The Green's function is said to be \emph{vanishing at infinity} if
\[\lim_{n\rightarrow \infty}G(x_n,y)=0,\]
for every sequence $\{x_n\}\subset X$ which converges to some end.

The condition that the Green's function be vanishing at infinity cannot be dropped. In \cite[Thm 7.15]{W94} it is stated that for graphs with at least two ends and a transient Green's function, the Dirichlet problem is solvable if and only if the Green's function vanishes at infinity.

The following lemma is easily seen to be a consequence of a transient Green's function which vanishes at infinity.
\begin{lma}\label{L:trans_G_at_inf}
Let $X$ be a connected quasi-reversible one ended graph admitting a transient Green's function which vanishes at infinity. Then for any point $y_0\in \partial X$ and any $\varepsilon>0$ there exists $N_1$ and $N_2$ such that for all $k>N_1$ and all points $x$ with $\dist(x,y_0)>N_2$, we have $\lambda^{\diamond k}(x,y_0)<\varepsilon$.  Here $N_1$ and $N_2$ are allowed to depend on the $y_0$ and $\varepsilon$.
\end{lma}

We are now ready to solve the Dirichlet problem for one ended graphs.
\begin{thm}\label{T:exists}
Let $X$ be a connected quasi-reversible one ended graph admitting a transient Green's function which vanishes at infinity.  If $f\colon \partial \hat{X}\rightarrow \mathbb{R}$ is bounded and continuous at infinity, then there exists a unique $h\in H(\hat{X})$ such that $h=f$ on $\partial\hat{X}$.
\end{thm}
\begin{proof}
Uniqueness follows from Theorem \ref{T:unique}.

Let $\omega$ denote the end of $X$.  By replacing $f$ with $f-f(\omega)$ we may assume without loss of generality that $f(\omega)=0$.

Given a function $f$ on $\partial\hat{X}$.  We consider functions $f^+ = \max\{f,0\}.$ and $f^- = -\min\{f,0\}$ so that $f=f^+-f^-$ and $|f|=f^++f^-$.  If $h^+$ and $h^-$ solve the problem for $f^+$ and $f^-$ respectively, then $h=h^+ - h^-$ solves the problem for $f$.  Furthermore if $h$ solves the problem for $f\ge 0$, then $-h$ solves the problem for $-f\le 0$.  Therefore it suffices to solve the problem with non-negative boundary data.  Hence we will assume for the remainder of the proof that $f$ is non-negative and $f(\omega)=0$.

Pick any $\varepsilon >0$.  By continuity at infinity the set
\[A=\{x\in \partial\hat{X} \colon f(x) \ge \varepsilon/2\}\]
is finite.  We will use the notation $|A|$ to denote the cardinality of $A$.

Let $M=\sup\{f(x)\colon x\in \partial\hat{X}\}$.  By Lemma \ref{L:trans_G_at_inf} we can find $N_1$ and $N_2$ such that for all $k>N_1$ and all $x\in X$ with $\dist(x,A)>N_2$ we have
\[\lambda^{\diamond k}(x,y)< \frac{\varepsilon}{2M|A|},\qquad (y\in A) \] where $\dist(x,A)$ denotes the maximum of $\dist(x,y)$ with $y\in A$.

As usual we denote the extension of $f$ by $0$ by $\tilde{f}$.  Hence for all $x\in X$ with $\dist(x,A)>N_2$ and any $k>N_1$, we have
\begin{align*}
\lambda^{\diamond k}(x,y)\tilde{f}(y) \le  \frac{\varepsilon}{2M|A|}M = \frac{\varepsilon}{2|A|} \qquad &(y\in A)\\
\lambda^{\diamond k}(x,y)\tilde{f}(y) \le  \lambda^{\diamond k}(x,y)\frac{\varepsilon}{2} \qquad &(y\not\in A)
\end{align*}

Thus for $k>N_1$ and all $x$ with $\dist(x,A)>N_2$ and any $k>N_1$, we have
\begin{align*}
\omega_x^k(\tilde{f}) &= \sum_{y\in X}\lambda^{\diamond k}(x,y)\tilde{f}(y) \\
&= \sum_{y\in X\setminus A}\lambda^{\diamond k}(x,y)\tilde{f}(y) +  \sum_{y\in A}\lambda^{\diamond k}(x,y)\tilde{f}(y) \\
&\le \sum_{y\in X\setminus A}\lambda^{\diamond k}(x,y)\frac{\varepsilon}{2} +  \sum_{y\in A}\frac{\varepsilon}{2|A|} \\
&\le \frac{\varepsilon}{2}\sum_{y\in X}\lambda^{\diamond k}(x,y) +  \frac{\varepsilon}{2} = \varepsilon
\end{align*}
Note that in the last step we used that $\sum_{y\in X}\lambda^{\diamond k}(x,y)=1$ for all $k$ and any $x\in X$.
As in the previous theorem, take $h(x)=\lim_{k\rightarrow \infty}\omega_x^k(\tilde{f})$ and observe that $h(x)\le \varepsilon$ whenever $\dist(x,A)>N_2$.

Since the graph is locally finite, the set
\[B=\{x\in X\colon \dist(x, A)\le N_2\}\]
is finite.  Notice that $h$ has the property that $h(x)\le \varepsilon$ for all $x\in X\setminus B$.  Now consider any ray $\pi=x_0x_1\ldots $ in the graph.  There can be at most finitely many vertices of $\pi$ in $X\setminus B$.  Thus
\[\limsup_{i\rightarrow \infty}h(x_i) \le \varepsilon\]
for every ray $\pi$ in the graph.

Since $f$ is assumed to be non-negative, it follows that $h$ too is non-negative.  As $\varepsilon$ was arbitrary we see that $\lim_{i\rightarrow \infty}h(x_i)=0$ along every ray $\pi=x_0x_1$ in the graph.  Hence $h$ extends harmonically to $\omega$ as $0$ which is, of course, the value of $f$ at $\omega$ as well.  In the previous theorem it was noted that $h=f$ on $\partial X$.  Thus $h\in H(\hat{X})$ and $h=f$ on $\partial \hat{X}$.
\end{proof}

We have now resolved the setting of the Dirichlet problem on the upper half plane (Example 1) which we originally used to motivate the need for including ends.  It is interesting to compare this result to that of \cite[Section 5]{K05}, in particular Example 5.2,  which also concerns the Dirichlet problem on the upper half plane with the $x$-axis as the boundary.

Here one could extend the `boundary data' to the end by continuity, which is precisely what is occurring in Example 5.2 where one always gets a unique solution on the upper half plane.  By taking $f=0$ and $g=0$ in \cite[Example 5.2]{K05}, we are in a similar setting as Example 1 where we demonstrate that there are multiple solutions to the Dirichlet problem with this boundary condition.  The construction of \cite{K05} only produces the trivial solution $u=0$, implying that $g$ takes the value $0$ on the end. However in general there may be ends that are not limit points of $\partial X$.

Furthermore the technique in Thm 5.1 of \cite{K05} requires a specific decomposition of the domain based on a growth condition.  As this decomposition is built inductively, it is not clear that one could include boundary values on the ends which are not limit points of $Y$ in a way in which they could be incorporated into the construction technique of \cite[Thm 5.1]{K05}.  Therefore the above Theorem \ref{T:exists} handles boundary data on an end which is not a limit point of $\partial X$ where \cite{K05} would not.

\section{Existence for graphs with finitely many ends.}
We will need one last definition before moving on to our final result.

\begin{df} A slice of a graph $X$ is a finite sequence $y_0y_1y_2\ldots y_m$ in $X$ such that consecutive vertices are adjacent, no vertex is repeated, and $y_0, y_m\subset \partial X$.
\end{df}

We can use the solution for the one-ended case together with a variant of the Schwartz Alternating Method \cite[pp 37--39]{GM08} to solve the multi-ended case.
\begin{thm}\label{T:exists2}
Let $X$ be a connected quasi-reversible graph with finitely many ends admitting a transient Green's function which vanishes at infinity.  If $f\colon \partial \hat{X}\rightarrow \mathbb{R}$ is bounded and continuous at infinity, then there exists a unique $h\in H(\hat{X})$ such that $h=f$ on $\partial\hat{X}$.
\end{thm}
\begin{proof}
Suppose $X$ has $n$ ends. We must now take $2n$ disjoint slices. For each end $\omega_i$, we take two disjoint slices $\gamma_{i, inside}$ and $\gamma_{i, outside}$, where each slice partitions $X$ into two components such that one of the components contains only one end $\omega_i$.  As the slices $\gamma_{i, inside}$ and $\gamma_{i, outside}$ are disjoint, we may suppose that $\gamma_{i, outside}$ is entirely contained  in the component of $X\setminus \gamma_{i, inside}$ that includes $\omega_i$.  We do this for each end.

Let $X_i$ be the vertices of the component of $X\setminus \gamma_{i, inside}$ that includes $\omega_i$.  Let $Y_i = \{y\in X\colon \lambda(x,y) >0 \text{ for some } x\in X_i\}$.  We make $Y_i$ a graph by keeping the induced structure from $X$, except at the points $Y_i\setminus X_i$ which be come Kiselman boundary points, i.e. $\lambda(y,y)=1$ for all $y\in Y_i\setminus X_i$.  Let $X_{n+1}$ be the component of $X\setminus \left(\cup_{i=1}^n \gamma_{i, outside}\right)$ that contains no ends, and define $Y_{n+1} = \{y\in X \colon \lambda(x, y)>0 \text{ for some } x \in X_{n+1}\}$.  Again we give $Y_{n+1}$ the structure of a graph, by taking the induced structure on $X_{n+1}$ and making all $y\in Y_{n+1}\setminus X_{n+1}$ Kiselman boundary points.

To summarize, we've taking $X$ and grouped it into $n+1$ sections: $Y_1, \cdots Y_{n+1}$.  Each section $Y_i$ for $i=1$ to $n$ has exactly one end $\omega_i$, and $Y_{n+1}$ has no ends.  Furthermore the $Y_i$ for $i=1$ to $n$ are disjoint, but each overlaps with $Y_{n+1}$.  The new boundaries are defined so that the graph structure in the interior and on the overlapping sections remains unchanged.

Consider our boundary data $f:\partial \hat{X}\rightarrow \mathbb{R}$.  On each piece $Y_i$ for $i=1$ to $n$ keep it the same only extend it to the new added boundary as $f(y)= \max\{f(x) \colon x \partial X\}$ for every $y\in Y_i\setminus X_i$, i.e. the new boundary points. Since each of these sections $Y_i$ has only one end we can find a harmonic extension $h_1$ of $f$ to $Y_i$ for for $i=1$ to $n$.  Without loss of generality we use the same labeling $h_1$ for the harmonic solution on each $Y_i$ for $i=1$ to $n$ as the are disjoint.

Now we solve the Dirichlet problem on $Y_{n+1}$ with boundary data $f(x)$ when $x\in  X_{n+1}\cap \partial X$ or $h_1(y)$ when $y\in \partial Y_{n+1}\cap (X\setminus X_{n+1})$, that is we take the $h_1$ as the boundary values for the added boundary points of $Y_{n+1}$.  We call $h_1'$ the solution to the Dirichlet problem on $Y_{n+1}$ with this boundary data.

Now we repeat this process, to find $h_2$ on $Y_i$ for $i=1$ to $n$ we use the boundary data $f$ on the original boundary, and $h_1'$ on the $\partial Y_i\setminus \partial X$.  Then we find $h_2'$ on $Y_{n+1}$ using the original boundary data where defined and $h_2$ on $\partial Y_{n+1}\setminus \partial X$.  And we repeat.

This gives us two sequences: $h_n$ and $h_n'$.  I claim they are related in the following way:
\begin{equation}\label{E:sal}
h_1\ge h_1'\ge h_2\ge h_2' \ge \cdots
\end{equation}

It follows from the maximum principle that $h_i\ge h_i'$ and that $h_i'\ge h_{i+1}$ as the boundary points of $Y_{n+1}$ are interior points of $Y_i$ for $i=1$ to $n$ and vice versa.

As $f$ is bounded below, the maximum principle implies that $h_i\ge \min\{f(x)\colon x\in \partial X\}$.  Hence the sequence \ref{E:sal} converges.  Let $h$ be the limit.  Since $h_i=f$ on $\partial X$ and $h_i'=f$ on $\partial X$ for every $i$, this means that the limit $h=f$ on $\partial X$.

It remains to be seen that $h$ is harmonic.  Let $x$ be an interior point of any of the $Y_i$ for $i=1$ to $n$.  Then as the sequence is decreasing
\[h(x)\le h_i(x) = \sum\lambda(x,y)h_i(x) \]
for all $i$.  Hence
\[h(x) \le \sum\lambda(x,y)h(x).\]

As $\lambda(x,y)\ge 0$, this implies that
\[\sum\lambda(x,y)h(x) \le \sum\lambda(x,y)h_i(x)=h_i(x) \]
for all $i$. Hence
\[\sum\lambda(x,y)h(x) \le h(x), \]
and $h$ is harmonic at $x$.  The same argument with $h_i'$ shows that $h$ is harmonic at the interior points of $Y_{n+1}$.  As the graph structure agrees on the overlap of the $Y_i$'s, this means that $h$ is harmonic everywhere.
\end{proof}

\section*{Acknowledgments}
The author would like to thank Simon Smith for many helpful discussions.  We would also like to thank the reviewers for their many constructive and helpful suggestions.


TITLE: Do the sizes of the orbits determine a permutation representation?
QUESTION [1 upvotes]: Suppose $\pi: G \to \mathrm{Sym}(X)$ and $\pi': G \to \mathrm{Sym}(X')$ are two permutation representations with, respectively, orbits $X_i (i \in I)$ and $X_j (j \in J)$. Suppose further that there is a bijection $\sigma: I \to J$ such that $|X_i| = |X_{\sigma(i)}|$. Does it follow that $\pi$ and $\pi'$ are equivalent, i.e. that there is a bijection $\beta: X \to X'$ such that $\beta(\pi(x)) = \pi'(\beta(x))$ for any $x \in X$?
I have a strong feeling that the answer is affirmative; clearly there is some bijection from $X$ to $X'$, since, by the hypothesis, they have the same cardinality. But I'm not totally sure about how to find the desirable $\beta$. Any clues?

REPLY [3 votes]: Let's think about what this means in the case that there is only one orbit in each of $X$ and $X'$ (the general case is easily reduced to that case anyways).  In that case, if you let $H$ be the stabilizer of a point of $X$ and $H'$ be the stabilizer of a point of $X'$, $\pi$ is equivalent to the action of $G$ on the coset space $G/H$ and $\pi'$ is equivalent to the action of $G$ on the coset space $G/H'$.  Two such coset spaces are equivalent representations of $G$ iff $H$ and $H'$ are conjugate as subgroups of $G$.
So, in this framework, your question becomes: if a group $G$ has subgroups $H$ and $H'$ such that $|G/H|=|G/H'|$, then must $H$ and $H'$ be conjugate?  Can you answer the question yourself now?  The answer is hidden below.

 The answer is no.  For the smallest counterexample, take $G=\mathbb{Z}/2\times\mathbb{Z}/2$ and let $H$ be generated by $(1,0)$ and $H'$ be generated by $(0,1)$.


TITLE: Relative speed of Geostationary satellite with respect to Earth?
QUESTION [1 upvotes]: I was wondering whether relative speed of geostationary satellite with respect to earth is zero or not. Since angular velocity of satellite about earth is same as angular speed of earth about its own axis but distance of surface of earth from axis of rotation is different from distance of satellite from axis, it implies that speed of both (observer on the surface of earth watching satellite and satellite itself) is different (Since $v=rw $).
It means that relative speed of geostationary satellite with respect to earth should not equal to zero. But shouldn't it should be zero since to an observer on earth geostationary satellite would appear to be at rest.

REPLY [0 votes]: A geostationary satellite has relative angular velocity=0, not relative tangential velocity.. This is obvious since the satellite covers a much larger circumference in the same time. It's sort of like a small golf ball stuck to a football with a stick. Same angular velocity as the earth, different tangential velocity.


TITLE: Do all cyclic numbers(base10) have the digits 1,4,2,5,8 and 7?
QUESTION [1 upvotes]: I found that the first few all contain those digits. Is there a counterexample?
For reference: https://en.m.wikipedia.org/wiki/Cyclic_number

REPLY [0 votes]: I would guess it is likely so, but would be hard to prove.  The Wikipedia article you reference has all of them up to $100$ digits.  We can verify by eye that every one has the digits $1,4,2,8,5,7$ included.  OEIS A001913 has a list of the primes less than $1000$ that generate cyclic numbers.  There are only $51$ with three digits.  If we view the digits as "random" the chance that a $100$ digit number is missing a given digit is $0.9^{100} \approx 2.6\cdot 10^{-5}$.  By $1000$ digits the chance is down to $10^{-46}$  The references in the OEIS entry seem to promise some idea of the density of these numbers.  We could then sum the probabilities to find a very small number.  This is certainly not a proof; however, I don't see a reasonable way to get to a proof.


TITLE: How to determine the entropy change in a system with heat and mass transfer?
QUESTION [3 upvotes]: Consider the system as shown in the picture. It consists of two chambers filled with a gas and connected with a tube. One chamber is closed with a piston. Everything is thermally insulated.

We make two assumptions:

The total amount of gas is constant;
The connecting tube is such that the pressure in both chambers gets equilibrated.

The initial state is such that the pressures are equal, i.e., $p_1=p_2$ and the temperatures are different: $T_1\neq T_2$.
Let the piston move s.t. the volume in the second chamber changes by $\delta V$. So, we have (here the prime $'$ denotes the state after the transition)
$$V_1'=V_1,\, V_2'=V_2+\delta V,\, N_1'=N_1+\delta N,\, N_2'=N_2-\delta N,$$
and $\delta N$ is determined from the condition $p_1=p_2=p$.
So, my question is

How to describe the change in entropy: $S_1'=?, S_2'=?$

Let $S_1'=S_1+\delta S_1, S_2'=S_2+\delta S_2$. We can compute the change in total energy:
$$(U_1'+U_2')-(U_1+U_2)=T_1\delta S_1 +\mu_1\delta N + T_2\delta S_2 -p\delta V -\mu_2\delta N,$$
which is equal to work done on the system, $\Delta W=-p\delta V$. So, we conclude that it must hold that
$$0=T_1\delta S_1 +\mu_1\delta N + T_2\delta S_2 -\mu_2\delta N.$$
The terms $\delta S_1$ and $\delta S_2$ should satisfy this equality. However, I'm still not clear what would be the exact form of these terms. I tried several options, but couldn't convince myself.
Any help on this problem will be very much appreciated.

EDIT1: First let me note that this is a simplified version of a more complex system, so it might look somehow artificial at first sight. Let me know if something is missing. I'll try to refine my assumptions to make the problem more tractable.
So, we assume that

the time interval is finite, i.e., we do not consider any slow processes like, e.g., heat transfer through the tube.
the piston moves sufficiently slowly$^*$ so that pressure equilibrates immediately.
the section of the tube is sufficiently small so that we can neglect the heat transfer through the tube.
the only heat transfer source is due to the mass transfer associated with the move of piston.
the transferred amount of gas mixes ideally with the contents of the chamber thus resulting in some entropy production.

$^*$ according to Callen it should be at most 0.1 of sound speed.

REPLY [2 votes]: What we are dealing with here is an irreversible process, where some of the gas from chamber 2 at temperature $T_2$ flows through the intervening tube and mixes with the gas already present in chamber 1 at temperature $T_1$.  This mixing gives rise to irreversibility present in the process.  Accordingly, to establish the entropy change for this irreversible process, we must follow the standard procedure of first employing the first law of thermodynamics to establish the final state of the system, and then determining the entropy difference between the initial and final states.  (Without establishing the final state of the system, it is not possible to determine the entropy change)
Were are told that at each stage of this process, the pressures within the two chambers are equal.  This enables us to establish relationships for the number of moles in each chamber and for the pressure.  Let the total number of moles in the two chambers be N, and let the initial number of moles in each chamber be $N_{10}$ and $N_{20}$.  And let then number of moles in the two chamber at any other stage of the process be $N_1$ and $N_2$, such that $$N_1+N_2=N_{10}+N_{20}=N\tag{1}$$The condition of equal pressure in the two chambers requires that $$\frac{N_1T_1}{V_1}=\frac{N_2T_2}{V_2}\tag{2}$$If we combine Eqns. 1 and 2, we obtain:
$$N_1=\frac{V_1T_2}{(V_1T_2+V_2T_1)}N\tag{3a}$$and$$N_2=\frac{V_2T_1}{(V_1T_2+V_2T_1)}N\tag{3b}$$
And, for the pressure, we obtain:  $$P=\frac{NRT_1T_2}{(V_1T_2+V_2T_1)}\tag{4}$$
Since each of the chambers is an open system, with gas flowing in or out, we must use the open system (control volume) version of the first law of thermodynamics to describe the energy balances.  For chambers 1 and 2, these read respectively:
$$d(N_1u_1)=h_2dN_1\tag{5a}$$
$$d(N_2u_2)=h_2dN_2-PdV_2\tag{5b}$$where u and h represent internal energy and enthalpy per mole of gas.  The terms $h_2dN_1$ and $h_2dN_2$ in these equations represent enthalpy flow from chamber 2 into chamber 1 and enthalpy flow out of chamber 2, respectively.  If we combine Eqns. 3-5, we obtain two equations in two unknowns for the changes in $T_1$ and $T_2$ as functions of the changes in $V_2$.
Let us first work with Eqn. 5b.  If we apply the product rule to the left hand side of this equation, we obtain:
$$N_2du_2=(h_2-u_2)dN_2-PdV_2\tag{6}$$But, for an ideal gas, we have: $du_2=C_vdT_2$, $h_2-u_2=RT_2$, and $P=N_2RT_2/V_2$; making these substitutions into Eqn. 6 yields:  $$N_2C_vdT_2=RT_2dN_2-\frac{N_2RT_2}{V_2}dV_2\tag{7}$$Dividing this equation by $N_2T_2$yields an exact differential:  $$d\ln{\left[T_2\left(\frac{V_2}{N_2}\right)^{R/C_v}\right]}=0\tag{8}$$or, combining this with Eqn. 3b yields:$$T_2\left(\frac{V_1T_2+V_2T_1}{T_1}\right)^{R/C_v}=T_{20}\left(\frac{V_1T_{20}+V_{20}T_{10}}{T_{10}}\right)^{R/C_v}\tag{9}$$
Once $V_2$ is specified, the only unknowns in Eqn. 9 are $T_1$ and $T_2$.  Another equation relating these unknowns is provided by Eqn. 5a, the first law open system energy balance on chamber 1.  Unfortunately, I have not been able to arrive at an analytic integration of this equation the way I have for Eqn. 5b.  However, I will report on what I have obtained so far.
If we employ ideal gas relationships to Eqn. 5a similar to those used for Eqn. 5b, we obtain:  $$C_vdT_1=[C_v(T_2-T_2)+RT_2]d\ln{N_1}\tag{10a}$$with $$d\ln{N_1}=d\ln{\left(\frac{T_2}{V_1T_2+V_2T_1}\right)}\tag{10b}$$
Maybe someone else can figure out a way of analytically integrating Eqns. 10, subject to Eqns. 9 to obtain $T_1$ and $T_2$ as functions of $V_2$.  So far this has eluded me.  As noted previously, we need to obtain these functional relationships in order to determine the change in entropy of the system as a unique function of $V_2$.  In practice, if I could not carry out the integration of the equations analytically, I would resort to numerical integration.
ADDENDUM
I did some additional analysis on this problem and was able to simplify Eqns. 10 by combining them with Eqn. 9 to obtain:
$$\frac{dT_1}{dT_2}=\frac{C_v}{R}\frac{T_1}{T_2}\left(\frac{C_p}{C_v}-\frac{T_1}{T_2}\right)\tag{11}$$Note that this equation no longer contains the volumes, and thus describes how $T_1$ must vary in tandem with $T_2$, starting with specified initial values of these parameters, for any arbitrary variation in $V_2$.
GOOD NEWS. (3/5/18)
I've finally been successful in integrating Eqn. 11 analytically to obtain $T_1$ as an explicit function of $T_2$.  The result is:
$$T_1=\frac{T_2}{\left[1+\left(\frac{T_{20}}{T_{10}}-1\right)\left(\frac{T_{20}}{T_2}\right)^{C_v/R}\right]}\tag{11a}$$
Note from this that, as would be expected, if $T_{10}=T_{20}$, $T_1=T_2$
CHANGE IN ENTROPY
The change in entropy for this system is given by:
$$\Delta S=(N_1s_1+N_2s_2)-(N_{10}s_{10}+N_{20}s_{20})\tag{12}$$
where the s's are molar entropies:
$$s=C_v\ln{(T/T_{ref})}+R\ln{(v/v_{ref})}\tag{13}$$where $T_{ref}$ and $v_{ref}$ are the temperature and molar volume at some arbitrary reference state;  these parameters cancel out of the calculations.  The specific volume $v_j$ for chamber j is given by  $v_j=V_j/N_j$.
ADDITIONAL ANALYSIS ON 3/5/18
Intuitively, and, based on Eqns. 8 and 9 of the present analysis, we know that the gas remaining in chamber 2 at any time during this process has experienced an adiabatic reversible compression, such that its final entropy per unit mass is equal to its initial entropy per unit mass:  $$s_2=s_{20}$$If we substitute this into Eqn. 12, this yields:
$$\Delta S=N_1s_1-N_{10}s_{10}-(N_{20}-N_2)s_{20}\tag{14}$$
Unfortunately, the same kind of simplification can not be made for chamber 1.  However, further simplification is possible in the following way:  We can substitute the identity $N_1=N_{10}+(N_1-N_{10}$ Into Eqn. 14 to obtain:  $$\Delta S=N_{10}(s_1-s_{10})+(N_1-N_{10})s_1-(N_{20}-N_2)s_2\tag{15}$$But, from the material balance, we have, $$(N_1-N_{10})=(N_{20}-N_2)$$Substituting this into equation 15 then yields:
$$\Delta S=N_{10}(s_1-s_{10})-(N_{20}-N_2)(s_2-s_1)\tag{16}$$But, since the pressures are equal in chambers 1 and 2, the term $(s_2-s_1)$ is just:
  $(s_2-s_1)=C_p\ln{(T_2/T_1)}$. Therefore, Eqn. 16 becomes:
$$\Delta S=N_{10}(s_1-s_{10})-(N_{20}-N_2)C_p\ln{(T_2/T_1)}\tag{17}$$
CALCULATING THE ENTROPY CHANGE:

Specify a value for $T_2$
Use Eqn. 11 to calculate the corresponding value of $T_1$
Use Eqn. 9 to calculate the corresponding value of $V_2$
Use Eqns. 3 to calculate the values of $N_1$, $N_2$, $N_{10}$, and $N_{20}$
Plug values into Eqn. for entropy change


TITLE: Riemann integral show $f(x)=g(x)$ for at least 1 $x$ in [a,b]
QUESTION [0 upvotes]: Let $f$ and $g$ be continuous functions on $[a,b]$ such that $\int_a^b f = \int_a^b g$. Show that there exists $x\in [a,b]$ such that $f(x) = g(x) $.
I want to assume not and then show that the integrals cannot be equal. but perhaps an argument on an upper or lower sums of both fuctions could find the point?

REPLY [2 votes]: Let $f$ and $g$ be continuous functions on $[a, b]$ such that
$$
\int_a^b f(x)\ dx = \int_a^b g(x)\ dx.
$$
Then
$$
\int_a^b f(x)-g(x)\ dx = 0.
$$
Since $f$ and $g$ are continuous, then $f-g$ is continuous. Hence, if $f-g$ is never zero on $[a, b]$, then it must be strictly positive or negative on $[a, b]$. But then $\int_a^b f(x)-g(x)\ dx \neq 0$, which is a contradiction.


TITLE: Basic Iwasawa Theory Question
QUESTION [4 upvotes]: I'm looking at a paper that introduces some terms and intends to use concepts from Iwasawa Theory. I instantly find myself stuck at the second sentence and even after much searching on the internet, I still can't quite understand it.
The paragraph that I'm trying to understand is taken from page 19 of http://wstein.org/papers/shark/shark.pdf
This is the bit that I do not understand:
Let $\Lambda$ be the completed group algebra $\mathbb{Z}_p[[\Gamma]]$. We use a fixed topological generator $\gamma$ of $\Gamma$ to identify $\Lambda$ with $\mathbb{Z}_p[[T]]$ by sending $\gamma$ to $1+T$. Any finitely-generated $\Lambda$-module admits a decomposition up to quasi-isomorphism as a direct sum of elementary $\Lambda$-modules.

What is a completed group algebra $\mathbb{Z}_p[[\Gamma]]$? I've seen the wikipedia page http://en.wikipedia.org/wiki/Group_algebra but it doesn't seem to give me anything I can understand. An elaboration or an example might be good.
How is $\mathbb{Z}_p[[\Gamma]]$ different from $\mathbb{Z}_p[[T]]$?
What are elementary modules?

Thanks for any help.

REPLY [2 votes]: 1) Think of the completed group algebra as "convergent power series in elements of $\Gamma$ with coefficients in $\mathbb{Z}_p$". Alternatively, since as it turns out this is isomorphic to $\mathbb{Z}_p[[T]]$, think of it just as power series in a variable $T$ with coefficients in $\mathbb{Z}_p$.
In general, a group algebra $R[G]$ is the set of polynomials in the "variables" which are just the elements of the group $G$ whose coefficients are elements of some ring $R$. The addition of two such polynomials is the obvious thing, while multiplication is given by the standard "FOIL" you learn in elementary school, only now we are multiplying elements of the group $G$ rather than indeterminates like $x,y,z$ etc. So to "complete" such a thing is literally a completion, in the sense that we can put a topology on the group algebra and then complete it so that all its Cauchy sequences converge. As it turns out, in this case the "completion" of polynomials gives what you expect, which are power series!
2) The difference is a technical one, which I explained in the first paragraph. But you should think of them as behaving the same, since they are isomorphic! The particular choice of isomorphism is important, though.
3) An elementary $\Lambda$ module is the analogue of a finitely generated module over a PID. In the latter case, the structure theorem tells us all f.g. modules over a PID $R$ are isomorphic to $R^n\times torsion$, where the torsion piece is just $R$ modulo various proper (principal!) ideals satisfying some divisibility criterion. In this case, an elementary $\Lambda$ module is similar: It is just a free part $\Lambda^n$ plus a direct sum of things that look like $\Lambda/(f^{\alpha})$ where $f$ is either the prime $p$ or else an irreducible distinguished polynomial, and $\alpha$ is just some power.


TITLE: Derivation of Birthday Paradox formula with unknown n
QUESTION [1 upvotes]: I have been trying to derive the formula for the upper bound probability of the birthday paradox for any number of occurrences $n$.
Assuming we want to find the number of occurrences $k$ such that there is >50% probability they share a property, I am given it to be:
$exp(-k(k-1)/2n)$
Now given the fact that P[share a property] = $\frac{1}{2}$ = $exp(-k(k-1)/2n)$, I would like to find the formula for $k$, so I can just plug in any $n$, to see the number of occurrences required with different values of $n$. This is only an approximation, so I need the formula to be in the form k ≈ ...
I have tried solving for $k$, but got stuck after getting rid of the exponential, which I'm not sure I even did correctly, as it gave me: $2n\ ln(2) < k^2-k$
I managed to find an answer to this online which said that $k ≈ 1.18\sqrt{n}$, but I have no idea how to get to that answer.

REPLY [1 votes]: Since we are finding an approximation for $k$, we should have equality in $2n\ln2<k^2-k$, not just an inequality. The approximation comes after the quadratic formula.
$$k^2-k-2n\ln2=0$$
$$k=\frac{1+\sqrt{1+8n\ln2}}2\approx\sqrt{2n\ln2}=\sqrt{2\ln2}\sqrt n$$
and $\sqrt{2\ln2}=1.17741\dots$


TITLE: Taylor series representation of a function
QUESTION [0 upvotes]: I'm given a function and asked to represent it as a Taylor series, but it seems that taking derivatives of this function gets more and more tedious.  Is there an alternative way to solve this problem?

REPLY [0 votes]: Also, calculating derivatives is easy:
$$f(x)=5(1-2x)^{-1}\\
f'(x)=5\cdot 2(1-2x)^{-2}\\
f''(x)=5\cdot 2\cdot 2(1-2x)^{-3}\\
f'''(x)=5\cdot 2^2\cdot 2\cdot 3(1-2x)^{-3}\\
...\\
f^{(n)}(x)=5\cdot 2^n\cdot n!(1-2x)^{-n-1}$$
For $x=-2$
$$f^{(n)}(-2)=5\cdot 2^n\cdot n!(5)^{-n-1}=\left(\frac{2}{5}\right)^n n!$$


text:
\begin{document}

\twocolumn[
\icmltitle{Linear Spectral Estimators and an Application to Phase Retrieval}

\icmlsetsymbol{equal}{*}

\begin{icmlauthorlist}
	\icmlauthor{Ramina Ghods}{cu}
	\icmlauthor{Andrew S. Lan}{pr}
	\icmlauthor{Tom Goldstein}{mr}
	\icmlauthor{Christoph Studer}{cu}
\end{icmlauthorlist}

\icmlaffiliation{cu}{School~of Electrical and Computer Engineering, Cornell University, Ithaca, NY}
\icmlaffiliation{pr}{Department of EE, Princeton University}
\icmlaffiliation{mr}{University of Maryland}

\icmlcorrespondingauthor{Ramina Ghods}{rg548@cornell.edu}
\icmlcorrespondingauthor{Christoph Studer}{studer@cornell.edu}

\icmlkeywords{[phase retrieval], machine learning, ICML}

\vskip 0.3in
]

\printAffiliationsAndNotice{}

\begin{abstract}

Phase retrieval refers to the problem of recovering real-  or complex-valued vectors from magnitude measurements.

The best-known algorithms for this problem are iterative in nature and rely on so-called spectral initializers that provide accurate initialization vectors.

We propose a novel class of estimators suitable for general nonlinear measurement systems, called linear spectral estimators~(LSPEs), which can be used to compute accurate initialization vectors for phase retrieval problems.

The proposed LSPEs not only provide accurate initialization vectors for noisy phase retrieval systems with structured or random measurement matrices, but also enable the derivation of sharp and nonasymptotic mean-squared error bounds.

We demonstrate the efficacy of LSPEs on synthetic and real-world phase retrieval problems, and show that our estimators significantly outperform existing methods for structured measurement systems that arise in practice.

\end{abstract}

\input{1-introduction.tex}
\input{2-estimator.tex}
\input{3-phaseretrieval.tex}
\input{4-results.tex}
\input{5-conclusions.tex}

\section*{Acknowledgments}

R. Ghods and C.~Studer were supported in part by Xilinx, Inc.\ and by the US National Science Foundation (NSF) under grants ECCS-1408006, EECS-1740286, CCF-1535897,  CCF-1652065, and CNS-1717559.

T. Goldstein was supported by the US NSF under grant CCF-1535902, the US ONR under grant N00014-15-1-2676, the DARPA Lifelong Learning Machines program, and the Sloan Foundation.

\appendix

\input{6-appendices-smushed.tex}

\input{7-supplementary.tex}

\bibliographystyle{icml2018}

\bibliography{confs-jrnls,publishers,phase}

\balance

\end{document}


TITLE: Homology of "Intersecting" Spaces
QUESTION [1 upvotes]: It is fairly routine in Topology textbooks to show how to compute the homology groups of spaces that "look like" $X_1 \times X_2$ or $\bigvee X_i$. But how do you compute the homology groups $H_n$ of spaces that merely interest not in any specific way but rather pass through each other. For instance, take $X$ to be the space formed by the two tori passing through each other below.
My first thought was to create a $\Delta$-complex or CW-complex for the space but it wasn't apparent to me what it should be. Looking through the standard theorems, the only viable approach to me is something like excision but I'm not seeing how this is helping us since I don't see a useful way to decompose the space. How would go about computing $H_n$ in this case? Or perhaps something more simple like a torus passing through a sphere, two spheres passing through each other, or whatever may be less pathological than the case shown here.

REPLY [3 votes]: This is exactly what Mayer-Vietoris sequences are for.  Suppose $X$ is a space and $U$ and $V$ are open subspaces of $X$ with $U\cup V=X$.  Then there is a long exact sequence of homology groups \begin{align*}\dots & \to H_n(U\cap V)\to H_n(U)\oplus H_n(V)\to H_n(X)
\\
 &\to H_{n-1}(U\cap V)\to H_{n-1}(U)\oplus H_{n-1}(V)\to H_{n-1}(X)\\
&\to\dots
\end{align*}
In this sequence, the map $H_n(U\cap V)\to H_n(U)\oplus H_n(V)$ is given by $x\mapsto (i_*(x),-j_*(x))$ where $i:U\cap V\to U$ and $j:U\cap V\to V$ are the inclusion maps.  The map $H_n(U)\oplus H_n(V)\to H_n(X)$ is given by $(y,z)\mapsto k_*(y)+\ell_*(z)$, where $k:U\to X$ and $\ell:V\to X$ are the inclusion maps.
In your case where $X$ is two tori glued together, you can take $U$ to be a small open neighborhood of the left torus and $V$ to be a small open neighborhood of right torus, so $U$ and $V$ both deformation-retract to the tori and $U\cap V$ deformation-retracts to the intersection of the two tori, which is a disjoint union of two circles.  The inclusion map $U\cap V\to U$ is nullhomotopic (both circles enclose disks in the left torus), but the inclusion map $U\cap V\to V$ sends both generators of $H_1(U\cap V)\cong \mathbb{Z}^2$ to one of the generators of $H_1(V)\cong \mathbb{Z}^2$ (since the two circles in $U\cap V$ are both meridans of the right torus).
We can then compute $H_2(X)$ using the Mayer-Vietoris sequence $$H_2(U\cap V)\to H_2(U)\oplus H_2(V)\to H_2(X)\to H_1(U\cap V)\to H_1(U)\oplus H_1(V)$$ which becomes $$0\to \mathbb{Z}\oplus\mathbb{Z}\to H_2(X)\to \mathbb{Z}^2\to \mathbb{Z}^2\oplus\mathbb{Z}^2.$$  The last map sends both $(1,0)$ and $(0,1)$ to $(0,0,-1,-1)$ by the analysis of the inclusion maps $U\cap V\to U$ and $U\cap V\to V$ of the previous paragraph.  In particular, its kernel is generated by $(1,-1)$ and is isomorphic to $\mathbb{Z}$, so we have a short exact sequence $$0\to\mathbb{Z}\oplus\mathbb{Z}\to H_2(X)\to\mathbb{Z}\to 0$$ which gives $H_2(X)\cong \mathbb{Z}^3$.
I'll leave it as an exercise for you to similarly compute $H_1(X)$ using the Mayer-Vietoris sequence.


TITLE: Why does an adiabatic process become an isothermal process when D.O.F. are high?
QUESTION [1 upvotes]: Say that during an adiabatic process, the pressure changes from $p_0$ to $a*p_0$, and let the heat capacities ratio be denoted by b ; using the basic adiabatic relations for an ideal gas, we can find that the temperature changes from $T_0$ to $a^{1-1/b}*T_0$. As the degrees of freedom of  a molecule in the gas tend to infinity, b will tend to 1, which implies that for high degrees of freedom there is little to no temperature change during an adiabatic process i.e. it becomes isothermal. Why is this?
My intuition tells me that high D.O.F. implies more places to store energy, requiring more energy for a given V,P,& T; hence an adiabatic process w/ high D.O.F. will have so much stored energy that the temperature change caused by moving from $p_0$ to $a*p_0$ will be negligible. Is this the right idea?
On a different note, how valid is the ideal gas law when it comes to gases with high D.O.F ? What gases have the highest D.O.F ?

REPLY [1 votes]: In my judgment, your assessment is basically correct.  In an adiabatic process, for a specified amount of work done, the change in internal energy is likewise specified.  And, for a particular internal energy change, the higher the heat capacity of the gas, the lower the temperature change.  So increasing the heat capacity makes the process closer to isothermal.
With regard to your question about the ideal gas law, all gases approach ideal gas behavior in the limit of low densities (irrespective of the DOF).  More precisely, in the limit of low reduced pressures.