text:
\section{\textbf{Numerical Results}}
\label{Sec: numerical results part I}

In the first part of numerical results, we investigate the performance of developed PG scheme in solving FPDE and the adjoint FSEs. We consider the coupled $(1+1)$-d FPDE and FSEs with one-sided fractional derivative and $k=1$, as

\begin{align}

\label{Eq: Numerical FPDE}
&
\prescript{}{0}{\mathcal{D}}_{t}^{\alpha} u
- \prescript{}{-1}{\mathcal{D}}_{x}^{\beta} \, u
= f ,
\\
\label{Eq: Numerical FSE temporal}
&
\prescript{}{0}{\mathcal{D}}_{t}^{\alpha} S_{u,\alpha}
- \prescript{}{-1}{\mathcal{D}}_{x}^{\beta}	S_{u,\alpha}
= S_{f,\alpha}
- \mathcal{A}_1(\alpha) \prescript{}{0}{\mathcal{D}}_{t}^{\alpha} u
+ \prescript{LP}{0}{\mathcal{D}}_{t}^{\alpha} u,
\\
\label{Eq: Numerical FSE spatial}
&
\prescript{}{0}{\mathcal{D}}_{t}^{\alpha} S_{u,\beta}
- \prescript{}{-1}{\mathcal{D}}_{x}^{\beta} S_{u,\beta}
= S_{f,\beta}
+ \mathcal{A}_2(\beta) \, \prescript{}{-1}{\mathcal{D}}_{x}^{\beta}  u
- \prescript{LP}{-1}{\mathcal{D}}_{x}^{\beta} u.

\end{align}

We consider two cases of exact solution as

\begin{itemize}
	\item Case I: $u^{ext}(t,x) =  t^{3+\alpha/2} \, \left((1+x)^{3+\beta/2}-\frac{1}{2}(1+x)^{4+\beta/2}\right)$,

	\item Case II: $u^{ext}(t,x) = t^{3+\alpha/2} (t-0.4)(t-0.9)  \,\, \left((1+x)^{3+\beta/2}-\frac{1}{2}(1+x)^{4+\beta/2}\right)$.

\end{itemize}

where $\alpha/2 = 0.25$, and $\beta/2 = 0.75$. The exact solution and sensitivity fields, obtained by taking $\frac{\partial}{\partial \alpha}$ and $\frac{\partial}{\partial \beta}$ of the exact solutions, are shown in Fig. \ref{Fig: uext suext Case I} and \ref{Fig: uext suext Case II} for the two cases I and II, respectively. We employ the developed PG method to solve FPDE \eqref{Eq: Numerical FPDE} and obtain $u_N$, which we use to construct the right hand side of adjoint FSEs. Then, we again employ the developed PG method to solve FSEs \eqref{Eq: Numerical FSE temporal} and \eqref{Eq: Numerical FSE spatial} and obtain the numerical sensitivity fields, $S_{N_{u,\alpha}} , \, S_{N_{u,\beta}}$. We study the $L^2$-norm convergence of our proposed method by increasing the number of basis functions, as shown in Fig. \ref{Fig: uext suext error case I}.

\begin{figure}[t]
	\centering
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{uext_I.pdf}

	\end{subfigure}
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Su_temporal_ext_I.pdf}

	\end{subfigure}
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Su_spatial_ext_I.pdf}

	\end{subfigure}
	\vspace{-0.15 in}
	\caption{Plot of exact functions for case I with $\alpha/2 = 0.25$ and $\beta/2 = 0.75$: exact solution $u^{ext} $ (left), exact sensitivity field $S_{u^{ext},\alpha} = \frac{\partial u^{ext}}{\partial \alpha}$ (middle), exact sensitivity field $S_{u^{ext},\beta} = \frac{\partial u^{ext}}{\partial \beta}$ (right).}
	\label{Fig: uext suext Case I}
\end{figure}

\begin{figure}[t]
	\centering
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{uext_II.pdf}

	\end{subfigure}
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Su_temporal_ext_II.pdf}

	\end{subfigure}
	\begin{subfigure}{0.32\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Su_spatial_ext_II.pdf}

	\end{subfigure}
	\vspace{-0.15 in}
	\caption{Plot of exact functions for case II with $\alpha/2 = 0.25$ and $\beta/2 = 0.75$: exact solution $u^{ext}$ (left), exact sensitivity field $S_{u^{ext},\alpha}$ (middle), exact sensitivity field $S_{u^{ext},\beta}$ (right).}
	\label{Fig: uext suext Case II}
\end{figure}

\begin{figure}[t]
	\centering
	\begin{subfigure}{0.49\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Case_I_u_SuTmep_SuSpat.pdf}

	\end{subfigure}
	\begin{subfigure}{0.49\textwidth}
		\centering
		\includegraphics[width=1\linewidth]{Case_II_u_SuTmep_SuSpat.pdf}

	\end{subfigure}
	\vspace{-0.1 in}
	\caption{PG spectral method, $L^2$-norm convergence study: $(1+1)$-d FPDE adjoint to corresponding FSEs with one-sided fractional derivative, $k=1$, $\alpha/2 = 0.25$, and $\beta/2 = 0.75$, for Case I (left) and Case II (right), where $N = M$.}
	\label{Fig: uext suext error case I}
\end{figure}

$\bullet$ \textbf{Fractional Model Construction.} The second part of numerical results is dedicated to study the efficiency of developed iterative algorithm in obtaining the set of model parameters $q$ (fractional indices) and thus, construct the fractional model. We test our developed scheme by method of fabricated solution, assuming a given set of input (exact solution) and output (force term) for our fractional model.

We begin with a fractional IVP of the form $\prescript{}{0}{\mathcal{D}}_{t}^{\alpha} u(t) = f(t)$, $\alpha\in(0,1) $, and assume that the exact solution and force function are given as,

\begin{align*}

&u^{*}(t)= sin(5 \pi \, \alpha^*/2) \, t^{3 + \alpha^*/2},
\\
&f^{*}(t)= sin(5 \pi \, \alpha^*/2) \, \frac{\Gamma(4+\alpha^*/2)}{\Gamma(4-\alpha^*/2)}  \, t^{3 - \alpha^*/2},

\end{align*}

and the fractional order $\alpha$ is the unknown model parameter. We start from an initial guess $\alpha^0$ and use the developed iterative algorithm to converge to the true value of fractional index $\alpha$. We also consider a fractional BVP of the form $\prescript{}{-1}{\mathcal{D}}_{x}^{\beta} u(x) = f(x)$, $\beta\in(1,2)$, and assume that the exact solution and force function are given as,

\begin{align*}

&u^{*}(x) = (1+x)^{3+\beta^*/2}-\frac{1}{2}(1+x)^{4+\beta^*/2}
\\
&f^{*}(x) = \frac{\Gamma(4+\beta^*/2)}{\Gamma(4-\beta^*/2)} (1+x)^{3+\beta^*/2} - \frac{1}{2} \frac{\Gamma(5+\beta^*/2)}{\Gamma(5-\beta^*/2)}  (1+x)^{4+\beta^*/2}

\end{align*}

and the fractional order $\beta$ is the unknown model parameter. We again use the developed iterative algorithm to capture the true value of fractional index $\beta$, starting from an initial guess $\beta^0$.

Tables \ref{Table: FIVP model construction} and \ref{Table: FBVP model construction} show two examples for each case of fractional IVP and BVP, where the true values of fractional orders are $\alpha^* = 0.3$, $\alpha^* = 0.9$, $\beta^* = 1.1$, and $\beta^* = 1.7$. We observe that the proposed iterative formulation converges accurately to the exact values with in few numbers of iterations. We note that in the case of fractional IVP and BVP, the search region is already small enough so that the nearby solution is valid, and therefore, we only need to perform the second stage of iterative algorithm.

\begin{table}[t]
	\center
	\caption{\label{Table: FIVP model construction} Fractional model construction for the two cases of fractional IVP.}

	\vspace{-0.1 in}
	\scalebox{1}{
		\begin{tabular}

			{c@{\hspace*{.40in}} c@{\hspace*{.40in}} c }
			Iteration Index & \multicolumn{2}{c}{$\prescript{}{0}{\mathcal{D}}_{t}^{\alpha} u(t) = f(t)  $}   \\
			\hline
			\hline
			i & $\alpha^i$ &  $\alpha^i$   \\
			\hline
			initial guess &  $0.300000$ & $0.900000$  \\
			\hline
			1 &  $0.971980$ & $0.320520$   \\
			\hline
			2 &  $0.900418$ & $0.300068$   \\
			\hline
			3 &  $0.900000$ & $0.300000$  \\
			\hline
			\hline
			True Value &  $0.9$ & $0.3$  \\
			\hline

		\end{tabular}

	}

\end{table}

\begin{table}[t]
	\center
	\caption{\label{Table: FBVP model construction} Fractional model construction for the two cases of fractional BVP.}

	\vspace{-0.1 in}
	\scalebox{1}{
		\begin{tabular}

			{c@{\hspace*{.40in}} c@{\hspace*{.40in}} c }
			Iteration Index  & \multicolumn{2}{c}{$\prescript{}{-1}{\mathcal{D}}_{x}^{\beta} u(x) = f(x)  $} \\
			\hline
			\hline
			i &  $\beta^i$ & $\beta^i$ \\
			\hline
			initial guess & $1.100000$ & $1.9000000$  \\
			\hline
			1 & $1.882020$ & $1.228040$  \\
			\hline
			2 & $1.708120$ & $1.106096$  \\
			\hline
			3 & $1.700020$ & $1.100016$  \\
			\hline
			4 & $1.700000$ & $1.100000$  \\
			\hline
			\hline
			True Value & $1.7$ & $1.1$  \\
			\hline

		\end{tabular}

	}

\end{table}

Moreover, we consider FPDE of the form $ \prescript{}{0}{\mathcal{D}}_{t}^{\alpha} u - k \prescript{}{-1}{\mathcal{D}}_{x}^{\beta} \, u = f  $. We assume the exact solution $u^{*} = t^{1+\alpha^*/2} \left( (1+x)^{3+\beta^*/2}-\frac{1}{2}(1+x)^{4+\beta^*/2} \right)$ and plug it into the FPDE with given $ \{\alpha^* , \beta^*\} $ to obtain the exact force function $f^*$. We study the example, in which, $ \{\alpha^* , \beta^*\} = \{0.1 , 1.64\}$. We perform the two stages of iterative algorithm, where in the first stage, we shrink down the search region 16 time smaller than the original size, by computing the model error at 8 points (See Fig. \ref{Fig: Iterative solver FDE 1}, right). Then, in the next stage, we start from the initial guess $\{ \alpha^0 ,\beta^0 \}=\{ 0.125,1.75 \}$, and observe that the developed iterative method converges to a close neighborhood of true values $\{0.1 , 1.64\}$ within $10^{-3}$ tolerance.

\begin{figure}[t]
	\centering
	\includegraphics[width=0.9\linewidth]{IS_05_82_ver2.pdf}
	\vspace{-0.1 in}
	\caption{Fractional model construction for the case FPDE, using FSEM based iterative algorithm. The true values of fractional indices are $ \{\alpha^* , \beta^*\} = \{0.1 , 1.64\}$.}
	\label{Fig: Iterative solver FDE 1}
\end{figure}

The developed model construction method can also be applied in formulating fractional models to study complex time-varying nonlinear fluid-solid interaction phenomena \cite{atanackovic2014,afzali2016vibrational,afzali2017analysis} and also the effect of damping in structural vibrations \cite{zamani2015asymmetric,abdullatif2018stabilizing}.


TITLE: Proof - a property in positive semi definite (PSD) cone?
QUESTION [1 upvotes]: The clue for proving:

It can also be shown that for any $A,B\in\mathbb S^n_{++}$, $$A\preceq B\quad\Leftrightarrow\quad {\cal E}_A=\left\{u\mid u^TA^{-1}u\le1\right\}\subseteq {\cal E}_B.$$

REPLY [1 votes]: Prove first that ${\cal E}_A\subseteq {\cal E}_B$ $\Leftrightarrow$ $B^{-1}\preceq A^{-1}$.
"$\Leftarrow$" Easy.
"$\Rightarrow$" For any nonzero $u\in\Bbb{R}^n$ set $w=\frac{u}{\sqrt{u^TA^{-1}u}}$ and note that $w\in{\cal E}_A$. Then $w^TB^{-1}w\le 1$ $\Leftrightarrow$ $u^TB^{-1}u\le u^TA^{-1}u$.

Now the claim in question follows from this answer that proves that $B-A\succeq 0$ $\Leftrightarrow$ $A^{-1}-B^{-1}\succeq 0$. (It proves actually only $\Rightarrow$, but the equvalence follows from applying the implication to $A_1=B^{-1}$ and $B_1=A^{-1}$.)
As an alternative proof, both statements "$B-A$ is PSD" and "$A^{-1}-B^{-1}$ is PSD" are equivalent (via Schur complement) to the matrix
$$
M=\begin{bmatrix}
B & A^{1/2}\\A^{1/2} & I
\end{bmatrix}
$$
being PSD. Here $A^{1/2}$ is the principal square root of $A$. Indeed, the Schur complements are
$$
M/I=B-A^{1/2}A^{1/2}=B-A,\quad M/B=I-A^{1/2}B^{-1}A^{1/2},
$$
and $B-A$ is PSD $\Leftrightarrow$ $M$ is PSD $\Leftrightarrow$ $I-A^{1/2}B^{-1}A^{1/2}$ is PSD $\Leftrightarrow$ $A^{-1}-B^{-1}$ is PSD (pre- and postmultiply the previous matrix by $A^{-1/2}$).


TITLE: Linear mapping being not open and not closed
QUESTION [0 upvotes]: Let $T : V → V$ be a linear mapping, where V is a subspace of the Hilbert space H with orthogonal basis $(e_k)_{k≥1}$,
$V = \operatorname{span}\{e_k : k ≥ 1\}.$
$T(e_1) = e_1$ and $T(e_k) = ke_1+e_k$, for all $n ≥ 2$.
I know that $T^{-1}$ is bounded and that $T$ bijective is.
I have problems to show that $T$ is not open and not closed.

REPLY [0 votes]: Why follows it from $T^{-1} $ unbounded that $T$ can't be an open map?
From the Open Mapping Theorem we have that $T^{-1}$ unbounded $\Rightarrow$  $T^{-1}$ not a closed linear map.


TITLE: A graph-theoretic optimization problem
QUESTION [0 upvotes]: Let $G=(V,E)$ be a directed graph with vertex set $V=\{1,\dots,n\}$ and edge set $E$. I associate to each vertex of $G$ a (positive) weight $w_i\in\mathbb{R}$, and denote by $w=[w_1 \dots w_n]^\top$ the vector containing all weights. Let $B\in\mathbb{R}^{n\times |E|}$ denote the incidence matrix of the graph $G$ and $b\in\mathbb{R}^{|E|}$ be a vector with positive entries.
I'm interested in the following (linear) problem:
\begin{align*}
&\max_{\{w_i\}} w_n - w_1 \\
& \text{s.t. }\ \  B^\top w \le b
\end{align*}
Specifically:

Is this problem related to some "standard" graph-theoretic problem? Are there efficient algorithms to solve it?

REPLY [1 votes]: I assume that by incidence matrix you mean its directed version (the one that has $\pm 1$ entries as opposed to just $1$-s).
Your linear program is dual to the linear formulation of the problem of finding a shortest $v_1v_n$ path with edge weights given by $b$, see here. Its solutions are sometimes called "feasible potentials". After running Dijkstra's algorithm starting from $v_1$, the "tentative distance values" given by the algorithm form an optimal solution.


TITLE: probability circle determined by chord determined by two random points is enclosed in bigger circle
QUESTION [5 upvotes]: Two points $A$ and $B$ are chosen uniformly at random from the interior of a circle $X_1$. Let $X_2$ be the circle whose diameter is the segment $AB$. What is the probability that $X_2$ is contained entirely inside $X_1$?
Progress: Not much luck with random integrating.

REPLY [3 votes]: For points $P$ and $Q$ in the plane, let $\Gamma(P,Q)$ denote the circle with segment $PQ$ as its diameter.
We first prove a lemma.
Lemma: Let $\Gamma$ be a circle, $P$ a point inside $\Gamma$, and $P'$ the reflection of $P$ about the center of $\Gamma$. Denote by $\mathcal{L}$ the locus of points $Q$ inside $\Gamma$ such that $\Gamma(P,Q)$ is internally tangent to $\Gamma$. Then $\mathcal{L}$ is the unique ellipse with foci $P$ and $P'$ that is internally tangent to $\Gamma$.
Proof: Suppose $Q$ is inside $\Gamma$ such that $\Gamma(P,Q)$ internally tangent. Let $A$ be the point of tangency, $O$ the center of $\Gamma$, and $O_1$ the center of $\Gamma(P,Q)$. Note that $PQ = 2PO_1$, and $OO_1 = AO - AO_1 = AO - PO_1$. Since $PO = P'O$ and $PO_1 = QO_1$, it follows that $\triangle PO_1 O \sim \triangle PQP'$. Thus $P'Q = 2OO_1 = 2(AO - PO_1)$. Then $PQ + P'Q = 2AO$, which is a constant.
Assume that $X_1$ is of radius 1, and suppose $A$ is distance $x$ from the center of the circle. By the lemma, the probability that $B$ is chosen such that $\Gamma(A,B) \subset \Gamma$ is exactly $(\pi \sqrt{1-x^2})/\pi = \sqrt{1-x^2}$. Thus, the answer is $$\int_{0}^{1} x \sqrt{1-x^2} \, dx = \frac{1}{3}$$


TITLE: conitional probability-probability this given this
QUESTION [0 upvotes]: According to U.S. Department of Labor employment reports,in 2010, 39.3% of jobs were classified as management, professional, and related occupations (Mgt), 14.5% were Service occupations (Svc), 23.2% were Sales and office occupations (SO), 9.9% were Natural resources, construction, and maintenance occupations (NCM), and 13.1% were Production, transportation, and material moving occupations (PTM).
Among Mgt, 48.6% were held by male workers, and 51.4% were held by female workers.
The other categories were:

Svc, 50.6% male, 49.4% female
SO, 38.3% male, 61.7% female
NCM, 95.9% male, 4.1% female
PTM, 80.2% male, 19.8% female

D=NCM, F=female
I want to calculate $P(D|F).$
I know that $P(D|F)=\frac{P(D∩F)}{P(F)}=\frac{P(D)+P(F)−P(D∪F)}{P(F)}$ but how would I find $P(D∪F)$? (I think this is what you're supposed to do? Correct me if I'm wrong)
I do know that the answer is about $0.009$ by the way but I'm trying to figure out how to get that

REPLY [0 votes]: $$P(D|F)=\frac{P(DF)}{P(F)}=\frac{P(F|D)P(D)}{P(F)}\frac{0.041~ X~0.099}{P(F)}$$
To find $P(F)$ you can use the law of total probability which states:
$$
P(F)=\sum_n P(F \cap A_n)=\sum_nP(F|A_n)P(A_n)
$$
So you would have:
$$
P(F)=P(F|D)P(D)+P(F|Mgt)P(Mgt)+...
$$
Hope this helps

REPLY [0 votes]: $$P\left(D\mid F\right)=P\left(F\mid D\right)\times\frac{P\left(D\right)}{P\left(F\right)}$$ and:
$$P\left(F\right)=P\left(F\mid D\right)P\left(D\right)+\dots+P\left(F\mid Svc\right)P\left(Svc\right)$$


text:
For two integers $a,b$, let ${\rm gcd}(a,b)$ be the largest positive integer that evenly divides both $a$ and $b$.
It is a well-established result in number theory that
\begin{equation}\label{eq:one}
\lim_{ n \rightarrow \infty } \frac{\#\left\{(a,b)\in [n]^2,~{\rm gcd}(a,b)=1\right\}}{n^2} = \frac{6}{\pi^2}\,.
\end{equation}
\citep[Theorem 331]{hardy-wright2008}, where $[n]=\{1,2,...,n\}$. They then write
``it is natural" to interpret \eqref{eq:one} as a probability, and conclude (Theorem 332) that
\begin{equation}\label{eq:claim}
\text{the \textit{probability} that two randomly chosen integers are co-prime is $6/\pi^2$.}
\end{equation}

The purpose of this paper is to reconcile \eqref{eq:claim} with modern probability theory. To do so, we first introduce the two main frameworks used in probability, and then apply them to \eqref{eq:claim}.

\subsection{A brief introduction to probability axioms} There are two different axiom systems for probability. The first, and most familiar, is countably additive. It starts with a triple of objects: $(\Omega, \mathcal B, P)$, where $\Omega$ is the basic set of objects, $\mathcal B$ is a $\sigma$-field of subsets of $\Omega$, and $P\{\cdot\}$ is a probability over elements of $\mathcal B$ satisfying
\begin{enumerate}
\item[(a)] $P \{B\} \geq 0$ for all $B \in \mathcal B$
\item[(b)] $P \{\Omega\} = 1$
\item[(c)] If $B_1, B_2,\ldots$ is a countable sequence of disjoint elements of $\mathcal B$, then
$$
P\left\{\bigcup^\infty_{i=1} B_i\right\} = \sum^\infty_{i=1} P\{B_i\}.
$$
\end{enumerate}

This is the axiom system advocated by \citet{kolmogorov1933}\footnote{For an English translation, see \citet{kolmogorov2018}.}. It has the advantage that conditional probabilities obey the tower property:
\begin{equation}\label{eq:j1}
E(X) = E\left[E(X | Y)\right],
\end{equation}
but the disadvantage that it is defined only on $\mathcal B$, and cannot, in general, be extended to the power set of $\Omega$ (\citet[][Section 3]{billingsley1995probability} shows
the existence of non-measurable sets).

The second axiom system is finitely additive, replacing (c) above with the condition:
\begin{enumerate}
\item[(c$^\prime$)] If $B_1,B_2,\ldots, B_n$ is a finite collection of disjoint subsets of $\Omega$, then
$$
P\left\{\bigcup^n_{i=1} B_i\right\} = \sum^n_{i=1} P\{B_i\}.
$$
\end{enumerate}
This has the advantage that a finitely additive distribution can be extended to the power set, but the disadvantage that the tower property does not, in general, hold for them. This sense of probability was particularly advocated by \citet{deFinetti1937prevision}\footnote{For an English translation, see \citet{kyburg1980studies}.}.

Every countably additive probability is finitely additive, but not conversely.

\subsection{Application to coprime integers}
Let $G = \{(a,b) \in \mathbb N^2: {\rm gcd}(a,b) = 1\}$ be the set of pairs of integers that are coprime. We explore the probability of $G$ under various different settings, beginning with limiting relative frequency. Limiting relative frequency cannot be countably additive, since the limiting relative frequency of each pair of integers is zero, but the countable union of them, $\mathbb N^2$, has limiting relative frequency one. Hence, we consider first finitely additive probabilities on $\mathbb N^2$, including limiting relative frequency, in Section~\ref{sec:finitely}. Sections~\ref{sec:rel_freq}, \ref{sec:residue-classes} and \ref{sec:shift-invariance} apply finitely additive probability on $\mathbb N^2$ respectively to limiting relative frequency, residue classes and shift invariance.  Section~\ref{sec:countably} proposes a countably additive probability specification that also supports $P\{G\} = 6/\pi^2$.

config: arxiv


text:
\section{Preliminaries}

\subsection{Bi-partitions and symbols}\label{0208}
For a partition $\lambda=[\lambda_1,\lambda_2\ldots,\lambda_r]$ (with $\lambda_1\geq\lambda_2\geq\cdots\geq\lambda_r\geq 0$),
we define $\|\lambda\|=\lambda_1+\cdots+\lambda_r$.
If $\|\lambda\|=n$, $\lambda$ is called a \emph{partition of $n$}.
The set of partitions of $n$ is denoted by $\calp(n)$.
For two partitions $\lambda=[\lambda_1,\ldots,\lambda_k]$ and $\lambda'=[\lambda'_1,\ldots,\lambda'_{k'}]$ of $n$,
we say that $\lambda<\lambda'$ in \emph{lexicographic order} if
there exists an index $k_0$ such that $\lambda_{k_0}<\lambda'_{k_0}$ and
$\lambda_i=\lambda'_i$ for each $i=1,\ldots,k_0-1$.
This gives a linear order on $\calp(n)$.

For a partition $\lambda=[\lambda_i]$, define its \emph{dual partition}
$\lambda^\rmT=[\lambda_j^*]$ by $\lambda_j^*=|\{\,i\mid\lambda_i\geq j\,\}|$ for $j\in\bbN$.
For $\lambda=[\lambda_1,\ldots,\lambda_r]\in\calp(n)$ and $\mu=[\mu_1,\ldots,\mu_s]$,
define their union $\lambda\cup\mu$ to be the partition in $\calp(n+m)$ with parts $\lambda_1,\ldots,\lambda_r,\mu_1,\ldots,\mu_s$.

A \emph{bi-partition of $n$} is an ordered pair of two partitions $\sqbinom{\mu}{\nu}$ such that
\[
\left\|\sqbinom{\mu}{\nu}\right\|:=\|\mu\|+\|\nu\|=n.
\]
The first (resp.~second) row of a bi-partition $\Sigma$ is denoted by $\Sigma^*$ (resp.~$\Sigma_*$), i.e.,
$\Sigma=\sqbinom{\Sigma^*}{\Sigma_*}$.
The set of bi-partitions of $n$ is denoted by $\calp_2(n)$.
For a bi-partition $\sqbinom{\mu}{\nu}$,
we define its \emph{transpose} $\sqbinom{\mu}{\nu}^\rmt=\sqbinom{\nu}{\mu}$.
We define the union of two bi-partitions by
\[
\sqbinom{\lambda}{\mu}\cup\sqbinom{\nu}{\xi}
:=\sqbinom{\lambda\cup\nu}{\mu\cup\xi}.
\]

A \emph{$\beta$-set} is a finite subset $A=\{a_1,\ldots,a_m\}$ (possibly empty) of non-negative integers
written in (strictly) decreasing order, i.e., $a_1>a_2>\cdots>a_m$.
A \emph{symbol} is an ordered pair
\[
\Lambda=\binom{A}{B}=\binom{a_1,a_2,\ldots,a_{m_1}}{b_1,b_2,\ldots,b_{m_2}}
\]
of two $\beta$-sets.
Define an equivalence relation on the set of symbols generated by the rule
\begin{equation}\label{0230}
\binom{a_1,a_2,\ldots,a_{m_1}}{b_1,b_2,\ldots,b_{m_2}}\sim
\binom{a_1+1,a_2+1,\ldots,a_{m_1}+1,0}{b_1+1,b_2+1,\ldots,b_{m_1}+1,0}.
\end{equation}
A symbol $\Lambda=\binom{A}{B}$ is \emph{reduced} if $0\not\in A\cap B$.
The first (resp.~second) row of a symbol $\Lambda$ is denoted by $\Lambda^*$ (resp.~$\Lambda_*$), i.e.,
$\Lambda=\binom{\Lambda^*}{\Lambda_*}$.
For a symbol $\Lambda=\binom{A}{B}$,
we define its \emph{transpose} $\Lambda^\rmt=\binom{B}{A}$, and its \emph{rank} and \emph{defect} by
\begin{align}\label{0202}
\begin{split}
{\rm rk}(\Lambda)
&= \sum_{a\in A}a+\sum_{b\in B}b-\left\lfloor\biggl(\frac{|A|+|B|-1}{2}\biggr)^2\right\rfloor \\
{\rm def}(\Lambda)
&= |A|-|B|
\end{split}
\end{align}
where $|X|$ denotes the number of elements in a finite set $X$.
It is easy to see that two equivalent symbols have the same rank and the same defect,
and
\begin{align}\label{0201}
\begin{split}
{\rm rk}(\Lambda)&\geq \left\lfloor\biggl(\frac{{\rm def}(\Lambda)}{2}\biggr)^2\right\rfloor, \\
\sum_{a\in A}a+\sum_{b\in B}b &={\rm rk}(\Lambda)+
\begin{cases}
m^2, & \text{if $|A|+|B|=2m+1$};\\
m(m-1), & \text{if $|A|+|B|=2m$}.
\end{cases}
\end{split}
\end{align}

\begin{lem}\label{0210}
Let
\[
\Lambda=\binom{a_1,a_2,\ldots,a_{m_1}}{b_1,b_2,\ldots,b_{m_2}}\quad\text{and}\quad
\Lambda'=\binom{a'_1,a'_2,\ldots,a'_{m'_1}}{b'_1,b'_2,\ldots,b'_{m'_2}}
\]
be two reduced symbols.
If $m_1=m_1'+1$, $m_2=m'_2+1$, $a_i>a'_i$ for $i=1,2,\ldots,m_1-1$,
and $b_j>b'_j$ for $j=1,2,\ldots,m_2-1$,
then ${\rm rk}(\Lambda)>{\rm rk}(\Lambda')$.
\end{lem}
\begin{proof}
Let
\[
\Lambda''=\binom{a'_1+1,a'_2+1,\ldots,a'_{m'_1}+1,0}{b'_1+1,b'_2+1,\ldots,b'_{m'_2}+1,0}.
\]
It is known that ${\rm rk}(\Lambda'')={\rm rk}(\Lambda')$.
Now $a_i\geq a'_i+1$ for $i=1,2,\ldots,m_1-1$ and $b_j\geq b'_j+1$ for $j=1,2,\ldots,m_2-1$.
Because now $\Lambda$ is reduced, we have $a_{m_1}>0$ or $b_{m_2}>0$.
Therefore ${\rm rk}(\Lambda)>{\rm rk}(\Lambda'')$ by the definition in (\ref{0202}).
\end{proof}

Let $\cals$ denote the set of reduced symbols,
and let $\cals_{n,\delta}$ denote the set of reduced symbols of rank $n$ and defect $\delta$.
The mapping
\begin{equation}\label{0209}
\Upsilon\colon \binom{a_1,\ldots,a_{m_1}}{b_1,\ldots,b_{m_2}}\mapsto
\sqbinom{a_1-(m_1-1),a_2-(m_1-2),\ldots,a_{m_1-1}-1,a_{m_1}}{b_1-(m_2-1),b_2-(m_2-2),\ldots,b_{m_2-1}-1,b_{m_2}}
\end{equation}
gives a bijection
\begin{equation}\label{0205}
\cals_{n,\delta}\rightarrow\begin{cases}
\calp_2(n-(\frac{\delta}{2})^2), & \text{if $\delta$ is even};\\
\calp_2(n-(\frac{\delta+1}{2})(\frac{\delta-1}{2})), & \text{if $\delta$ is odd}.
\end{cases}
\end{equation}
Modified from \cite{lg}, we define
\begin{align}\label{0220}
\begin{split}
\cals_{\Sp_{2n}} &=\{\,\Lambda\in\cals\mid{\rm rk}(\Lambda)=n,\ {\rm def}(\Lambda)\equiv 1\pmod 4\,\}; \\
\cals_{\rmO_{2n}^+} &=\{\,\Lambda\in\cals\mid{\rm rk}(\Lambda)=n,\ {\rm def}(\Lambda)\equiv 0\pmod 4\,\}; \\
\cals_{\rmO_{2n}^-} &=\{\,\Lambda\in\cals\mid{\rm rk}(\Lambda)=n,\ {\rm def}(\Lambda)\equiv 2\pmod 4\,\}.
\end{split}
\end{align}

\subsection{Unipotent characters}
Let $\bff_q$ be a finite field of $q$ elements where $q$ is a power of an odd prime $p$.
Let $\bfG$ be a classical group defined over $\bff_q$,
and let $G$ denote the group of rational points.
Let $\cale(G)=\Irr(G)$ denote the set of irreducible characters of $G$,
and let $\calv(G)$ denote the space of (complex valued) class functions on $G$.
Then $\calv(G)$ is an inner product space with $\cale(G)$ as an orthonormal basis.

The \emph{Lusztig series} $\cale(G)_s$ associated to the conjugacy class of a semisimple element $s$
in the connected component $(G^*)^0$ of the dual group $G^*$ of $G$ is given by
\[
\cale(G)_s=\{\,\rho\in\cale(G)\mid\langle\rho,R_{\bfT^*,s}\rangle\neq0\text{ for some $\bfT^*$ containing $s$}\,\}.
\]
Here $\bfT^*$ is a rational maximal torus in $\bfG^*$ and $s\in T^*$ (the rational points of $\bfT^*$)
and $R_{\bfT^*,s}$ is the Deligne-Lusztig virtual character associated to the pair $(\bfT^*,s)$
(\cf.~\cite{dl}).
Then we have a partition of $\cale(G)$ indexed by the conjugacy classes $(s)$:
\[
\cale(G)=\bigsqcup_{(s)\subset(G^*)^0}\cale(G)_s.
\]
Let $\calv(G)_s$ denote the subspace of $\calv(G)$ spanned by $\cale(G)_s$.
We need the following result (\cf.~\cite{DM} theorem 13.23, remark 13.24):
\begin{prop}[Lusztig]
Let $\bfG$ be a classical group.
There exists a bijection
\[
\grL_s\colon\cale(G)_s\rightarrow\cale(C_{G^*}(s))_1
\]
such that
\[
\langle\rho,R^\bfG_{\bfT^*,s}\rangle_G
=\langle\grL_s(\rho),R^{C_{\bfG^*}(s)}_{\bfT^*,1}\rangle_{C_{G^*}(s)}
\]
for any $\rho\in\cale(G)$.
Here $\langle,\rangle_G$ denotes the inner product of $\calv(G)$.
\end{prop}
Note that the mapping $\grL_s$ is usually not uniquely determined.
An element in $\cale(G)_1$ is called a \emph{unipotent character} of $G$.
The following fundamental result is from \cite{lg}:

\begin{prop}[Lusztig]
Let $\bfG$ be a symplectic group or an even orthogonal group.
There exists a bijection $\cals_\bfG\rightarrow\cale(G)_1$
where $\cals_\bfG$ is given in (\ref{0220}).
\end{prop}

Then the irreducible unipotent character of $G$ corresponding to the symbol $\Lambda\in\cals_\bfG$ is denoted by $\rho_\Lambda$.
If $\bfG$ is an orthogonal group,
it is known that $\rho_{\Lambda^\rmt}=\rho_\Lambda\cdot\sgn$.
Moreover, the trivial character $\bf 1_{\bfG}$ of $G$ is parametrized by
\[
{\bf 1}_\bfG=
\begin{cases}
\rho_{\binom{n}{-}}, & \text{if $\bfG=\Sp_{2n}$};\\
\rho_{\binom{n}{0}}, & \text{if $\bfG=\rmO^+_{2n}$};\\
\rho_{\binom{-}{n,0}}, & \text{if $\bfG=\rmO^-_{2n}$}.
\end{cases}
\]
Here $\binom{n}{-}$ means that the second row of the symbol is empty.

\subsection{The order of a symbol}\label{0221}
If $f(q)$ is a polynomial in $q$,
let $\deg(f)$ denote the degree of $f$.
For a $\beta$-set $A=\{a_1,\ldots,a_{m_1}\}$,
we define
\begin{align*}
\Delta(A,q) &=\prod_{a,a'\in A,\ a>a'}(q^a-q^{a'}), \\
\Theta(A,q^2) &=\prod_{a\in A}\left(\prod_{h=1}^a(q^{2h}-1)\right).
\end{align*}
Because $a_1>a_2>\cdots>a_{m_1}$,
we have
\[
\deg(\Delta(A,q))=\sum_{i=1}^{m_1}(m_1-i)a_i\quad\text{and}\quad
\deg(\Theta(A,q^2))=\sum_{i=1}^{m_1}a_i(a_i+1).
\]
For a symbol $\Lambda=\binom{A}{B}=\binom{a_1,a_2,\ldots,a_{m_1}}{b_1,b_2,\ldots,b_{m_2}}$,
we define
\[
\Pi(\Lambda,q)=\prod_{(a,b)\in A\times B}(q^a+q^b),
\]
and then we have
\[
\deg(\Pi(\Lambda,q))=\sum_{i=1}^{m_1}\sum_{j=1}^{m_2}\max(a_i,b_j).
\]
The following result is from \cite{lg}, theorem 8.2:

\begin{prop}[Lusztig]\label{0211}
Let $\Lambda=\binom{A}{B}=\binom{a_1,a_2,\ldots,a_{m_1}}{b_1,b_2,\ldots,b_{m_2}}\in\cals_\bfG$.
Then the dimension of $\rho_\Lambda$ is
\[
\rho_\Lambda(1)
=\frac{1}{2^c}|G|_{p'}\cdot \frac{\Delta(A,q)\Delta(B,q)}{\Theta(A,q^2)\Theta(B,q^2)}
\cdot\frac{\Pi(\Lambda,q)}{q^{\binom{m_1+m_2-2}{2}+\binom{m_1+m_2-4}{2}+\cdots}}
\]
where $c=\lfloor\frac{m_1+m_2-1}{2}\rfloor$ if $A\neq B$; $c=m_1=m_2$ if $A=B$;
$|G|_{p'}$ means the maximal factor of $|G|$ prime to $p$.
\end{prop}

The \emph{order} of $\Lambda\in\cals_\bfG$ is defined and denoted by $\ord(\Lambda)=\deg(\rho_\Lambda(1))$.
A symbol
\[
Z=\begin{cases}
\binom{z_1,z_3,\ldots,z_{m-2},z_m}{z_2,z_4,\ldots,z_{m-1}}, & \text{if $Z$ is of defect $1$};\\
\binom{z_1,z_3,\ldots,z_{m-1}}{z_2,z_4,\ldots,z_m}, & \text{if $Z$ is of defect $0$}
\end{cases}
\]
is called \emph{special} if $z_1\geq z_2\geq z_3\geq\cdots\geq z_{m-1}\geq z_m$.

\begin{lem}\label{0214}
Let $Z$ be a special symbol with entries $z_1\geq z_2\geq \cdots\geq z_m$.
Suppose that $k<l$.
Then $(l-k)+2(z_l-z_k-1)<0$.
\end{lem}
\begin{proof}
Note that two entries in the same row of a symbol must be different.
Therefore
\[
z_k-z_l\geq\begin{cases}
\frac{l-k}{2}, & \text{if $l-k$ is even;}\\
\frac{l-k-1}{2}, & \text{if $l-k$ is odd}.
\end{cases}
\]
for any $l>k$.
Then the lemma is proved immediately.
\end{proof}

\begin{lem}\label{0213}
Let $Z$ be a special symbol of rank $n$ with entries
$z_1,z_2,\ldots,z_m$ where $z_1\geq z_2\geq \cdots\geq z_m$.
Then $\ord(Z)$ is equal to
\[
\sum_{i=1}^m (m-i)z_i-\sum_{i=1}^m z_i(z_i+1)+
\begin{cases}
n(n+1)-\frac{1}{24}(m-1)(m-3)(2m-1), & \text{if $m$ odd};\\
n^2-\frac{1}{24}m(m-2)(2m-5), & \text{if $m$ even}.
\end{cases}
\]
\end{lem}
\begin{proof}
Write $Z=\binom{A}{B}$.
Because now $z_1\geq z_2\geq\cdots\geq z_m$,
from definition it is not difficult to see that
\begin{align*}
\deg(\Delta(A,q)\Delta(B,q)\Pi(Z,q))
&= \sum_{(z_i,z_j)\in Z\times Z,\ i\neq j}\max(z_i,z_j)
= \sum_{i=1}^m (m-i)z_i \\
\deg(\Theta(A,q^2)\Theta(B,q^2))
&= \sum_{i=1}^m z_i(z_i+1)
\end{align*}
Moreover,
\begin{align*}
\binom{m-2}{2}+\binom{m-4}{2}+\cdots
&= \begin{cases}
\frac{1}{24}(m-1)(m-3)(2m-1), & \text{if $m$ odd};\\
\frac{1}{24}m(m-2)(2m-5), & \text{if $m$ even},
\end{cases} \\
\deg(|G|_{p'})
&= \begin{cases}
n(n+1), & \text{if $\bfG=\Sp_{2n}$};\\
n^2, & \text{if $\bfG=\rmO^\pm_{2n}$}.
\end{cases}
\end{align*}
Note that $Z\in\cals_\bfG$ where $\bfG=\Sp_{2n}$ if $m$ is odd;
$\bfG=\rmO^\pm_{2n}$ if $m$ is even.
Then the lemma follows from Proposition~\ref{0211} immediately.
\end{proof}

For a special symbol $Z\in\cals_\bfG$,
let $\cals_Z$ denotes the set of symbols $\Lambda\in\cals_\bfG$ whose entries are exactly the same as
the entries of $Z$.

\begin{exam}
Let $Z=\binom{2,0}{1}\in\cals_{\Sp_4}$ is a special symbol of rank $2$ and defect $1$.
Then
\[
\textstyle
\cals_Z=\left\{\binom{2,0}{1},\binom{2,1}{0},\binom{1,0}{2},\binom{-}{2,1,0}\right\}\subset\cals_{\Sp_4}.
\]
\end{exam}

\begin{cor}\label{0216}
If $\Lambda\in\cals_Z$ for some special symbol $Z$,
then $\ord(\Lambda)=\ord(Z)$.
\end{cor}
\begin{proof}
From the proof of Lemma~\ref{0213},
we know that $\ord(\Lambda)$ depends only on the entries of $\Lambda$
but not on the positions of the entries.
\end{proof}

\begin{rem}
\begin{enumerate}
\item Suppose that $\bfG=\Sp_{2n}$.
If $\Lambda=\binom{n,n-1,\ldots,1,0}{n,n-1,\ldots,1}$,
then $m=2n+1$ and $z_{2i-1}=z_{2i}=n+1-i$ for $i=1,\ldots,n$.
Then
\begin{align*}
\sum_{i=1}^m (m-i)z_i &= \frac{1}{6}n(n+1)(8n+1), \\
\sum_{i=1}^m z_i(z_i+1) &= \frac{2}{3}n(n+1)(n+2), \\
\frac{1}{24}(m-1)(m-3)(2m-1) &= \frac{1}{6}n(n-1)(4n+1).
\end{align*}
So by Lemma~\ref{0213},
\begin{align*}
\ord(\Lambda)
&= \frac{1}{6}n(n+1)(8n+1)-\frac{2}{3}n(n+1)(n+2)+n(n+1)-\frac{1}{6}n(n-1)(4n+1) \\
&= n^2,
\end{align*}
i.e., $\rho_{\binom{n,n-1,\ldots,1,0}{n,n-1,\ldots,1}}$ is the Steinberg character of
$\Sp_{2n}(q)$.

\item Suppose that $\bfG=\rmO^+_{2n}$.
If $\Lambda=\binom{n,n-1,\ldots,1}{n-1,n-2,\ldots,0}$,
then $m=2n$ and $z_1=n$, $z_{2i}=z_{2i+1}=n-i$ for $i=1,\ldots,n-1$.
Then
\begin{align*}
\sum_{i=1}^m (m-i)z_i &= \frac{1}{6}n(8n^2-3n+1), \\
\sum_{i=1}^m z_i(z_i+1) &= \frac{1}{3}n(n+1)(2n+1), \\
\frac{1}{24}m(m-2)(2m-5) &= \frac{1}{6}n(n-1)(4n-5).
\end{align*}
So by Lemma~\ref{0213},
\begin{align*}
\ord(\Lambda)
&= \frac{1}{6}n(8n^2-3n+1)-\frac{1}{3}n(n+1)(2n+1)+n^2-\frac{1}{6}n(n-1)(4n-5) \\
&= n(n-1).
\end{align*}
So $\rho_{\binom{n,n-1,\ldots,1}{n-1,n-2,\ldots,0}}$ and $\rho_{\binom{n-1,n-2,\ldots,0}{n,n-1,\ldots,1}}$
are the two Steinberg characters of $\rmO^+_{2n}(q)$ for $n\geq 1$.

\item Suppose that $\bfG=\rmO^-_{2n}$.
If $\Lambda=\binom{n,n-1,\ldots,0}{n-1,n-2,\ldots,1}$,
then $\ord(\Lambda)=n(n-1)$ by (2) and Corollary~\ref{0216}.
So $\rho_\Lambda$ and $\rho_{\Lambda^\rmt}$ are the two Steinberg characters of $\rmO^-_{2n}(q)$ for $n\geq 1$.
\end{enumerate}
\end{rem}

Suppose that $z_1\geq z_2\geq\cdots\geq z_m$.
Now we consider the entries
\begin{equation}\label{0212}
z_1,\ldots,z_{k-1},z_k+1,z_{k+1},\ldots,z_{l-1},z_l-1,z_{l+1},\ldots,z_m
\end{equation}
for some $k<l$.
If $z_{k-1}<z_k+1$, then we have $z_{k-2}>z_{k-1}=z_k$.
Then the entries in (\ref{0212}) are the same as
\[
z_1,\ldots,z_{k-2},z_{k-1}+1,z_k,z_{k+1},\ldots,z_{l-1},z_l-1,z_{l+1},\ldots,z_m
\]
and we have $z_{k-2}\geq z_{k-1}+1$.
If $z_l-1<z_{l+1}$, then we have $z_l=z_{l+1}>z_{l+2}$.
Then the entries in (\ref{0212}) are the same as
\[
z_1,\ldots,z_{k-1},z_k+1,z_{k+1},\ldots,z_{l-1},z_l,z_{l+1}-1,z_{l+2},\ldots,z_m
\]
and we have $z_{l+1}-1\geq z_{l+2}$.
Therefore, without loss of generality,
we may assume that the sequence (\ref{0212}) is still monotonically decreasing .

\begin{lem}\label{0215}
Suppose that $Z$ is a symbol with entries $z_1,\ldots,z_m$ such that $z_1\geq\cdots\geq z_m$,
and $Z'$ is a symbol with entries
\[
z_1,\ldots,z_{k-1},z_k+1,z_{k+1},\ldots,z_{l-1},z_l-1,z_{l+1},\ldots,z_m
\]
such that $k<l$, $z_{k-1}\geq z_k+1$ and $z_l-1\geq z_{l+1}$.
Then $\ord(Z')<\ord(Z)$.
\end{lem}
\begin{proof}
Note that the sum of entries in $Z$ is the same as the sum of entries in $Z'$.
So by (\ref{0201}), we see that symbols $Z$ and $Z'$ are of the same rank.
Now
\begin{align*}
(z_k+1)(m-k)-(z_k+1)(z_k+2)-z_k(m-k)+z_k(z_k+1)
&= m-k-2z_k-2, \\
(z_l-1)(m-l)-(z_l-1)z_l-z_l(m-l)+z_l(z_l+1)
&= 2z_l-m+l.
\end{align*}
From Lemma~\ref{0213}, we see that
\begin{align*}
\ord(Z')-\ord(Z)
= m-k-2z_k+2z_l-m+l
= (l-k)+2(z_l-z_k-1).
\end{align*}
Hence the lemma follows from Lemma~\ref{0214} immediately.
\end{proof}

\begin{lem}\label{0218}
Let $Z,Z'$ be two special symbols of the same rank $n$.
Suppose that $Z$ has entries $z_1,\ldots,z_m$ with $z_1\geq z_2\geq\cdots\geq z_m$,
and $Z'$ has entries $z'_1,\ldots,z'_m$ with $z'_1\geq z'_2\geq\cdots\geq z'_m$.
If
\[
z_1+z_2+\cdots+z_i\geq z'_1+z'_2+\cdots+z'_i\qquad\text{for each $i=1,\ldots,m$},
\]
then $\ord(Z)\leq\ord(Z')$,
and the equality holds if and only if $z_i=z'_i$ for all $i=1,\ldots,m$.
\end{lem}
\begin{proof}
Because $Z,Z'$ have the same rank, we know that
\[
z_1+z_2+\cdots+z_m=z'_1+z'_2+\cdots+z'_m.
\]
Suppose that $Z,Z'$ are not identical.
So there are a smallest positive integer $i_0$ such that $z_{i_0}>z'_{i_0}$ and a smallest positive integer
$j_0$ such that $z_{j_0}<z'_{j_0}$.
By the assumption in the lemma, we know that $i_0<j_0$.
Let $Z''$ be a special symbol of entries $z''_1,\ldots,z''_m$ where
$z''_{i_0}=z'_{i_0}+1$, $z''_{j_0}=z'_{j_0}-1$ and $z''_k=z'_k$ for $k\neq i_0,j_0$.
Then it is clear that $z''_1\geq z''_2\geq \cdots\geq z''_m$ and $Z$ has rank $n$.
Moreover, we still have
\[
z_1+z_2+\cdots+z_i\geq z''_1+z''_2+\cdots+z''_i\qquad\text{for each $i=1,\ldots,m$}.
\]
Now $\ord(Z'')<\ord(Z')$ by Lemma~\ref{0215}.
Hence the lemma is proved by induction.
\end{proof}

\begin{lem}\label{0217}
Let
\[
\Lambda=\binom{a_1,\ldots,a_{m_1}}{b_1,\ldots,b_{m_2}}\quad\text{and}\quad
\Lambda'=\binom{a'_1,\ldots,a'_{m_1}}{b'_1,\ldots,b'_{m_2}}
\]
be two symbols of the same rank and the same defect.
\begin{itemize}
\item[(i)] Suppose that $b_j=b'_j$ for each $j$, and
\[
a_1+a_2+\cdots+a_i\geq a'_1+a'_2+\cdots+a'_i\qquad\text{for each $i=1,\ldots,m_1$},
\]
then $\ord(\Lambda)\leq\ord(\Lambda')$ and the equality holds if and only if $a_i=a'_i$ for all $i$.

\item[(ii)] Suppose that $a_i=a'_i$ for each $i$, and
\[
b_1+b_2+\cdots+b_j\geq b'_1+b'_2+\cdots+b'_j\qquad\text{for each $j=1,\ldots,m_2$},
\]
then $\ord(\Lambda)\leq\ord(\Lambda')$ and the equality holds if and only if $b_j=b'_j$ for all $j$.
\end{itemize}
\end{lem}
\begin{proof}
Let $Z,Z'$ be the special symbols with the same entries of $\Lambda,\Lambda'$ respectively.
Let $z_1,\ldots,z_{m_1+m_2}$ (resp.~$z'_1,\ldots,z'_{m_1+m_2}$) be the entries of $Z$ (resp.~$Z'$).
Clearly, the conditions in (i) imply the condition in Lemma~\ref{0218},
and we have $\ord(Z)\leq\ord(Z')$ and the equality holds if and only if $z_i=z'_i$ for all $i=1,\ldots,m_1+m_2$.
Then by Corollary~\ref{0216}, we have $\ord(\Lambda)\leq\ord(\Lambda')$
and the equality holds if and only if $a_i=a'_i$ for all $i$.

The proof of (ii) is similar and omitted.
\end{proof}

\begin{cor}\label{0219}
Let $\Lambda,\Lambda'$ be two symbols of the same rank and the same defect such that
\[
\Upsilon(\Lambda)=\sqbinom{\lambda_1,\ldots,\lambda_{m_1}}{\mu_1,\ldots,\mu_{m_2}}\quad\text{and}\quad
\Upsilon(\Lambda')=\sqbinom{\lambda'_1,\ldots,\lambda'_{m_1}}{\mu'_1,\ldots,\mu'_{m_2}}.
\]
\begin{itemize}
\item[(i)] Suppose that $\mu_j=\mu'_j$ for each $j$, and
\[
\lambda_1+\lambda_2+\cdots+\lambda_i\geq \lambda'_1+\lambda'_2+\cdots+\lambda'_i\qquad\text{for each $i=1,\ldots,m_1$},
\]
then $\ord(\Lambda)\leq\ord(\Lambda')$ and the equality holds if and only if $\lambda_i=\lambda'_i$ for all $i$.

\item[(ii)] Suppose that $\lambda_i=\lambda'_i$ for each $i$, and
\[
\mu_1+\mu_2+\cdots+\mu_j\geq \mu'_1+\mu'_2+\cdots+\mu'_j\qquad\text{for each $j=1,\ldots,m_2$},
\]
then $\ord(\Lambda)\leq\ord(\Lambda')$ and the equality holds if and only if $\mu_j=\mu'_j$ for all $j$.
\end{itemize}
\end{cor}
\begin{proof}
Write
\[
\Lambda=\binom{a_1,\ldots,a_{m_1}}{b_1,\ldots,b_{m_2}}\quad\text{and}\quad
\Lambda'=\binom{a'_1,\ldots,a'_{m_1}}{b'_1,\ldots,b'_{m_2}}.
\]
By (\ref{0209}) we have
$\lambda_i=a_i-(m_1-i)$, $\lambda'_i=a'_i-(m_1-i)$, $\mu_j=b_j-(m_2-j)$, and $\mu'_j=b'_j-(m_2-j)$ for each
$i,j$.
Then the corollary follows from Lemma~\ref{0217} immediately.
\end{proof}


text:
\begin{document}

\title[Population dynamics: from small and random to large and pseudo-deterministic]{Populations with interaction and environmental dependence: from few, (almost) independent, members into deterministic evolution of high densities.}

\author{P. Chigansky}
\address{Department of Statistics,
The Hebrew University,
Mount Scopus, Jerusalem 91905,
Israel}
\email{pchiga@mscc.huji.ac.il}

\author{P. Jagers}
\address{Mathematical Sciences, Chalmers University of Technology
and University of Gothenburg, SE-412 96 Gothenburg, Sweden}
\email{jagers@chalmers.se}

\author{F. Klebaner}
\address{School of Mathematical Sciences,
Monash University, Monash, VIC 3800, Australia}
\email{fima.klebaner@monash.edu}

\date{}

\begin{abstract}
Many populations, e.g. of cells, bacteria, viruses, or replicating DNA
molecules, but also of species invading a habitat, or physical systems
of elements generating new elements, start small, from a few lndividuals,
and grow large into a noticeable fraction of the environmental
carrying capacity $K$ or some corresponding regulating or system scale
unit.  Typically, the elements of the initiating, sparse set will not be
hampering each other  and their number will grow from $Z_0=z_0$  in a branching process or Malthusian like, roughly exponential
fashion, $Z_t \sim a^tW$, where $Z_t$ is the size at discrete time $t\to\infty$,
$a>1$ is the offspring mean per individual (at the low starting
density of elements, and large $K$), and $W$
a sum of $z_0$ i.i.d. random variables. It will, thus, become
detectable (i.e. of the same order as $K$) only after around  $\log K$
generations, when its density $X_t:=Z_t/K$ will tend to be strictly
positive. Typically,  this entity will be random, even if the very beginning
was not at all stochastic, as indicated by lower case $z_0$, due to
variations during the early development. However, from that time onwards,
law of large numbers effects will render the process deterministic, though
inititiated by the random density at time log $K$, expressed through the
variable $W$. Thus, $W$ acts both as a random veil concealing the start and
a stochastic initial value for later, deterministic population density development.

We make such arguments precise, studying general
density and also system-size dependent, processes, as
$K\to\infty$. As an intrinsic size parameter,  $K$  may also
be chosen to be the time unit. The fundamental ideas are to
couple the initial system
to a branching process and to show that late densities develop very much like
iterates of a conditional expectation operator.

The ``random veil'', hiding the start,  was first observed in the very
concrete special case of finding the initial copy number in
quantitative PCR under Michaelis-Menten enzyme kinetics, where the
initial individual replication variance is nil if and only if the
efficiency is one, i.e. all molecules replicate
\cite{JagKlePCR}.

\end{abstract}

\maketitle

\section{Introduction: Replication with interaction and dependence}

We consider sets of elements where, in principle, each element may
generate new elements. For lucidity we regard time as discrete,
labeling it by $n=0,1,2,\ldots$, referring to it also as generations,
cycles or rounds, and call the system a 'population' of 'individuals',
even though we have quite general such structures in mind. This is
like in branching processes but without independence between
individuals required.
Here, we assume that the individual
offspring generation (reproduction, replication or whatever) may be
influenced by a system 'carrying capacity', $K$, which we think of as
large, as compared to the population starting number $Z_0$, and also
by the number of other individuals present. We say that replication is
capacity and population size, or 'density' dependent.

The process definition is patterned after the recursive scheme used to
build up Galton-Watson processes: Let
$$ \xi_{n,j}, n\in\N,j\in\N,$$
be non-negative integer-valued random variables, where we think of
$\xi_{n,1}, \xi_{n,2}, \ldots$ as the possible offspring numbers of
various individuals in the $n-1$:th generation. Thus, we define
$\{Z_n, n=0,1,2,\ldots \}$, by the initial number  $Z_0$ and
\begin{equation}
\label{Zn}
Z_n =   \sum_{j=1}^{Z_{n-1}}  \xi_{n,j}.
\end{equation}
The dependence structure is made precise in a basic assumption:

Assumption A0. For each fixed $n\in \N$, the $\xi_{n,j}, j=1,2, \dots$,
are {\it conditionally} independently and identically
distributed, given the preceding, $\F_{n-1} := \sigma(\{\xi_{k,j}, k<n,
j\in\N\})$. The process is Markovian in the sense that the conditional
distribution should be determined by the couple $K$ and
$X_{n-1}=Z_{n-1}/K$, the {\em carrying capacity} and {\em population density}, in
such a manner that the variables increase in distribution with $K$ and
decrease with $x=X_{n-1}$, the limiting distribution, as $K\to\infty$,
{\it the asymptotic reproduction},
being proper for each $x\in\Real _+$.

Three entities pertaining to the density  turn out to be crucial
for the analysis of process start and late development.

They are:
\begin{enumerate}
\item the conditional mean number of offspring per individual,
$$m^K(X_{n-1}) = \E[\xi_{n,i}|\F_{n-1}],$$
\item the corresponding variance,
$$\sigma_K^2(X_{n-1}) = {\rm Var}[\xi_{n,i}|\F_{n-1}],$$
\item and the conditional expectation of the density process,
$$f^K(x) =\E[X_n|X_{n-1}=x]=xm^K(x),$$
\end{enumerate}
where the dependence of variance and expectation operators upon $K$ is implicit.
From A0 it follows
that the $m^K$ form a non-decreasing sequence of non-increasing
functions, and hence must have a non-increasing limit, $m$. The means
and variances $m^K$ and $\sigma_K^2$ are supposed defined on all of $\Real _+$.

We formulate boundedness and smoothness criteria for these functions,
which will lead to classical Malthusian growth for $Z_n$ in an early
stage, $n \leq n_K=c\log K, 0<c<1$. Then, we make use of a law of
large numbers for branching processes with a
  threshold and density dependence,  \cite{Klethr}, and a
  large initial value, in our case  $O(K^c)$,  at round $n_K$. All
logarithms are with base $a$.

The assumptions beyond A0 are:

\begin{enumerate}[label={A\arabic*}]

\item\label{A1}  The limiting expected conditional reproduction given a population density $x$, $m(x)$ has a derivative which is uniformly continuous in a neighbourhood to the right of the origin, and $a=m(0)>1$.
As $K\to\infty$, the continuous non-increasing functions
  $m^K$ converge uniformly to a bounded differentiable function $m$,
  $0\leq m(x)-m^K(x)\leq Cx + o(x)$ for some $C>0$ and uniformly in $K$, as $x\to 0$.

\item\label{A2}   The limiting conditional expected density $f, f(x)=xm(x), x\geq 0$, is strictly increasing.

\item  As $K\to\infty$, $X_0$ converges in probability to some limit $x_0\geq 0$. In particular, if there is a fixed starting number,  $x_0= 0$.

\item\label{A4}  The conditional reproduction variance $\sigma_K^2(x)=\mathrm{Var}[\xi_{n,i}|X_{n-1} =x]$ is uniformly bounded
and, as $K\to\infty$, converges to some $\sigma^2(x)$ uniformly. The latter, hence, is also bounded.

\item\label{A5}  There is a constant $C>0$ such that uniformly for all $K$
$$
a\geq m^K(x) = m^K(0)-Cx +o(x)\quad \text{as}\ x\to 0.
$$
 Further, $0\leq a-m^K(0)= O(1/\sqrt K)$ and also $\sup_{x\ge 0}|f^K(x)-f(x)| = O(1/\sqrt K)$.
\end{enumerate}

These look like innocuous smoothness requirements, but \ref{A2} contains something more. For fixed $K$ dependence upon the density is the same as dependence on population size, and it thus seems little of a restriction to ask that the next generation should tend to increase with density. It might however be argued that there could be a density above which for example no replication is possible. This in a sense, however, would introduce a sort of further carrying capacity, besides $K$.

\section{In spite of interaction and capacity dependence,  the
  beginning looks like branching, when the carrying capacity becomes large.}

An approximating process, at low density and high carrying capacity,
$\tilde Z=\{\tilde{Z}_n\}$, is crucial in the analysis. It has the same starting
number $Z_0=z_0$ as the original process, but then it continues as a
classical Galton-Watson process,
\begin{eqnarray}\label{tilden}
\tilde Z_0 & = &z_0\\
\tilde Z_{n} & = & \sum_{j=1}^{\tilde Z_{n-1}}\eta_{n,j},
\end{eqnarray}
where the $\eta$ variables are i.i.d. with the asymptotic reproduction distribution
as $K\to\infty$ for $x=0$. Thus, $\E[\eta]=a=m(0)>1$ and
$\Var[\eta]=\sigma^2(0)<\infty$.(Lower case $z_0$ indicates an unknown but deterministic starting number.)

From classical branching process theory,  $W(z_0):=\lim_{n\to\infty}
\tilde{Z}_n/a^n$ will have the distribution of $z_0$ independent
$W$-copies, each with expectation 1 and variance
$\sigma^2(0)/(a^2-a)$. In particular,
$$ \tilde Z_{n_K}/K^c = \tilde Z_{n_K}/a^{n_K} \sim W(z_0).$$
 By approximation, this extends to:
\begin{thm} Under assumptions A0, \ref{A1}, and \ref{A5},  $Z_{n_K}/a^{n_K} \to  W(z_0)$ and
thus $X_{n_K}\sim  W(z_0)K^{c-1}$,   in probability and $L^1$, as $K\to\infty$.
\end{thm}
\begin{proof}
Construct the replication processes $Z$ and $\tilde Z$, as well as a
third process $Z^\gamma=\{Z^\gamma_n\}$, on the same probability space
by the following coupling. Let $U_{n,j}$, $n,j\in \mathbb{N}$
be independent uniformly distributed random variables on
$[0,1]$. For each $K$ and $x$ define $t^K_{-1}(x)=t_{-1}=0$ and $0\leq t^K_0(x)\leq t^K_1(x)\leq t^K_2(x)\leq\ldots$
so that $\P(t^K_{k-1}(x)< U_{n,j}\leq
t^K_{k}(x))=\P(\xi_{n,j}=k|X_{n-1}=x), k\in \mathbb{N}$. Further, let $0\leq t_0\leq t_1\leq
t_2\leq\ldots$ so that $\P(t_{k-1}< U_{n,j}\leq
t_{k})=\P(\eta_{n,j}=k), k\in \mathbb{N}$. We can then define the
reproduction random variables $\xi_{n,j}$ and population sizes  $Z_n$, $\tilde Z_n$, as well as densities $X_n$
inductively on the same probability space by,
$$\xi_{n,j} = k \Leftrightarrow t^K_{k-1}(X_{n-1})< U_{n,j}\leq
t^K_{k}(X_{n-1})\mbox{ and }\eta_{n,j} = k \Leftrightarrow t_{k-1}< U_{n,j}\leq t_{k}.$$ and, as before,  \eqref{Zn} and \eqref{tilden}, using $\xi_{n,j}$ and $\eta_{n,j}$ respectively.
 Similarly, we write
$$\xi^\gamma_{n,j}:=\sum_{k=0}^\infty k1_{(t^K_{k-1}(K^{\gamma-1}),t^K_{k}(K^{\gamma-1})]}(U_{n,j})$$ and $Z^\gamma_n$ correspondingly.

By the distributional properties of $\xi_{n,j}|X_n=x$ and $\eta_{n,j}$ (Assumption A0),
$$
t^K_k(x) = \P(\xi_{n,j}\leq k|X_n=x) \geq \P(\eta_{n,j}\leq k)=t_k
$$
and $$t^K_k(K^{\gamma -1})\geq t^K_k(X_n),$$
the latter as long as $n<\tau:=\inf\{n;X_n>K^{\gamma-1}\}$.
Hence, by induction
for the random entities realised with the help of the $U_{n,j}, \; \tilde Z_n\geq Z_n, n\in\mathbb N,$ pointwise, and $Z^\gamma_n\leq Z_n, n<\tau$. Further, $\tilde Z_n\geq Z^\gamma_n$ for all $n$. It follows that
$$0\leq\tilde Z_n-Z_n \leq \tilde Z_n - Z^{\gamma}_n 1_{\{n<\tau\}} -
Z_n1_{\{n\geq\tau\}}  \leq \tilde Z_n - Z^{\gamma}_n 1_{\{n<\tau\}}\leq \tilde
Z_n - Z^{\gamma}_n  + Z^{\gamma}_n1_{\{n\geq\tau\}}.$$

Now, in order to show
that
$$
\lim_{K\to\infty}(\tilde Z_{n_K}-Z_{n_K})K^{-c} =0,
$$
we choose  $1/2 < c<\gamma <1$.
By this and \ref{A5},
\begin{align*}
a\geq m^K(K^{\gamma-1})=\, & a - \big(a-m^K(0)\big) - \big(m^K(0)- m^K(K^{\gamma-1})\big)\geq \\
& a - aAK^{-1/2} -aBK^{\gamma -1}+ o(K^{\gamma -1})
= a\big(1 - BK^{\gamma -1}+ o(K^{\gamma -1})\big)
\end{align*}
for suitable constants $A$ and $B$.
Hence,
\begin{align*}
\E\big(\tilde Z_{n_K} - Z^\gamma_{n_K}\big) =\, &
z_0 \big(a^{n_K} - m^K(K^{\gamma  -1})^{n_K}\big) = \\
&
z_0a^{c\log K}\big(1 - (1-BK^{\gamma-1} +o(K^{\gamma-1}))^{c\log K}\big) = o(K^{c}).
\end{align*}
Thus,
$$\E[\tilde X_{n_K} - X^\gamma_{n_K}]=o(K^{c-1}).$$

For the remaining term, note that
$$\E[Z^\gamma_{n_K};\tau\leq n_K]\le \E [\tilde Z_{n_K};\tau\le n_K]
\le \Big(\E[ {\tilde Z}^2_{n_K}]\P(\tau \le n_K)\Big)^{1/2},$$
by the Cauchy-Schwartz inequality.
Since $Z_n\le \tilde Z_n$ for all $n$, it takes longer for the former
process to reach $K^\gamma$  than for the latter, so that
$$\tau\ge \nu :=\inf\{n:\tilde Z_n>K^\gamma\}$$
and
\begin{align*}
\P (\tau\le n_K)\le\, & \P \big(\nu \le n_K\big)
=  \P \big(\sup_{n \le n_K}\tilde Z_n>K^\gamma\big)= \\
&
\P \big(a^{-n_K}\sup_{n\le n_K}\tilde Z_n>K^\gamma a^{-n_K}\big)\le \\
& \P \big(\sup_{n \le n_K}\tilde Z_na^{-n}>K^{\gamma -c}\big)\le K^{c-\gamma},
\end{align*}
where the last bound is Doob's inequality for the martingale $\{\tilde Z_na^{-n}\}$. Since
$\E[\tilde Z^2_{n_K}] =  O(K^{2c})$, by the formula for expectation and
variance of Galton-Watson processes,
$$
\lim_{K\to\infty} K^{-c}\E [\tilde Z_{n_K}; \nu\le  n_K]=0.
$$
Recalling  that $\gamma > c$, we conclude that
\begin{equation}
\lim_{K\to\infty}(\tilde Z_{n_K}-Z_{n_K})K^{-c} =0.
\end{equation}
holds in $L^1$, and hence in probability.
For the corresponding densities, division by $K$ yields
$$
\lim_{K\to\infty}(\tilde X_{n_K}-X_{n_K})K^{1-c} =0.
$$

 \end{proof}

\section{The branching like stage forms a random initial condition for later development.}

If the process does not die out, it will thus grow
exponentially in n, at least as long as it does not approach $K$ and
for fixed $K$ this holds for some $n_K=c\log K$ generations.
Then,  law of large numbers type effects should stabilise the subsequent
growth.We proceed to this, giving first a result on densities for
fixed time, $K\to\infty$, and $K$-dependent but stabilising starting density:

\begin{thm}\label{Fima} Under the assumptions stated,
for any time $n$,
$$\lim_{K\to\infty}X_n= x_n,$$ in probability, where $x_n$ is the
$n$:th iterate of $f$, $x_{n}=f_n(x_0)$. If $X_0\to x_0$ holds in $L^1$,
the conclusion can actually be strengthened to mean square
convergence.
\end{thm}
For a proof (under somewhat weaker conditions), see Theorem 1 of \cite{Klethr}.

Now, in our framework the second, ``post-branching'', stage starts
at time $n_K$ from $W(z_0)a^{n_K} =W(z_0)K^c$ individuals. Hence, the
starting density, $W(z_0)K^{c-1}\to x_0=0$. But this is a fixed point
of $f$, and so Theorem \ref{Fima} just yields convergence to zero. The
remedy is to consider ever later time points.

\begin{lem} If $f$ increases strictly but $m$ decreases and $a=m(0)>1$
(Assumptions A0, \ref{A1}, and \ref{A2}),then
$$
h(x)=\lim_{n\to\infty}f_n(x/a^n).
$$
is well defined, continuous, and strictly increasing.The convergence
is uniform and $h(0)=0$.
\end{lem}

\begin{proof}
Since $f$ is increasing,  so are all $f_n$. By definition,
 $$f(x/a)=m(x/a)x/a\leq m(0)x/a=x,$$
for $x \geq 0$.
Hence,
 $$f_{n+1}(x/a^{n+1})=f_n(f(x/a^{n+1}))\leq f_n( x/a^{n}).$$
The sequence $h_n(x) := f_n(x/a^n)$ thus decreases in $n$ for any positive
$x$, and its limit  $h$, as $n\to\infty$, must exist and be a non-decreasing function, like the $f_n$. By Dini's theorem, the
convergence is uniform on any compact interval. Clearly, $h(0)
=h_n(0)=f_n(0)=0$ for all $n$.

It remains to prove that the limit $h$ increases strictly. However, there exist $C>0$ and $ \epsilon >0$ such that
$$f'(x)=m(x)+xm'(x)=m(0)+m(x)-m(0)+xm'(x)\geq a-2x\sup_{0\leq u\leq x}|m'(u)|>a-Cx>0,$$
for $0<x<\epsilon$.

For any $x<\min(\epsilon,1/C)$,
\begin{align*}
h_n'(x)  =& a^{-n} f'_n(x/a^n) = a^{-n}\prod_{j=0}^{n-1} f'(f_j(x/a^n)) \ge
a^{-n}\prod_{j=0}^{n-1} \big(a- Cf_j(x/a^n)\big) \ge\\
&
a^{-n}\prod_{j=0}^{n-1} \big(a- Cx a^{j-n}\big)
\ge \prod_{j=0}^{n-1} \big(1-  a^{-j}\big)\ge e^{-a}, \quad \forall \, n\ge 0.
\end{align*}
Taking the limit $n\to\infty$, we see that $h$ increases strictly  in an open neighbourhood of the origin. However, as  $f_{n+1}(x/a^{n+1})=f(f_n((x/a)/a^{n}))$,  letting  $n\to\infty$, shows that $h$ solves Schr\"{o}der's functional equation
$$
h(x)=f(h(x/a)).
$$
Therefore, if it were constant on an interval $[x_1,x_2]$ with $x_2>x_1$, then also $h(x_1/a^k) = h(x_2/a^k)$, for any integer $k\ge 1$, contradicting the fact that $h$ increases strictly on some neighbourhood of the origin. Thus,
$h$ must be strictly increasing on the positive half line.

\end{proof}

An immediate consequence of this will be of explicit use in the proof
of our main Theorem \ref{main} later:
\begin{cor}
\begin{equation}
\lim_{n\to\infty}f_n(x/a^n +o(a^{-n})) = h(x).
\end{equation}
\end{cor}

Now, for fixed $K$, the density process $X$ satisfies the fundamental
recursive equation (cf. \cite{Klethr})
\begin{equation}
\label{barZ}
X_n = f^K(X_{n-1})  + \frac 1{\sqrt K}\eps_{n},
\end{equation}
where
$$
\eps_n =  \frac 1{\sqrt K}\sum_{j=1}^{KX_{n-1}} (\xi_{n,j}-\E[\xi_{n,j}|\F_{n-1}])
$$
a martingale difference sequence,
 $\E[\eps_n|\F_{n-1}]=0$, with
$$
\E [\eps^2_n|\F_{n-1}] = \mathrm{Var}[\eps_n|\F_{n-1}]= \sigma_K^2(X_{n-1})  .

$$

The corresponding deterministic recursion, obtained by omitting the
martingale difference term, is
$$
x^K_n=f^K(x^K_{n-1})=f^K_n(x_0).
$$

From now on, what is needed of Assumptions A0-\ref{A5} is used freely. We take $1/2<c<1$, write $\nu_K=\log K - n_K= (1-c)\log K$,
and interpret $X$ suffices as their integral parts.
\begin{lem}
$$
X_{\log K}-f^K_{\nu_K}(X_{n_K})\xrightarrow[K\to\infty]{L^1} 0.
$$
\end{lem}
\begin{proof}
Write
$$\Delta_n = X_{n}-f^K_{n-n_K}(X_{n_K}),$$
for $n>n_K$.Then,
$$\Delta_n = f^K(X_{n-1})+\frac 1{\sqrt K}\eps_{n}-f^K\circ f^K_{n-1-n_K}(X_{n_K}).$$
Since for any $x\geq 0$, $0\leq \frac d{dx}f^{K}(x)=m^K(x)+x\frac d{dx} m^{K}(x)\leq
m^K(x)\leq a$ by assumption,
\begin{align*}
|\Delta_n|\leq &
|f^K(X_{n-1})-f^K\circ f^K_{n-1-n_K}(X_{n_K})|+|\frac 1{\sqrt K}\eps_{n}|\leq \\
& a|\Delta_{n-1}|+|\frac 1{\sqrt
  K}\eps_{n}|\leq\ldots\leq \sum_{j=0}^{n-n_K-1}a^j|\frac 1{\sqrt
  K}\eps_{n-j}|.
\end{align*}
Adding to this that, for any natural $k$,
$$\E[|\eps_k|\leq \sqrt{\E[\eps_k^2]}=
\sqrt{\E[\E[\eps_k^2|X_{k-1}]]}\leq\sup_x\sigma_K(x) < \infty,$$
by \ref{A4}, we can conclude that
$$\E[|\Delta_{\log K}|]\leq Ca^{\nu_K}\frac 1{\sqrt
  K}\sup_x\sigma_K(x)=CK^{1/2-c}\sup_x\sigma_K(x)\to 0, $$
as $K\to\infty$.

\end{proof}

\begin{lem}
$$f^K_{\nu_K}(X_{n_K})-f_{\nu_K}(X_{n_K})\to 0.$$
\end{lem}
\begin{proof}
By Assumption \ref{A5}, for any $0\le x\le 1 $ and some $C>0$,
\begin{align*}
|f^K_n(x)-f_n(x)| \leq & |f^K\circ f^K_{n-1}(x) - f\circ f^K_{n-1}(x)|
+ |f\circ f^K_{n-1}(x)-f\circ f_{n-1}(x)| \leq \\
& C/\sqrt{K} +
a|f^K_{n-1}(x) - f_{n-1}(x)|.
\end{align*}

Hence, by induction, for any $x$ and $n$
$$|f^K_n(x)-f_n(x)| \leq \frac{C}{\sqrt K}\sum_{j=0}^{n-1}a^j \leq
\frac{C}{(a-1)\sqrt K}a^n,$$
and
$$\sup_{0\le x}|f^K_{\nu_K}(x)-f_{\nu_K}(x)| =
 O( a^{\nu_K}/\sqrt K) = O(K^{1/2-c})\to 0,$$
as $K\to\infty$.
\end{proof}

After these lemmas and the corollary, the proof of the main theorm below is direct.
\begin{thm}\label{main}
Assume $Z_0=z_0$ given and all of Assumptions A0-\ref{A5} valid.   Then
$X_{\log K}$ converges in distribution
$$
X_{\log K} \xrightarrow[K\to\infty]{ D} h\circ W(z_0).
$$

\end{thm}

\begin{rem}
The limits increase strictly with $n$.
Recall that logarithms are with
base $a$.

\end{rem}

\begin{cor}
For any fixed $n$
$$
X_{\log K+n} \xrightarrow[K\to\infty]{ D} f_n\circ h\circ W(z_0),
$$
where   $f_n$ still denotes the $n$-th iterate of $f$.
This  extends to weak convergence of the sequences, regarded as random elements in
$\mathbb{R}^{\mathbb{Z}}$:
$$
\{X_{\log K+n}\}_{-\infty}^{\infty} \xrightarrow[K\to\infty]{ D}
  \{f_n\circ h\circ W((z_0)\}_{-\infty}^{\infty}.
$$
\end{cor}

\begin{proof}
This follows by induction on $n$ from the fundamental representation
\eqref{barZ}. For $n=0$ it is the statement of the main result. For
$n=1$ take limits as $K\to \infty$ in \eqref{barZ}, and note that the
stochastic term vanishes. Similarly, if it holds true for $n$, it
follows for $n+1$. Functional convergence follows from
finite dimensional convergence, {\em cf.} \cite{B}, p. 19.
\end{proof}

\begin{cor}
For any sequence $\lambda_K=o(\log K)$, $$X_{\lambda_K}
\xrightarrow[K\to\infty]{ L^1} 0.$$
\end{cor}
\begin{proof}
This is direct from
$$\E[X_{\lambda_K}]\le a^{\lambda_K-\log K}\to 0, \mbox{ as }
K\to\infty.$$
\end{proof}

This means that there is a very particulular scale, $O(\log K)$, at
which an interesting weak limit is obtained, whereas slower or faster
rates result in simpler convergences, as exhibited.

\section{Concluding remarks}

Measuring population or set size in density rather than numbers,
i.e. in capacity units, invites making the corresponding time change
into an intrinsic scale also with unit $K$,
$\bar X_t:= X_{tK} = Z_{[tK]}/K, t\ge 0$. For that process Theorem
\ref{main} yields that
 $$\bar X_0\leftarrow \bar X_{(\log K)/K} = X_{\log K}
\xrightarrow[K\to\infty]{ D} h\circ W(z_0).$$
Thus, the process in the intrinsic time scale seems to have started
from a random number of first elements, unless the variance of $W$ is
zero. Only in that case, corresponding to a completely deterministic
initial reproduction or replication process, can the the number $z_0$
of ancestors or corresponding originators be recovered behind the
random veil of history, by inversion of $h$ \cite{ChJagKle}.

As mentioned, this article was sparked by the concrete problem of
finding the number of original templates in PCR and answering
questions about single- or multicell origin of cancers. It is,
however,  tempting to suspect that similar patterns of late observed
growth with unknown, seemingly random, origin may occur in many other
contexts.

\subsection*{Acknowledgement}
Research supported by ARC Grant DP150103588.  P. Jagers was further supported by the Knut och
Alice Wallenberg Foundation and F. C. Klebaner by ARC through DP150102758.


TITLE: What is the matrix of a coordinate map?
QUESTION [0 upvotes]: The coordinate map $g_1 : V \rightarrow \mathbb R^n$ is an isomorphism. Usually this is illustrated by taking a vector $v\in V$, expressing it as a linear combination of basis vectors $v=a_1v_1 + a_2v_2 + \ldots + a_nv_n$, and then forming the coordinate vector $\begin{bmatrix}a_1&a_2&\ldots & a_n\end{bmatrix}^T$. I also learned that $\mathcal{M} : \mathcal L(V,W) \rightarrow M_{m\times n}(\mathbb R)$ is an isomorphism. Based on that, what is the matrix $A\in M_{m\times n}$ corresponding with $g_1$?
I'm wondering if it's even a sensible question. $A$ relies on bases for $V$ and $\mathbb R^n$ so my guess was to take the same basis for $V$ and use it for $\mathbb R^n$. Then the result is the identity matrix $I$.
I'm even more confused since I've seen that a matrix is supposed to stand in for a composition of transformations looking something like $g_2 \circ f \circ g_1^{-1}$ for $f : V \rightarrow W$,  $g_1$ as defined, and $g_2 : W \rightarrow \mathbb R^m$. But if $g_1$ and $g_2$ can have corresponding matrices, then those could be seen as some other composition of 3 functions, and so on forever.

REPLY [0 votes]: You haven't defined what $\mathcal{M}$ is so it doesn't make sense to say $\mathcal{M}:\mathcal{L}(V,W)\to M_{m\times n}(\Bbb{R})$ is an isomorphism. What does make sense is to say that $\mathcal{L}(V,W)\cong M_{m\times n}(\Bbb{R})$ (assuming $\dim V=n,\dim W=m$), i.e the two vector spaces are isomorphic.
For example, if you fix a basis $\beta=\{v_1,\dots, v_n\}$ for $V$, and you consider the corresponding coordinate map $g_{\beta}:V\to \Bbb{R}^n$, then you're right this is an isomorphism of $V$ onto $\Bbb{R}^n$. Also, you're perfectly correct in your second paragraph: matrix representations for $g_{\beta}$ depend on the choice of basis on the domain, $V$, and the target, $\Bbb{R}^n$. For instance, if you choose $\beta$ on the domain and $\sigma=\{e_1,\dots, e_n\}$, the 'standard' basis on the target $\Bbb{R}^n$, then indeed the matrix representation is the identity $[g_{\beta}]_{\beta}^{\sigma}=I_n$ (afterall, the definition of the linear map $g_{\beta}$ is designed to make this equation true).
If for some weird reason you decide to mess with the bases, for example, using say $\beta'=\{2v_1,v_2,\dots, v_n\}$ and $\sigma'=\{e_1,2e_2,\dots, 2e_n\}$, then
\begin{align}
[g_{\beta}]_{\beta'}^{\sigma'}&=
\begin{pmatrix}
2 & 0& 0 &\dots & 0\\
0 & \frac{1}{2}& 0 & \dots & 0\\
0 & 0 &\frac{1}{2} & \dots & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
0 & 0 & 0 & \dots & \frac{1}{2}
\end{pmatrix}.
\end{align}
So the result is no longer the identity matrix (but it is still an invertible matrix, as we expect, since $g_{\beta}$ is an isomorphism).

Regarding the triple composition, here's what's going on. Say you have a linear map $f:V\to W$, where $\dim V=n,\dim W=m$ and say you fix  bases $\beta$ for $V$ and $\gamma$ for $W$. Then, we have linear isomorphisms $g_{\beta}:V\to\Bbb{R}^n$ and $g_{\gamma}:W\to\Bbb{R}^m$. This gives a corresponding linear map $F:\Bbb{R}^n\to\Bbb{R}^m$ defined by the composition $F=g_{\gamma}\circ f\circ g_{\beta}^{-1}$. Now, the statement is that
\begin{align}
[F]_{\sigma_n}^{\sigma_m}&=[f]_{\beta}^{\gamma},
\end{align}
i.e the matrix representation of the composed map $F:\Bbb{R}^n\to\Bbb{R}^m$, with respect to the standard bases $\sigma_n,\sigma_m$ on $\Bbb{R}^n,\Bbb{R}^m$, is equal to the matrix representation of $f:V\to W$ with respect to the bases $\beta,\gamma$ on $V,W$. The above equation holds because of composition corresponds to multiplication of matrices once the correct bases are chosen:
\begin{align}
[F]_{\sigma_n}^{\sigma_m}&=[g_{\gamma}\circ f\circ g_{\beta}^{-1}]_{\sigma_n}^{\sigma_m}\\
&=[g_{\gamma}]^{\sigma_m}_{\gamma}\cdot[f]_{\beta}^{\gamma}\cdot[g_{\beta}^{-1}]_{\sigma_n}^{\beta}\\
&=I_m\cdot [f]_{\beta}^{\gamma}\cdot (I_n)^{-1}\\
&=[f]_{\beta}^{\gamma}.
\end{align}


TITLE: Resolving GR with two dropped objects
QUESTION [0 upvotes]: I'm trying to understand GR and geodesics in relation to a specific example.
Two objects, suspended at different heights so that one is over the other while both of their velocities relative to the ground are zero.  Both are released so that they enter free fall with a timing of release so both objects strike the ground at the same time.
In proxies for GR, such as two paths on a sphere which are pointing to the same location (walking to the north pole example), the rate which objects approach one another is dictated by the curvature. But in the example above, while both objects are approaching the same location, they approach it at different velocities.
For past questions I have asked about GR and geodesics I typically get an answer like "you are neglecting time and only looking at the curvature of space instead of the curvature of spacetime".  I do understand that the curvature of time matters, and for past examples, like throwing objects into the air, I have been able to understand how time becomes relevant for them. (I think anyway, maybe this example shows I don't understand it)
I'm asking for help understanding how the curvature of time is changing the approach speed, not just that the answer lies in the curvature of time.

REPLY [3 votes]: As you know already from @Dale's and my answers to your previous question
(How do geodesics explain two identical balls thrown up at the different
speeds?), all trajectories in 4-dimensional space-time with gravity
$g=10\ \text{m/s}^2$
have the same very big radius of curvature $R=\frac{c^2}{g}$.
So let's draw two trajectories of two bodies
with the same curvature radius $R$.

The bodies are released at different heights ($h_1$ and $h_2$)
with zero velocity (i.e. with horizonzal slope).
The one starting from higher level is released first,
and the one starting from lower level is released at a later time.
After some time they meet at the same point in space and time.
They need different times of flight ($T_1$ and $T_2$)
until they reach this meeting-point.
And then they have different velocities (i.e.
different slopes in $z$-$ct$ diagram).
You see, there is nothing mysterious about the fact
that they reach the same point with different slope.
Edit (in response to comment):
You need to distinguish between slope and curvature.
Of course different trajectories can have different slopes
at the same spot in space-time. Slope is a property
of a trajectory, not a property of the spot in space-time.
However, all trajectories passing through this spot in space-time
share the same 4-dimensional curvature ($1/R$).
Therefore it makes sense to say: curvature is a property
of space-time itself, instead of a property of the trajectories.


text:
\section*{Broader Impact}

\paragraph{Benefits}

Deepening the theoretical understanding of machine learning models motivates people to explore their advanced usage. For example, the universality of MLPs boosted their usage as a building block of more advanced models as a function approximator (e.g., deep reinforcement learning). In this study, we investigated the probable optimization and generalization guarantees of GNNs, especially multi-scale GNNs. We expect that this research to broaden the applicability of GNNs in both theoretical and practical situations.

\paragraph{Potential Risks and Associated Mitigations}

The theoretical understanding of GNNs could result in their misuse, either intentionally or unintentionally. For example, if a GNN is used in social networks, the contamination of biased information on the networks such as fake news could affect the prediction of GNNs, thereby resulting in the promotion of social disruption or unfair treatment to minority groups. The methods devised in the study of fairness could mitigate such misuse of GNNs.


TITLE: Are the properties assigned to quarks meaningful?
QUESTION [3 upvotes]: Suspect this may have been asked before, but can't find it. My question is: If you can never have a free quark, what sense does it make to attribute properties to them, since you can never experimentally isolate a quark to measure that property (for example its mass)?

REPLY [1 votes]: Confinement implies that there is no unique definition of the quark mass. In particular, there is no analog of the pole mass that can be used to define the mass of the electron. However, the mass is a parameter in the lagrangian, and in any regularization scheme (MSbar, lattice, etc) the quark masses are rigorously defined. Also, the relation between the quark masses in different regularization schemes can be computed in perturbation theory, so that there is a well defined strategy for comparing the masses determined using different definitions.
The masses of the quarks determine the masses of hadrons (the hadron masses are finite in the limit $m_q\to 0$, but this does not change the fact that their precise values depend om $m_q$), and can therefore be extracted from experiment. These are the values that you find quoted in the Particle Data Tables and on wikipidia.


TITLE: Semi-log re-expression to find an exponential model.
QUESTION [1 upvotes]: I'm unsure of how to approach this problem because of the 'semi-log' part, would I find the line of best fit, then log both sides on that equation until it is in exponential form?
Thanks in advance.
E. coli has the potential to double every 20 minutes. A graduate student in biology collected the following data.  A solution was inoculated with an indeterminate amount of bacteria at t    = 0, and then the number of E. coli cells per milliliter was measured at 20-minute intervals.  For the first two time periods the number of bacteria was so small that it could not be measured.

Time Periods (t): 3 | 4 | 5 | 6 | 7 | 8  | 9 | 10 | 11 | 12
Billions of cells/ml (C): | 1.34 | 2.87 | 4.25  | 7.51 | 14.65 | 25.30 | 45.96 | 84.72 | 146.52 | 269.55

Use semi-log re-expression to find an exponential model for the given data using time as the independent variable.

REPLY [0 votes]: Hint
You have data points $(t_i,y_i)$. If you plot $y$ as a function of $t$ and suspect an exponential behavior, you then plot $\log(y)$ as a function of $t$ (this is a semi-log plot). If the data look now to be linear, then this confirm the model to be $$\log(y)=a +b t$$ To come back to the classical linear curve fit, define $z=\log(y)$ and use the classical method to obtain the value of $a$ and $b$.
Using your data makes all of the above very obvious.


TITLE: How many turns can a chess game take at maximum?
QUESTION [14 upvotes]: The shortest number of moves that a game of chess can have is 2, as far as I know:

White moves pawn from f2 to f3, black moves pawn from e7 to e5
White moves pawn from g2 to g4, black moves queen from d8 to h4. Checkmate.

Which results in this situation:

There might be more games which end after 2 rounds, but as far as I know there is no game with fewer rounds / moves.
How many moves do the longest games take?
I thought I have read that the number is about 8000 moves.
A finite maximum number exists, because of the fifty-move rule and threefold repetition and I assume that players claim draw by those rules if possible.
Please link also to the source of your information!

edit:  Jacob Schlather mentioned a blogpost with this information

[...] The
  Belgrade Marathon was a contest between Ivan Nicolic and Goran Arsovic
  that lasted over 20 hours and ended in a draw after 269 moves due to
  the so-called “50 Move Rule”, [...]

Source: The Longest Possible Chess Game
So the longest game that was actually played took at least 269 moves. Later he explains how he comes to 5,870 possible chess moves.

REPLY [8 votes]: Longest game that can be played with neither player having the opportunity to claim a draw under the 50 move rule (or any other rule): 5898 moves.
Longest game that can be played under current FIDE rules without being automatically drawn: 8847.5 moves.
Explanation: Each pawn can make 6 moves on the way to promotion.  To do so without capturing each other, 8 pieces have to be sacrificed along the way (to open up the files for them to pass each other), leaving 22 pieces after all the promotions (plus the two kings).  Those 22 pieces can all be captured, but the last capture ends the game (as King vs King is an automatic draw based upon insufficient material to bring about checkmate).  Being forced to occasionally (four times) switch the side moving the pawns/making the captures (first to open up all the files for the pawn moves, and later to finish capturing all the pieces) means that four half-moves--two moves--are lost.  (Only a minor amount of cleverness is needed during the stalling moves to insure that there is no possible claim of draw due to threefold repetition of position.)
Most internet sources I have found (for instance, Sonny_E's comment on the blogpost mentioned in the question, and many sites he lists) show that this leads to the following calculation:
2 sides * (6 pawn moves to promotion * 8 pawns + 8 captures of opposing promoted pawns + 3 captures of other opposing pieces than the four that need to be captured by pawns) * 50 move rule - 4 times that the side that makes pawn moves or captures switches * (1/2 move) = 5898.
It might seem (it did to me) that the calculation should use 49.5 moves instead of 50, to avoid allowing each player to claim a draw immediately before every capture or pawn move, since 50 full moves will have passed since the last such event.  However, the 50 in this calculation includes 49.5 stalling moves, and then adds the pawn move/capture for a total of 50.
White can win on his 5898th move (having one piece left), but if he does not, Black must finally be able to claim a draw on his 5898th move: he can capture White's last piece (if possible) and force a draw base on insufficient material to mate, or his move can leave White's piece alone, letting him claim the draw based on the 50 move rule, the first time that rule could be invoked the entire game.
But the players may not want to claim draws at all, or even entertain the possibility of drawing, and so intentionally avoid making claims and risking draws.  FIDE recently added a 75 move rule (9.6b) that automatically draws a game without recent pawn move or capture regardless of either player's claiming a draw (or even being made aware of it).  Doing the same calculation with 74.5 moves in between captures/pawn moves gives 8848 moves, the longest possible chess game under current FIDE rules.  Black's 8848th move would automatically end the game based on the 75 move rule (or on the insufficient material rule, since Black could only avoid that rule by capturing White's final piece, leaving King vs King).  Hence the longest possible non-drawn game would involve White checkmating Black on his 8848th move (or either player resigning just before Black's 8848th for that matter, since it is that move that causes the draw to happen, and resignations can still be offered even if the next move would necessarily result in a draw).