TITLE: Solving this recurrence relation
QUESTION [1 upvotes]: Hi all I'm preparing for a midterm and the following appeared as a practice problem that I'm not quite sure how to solve. It asks to find a tight bound on the recurrence using induction
$$
{\rm T}\left(n\right)
={\rm T}\left(\left\lfloor{n \over 2}\right\rfloor\right)
+{\rm T}\left(\left\lfloor{n \over 4}\right\rfloor\right)
+{\rm T}\left(\left\lfloor{n \over 8}\right\rfloor\right)
+n
$$
I'm aware a similar question has been asked here before, but that thread dates back to a year or so ago and I never really understood the rationale behind the answer given (see here: Need some help with this recurrence equation). My guess is that it is in $\Theta(n)$, but I'm not sure how to get a more precise relation than that. I've tried expanding out the recurrence a bit, but I'm not seeing any obvious pattern.

REPLY [1 votes]: The solution is cleary increasing. Use the change of variables $n = 2^k$ and $T(2^k) = a_k$, so that:
$$
a_k = a_{k - 1} + a_{k - 2} + a_{k - 3} + 2^k
$$
This is the same as:
$$
a_{k + 3} = a_{k + 2} + a_{k + 1} + a_k + 8 \cdot 2^k
$$
Define $A(z) = \sum_{k \ge 0} a_k z^k$, multiply the recurrence by $z^k$ and sum over $k \ge 0$ to get, after recognizing some sums:
$$
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
  = \frac{A(z) - a_0 - a_1 z}{z^2}
      + \frac{A(z) - a_0}{z}
      + A(z) + 8 \cdot \frac{1}{1 - 2 z}
$$
Set $a_0 = a_1 = a_2 = 1$ so that:
$$
A(z) = \frac{1 - 2 z - 2^2 + 10 z^3}{(1 - 2 z) (1 - z - z^2 - z^3)}
$$
By Descarte's rules of signs, $p(z) = 1 - z - z^2 - z^3$ has at most one positive zero, and we know $p(0) = 1$ and $p(1) = -2$ (the positive root is 0.543689, but in any case it is less than 1). Considering $p(-z) = 1 + z - z^2 + z^3$, again by the same rule there are at most 2 negative zeros. But we can write:
$$
p(z) = 1 - \frac{z (z^3 - 1)}{z - 1}
$$
For negative $z$, the second term is positive, there are no negative zeros.
A simple bound on the zeros of $a_0 + \dotsb + a_n z^n$ is that they are in the circle of radius $\rho$ around the origin, where:
$$
\rho = \min\left\{ n \left\lvert \frac{a_0}{a_1} \right\rvert, \sqrt[n]{\left\lvert \frac{a_0}{a_n} \right\rvert} \right\}
$$
This gives $\rho = 1$ in our case. By Bender's theorem (Bender, "Asymptotic Methods in Enumeration", SIAM Review 16:4 (oct 1974), pp 485-515), which states that if $A(z) = \sum_{n \ge 0} a_n z^n, B(z) = \sum_{n \ge 0} b_n z^n$, with convergence radii $\alpha \ge \beta > 0$,  $C(z) = A(z) \cdot B(z) = \sum_{n \ge 0} c_n z^n$, with $\lim_{n \to \infty} \frac{b_{n - 1}}{b_n} = b$, $A(b) \ne 0$ then $c_n \sim A(b) b_n$.
Apply this with $A(z) = (1 - 2 z - 2^2 + 10 z^3) / (1 - z - z^2 - z^3)$ and $B(z) = (1 - 2 z)^{-1}$. The limit $b = 1/2$, so the theorem tells us that:
$$
a_k \sim 8 \cdot 2^k
$$
Translating back, $T(n) \sim 8 n$


text:
\section{Primitive of Hyperbolic Cosine Function}
Tags: Primitives of Hyperbolic Functions, Hyperbolic Cosine Function, Primitives involving Hyperbolic Cosine Function

\begin{theorem}
:$\displaystyle \int \cosh x \rd x = \sinh x + C$
\end{theorem}

\begin{proof}
From [[Derivative of Hyperbolic Sine]]:
:$\map {\dfrac \d {\d x} } {\sinh x} = \cosh x$
The result follows from the definition of [[Definition:Primitive (Calculus)|primitive]].
{{qed}}
\end{proof}

config: wiki


TITLE: Local fermionic symmetry and GS action
QUESTION [5 upvotes]: I have a trouble understanding an argument which I think has a simple answer but I am not getting it.
The question is that if you don't impose local fermionic symmetry the GS action has only one term and one of the equation of motion looks as $Γ\cdot p\partial_0\psi=0$, where $\psi$ is a Majorana-Weyl spinor in 10 dimensions and $Γ$ are just generalized gamma matrices.
Now $(Γ\cdot p)^2 = p^2= 0$ for the on-shell condition, but now they say that since the square is zero hence half of the eigenvalues of $Γ\cdot p$ is zero and this is where I am not getting it. If the square of a matrix is zero then how can we say that half of it's eigenvalues are zero. Since the eigenvalues of a squared matrix is square of the eigenvalues of the matrix whose square is taken, so how can we say that half of the eigenvalues are zero? May be it can happen when spinor contain complex component but here the spinor is Majorana too (thinking in some different way that how it will impose constraint on half of the component of $\psi$ but this is not working either).
(For reference, see chapter 5 of GSW Vol.1.)

REPLY [2 votes]: Let us go into a frame where the light-like vector $p$ has only $p^0$ and $p^1$ as non-zero components with equal magnitude. So the question reduces to the properties of $\Gamma^0 + \Gamma^1$ (or perhaps $\Gamma^0 - \Gamma^1$ but the argument below works the same way for that).
If we look at the explicit bootstrapping of gamma matrices from 2d via repeated Kronecker products, we see that the $\Gamma^0 + \Gamma^1$ in even dimensions $d=2k$ is $(\sigma^1 + -\mathrm{i}\sigma^2)(\otimes \sigma^3)^{k-1}$, where by $(\otimes \sigma_3)^{k-1}$ I mean that we take the Kronecker product with $\sigma_3$ $k-1$-times.
Since $\sigma^3 = \begin{pmatrix} 1 & 0 \\ 0 & -1\end{pmatrix}$, the rank of $A\otimes \sigma^3$ is twice the rank of $A$. So in particular, if the rank of $A$ is half the dimension, so is the rank of $A\otimes \sigma^3$.
Finally, $\sigma^1 + -\mathrm{i}\sigma^2 = \begin{pmatrix}0 & 0 \\ 2 & 0\end{pmatrix}$, which obviously has half-rank, and therefore so does $\Gamma^0 + \Gamma^1$ in all even dimensions. Note that that the statement "half the eigenvalues are zero" is actually wrong, since $\Gamma^0 + \Gamma^1$ is nilpotent and nilpotent operators only have zero eigenvalues. The correct statement is that the rank of the operator is half the total dimension.


TITLE: How is the antipode defined?
QUESTION [1 upvotes]: In this page they define the antipode using the diagram

I am finding it difficult to understand what is going on. In partiulcar:

What is one the naked arrow going $k \to A$?
Shouldn't the top arrow go $S \otimes A : A \otimes A \to A \otimes A$? I mean, if we start with $a \in A$, we should go: $a \mapsto \Delta(a) = \sum_a a_{(1)} \otimes a_{(2)} \mapsto \sum_a S(a_{(1)}) \otimes a_{(2)}$ and that should equal $a \mapsto u(a)$ how?

REPLY [2 votes]: Since $A$ is a $k$-algebra, the arrow $k \to A$ is the unit (sometimes written $\eta$) - the unique $k$-algebra morphism (it maps a scalar $t \in k$ to $t1 \in A$).
Since $A \otimes A$ is the coproduct (in $k$-algebras) of $A$ and $A$, the two maps $S, \operatorname{id} \colon A \to A$ define a unique map from the coproduct $A \otimes A \to A$. This is the map denoted $(S,\operatorname{id})$; it maps $a \otimes b$ to $S(a)b$.

So the statement that the square commutes is just that, if $a \in A$ and $\Delta(a) = \sum_i a_i \otimes b_i$, then
$$ \sum_i S(a_i)b_i = \epsilon(a)1, $$
as explained on the following page.


TITLE: Permutation of matrix elements
QUESTION [4 upvotes]: Let each row and each column of a $n\times n$ matrix $A$ be a permutation of $\{1,2,\ldots,n\}$ and
let $A$ be symmetric.
(a) If $n$ is odd, prove that each of $1,2,\ldots,n$ occurs on the principle diagonal of $A$.
(b) For every even number $n$, show that there exists an $A$ in which not all of $1,2,\ldots,n$
appear on the diagonal.
My knowledge of matrices is pretty basic. I have noticed similar types of questions before. What topics do I need to learn to solve these types of problems?

REPLY [5 votes]: Part (a)
If $n$ is odd, then an odd number of each element must occur.
If an element occurs in a symmetric table at an odd number of locations, then that element must occur along a diagonal an odd number of times.
If one element occurs $3$ or more times along a diagonal then another must occur zero times.
Zero is not odd.
Part (b)
Pair up the numbers $1 .. n$ any partition you like, such as $c_1 = \{1,2\}, c_2 = \{3, 4\}, \dots,  c_{n/2} = \{n-1, n\}$.
Create ${n\over 2}$ 2x2 tables $B_k = \begin{bmatrix} c_{k,1} & c_{k,2} \\ c_{k,2} & c_{k,1}\end{bmatrix}$.
Create a table $M_{i,j} = B_{(i + j - 1) \text{mod} (n/2)}$:
$$M = \begin{bmatrix}
B_1 & B_2 & B_3 & ... & B_{n/2}\\
B_2 & B_3 & B_4 & ... & B_{1}\\
B_3 & B_4 & B_5 & ... & B_{2}\\
    &     & \vdots & & \\
B_{n/2} & B_1 & B_2 & ... & B_{n/2 - 1}\\
\end{bmatrix}$$
Continuing the example for 6x6, that would be
$$\left[\begin{array} {cc|cc|cc}
1 &2 &3 &4 &5 &6 \\
2 &1 &4 &3 &6 &5 \\ \hline
3 &4 &5 &6 &1 &2 \\
4 &3 &6 &5 &1 &2 \\ \hline
5 &6 &1 &2 &3 &4 \\
6 &5 &2 &1 &4 &3 \\
\end{array}\right]$$
Uniqueness of the elements of each row and column follows from construction.

Personal pet peeve, I'm against calling all 2D tables matrices.  A table only becomes a matrix when linear algebra is involved; the same way an integer only becomes a numerator when a fraction is involved.


TITLE: Finding all inner products on $\mathbb{R}^2$ for which a given linear map is orthogonal
QUESTION [3 upvotes]: Suppose that we are dealing with the real field $\mathbb{R}$ and we define $T:\mathbb R^2\to\mathbb R^2$ by $$T(u,v):=(-v,u).$$ It is trivial to see that $\langle(u,v),T(u,v)\rangle = 0$ for all $u, v \in \mathbb{R}$, where $\langle \, \cdot \, , \, \cdot \, \rangle$ is the standard inner product.
A question in Hoffmann-Kunze asks us to define all possible inner products $[ \, \cdot \, , \, \cdot \, ]$ such that $[\alpha, T(\alpha)]=0$ for all $\alpha\in\mathbb R^2$ and $T$ is as above. How does one find all such inner products?

REPLY [4 votes]: An inner product is a symmetric, positive definite, bilinear form on a vector space.
Now, we can write any symmetric bilinear form $[\,\cdot\, , \,\cdot\,]$ on $\mathbb{R}^2$ as
$$[(u, v), (u', v')] = A uu' + B(uv' + u'v) + C vv'$$
($B$ is coefficient of both of the middle products precisely because the form is symmetric).
So, to determine which symmetric bilinear forms satisfy
$$[(u, v), T(u, v)] = 0, \qquad (\ast)$$ we can substitute in the above decomposition and determine conditions on $A, B, C$.

\begin{align}0&= [(u, v), T(u, v)]\\&= [(u, v), (-v, u)]\\&= -Auv + B(u^2 + v^2) + Cuv\\&= B u^2 + (-A + C) uv + B v^2.\end{align}This polynomial must vanish for all points $(u, v) \in \mathbb{R}^2$, i.e., for all $u, v$, so each of its coefficients must vanish, giving that the symmetric bilinear forms satisfying $(\ast)$ are precisely the ones for which $A = C$, $B = 0$. But the standard inner product has coefficients $A = 1$, $B = 0$, $C = 1$, so the symmetric bilinear forms satisfying $(\ast)$ are precisely the multiples of the standard inner product. Checking shows that such a bilinear form is an inner product exactly if it is a positive multiple of the standard inner product, that is, if it has the form $$[\, \cdot \, , \, \cdot \,] = \lambda^2 \langle\, \cdot \, , \, \cdot \,\rangle$$ for some constant $\lambda \in \mathbb R$.


TITLE: Conditional Permutations with allowed repeating
QUESTION [0 upvotes]: Let's say we have four elements A, B, C, and D.
How can I calculate number of all possible permutations (order matters) for set of 4, if repetitions are allowed, but it is required to have at least one B and one C element in each set?
How can I calculate similar task for same elements, same conditions, but for set of 5?

REPLY [3 votes]: The total orderings are $4^4$, since each blank has $4$ choices. Now calculate the orderings which have no $B’s$ or no C’s:
$$n(\bar B \cup \bar C) = n(\bar B) + n(\bar C) - n(\bar B \cap \bar C) \\ =3^4 + 3^4 -2^4 \\ =146
 $$
Hence, our desired answer is  $4^4 -146 =110$
You can use a similar procedure for any number of blanks.


text:
\begin{document}

\maketitle

\noindent {\bf Abstract.}
 We show that the number of  anti-lecture
hall compositions of $n$ with the first entry not exceeding $k-2$ equals the number of overpartitions of $n$
with non-overlined parts not congruent to $0,\pm 1$ modulo $k$. This identity  can be considered as a refined version of the
anti-lecture hall theorem of Corteel and Savage.
To prove this result, we find two Rogers-Ramanujan type identities for overpartition which are analogous to the Rogers-Ramanjan type identities due to Andrews.
When $k$ is odd, we give an alternative proof by using a generalized Rogers-Ramanujan identity due to Andrews, a bijection of Corteel and Savage and a refined version of a bijection also due to Corteel and Savage.

\noindent {\bf Keywords.} Anti-lecture hall composition,  Rogers-Ramanujan identity, overpartition, Durfee dissection

\noindent {\bf AMS Subject Classification.} 05A17, 11P84

\section{ Introduction}

The objective of this paper is to establish a
connection between anti-lecture hall compositions
with an upper bound on the first entry and overpartitions under a congruence condition
on non-overlined parts.

In \cite{cor02}, Corteel and Savage introduced
the notion of anti-lecture hall compositions and obtained a formula for the generating function by constructing a bijection.
An anti-lecture hall composition of length $k$ is defined to be an integer sequence $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_k)$ such that
\[\frac{\lambda_1}{1}\geq\frac{\lambda_2}{2}\geq\cdots\geq\frac{\lambda_{k-1}}{k-1}\geq\frac{\lambda_k}{k}\geq0.\]
The set of anti-lecture hall compositions of length $k$ is denoted by $A_k$.
Corteel and Savage have shown that
\begin{equation}\label{anti}
\sum_{\lambda\in A_k}q^{|\lambda|}=\prod_{i=1}^k\frac{1+q^i}{1-q^{i+1}}.
\end{equation}
Let $A$ denote
the set of anti-lecture hall compositions. Since any anti-lecture hall composition can be written as
 an infinite vector ending with zeros, we have $A= A_\infty$ and
\begin{equation}\label{anti2}
\sum_{\lambda\in A}q^{|\lambda|}=\prod_{i=1}^{\infty}\frac{1+q^i}{1-q^{i+1}}.
\end{equation}

In view of the above generating function, one sees that
anti-lecture hall compositions are related to overpartitions. An overpartition of $n$ is defined by  a non-increasing sequence of natural numbers whose sum is $n$
in which the first occurrence of a number may be overlined, see,  Corteel and Lovejoy \cite{cor04}. In the language of overpartitions, the right side of (\ref{anti2})
is the generating function for  overpartitions of $n$ with the non-overlined parts larger than $1$.

The main result of this paper is the following
refinement of the anti-lecture hall theorem of
Corteel and Savage \cite{cor02}:

\begin{thm}\label{m-thm-1} For $k\geq 3$,
\begin{equation}
 \sum_{\lambda_1\leq k-2, \lambda\in A}q^{|\lambda|}=\frac{(-q;q)_{\infty}}{(q;q)_{\infty}}
(q;q^{k})_{\infty}(q^{k-1};q^{k})_{\infty}(q^{k};q^{k})_{\infty}.
\end{equation}
\end{thm}

We shall make a connection
between  anti-lecture hall
compositions and the  overpartions with congruence restrictions.
Let $F_k(n)$ be the set of anti-lecture hall compositions  $\lambda=(\lambda_1,\lambda_2,\ldots)$ of $n$ such that
$\lambda_1 \leq k$.
Let $H_k(n)$ be the set of overparitions of $n$ for which the non-overlined parts are not
congruent to $0,\pm 1$ modulo $k$.
 Therefore, Theorem \ref{m-thm-1} can be restated
 as the following equivalent form.

  \begin{thm}\label{main}
For $k\geq 3$ and any positive integer $n$, we have
\begin{equation}
 |F_{k-2}(n)|=|H_k(n)|.
\end{equation}
\end{thm}

To prove the main result, we need to compute the
generating functions of the anti-lecture
hall compositions $\lambda$ with $\lambda_1\leq k$,
depending on the parity of $k$.
Then we shall show that these two generating functions of the anti-lecture hall compositions
 in $F_{2k-2}(n)$ and $F_{2k-3}(n)$
are equal to the generating functions of overpartitions in $H_{2k}(n)$ and $H_{2k-1}(n)$ respectively.
To this end, we  establish two Rogers-Ramanujan type identities (\ref{id1}) and (\ref{id2}) for overpartitions which are analogous to
  the following Rogers-Ramanujan type identity obtained by Andrews \cite{and74, and75}:
  \begin{equation}\label{generr}
\sum_{N_1\geq N_2 \geq \cdots \geq N_{k-1}\geq 0}
\frac{q^{N_1^2+N_2^2+\cdots+N_{k-1}^2+N_a+\cdots+N_{k-1}}}{(q)_{n_1}(q)_{n_2}\cdots(q)_{n_{k-1}}}
=\frac{(q^{a}; q^{2k+1})_{\infty}(q^{2k+1-a}; q^{2k+1})_{\infty}(q^{2k+1}; q^{2k+1})_{\infty}}{(q;q)_{\infty}}
\end{equation}
where $n_i=N_i-N_{i+1}$ and $1\leq a \leq k$. For $k=2$ and $a=1,2$, (\ref{generr}) implies the classical
Rogers-Ramanujan identities \cite{gor61}:
\begin{equation}\label{rr1}
\sum_{n=0}^{\infty}\frac{q^{n^2}}{(q)_n}=\prod_{n=0}^{\infty}(1-q^{5n+1})^{-1}(1-q^{5n+4})^{-1}
\end{equation}

\begin{equation}\label{rr2}
\sum_{n=0}^{\infty}\frac{q^{n^2+n}}{(q)_n}=\prod_{n=0}^{\infty}(1-q^{5n+2})^{-1}(1-q^{5n+3})^{-1}.
\end{equation}
It is worth mentioning that  Andrews' multiple series transformation \cite{and75} can be employed to derive the overpartition analogues of (\ref{generr}).

 When the upper bound $k$ is even, the
  weighted counting anti-lecture hall compositions leads to the left hand side
  of the first Rogers-Ramanujan type identity (\ref{id1}), whereas the generating
  function for the number of overpartitions equals the right hand side of
 the first Rogers-Ramanujan type identity (\ref{id1}). The case when $k$ is odd can be dealt with in  the same way.

When $k$ is odd, we  provide an alternative proof based on a refined version of  a bijection of Corteel and Savage
\cite{cor02}, a bijection of Corteel and Savage in the original form for the anti-lecture hall
theorem,  and a generalized Rogers-Ramanujan identity (\ref{generr}) of Andrews.

This paper is organized as follows: In Section 2, we give two Rogers-Ramanujan type identities for overpartitions.
Section 3 is concerned with the case of an even upper bound $k$. Two  proofs
for the case of an odd upper bound will be presented in Section 4.

\section{Rogers-Ramanujan type identities for overpartitions}

In this section, we  give two Rogers-Ramanujan type identities (\ref{id1}) and (\ref{id2})
for overpartitions. It can be seen that the right side of (\ref{id1}) is the generating function
for overpartitions in $H_{2k}(n)$. In the next section we shall show that the left side of (\ref{id1}) equals
the generating function for anti-lecture hall compositions in $F_{2k-2}(n)$.
Similarly, the right side of (\ref{id2}) equals the generating function for overpartitions in $H_{2k-1}(n)$. In
Section 4 we shall show that the left side of (\ref{id2}) equals the generating function for anti-lecture hall
 compositions in $F_{2k-3}(n)$.

Let us recall Andrews' multiple series transformation \cite{and75}:
\begin{align}\label{andtr}
&_{2k+4}\phi_{2k+3}
\left[{ {a,q\sqrt{a},-q\sqrt{a},b_1,c_1,b_2,c_2,\ldots,b_k,c_k,q^{-N};q,\frac{a^k q^{k+N}}{b_1\cdots b_kc_1\cdots c_k}}
 \atop  {\sqrt{a},-\sqrt{a},aq/b_1,aq/c_1,aq/b_2,aq/c_2,\ldots,aq/b_k,aq/c_k,aq^{N+1}}}\right]\nonumber\\
& =\frac{(aq)_N(aq/b_kc_k)_N}{(aq/b_k)_N(aq/c_k)_N}\sum_{m_1,\ldots, m_{k-1}\geq 0}
\frac{(aq/b_1c_1)_{m_1}(aq/b_2c_2)_{m_2}\cdots (aq/b_{k-1}c_{k-1})_{m_{k-1}}}
{(q)_{m_1}(q)_{m_2}\cdots (q)_{m_{k-1}}}\nonumber\\[3pt]
&\quad\cdot \frac{(b_2)_{m_1}(c_2)_{m_1}(b_3)_{m_1+m_2}(c_3)_{m_1+m_2}\cdots (b_k)_{m_1+\cdots+m_{k-1}}}
{(aq/b_1)_{m_1}(aq/c_1)_{m_1}(aq/b_2)_{m_1+m_2}(aq/c_2)_{m_1+m_2}\cdots (aq/b_{k-1})_{m_1+\cdots+m_{k-1}}}\nonumber\\[3pt]
&\quad\cdot \frac{(c_k)_{m_1+\cdots+m_{k-1}}}{(aq/c_{k-1})_{m_1+\cdots+m_{k-1}}}\cdot
\frac{(q^{-N})_{m_1+m_2+\cdots +m_{k-1}}}{(b_kc_kq^{-N}/a)_{m_1+m_2+\cdots +m_{k-1}}}\nonumber\\[3pt]
&\quad \cdot \frac{(aq)^{m_{k-2}+2m_{k-3}+\cdots +(k-2)m_1}q^{m_1+m_2+\cdots +m_{k-1}}}
{(b_2c_2)^{m_1}(b_3c_3)^{m_1+m_2}\cdots (b_{k-1}c_{k-1})^{m_1+m_2+\cdots +m_{k-2}}}.
\end{align}

The following summation formula
can be derived from the above  transformation formula of Andrews. It
can be considered as a Rogers-Ramanujan type
identity for overpartitions.

\begin{thm}\label{even3} For $k\geq 2$, we have
\begin{align}\label{id1}
&\sum_{N_1 \geq N_2 \geq \cdots \geq N_{k-1}\geq 0}
  \frac{q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q;q)_{N_1-N_2}\cdots (q;q)_{N_{k-2}-N_{k-1}}(q;q)_{N_{k-1}}}\nonumber\\
&\quad=\frac{(-q;q)_{\infty}(q;q^{2k})_\infty(q^{2k-1};q^{2k})_{\infty}(q^{2k};q^{2k})_\infty}{(q;q)_\infty}.
\end{align}
\end{thm}

\pf
Applying the above transformation formula of Andrews  by setting
all variables to infinity except for  $c_k$, $a$ and $q$, we get
\begin{align*}
&\sum_{ N_1 \geq \cdots\geq N_{k-1}\geq 0}
\frac{(c_k)_{N_{1}}a^{N_1+\cdots +N_{k-1}}q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-c_k)^{N_{1}}}\nonumber\\
&\quad=\frac{(aq/c_k;q)_{\infty}}{(a,q)_{\infty}} \sum_{n\geq 0} \frac{(1-aq^{2n})
(a,c_k;q)_{n}a^{kn}q^{kn^2}}{(q,aq/c_k;q)_{n}c_k^n}.
\end{align*}
Setting $a=q$ and $c_k=-q$, we find that
\begin{align}
&\sum_{ N_1 \geq \cdots\geq N_{k-1}\geq 0}
\frac{q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2+N_2+\cdots +N_{k-1}}(-q)_{N_{1}}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}}\nonumber \\
&\quad= \frac{(-q;q)_{\infty}}{(q;q)_{\infty}} \sum_{n\geq 0} (-1)^n(1-q^{2n+1})q^{kn^2+(k-1)n}. \label{a1}
\end{align}
Using Jacobi's triple product identity, we get
\begin{align}
&(q;q^{2k})_{\infty}(q^{2k-1};q^{2k})_{\infty}(q^{2k};q^{2k})_{\infty}\nonumber\\
&\quad =\sum_{n=-\infty}^{\infty}(-1)^nq^{kn^2+(k-1)n}\nonumber\\
&\quad =\sum_{n=0}^{\infty}(-1)^n(1-q^{2n+1})q^{kn^2+(k-1)n}.\label{j1}
\end{align}
In view of (\ref{a1}) and (\ref{j1}), we obtain (\ref{id1}).
 This completes the proof.
\qed

Our second Rogers-Ramanujan type identity for
overpartitions is stated as follows.

\begin{thm}\label{odd2}
For $k\geq 2$, we have
\begin{align}
&\sum_{N_1 \geq N_2 \geq \cdots \geq N_{k-1} \geq 0}
  \frac{q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q;q)_{N_1-N_2}\cdots(q;q)_{N_{k-2}-N_{k-1}} (q;q)_{N_{k-1}}(-q;q)_{N_{k-1}}}\nonumber\\
&\quad =\frac{(-q;q)_{\infty}(q;q^{2k-1})_\infty(q^{2k-2};q^{2k-1})_{\infty}(q^{2k-1};q^{2k-1})_\infty}{(q;q)_\infty}.\label{id2}
\end{align}
\end{thm}

\pf
Applying Andrews'   transformation formula by setting  all variables except for
 $c_1$, $c_k$, $a$ and  $q$  to infinity, we find \begin{align*}
&\sum_{ N_1 \geq \cdots\geq N_{k-1}\geq 0}
\frac{(c_k)_{N_{1}}a^{N_1+\cdots +N_{k-1}}q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-c_k)^{N_{1}}(aq/c_1)_{N_{k-1}}}\\
&\quad =\frac{(aq/c_k;q)_{\infty}}{(a,q)_{\infty}}
\sum_{n\geq 0}
\frac{(-1)^n(1-aq^{2n})(a,c_k;q)_{n}(c_1)_n a^{kn}q^{kn^2-(n-1)n/2}}{(q,aq/c_k;q)_{n}(aq/c_1)_n c_1^nc_k^n}.
\end{align*}
Moreover, setting $a=q$, $c_k=-q$ and  $c_1=-q$ yields
\begin{align}
&\sum_{ N_1 \geq \cdots\geq N_{k-1}\geq 0}
\frac{q^{N_2+\cdots +N_{k-1}}q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2}(-q)_{N_{1}}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-q)_{N_{k-1}}}\nonumber\\
&\quad =\frac{(-q;q)_{\infty}}{(q,q)_{\infty}}
\sum_{n\geq 0}
(-1)^n(1-q^{2n+1}) q^{kn^2+kn-n^2/2-3n/2}.\label{a2}
\end{align}
Using Jacobi's triple product identity, we have
\begin{align}
&(q;q^{2k-1})_{\infty}(q^{2k-2};q^{2k-1})_{\infty}(q^{2k-1};q^{2k-1})_{\infty}\nonumber\\
&\quad =\sum_{n=-\infty}^{\infty}(-1)^nq^{kn^2+kn-n^2/2-3n/2}\nonumber\\
&\quad = \sum_{n=0}^{\infty}(-1)^n(1-q^{2n+1})q^{kn^2+kn-n^2/2-3n/2}.\label{j2}
\end{align}
Combining (\ref{a2}) and (\ref{j2}), we deduce (\ref{id2}).
This complete the proof.
\qed

\section{The case when $k$ is even}

In this section, we shall give a proof of
Theorem \ref{main} for an even upper bound $2k-2$. More precisely,  this case can be stated as follows.

\begin{thm}\label{thmeven}For $k\geq 2$ and $n\geq 1$, we have
\begin{equation}
 |F_{2k-2}(n)|=|H_{2k}(n)|.
\end{equation}
\end{thm}

 Recall that the generating function for overpartitions in  $H_{2k}(n)$ equals
 \begin{equation}
 \sum_{n\geq 0 }|H_{2k}(n)|q^n=\frac{(-q;q)_{\infty}(q;q^{2k})_\infty(q^{2k-1};q^{2k})_{\infty}
 (q^{2k};q^{2k})_\infty}{(q;q)_\infty}.
 \end{equation}

 In view of ({\ref{id1}}),  in order to prove Theorem \ref{thmeven} we only need to show that the generating function of anti-lecture hall compositions in
 $F_{2k-2}(n)$
 equals
 the left hand side of ({\ref{id1}}), as stated below.

\begin{thm}\label{even1}
The generating function of anti-lecture hall compositions in  $F_{2k-2}(n)$ is given by
\begin{equation}
 \sum_{n=0}^{\infty}|F_{2k-2}(n)|q^n
=\sum_{N_1 \geq N_2 \geq \cdots \geq N_{k-1}\geq 0}
  \frac{q^{N_1(N_1+1)/2+N_2^2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q;q)_{N_1-N_2}\cdots (q;q)_{N_{k-2}-N_{k-1}}(q;q)_{N_{k-1}}}.
\end{equation}
\end{thm}

In order to prove Theorem \ref{even1}, we  introduce a triangular representation
$T(\lambda)=(t_{ij})_{1 \leqslant i \leqslant j}$
 of an anti-lecture hall composition $\lambda$ which is similar to a T-triangles introduced by
Bousquet-M\'{e}lou \cite{bous99}.

 It should be noted that Corteel and Savage \cite{cor02} used a representation of a composition $\lambda$ as
 a pair of vectors
$(l,r)=((l_1, l_2, \ldots),(r_1,r_2,\ldots))$, where $\lambda_i=il_i+r_i$, with $0\leq r_i\leq i-1$.
Then $l=\lfloor \lambda \rfloor=(\lfloor \lambda_1/1 \rfloor, \lfloor \lambda_2/2 \rfloor,\ldots)$.
It can be checked that a composition $\lambda$ is an anti-lecture hall composition if and only if
\begin{itemize}
\item[(1)] $l_1\geq l_2 \geq \cdots \geq 0$, and

\item[(2)] $r_{i}\geq r_{i+1}$ whenever $l_i=l_{i+1}$.
\end{itemize}

\begin{defi}
The A-triangular representation $T(\lambda)=(t_{i,j})_{1 \leqslant i \leqslant j}$
of an anti-lecture hall composition $\lambda=(\lambda_1,\lambda_2,\ldots)$ is defined to be a
triangular array $(t_{i,j})_{1 \leqslant i \leqslant j}$
of nonnegative integers satisfying the following conditions:
\begin{itemize}
\item[(1)] A diagonal entry $t_{j,j}$ in $T(\lambda)$ equals $l_j=\lfloor \lambda_{j}/j\rfloor$.

\item[(2)]  The first $r_j$ entries of the $j$-th column are equal to $t_{j,j}+1$, while
the other entries in the $j$-th column are equal to $t_{j,j}$.
\end{itemize}
\end{defi}
The sum of all entries of $T(\lambda)$ is equal to $|\lambda|=\lambda_1+\lambda_2+\cdots$. It can be verified that
 the A-triangular representation $T(\lambda)$
of an anti-lecture hall composition possesses the following properties:
\begin{itemize}
\item[(1)]  The diagonal entries of $T$ are weakly decreasing, that is,
 $t_{1,1}\geq t_{2,2} \geq \cdots \geq 0$.

\item[(2)] The entries in the $j$-th column are non-increasing, and they are equal to either the $t_{j,j}$ or $t_{j,j}+1$.

\item[(3)] If $t_{j,j}=t_{j+1,j+1}$, then $t_{i,j}\geq t_{i,j+1}$.
\end{itemize}

Conversely, a triangular
 array satisfying the above conditions must  be the A-triangular representation of an anti-lecture
hall composition.

For example, let
 $\lambda=(4,8,11,14,16,15,11,10,5,2)$. The A-triangular  representation $T(\lambda)$ of $\lambda$  is illustrated
as follows.

\begin{center}
\begin{tabular}{llllllllll}
4&4&4&4&4&3&2&2&1&1\\
&4&4&4&3&3&2&2&1&1\\
&&3&3&3&3&2&1&1&0\\
&&&3&3&2&2&1&1&0\\
&&&&3&2&1&1&1&0\\
&&&&&2&1&1&0&0\\
&&&&&&1&1&0&0\\
&&&&&&&1&0&0\\
&&&&&&&&0&0\\
&&&&&&&&&0\\
\end{tabular}
\end{center}

Now we are ready to give a proof of Theorem \ref{even1} by using the A-triangular representation of an anti-lecture hall
composition.

\noindent{\it Proof of Theorem \ref{even1}.}
Let $\lambda$ be an anti-lecture hall composition  with $\lambda_1\leq 2k-2$.  Let us consider the
 A-triangular representation $T(\lambda)$ of
 $\lambda$.
We use $N_i$ to denote the number of diagonal entries $t_{j,j}$ in $T(\lambda)$ which are greater than or
 equal to
 $2i-1$ for $1\leq i \leq k-1$. Then we have
$N_1\geq N_2 \geq \cdots \geq N_{k-1}\geq 0$. Let $F_{2k-2}(N_1, \ldots, N_{k-1}; n)$ denote
the set of anti-lecture hall compositions $\lambda$ such that there are $N_i$ diagonal entries in $T(\lambda)$
that are greater than or equal to $2i-1$ and $\lambda_1\leq 2k-2$. We aim to compute the generating function of
anti-lecture hall composition in
 $F_{2k-2}(N_1, \ldots, N_{k-1}; n)$, which can be summed up to yield
the generating function of the anti-lecture hall compositions in  $F_{2k-2}(n)$.

Let  $\lambda$ be an anti-lecture hall composition  in $F_{2k-2}(N_1, \ldots, N_{k-1}; n)$, and
let $\lambda^{(1)}=(\lambda_1,\ldots,$ $\lambda_{N_1})$, $\lambda^{(2)}=(\lambda_{N_1+1},\ldots,\lambda_l)$.
Since $\lfloor \lambda_{N_1+1}/(N_1+1)\rfloor=\cdots=\lfloor \lambda_{l}/l\rfloor=0$,   we see that
$\lambda_l\leq \cdots \leq \lambda_{N_1+1} \leq N_1$.
Evidently $\lambda^{(2)}$ is a partition  whose first part is less than $N_1+1$,
and the generating function for possible choices of $\lambda^{(2)}$ equals $1/(q;q)_{N_1}$.

 Let us examine the composition $\lambda^{(1)}$ and its A-triangular representation $T(\lambda^{(1)})$. The triangular array $T(\lambda^{(1)})$
can be split into  $k$ triangular arrays and we can  compute the
generating function for possible choices of $\lambda^{(1)}$.

\noindent
Step 1. Let $T^{(1)}=T(\lambda^{(1)})$. Extract $1$ from each entry in the first $N_1$ columns of $T^{(1)}$ to form a
triangular array of size $N_1$ with all the
entries equal to $1$, denoted by $R(N_1,1)$.

\noindent
Step 2. For $2\leq i \leq k-1$, extract $2$ from each entry in the first $N_i$ columns of the remaining
triangular array $T^{(1)}$  to
     generate a triangular array of size $N_i$ with all the entries equal to $2$, denoted by $R(N_i,2)$.

\noindent
Step 3. Let $S$ denote the remaining triangular array $T^{(1)}$.

After the above operations, $T(\lambda^{(1)})$ is decomposed  into $k$ triangular arrays, including an A-triangle $R(N_1,1)$
of size $N_1$ with  entries $1$,
$k-2$ A-triangular arrays $R(N_i,2)$ of sizes $N_2, \ldots, N_{k-1}$ respectively
 with  entries $2$ where  $i=2, \ldots, k-1$, and
a triangular array $S=(s_{i,j})_{1\leq i \leq j\leq N_1}$ of  size $N_1$. It is easy to see that the generating function
 for triangular arrays in $R(N_1,1)$ is
$q^{(N_1+1)N_1/2}$ and the generating function
of triangular arrays in $R(N_i,2)$ is $q^{N_i^2+N_i}$.

It can be verified that $S$ possesses the following properties by the definition of the A-triangular representation of an
anti-lecture hall composition:
\begin{itemize}
\item[(1)] All the entries in the diagonals of $S$ are equal  to $1$ or $0$. Note that $S$ has $N_1$ diagonal
elements
$s_{1,1}, s_{2,2}, \ldots, s_{N_1,N_1}$.
    These diagonal elements can be divided into $k-1$ segments such that  the first
     segment contains $n_1=N_1-N_2$ elements $s_{N_2+1,N_2+1},\ldots, s_{N_1,N_1}$,
the second segment contains $n_2=N_2- N_3$ elements $s_{N_3+1,N_3+1},\ldots, s_{N_2,N_2}$,
 and so on, while the last segment contains $n_{k-1}=N_{k-1}$ elements $s_{1,1},\ldots,s_{N_{k-1},N_{k-1}}$.
Moreover, the $i$-th segment contains $m_i$ 1's followed by 0's.

\item[(2)] The entries in the $j$-th column are non-increasing, and they are equal to
either the $t_{j,j}$ or $t_{j,j}+1$.

\item[(3)] If $s_{j,j}=s_{j+1,j+1}$, then $s_{i,j}\geq s_{i,j+1}$.
\end{itemize}

We denote the set of triangular arrays possessing the above three properties by $S(N_1, N_2, \ldots,$ $N_{k-1})$. Now we are in a position to compute
 the generating function of triangular arrays in $S(N_1,N_2,\ldots,N_{k-1})$.

 We may partition a triangular array $S\in S(N_1,N_2,\ldots,N_{k-1})$   into $k-1$ blocks of columns, where
  the $i$-th block consists of the
 $(N_{i+1}+1)$-th column to the $N_i$-th column of $S$. We denote the $i$-th block by $S_i$.
According to the above three properties, we deduce that the first $m_i$ diagonal entries of $S_i$ must be $1$ and the entries in the first $m_i$ columns of $S_i$
  are either $1$ or $2$.

We shall split $S_i$ into three trapezoidal arrays $S_i^{(1)}$, $S_i^{(2)}$ and $S_i^{(3)}$.
First, we may form a  trapezoidal array $S_i^{(1)}$  of the same size as $S_i$ and with the entries
in the first $m_i$ columns  equal  to $1$ and the other entries equal to 0.
     Let $S^{\,'}_i$ denote the trapezoidal  array obtained from $S_i$ by subtracting
     1 from every entry in the first $m_i$ columns. Observe that every entry in
      $S^{\,'}_i$ is either $1$ or $0$, and $S^{(1)}_i$ can be regarded as the Ferrers diagram
 of the conjugate of the partition
\[ \alpha^{(1)}=(N_{i+1}+m_i, N_{i+1}+m_i-1, \ldots, N_{i+1}+1).\]
Furthermore,   $S^{\,'}_i$ satisfies the following conditions:
\begin{itemize}
\item[(1)] All entries in $S^{\,'}_i$ are equal to $0$ or $1$, but the diagonal entries   must be $0$.

\item[(2)] The entries in the same column must be non-increasing.

\item[(3)] The first $m_i$ entries in the $j$-th row must be non-increasing,  and the remaining entries in the $j$-th
 row are also non-increasing.
\end{itemize}

We continue to consider the trapezoidal array
formed by the first $m_i$ columns of  $S^{\,'}_i$, and
denote it by $S_i^{(2)}$.
Similarly, we see that $S_i^{(2)}$ can be
 regarded
as the Ferrers diagram of the conjugate of a partition $\alpha^{(2)}$, where \[ \alpha^{(2)}_1\leq N_{i+1}, \quad \mbox{and} \quad
 l(\alpha^{(2)})\leq m_i.\]

 Define  $S_i^{(3)}$ to be the trapezoidal array
formed by the
 $(m_i+1)$-th column to the $(N_i-N_{i+1})$-th column  of $S'_i$. Again, $S^{(3)}$ can be regarded
as the Ferrers diagram of the conjugate of a partition $\alpha^{(3)}$, where
 \[ \alpha^{(3)}_1\leq N_{i+1}+m_i\quad \mbox{and} \quad
l(\alpha^{(3)})\leq N_i-N_{i+1}-m_i.\] So the generating function for  possible choices of the $i$-th block $S_i$ is given by
\begin{align}\label{si1}
\sum_{m_i=0}^{N_i-N_{i+1}}q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_{i+1}+m_i}}{(q;q)_{m_i}(q;q)_{N_{i+1}}}
\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}+m_i}(q;q)_{N_i-N_{i+1}-m_i}}.
\end{align}
which equals
\begin{align}
\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}}(q;q)_{N_i-N_{i+1}}}\sum_{m_i=0}^{N_i-N_{i+1}}
q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_i-N_{i+1}}}{(q;q)_{m_i}(q;q)_{N_i-N_{i+1}-m_i}}.
\end{align}
Observe that the sum
\[\sum_{m_i=0}^{N_i-N_{i+1}}q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_i-N_{i+1}}}{(q;q)_{m_i}(q;q)_{N_i-N_{i+1}-m_i}}\]
 is   the generating function for    partitions
with distinct parts between $N_{i+1}+1$ and $N_i$. Therefore,
\begin{align}\label{si2}
 \sum_{m_i=0}^{N_i-N_{i+1}}q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_i-N_{i+1}}}{(q;q)_{m_i}(q;q)_{N_i-N_{i+1}-m_i}}
=(-q^{N_{i+1}+1};q)_{N_i-N_{i+1}}.
\end{align}
By (\ref{si2}),  the generating function (\ref{si1}) can be simplified to
\begin{equation}
\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}}(q;q)_{N_i-N_{i+1}}}(-q^{N_{i+1}+1};q)_{N_i-N_{i+1}}.
\end{equation}
Thus the generating function for triangular arrays in $S$  can be written as
\begin{equation*}
\prod_{i=1}^{k-1}\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}}(q;q)_{N_i-N_{i+1}}}(-q^{N_{i+1}+1};q)_{N_i-N_{i+1}}
=\frac{(q)_{N_1}(-q;q)_{N_1}}{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}}.
\end{equation*}

Recall that the generating function for  possible choices of  $T(\lambda^{(2)})$ equals $1/(q;q)_{N_1}$ and
the generating functions for $R(N_1,1)$, $R(N_2,2), \ldots, R(N_{k-1},2)$ are equal to $q^{(N_1+1)N_1/2}$, $q^{N_2^2+N_2}$,$\ldots,$ $q^{N_{k-1}^2+N_{k-1}}$
respectively. We also note that
the generating function for anti-lecture hall compositions in
 $F_{2k-2}(N_1,\ldots, N_{k-1}, n)$ is  the product of the generating functions for
$T(\lambda^{(2)})$, $R(N_1,1)$, $R(N_2,2), \ldots, R(N_{k-1},2)$
and $S$, and therefore it equals
\begin{align*}
&\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}}{(q)_{N_1}}
\frac{(q)_{N_1}(-q;q)_{N_1}}{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}}\\
&\quad=
\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}}.
\end{align*}

Summing up the generating functions of anti-lecture hall compositions in
 $F_{2k-2}(N_1,\ldots, N_{k-1}, n)$, we get the generating function for anti-lecture hall compositions in  $F_{2k-2}(n)$,
\begin{equation}
\sum_{n\geq 0}|F_{2k-2}(n)|q^n
=\sum_{N_1\geq \cdots \geq N_{k-1}\geq 0}
\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}}.
\end{equation}
The proof is therefore completed.
\qed

For example, let  $\lambda=(4,8,11,14,16,15,11,10,5,2)$ and let $k=3$. Then $\lambda^{(2)}=(5,2)$, $N_1=8$, $N_2=5$,
$m_1=2$ and $m_2=1$.
The decomposition of $T(\lambda)$
is illustrated as follows:
\begin{center}
\setlength{\tabcolsep}{5.5pt}
\begin{tabular}{ccccc}
\begin{tabular}{llllllllll}
4&4&4&4&4&3&2&2&1&1                \\
&4&4&4&3&3&2&2&1&1                     \\
&&3&3&3&3&2&1&1&0           \\
&&&3&3&2&2&1&1&0            \\
&&&&3&2&1&1&1&0       \\
&&&&&2&1&1&0&0            \\
&&&&&&1&1&0&0             \\
&&&&&&&1&0&0            \\
&&&&&&&&0&0               \\
&&&&&&&&&0
\end{tabular}
&\hspace{-10pt}$\longrightarrow$
&
\hspace{-10pt}\begin{tabular}{llllllll}
         1&1&1&1&1&1&1&1                    \\
         &1&1&1&1&1&1&1             \\
         &&1&1&1&1&1&1             \\
         &&&1&1&1&1&1            \\
         &&&&1&1&1&1  \\
         &&&&&1&1&1                 \\
         &&&&&&1&1                  \\
         &&&&&&&1                 \\
         &&&&&&&                   \\
         &&&&&&                     \\
\end{tabular}
&
\hspace{-10pt}$+$
&
\hspace{-10pt}\begin{tabular}{lllll}
       2&2&2&2&2           \\
       &2&2&2&2\\
       &&2&2&2\\
       &&&2&2\\
       &&&&2\\
       &&&& \\
        &&&& \\
 &&&& \\
 &&&& \\
 &&&&
 \end{tabular}\\

 $T(\lambda)$& & $R(8,1)$ & & $R(5,2)$\\
\end{tabular}
\end{center}

\setlength{\tabcolsep}{5.5pt}

\vspace{10pt}\hspace{40pt}\begin{tabular}{cccc}
$+$
&
\begin{tabular}{lllllllll}
   &1&1&1&1&1&2&1&1                          \\
   &&1&1&1&0&2&1&1                     \\
   &&&0&0&0&2&1&0                      \\
   &&&&0&0&1&1&0                           \\
&&&&&0&1&0&0            \\
   &&&&&&1&0&0                             \\
   &&&&&&&0&0                                \\
   &&&&&&&&0                                  \\
   &&&&&&&&         \\
   &&&&&&&&
\end{tabular}
&
$+$
&
\begin{tabular}{llllllllll}
   0&0&0&0&0&0&0&0&1&1                             \\
   &0&0&0&0&0&0&0&1&1                     \\
   &&0&0&0&0&0&0&1&0                    \\
   &&&0&0&0&0&0&1&0                          \\
   &&&&0&0&0&0&1&0           \\
   &&&&&0&0&0&0&0                            \\
   &&&&&&0&0&0&0                               \\
   &&&&&&&0&0&0                                  \\
   &&&&&&&&0&0                                    \\
   &&&&&&&&&0
\end{tabular}\\

&$S$&&$T(\lambda^{(2)})$

\end{tabular}

\section{The case when $k$ is odd}

 The objective of this section is to provide two proofs of the following theorem which is
the  case of an odd upper bound $2k-3$ of Theorem \ref{main}. The first
is analogous to the proof of the even case.
The second  requires a Rogers-Ramanujan type identity of Andrews, a bijection of Corteel and Savage, and a refined version of a bijection also due to  Corteel and
Savage. The approach of the second proof does not seem to apply to the even case, namely, Theorem \ref{thmeven}.

\begin{thm}\label{thmodd}
For $k\geq 2$ and a positive integer $n$, we have
\begin{equation}
|F_{2k-3}(n)|=|H_{2k-1}(n)|.
\end{equation}
\end{thm}

The first proof relies on the following
  generating function formula for anti-lecture hall compositions in $F_{2k-3}(n)$.
  The proof of this formula is analogous to that of Theorem \ref{even1}.

\begin{thm}\label{odd1}
For $k\geq 2$,
\begin{equation}\label{gaodd}
\sum_{n=0}^{\infty}|F_{2k-3}(n)|q^n=\sum_{N_1 \geq N_2 \geq \cdots \geq N_{k-1} \geq 0}
  \frac{q^{(N_1+1)N_1/2+N_2^2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q;q)_{N_1-N_2}\cdots(q;q)_{N_{k-2}-N_{k-1}} (q;q)_{N_{k-1}}(-q;q)_{N_{k-1}}}.
\end{equation}
\end{thm}

\noindent
{\it Proof of Theorem \ref{odd1}.}
 Let $\lambda$ be an anti-lecture hall composition  with $\lambda_1\leq 2k-3$.  We consider the
 A-Triangular representation $T(\lambda)$ of
 $\lambda$.
Let $N_i$ be the number of diagonal entries $t_{jj}$ in $T(\lambda)$ which are greater than or equal to $2i-1$ for
$1\leq i \leq k-1$. Then we have
$N_1\geq N_2 \geq \cdots \geq N_{k-1}\geq 0$. Let $F_{2k-3}(N_1, \ldots, N_{k-1}; n)$ denote
the set of anti-lecture hall compositions $\lambda$ for which there are $N_i$ diagonal entries in $T(\lambda)$
that are greater than or equal to  $2i-1$ and $\lambda_1\leq 2k-3$.

Let $\lambda^{(1)}=(\lambda_1,\ldots,\lambda_{N_1})$, $\lambda^{(2)}=(\lambda_{N_1+1},\ldots,\lambda_l)$.
It is immediately verified that $\lambda^{(2)}$ is a partition  whose first part does not exceed $N_1$. Hence the
 generating function for possible choices of
$\lambda^{(2)}$ equals $1/(q;q)_{N_1}$.

Now consider $\lambda^{(1)}$ and its A-Triangular representation $T(\lambda^{(1)})$. We can split $T(\lambda^{(1)})$
into $k$ triangular arrays to  compute the
generating function for possible choices of  $\lambda^{(1)}$.

\noindent
Step 1. Let $T^{(1)}=T(\lambda^{(1)})$. Extract $1$ from each entry in the first $N_1$ columns of $T^{(1)}$ to form a
 triangular array of size $N_1$ with all
entries equal to $1$, denoted by $R(N_1,1)$.

\noindent
Step 2. For $i=2, \ldots, k-1$, extract $2$ from each entry in the first $N_i$ columns of the remaining array $T^{(1)}$  to
      form a triangular array of size $N_i$ with all entries equal to  $2$, denoted by $R(N_i,2)$.

\noindent
Step 3. Let $S$ be the remaining triangular array $T^{(1)}$.

After the above procedures, $T(\lambda^{(1)})$ is decomposed into $k$ triangular arrays, including an A-Triangle $R(N_1,1)$
of size $N_1$ with all entries being $1$,
$(k-2)$ A-Triangles $R(N_i,2)$ of sizes $N_2,\ldots, N_{k-1}$ respectively with  all entries being $2$ and
a triangular array $S=(s_{i,j})$ of size $N_1$
satisfying the following conditions:
\begin{itemize}

  \item[(1)]
All the entries in the diagonals of $S$ are equal  to $1$ or $0$. Note that $S$ has $N_1$ diagonal elements
$s_{1,1}, s_{2,2}, \ldots, s_{N_1,N_1}$.
    These diagonal elements can be divided into $k-1$ segments such that  the first
     segment contains $n_1=N_1-N_2$ elements $s_{N_2+1,N_2+1},\ldots, s_{N_1,N_1}$,
the second segment contains $n_2=N_2- N_3$ elements $s_{N_3+1,N_3+1},\ldots, s_{N_2,N_2}$,
 and so on, while the last segment contains $n_{k-1}=N_{k-1}$ elements $s_{1,1},\ldots,s_{N_{k-1},N_{k-1}}$.
Moreover, the $i$-th segment contains $m_i$ 1's followed by 0's.

\item[(2)] The entries in the $j$-th column are non-increasing, and they are equal to
either  $t_{j,j}$ or $t_{j,j}+1$.

\item[(3)] If $s_{j,j}=s_{j+1,j+1}$, then $s_{i,j}\geq s_{i,j+1}$.

\item[(4)] The entries in the first $N_{k-1}$ columns of $S$ are equal to $0$, that is, $m_{k-1}=0$.
\end{itemize}

Let us write $\overline{S}(N_1,N_2,\cdots, N_{k-1})$ for the set of triangular arrays possessing the above four properties.
We proceed to compute the generating function for the triangular arrays in $\overline{S}(N_1,N_2,\cdots$ $,N_{k-1})$.

We may partition a triangular array $S\in \overline{S}(N_1,N_2,\ldots,N_{k-1})$   into $k-1$ blocks of columns, where
  the $i$-th block consists of the
 $(N_{i+1}+1)$-th column to the $N_i$-th column of $S$. We denote the $i$-th block by $S_i$.
According to the above four properties, we infer that the first $m_i$ diagonal entries of $S_i$ must be $1$ and
the entries in the first $m_i$ columns of $S_i$
  are either $1$ or $2$ for $i=1,\ldots k-2$ and $S_{k-1}$ is a triangular array of size $N_{k-1}$ with all entries
eqaul to  $0$.

 We shall split $S_i$ into three trapezoidal arrays $S_i^{(1)}$, $S_i^{(2)}$ and $S_i^{(3)}$ for $i=1,\ldots k-2$.
First, we  may form a  trapezoidal array $S_i^{(1)}$ of the same size as $S_i$ and with the entries
in the first $m_i$ columns  equal  to $1$ and the other entries equal to 0.
     Let $S^{\,'}_i$ denote the trapezoidal  array obtained from $S_i$ by subtracting
     1 from every entry in the first $m_i$ columns. It is seen  that every entry in
      $S^{\,'}_i$ is either $1$ or $0$, and $S^{(1)}_i$ can be regarded as the Ferrers diagram
 of the conjugate of the partition
\[ \alpha^{(1)}=(N_{i+1}+m_i, N_{i+1}+m_i-1, \ldots, N_{i+1}+1).\]

Furthermore,   $S^{\,'}_i$ satisfies the following conditions for $i=1,\ldots, k-2$:
\begin{itemize}
\item[(1)] All the entries in $S^{\,'}_i$ equal $0$ or $1$, but the diagonal entries must be $0$.

\item[(2)] The entries in the $j$-th column must be non-increasing.

\item[(3)] The first $m_i$ entries in the $j$-th row must be non-increasing,  and the remaining entries in the $j$-th
 row are also non-increasing.
\end{itemize}

We continue to consider the trapezoidal array
formed by the first $m_i$ columns of  $S^{\,'}_i$, and
denote it by $S_i^{(2)}$.
Again, we see that $S_i^{(2)}$ can be
 regarded
as the Ferrers diagram of the conjugate of a partition $\alpha^{(2)}$, where \[ \alpha^{(2)}_1\leq N_{i+1}, \quad \mbox{and} \quad
 l(\alpha^{(2)})\leq m_i.\]

 Notice that there are still some columns
 to be dealt with. Define  $S_i^{(3)}$ to be the trapezoidal array
formed by the
 $(m_i+1)$-th column to the $(N_i-N_{i+1})$-th column  of $S^{\,'}_i$. Once more, $S_i^{(3)}$ can be regarded
as the Ferrers diagram of the conjugate of a partition $\alpha^{(3)}$, where
 \[ \alpha^{(3)}_1\leq N_{i+1}+m_i\quad \mbox{and} \quad
l(\alpha^{(3)})\leq N_i-N_{i+1}-m_i.\]

 As a consequence, the generating function for possible choices of the $i$-th block $S_i$ for $i=1,\ldots,k-2$ equals
\begin{align*}
\sum_{m_i=0}^{N_i-N_{i+1}}q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}\frac{(q;q)_{N_{i+1}+m_i}}{(q;q)_{m_i}(q;q)_{N_{i+1}}}
\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}+m_i}(q;q)_{N_i-N_{i+1}-m_i}}
\end{align*}
which can be rewritten as
\begin{align*}
\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}}(q;q)_{N_i-N_{i+1}}}\sum_{m_i=0}^{N_i-N_{i+1}}
q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_i-N_{i+1}}}{(q;q)_{m_i}(q;q)_{N_i-N_{i+1}-m_i}}.
\end{align*}
Evidently, the sum in the above expression
is  the generating function for  partitions
with distinct parts between $N_{i+1}+1$ and $N_i$. So we deduce that
\begin{align*}
\sum_{m_i=0}^{N_i-N_{i+1}}q^{\frac{(N_{i+1}+1+N_{i+1}+m_i)m_i}{2}}
\frac{(q;q)_{N_i-N_{i+1}}}{(q;q)_{m_i}(q;q)_{N_i-N_{i+1}-m_i}}
=(-q^{N_{i+1}+1};q)_{N_i-N_{i+1}}.
\end{align*}
Since the generating function for $S_{k-1}$ equals $1$, the generating function for possible choices of $S$ is the product of the
generating functions for $S_i$ for $i=1,\ldots,k-2$, that is,
\begin{equation*}
\prod_{i=1}^{k-2}\frac{(q;q)_{N_i}}{(q;q)_{N_{i+1}}(q;q)_{N_i-N_{i+1}}}(-q^{N_{i+1}+1};q)_{N_i-N_{i+1}}
=\frac{(q)_{N_1}(-q;q)_{N_1}}{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-q;q)_{N_{k-1}}}.
\end{equation*}

Recall that the generating function for possible choices of  $T(\lambda^{(2)})$ equals $1/(q;q)_{N_1}$ and
the generating functions
 for  $R(N_1,1)$, $R(N_2,2), \ldots, R(N_{k-1},2)$ are equal to
$q^{(N_1+1)N_1/2}$, $q^{N_2^2+N_2},\ldots$ $, q^{N_{k-1}^2+N_{k-1}}$
respectively. We also observe that
the generating function for anti-lecture hall compositions in  $F_{2k-2}(N_1,\ldots, N_{k-1}, n)$ is  the
 product of the generating functions for
$T(\lambda^{(2)})$, $R(N_1,1)$, $R(N_2,2), \ldots, R(N_{k-1},2)$
and $S$. Hence it equals
\begin{align*}
&\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}}{(q)_{N_1}}
\frac{(q)_{N_1}(-q;q)_{N_1}}{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-q;q)_{N_{k-1}}}\\
&=\quad
\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-q;q)_{N_{k-1}}}.
\end{align*}
Summing up the generating functions for anti-lecture hall compositions in $F_{2k-3}(N_1,\ldots, N_{k-1}, n)$ yields the generating function for $F_{2k-3}(n)$,
\begin{equation}
 \sum_{n\geq 0}|F_{2k-3}(n)|q^n
=\quad \sum_{N_1\geq \cdots \geq N_{k-1}\geq 0}
\frac{q^{(N_1+1)N_1/2+N^2_2+\cdots+N_{k-1}^2+N_2+\cdots+N_{k-1}}(-q;q)_{N_1}}
{(q)_{N_1-N_2}\cdots (q)_{N_{k-2}-N_{k-1}}(q)_{N_{k-1}}(-q;q)_{N_{k-1}}}.
\end{equation}
This completes the proof.
\qed

For example, the composition $\lambda=(5,10,14,17,18,20,18,15,12,3)$ can decomposed into the following triangular arrays

\begin{center}
\setlength{\tabcolsep}{4.5pt}
\begin{tabular}{cccccccc}

\hspace{-10pt}\begin{tabular}{llllllllll}
5&5&5&5&4&4&3&2&2&1   \\
&5&5&4&4&4&3&2&2&1  \\
&&4&4&4&3&3&2&2&1       \\
&&&4&3&3&3&2&1&0         \\
&&&&3&3&2&2&1&0    \\
&&&&&3&2&2&1&0   \\
&&&&&&2&2&1&0   \\
&&&&&&&1&1&0\\
&&&&&&&&1&0 \\
&&&&&&&&&0
\end{tabular}
&\hspace{-10pt}$\longrightarrow$
&
\hspace{-10pt}\begin{tabular}{lllllllll}
         1&1&1&1&1&1&1&1&1                    \\
         &1&1&1&1&1&1&1&1             \\
         &&1&1&1&1&1&1&1             \\
         &&&1&1&1&1&1&1            \\
         &&&&1&1&1&1&1  \\
         &&&&&1&1&1&1                 \\
         &&&&&&1&1&1                  \\
         &&&&&&&1&1                 \\
         &&&&&&&&1                   \\
         &&&&&&&&                     \\
\end{tabular}
&
\hspace{-10pt}$+$
&
\hspace{-10pt}\begin{tabular}{llllll}
       2&2&2&2&2&2           \\
       &2&2&2&2&2\\
       &&2&2&2&2\\
       &&&2&2&2\\
       &&&&2&2\\
       &&&&&2 \\
        &&&&& \\
 &&&& &\\
 &&&&& \\
 &&&& &
 \end{tabular}
&
\hspace{-10pt}$+$
&
\hspace{-10pt}\begin{tabular}{llllll}
       2&2           \\
       &2\\
       &\\
       &\\
       &\\
       & \\
        & \\
 &\\
 & \\
 &
 \end{tabular}\\

 $T(\lambda)$& & $R(9,1)$ & & $R(6,2)$&&$R(3,2)$\\
\end{tabular}
\end{center}

\setlength{\tabcolsep}{4.5pt}
\vspace{10pt}\hspace{50pt}\begin{tabular}{cccc}
$+$
&
\begin{tabular}{lllllllll}
  0&0&2&2&1&1&2&1&1   \\
&0&2&1&1&1&2&1&1  \\
&&1&1&1&0&2&1&1       \\
&&&1&0&0&2&1&0         \\
&&&&0&0&1&1&0    \\
&&&&&0&1&1&0   \\
&&&&&&1&1&0   \\
&&&&&&&0&0\\
&&&&&&&&0
\end{tabular}
&
$+$
&
 \begin{tabular}{llllllllll}
0&0&0&0&0&0&0&0&0&1   \\
&0&0&0&0&0&0&0&0&1  \\
&&0&0&0&0&0&0&0&1       \\
&&&0&0&0&0&0&0&0         \\
&&&&0&0&0&0&0&0    \\
&&&&&0&0&0&0&0   \\
&&&&&&0&0&0&0   \\
&&&&&&&0&0&0\\
&&&&&&&&0&0 \\
&&&&&&&&&0
\end{tabular}\\

&$S$&&$\lambda^{(2)}$

\end{tabular}

  In virtue of (\ref{id2}),   Theorem \ref{thmodd} immediately follows from Theorem \ref{odd1}, since
   the generating function for overpartitions in
 $H_{2k-1}(n)$ is given by
\begin{align}
\frac{(-q;q)_{\infty}
(q;q^{2k-1})_\infty(q^{2k-2};
q^{2k-1})_{\infty}
(q^{2k-1};q^{2k-1})_\infty}{(q;q)_\infty}.
\end{align}

We now come to the second proof of Theorem \ref{thmodd}. In their proof of anti-lecture hall theorem,
 Corteel and Savage \cite{cor02} established two
 bijections.
The first  is a bijection between
 the set $E(n)$ of  anti-lecture hall compositions $\mu$ of $n$  such that
 $\lfloor \mu_i/i \rfloor$
is even
 and  the set $P(n)$ of
partitions of $n$ with each part greater than one. The  second
bijection is between the set $A(n)$ of anti-lecture hall compositions of $n$  and the set $D \times E(n)$ of pairs $(\lambda, \mu)$ such that $|\lambda|+|\mu|=n$ and
 $\lambda\in D$, $\mu \in E$, where $D$ is the set of partitions into distinct parts.
 Then the anti-lecture hall theorem can
 follows from the correspondence between $A(n)$ and $D \times P(n)$.

 We shall present a  bijection between
a subset of $P(n)$ and a subset of  $E(n)$. Together with the second bijection of
 Corteel and Savage, we arrive at the assertion in Theorem \ref{thmodd}.

To be more specific,
 let $Q_k(n)$ be the subset of $E(n)$ consisting of  anti-lecture hall compositions $\lambda$ such that
$\lambda_1\leq k$ and let $R_k(n)$ be the subset of $P(n)$ consisting of   partitions having at most
$k-1$ successive $N\times (N+1)$ Durfee rectangles such that there is no part below the last Durfee rectangle. Then we have the following
correspondence, which can be considered as a refined version of the first bijection of Corteel and Savage.

\begin{thm}\label{odd3} There is a bijection
between the set
$R_k(n)$ and the set $Q_{2k-2}(n)$.
\end{thm}

\pf
We proceed to give a construction of the bijection $\theta$ from $R_k(n)$ to  $Q_{2k-2}(n)$.
Consider the A-triangular representation $T(\mu)$ of an anti-lecture hall composition $\mu$ of $n$  such that   $\lfloor \frac{\mu_i}{i}\rfloor$ are even for all $i$
and  $\mu_1\leq 2k-2$.  By definition,   all the diagonal entries of $T(\mu)$ are  even and $t_{1,1}\leq 2k-2$.

Now we define the map  $\theta$ from a partition $\lambda$ in $P$
 with exactly $k-1$ successive Durfee rectangles to an
anti-lecture hall composition $\mu$ of $n$.

\noindent
Step 1. We break the Ferrers diagram of $\lambda$ into $k-1$ blocks such that the $i$-th block
contains the $i$-th Durfee rectangle and the dots on the right of  the $i$-th Durfee rectangle.

\noindent
Step 2. Change the $i$-th Durfee rectangle in the $i$-th block into a triangular array with all entries being $2$,
 and the
       rest dots in the $i$-th block into entries equal to $1$. Then these $k-1$ blocks become $k-1$
A-triangles with
all the diagonal entries  equal to $0$ or $2$ where $0$'s are omitted.

\noindent
Step 3. Put  the $k-1$ A-triangles obtained in Step 2 together to form an A-triangle $T$.

The resulting A-triangle
corresponds to an anti-lecture hall composition
$\mu$ such that  $\mu_1=2k-2$ and
 $\lfloor \lambda_i/i \rfloor$ are even for all $i$.

 It is easily verified that the map $\theta$ is reversible. This completes the proof.
\qed

For example,
 let
 \[\lambda=(10,10,9,8,7,7,7,7,5,4,3)\] be a partition in $R_4(77)$. Then the corresponding anti-lecture hall
composition in $Q_6(77)$ equals \[\mu=(6,12,13,11,12,14,4,3,2).\]
 The successive Durfee rectangles of $\lambda$ are exhibited as follows.

\hspace{-30pt} \begin{tabular}{lclcl}
\begin{tabular}{ll}
 \fbox{$\begin{matrix}
 \circ &\circ &\circ &\circ &\circ &\circ &\circ\\
 \circ &\circ &\circ &\circ &\circ &\circ &\circ \\
 \circ &\circ &\circ &\circ &\circ &\circ &\circ \\
 \circ &\circ &\circ &\circ &\circ &\circ &\circ \\
 \circ &\circ &\circ &\circ &\circ &\circ &\circ  \\
 \circ &\circ &\circ &\circ &\circ &\circ &\circ
 \end{matrix}$}
&\hspace{-5pt}$\begin{matrix}
\circ  &\circ &\circ\\
\circ &\circ &\circ\\
\circ &\circ &\\
\circ &&\\
\ &&\\
\ &&\\
  \end{matrix}$
\end{tabular}
&\hspace{-5pt}$\rightarrow$
&\hspace{-5pt}\begin{tabular}{lllllllll}
2 &2 &2 &2 &2 &2&1&1&1\\
 &2 &2 &2 &2 &2&1&1&1\\
&&2 &2 &2 &2&1&1&\\
  && &2 &2 &2&1&&\\
&&&&2&2&&&\\
  &&&&&2&&&
 \end{tabular}
&\hspace{-5pt}$\rightarrow$
&
\hspace{-5pt}\begin{tabular}{lllllllll}
6 &6 &5 &3 &3 &3&1&1&1\\
 &6 &4 &3 &3 &3&1&1&1\\
&&4 &3 &2 &2&1&1&\\
  && &2 &2 &2&1&&\\
&&&&2&2&&&\\
  &&&&&2&&&
 \end{tabular}
\\
\begin{tabular}{ll}
\fbox{$\begin{matrix}
 \circ &\circ &\circ &\circ\\
 \circ &\circ &\circ &\circ\\
 \circ &\circ &\circ &\circ\\
 \end{matrix}$}
&\hspace{-5pt}$\begin{matrix}
 \circ &\circ &\circ\\
 \circ &\circ &\circ \\
 \circ  &\  &\  \\

  \end{matrix}$
 \end{tabular}
&
&\hspace{-5pt}\begin{tabular}{llllll}
2 &2 &2 &1 &1 &1\\
 &2 &2 &1 &1 &1\\
&&2 &1 & &
 \end{tabular}
& & \\
\begin{tabular}{ll}
\fbox{$\begin{matrix}
  \circ &\circ &\circ\\
 \circ &\circ &\circ \\
\end{matrix}$}
&\hspace{-5pt}$\begin{matrix}
  \circ\\
\
 \end{matrix}$
\end{tabular}
&
&\hspace{-5pt}\begin{tabular}{lll}
2 &2 &1\\
 &2 &\\

 \end{tabular}
&\
&\ \\
\\
\end{tabular}

\noindent{\it   Second Proof of  Theorem \ref{thmodd}.}
 Examining Corteel and Savage's second bijection $\gamma$ from $A$ to $D\times E$,
we see that it maps an anti-lecture hall composition of $n$ in $A$ with the first part not exceeding
$2k-1$  to a pair $(\alpha, \beta)$ in $D\times E$ such that $\beta$ is an
anti-lecture hall composition in $E$ with the first part $\beta_1$ not exceeding $2k-2$ and the sum of parts of $\alpha$ and $\beta$ equals $n$. In other words,
 $\gamma$ is a bijection between $F_{2k-1}$ and $D\times Q_{2k-2}$. Together with Theorem \ref{odd3}, we are led to a bijection between $F_{2k-1}$ and $D \times R_k$.

On the other hand, there is   a combinatorial interpretation of the left hand side of (\ref{generr}) in terms of the
 Durfee dissection of a partition, given by Andrews \cite{and79}.
 We observe that technique of Andrews easily extends to Durfee rectangle dissection of a
 partition. In this way,
 we find that the generating function of partitions in $R_k(n)$ is given by
 \begin{equation}\label{DE}
\sum_{n=0}^{\infty}|R_k(n)|q^n
=\sum_{N_1\geq N_2 \geq\ldots\geq N_{k-1}\geq 0}\frac{q^{N_1^2+\ldots+ N_{k-1}^2+N_1+\ldots +N_{k-1}}}
{(q)_{N_1-N_2}\ldots(q)_{N_{k-2}-N_{k-1}}
(q)_{N_{k-1}}}.
\end{equation}

 Setting $a=1$ in the generalization of the Rogers-Ramanujan identity (\ref{generr}) gives
 \begin{equation*}
\sum_{N_1\geq N_2 \geq \cdots \geq N_{k-1}\geq 0}
\frac{q^{N_1^2+\cdots+N_{k-1}^2+
N_1+\cdots+N_{k-1}}}{(q)_{N_1-N_2}\ldots(q)_{N_{k-2}-N_{k-1}}
(q)_{N_{k-1}}}
=\frac{(q,q^{2k},q^{2k+1};q^{2k+1})_{\infty}}
{(q;q)_{\infty}}.
\end{equation*}
Hence the generating function of partitions in  $R_k(n)$ can be expressed as follows
\begin{equation}\label{DE2}
\sum_{n=0}^{\infty}|R_k(n)|q^n
=\frac{(q,q^{2k},q^{2k+1};q^{2k+1})_{\infty}}
{(q;q)_{\infty}}.
\end{equation}
By the bijection between  $F_{2k-1}(n)$
 and $D\times R_k(n)$ we conclude that
\begin{equation}\label{F}
\sum_{n=0}^{\infty}|
F_{2k-1}(n)|q^n=\frac{(-q;q)_{\infty}(q,q^{2k},q^{2k+1};q^{2k+1})_{\infty}}{(q;q)_{\infty}}.
\end{equation}
It is easy to see that the right hand side of the above identity is the generating function of overpartitions in
 $H_{2k+1}(n)$.
This completes the proof.
\qed

 \noindent{\bf Acknowledgments.}  This work was supported by  the 973
Project, the PCSIRT Project of the Ministry of Education,  and the National Science
Foundation of China.

config: arxiv


TITLE: Measurability of product space function $\Phi : \mathbb{R}^D \times D \to \mathbb{R}$
QUESTION [0 upvotes]: Let $D$ be a (possibly uncountable) compact topological space with Borel $\sigma$-algebra $\mathcal{B}(D)$.
Let the space of functions from $D$ to $\mathbb{R}$
$$ \mathbb{R}^{D}: = \{f \mid f : D \to \mathbb{R} \} $$
be equipped by the $\sigma$-algebra $\mathcal{A}(\mathbb{R}^{D})$, which is generated by all the projection maps
$$j_{\pi} : \mathbb{R}^D \rightarrow \mathbb{R}, \quad j_\pi (f) = f(\pi)$$
for $\pi \in D$.
Now let us define a map
$$ \Phi : \mathbb{R}^D \times D \to \mathbb{R}, \quad \Phi(f,\pi) = f(\pi)  .$$
Is it true, that $\Phi$ is $(\mathcal{A}(\mathbb{R}^{D}) \otimes \mathcal{B}(D))/\mathcal{B}(\mathbb{R})$-measurable? How could I show this?

REPLY [2 votes]: It is not measurable. If it is measurable the its section $\pi \to f(\pi)$ would be a measurable map from $D$ to $\mathbb R$ for any fixed $f \in \mathbb R^{D}$.  But $f:D \to \mathbb R$ is an arbitrary function so it need not be Borel measurable.


TITLE: Exponential regression plus a constant
QUESTION [1 upvotes]: I've been looking for a convenient way to fit an expression of the form $y=a\cdot b^x + c$ to a set of points in the (x; y) plane.
The technique I'm looking for should be sufficiently "light" from a theoretical point of view (no calculus) and be feasible with "by hand calculation" at least in some easy case to show as an example (then I would use a PC).
The purpose is didactic, and my aim is to use the technique with students in Italian secondary school (which would be equivalent to first-year college in terms of mathematical competence).
The students would already know linear regression, so my first attempt was to try to linearize the model with the log function, but of course the trick doesn't work when there's a translation due to c.
Does any of you have good ideas about how to deal with that?

REPLY [1 votes]: So, you want to fit a model $$y=a \times b^x+c$$ based on $n$ data points $(x_i,y_i)$. As said, in principle, you cannot avoid nonlinear regression.
However, suppose that you assign a value to parameter $b$; so, defining $z_i=b^{x_i}$, the model reduces to $$y=a z+c$$ which is linear and the standard linear regression will provide $a(b)$, $c(b)$ and $SSQ(b)$.
So try different values of $b$ until you see a minimum of $SSQ(b)$. You can polish the solution to the level you want.


TITLE: Genetic Percentage
QUESTION [1 upvotes]: If a half-brother married a lady and then his half-sister married the ladies brother, what is the genetic percentage that the children share?
I know half-siblings share 25 percent and full siblings share 50 percent.  Aunts and uncle's share 25 percent and half-uncle and half-aunts share 12.5.  Would the children then share around 12.5 percent also?

REPLY [0 votes]: The children would have:

two parents that are brother and sister and who then share $50\%$ of genes;
two parents that are half-brother and half-sister and who then share $25\%$ of genes.

Each of the four parents shares $50\%$ of genes with his/her own children. So the two children would share
$$0.5^2 (0.5+0.25)=18.75\%$$
Therefore, they would be genetically more similar than first cousins (who have two parents that are brothers/sisters and two other uncorrelated parents, resulting in $12.5\%$ gene sharing), but less similar than uncles-aunts/nephews-nieces or other half-siblings ($25\%$ sharing).


text:
\section{Proof of PCA-SDDN Corollary with Subspace Change and Most General PCA Result} \label{sec:pca_app}

\subsection{Proof of Corollary \ref{pca_ssch}} \label{proof_pca_ssch}
\begin{proof}[Proof of Corollary \ref{pca_ssch}]
We again apply the sin theta theorem,  Lemma \ref{sintheta}, with $\bm{D} = \frac{1}{\tmaxpca}\sum_t \yt \yt{}'$.  $\Phat$ is the matrix of top $r$ eigenvectors of $\bm{D}$.  But we need to pick $\D_0$ more carefully now. Let
\[
\D_0 = \frac{1}{\alpha}  \P \left(  (\alpha-\alpha_0) \Lam +  \alpha_0 \P' \P_0  \Lam \P_0' \P \right) \P'
\]
This is a Hermitian matrix as needed by the sin theta theorem, and $\P$ is its matrix of top $r$ eigenvectors. Moreover, it is rank $r$, so that $\lambda_{r+1}(\D_0) = 0$.

Notice that
\begin{align*}
\D - \D_0 &= \cross + \cross{}' +  \noise  \\
&+ \left(\frac{1}{\alpha} \sum_t \lt \lt'  - \E[\frac{1}{\alpha} \sum_t \lt \lt'] \right) +  \left( \E[\frac{1}{\alpha} \sum_t \lt \lt'] - \D_0 \right)

\end{align*}
where $\cross, \noise$ are as defined earlier with the change that $\lt$ is now defined differently. {\em Thus, the only thing that changes when bounding these is our definition of $q$. We now let $q$ be the upper bound on
$\max(\|\Mtone \P_0\|, \|\Mtone \P\|)$.}

For our current model, we have $\sum_t \lt \lt' = \alpha_0 \P_0 \Lam \P_0' + (\alpha - \alpha_0) \P \Lam \P'$.
Since we can always express $\P_0 $ as $\P_0 = \P \P' \P_0 + \P_\perp \P_\perp{}' \P_0$, we have
\begin{align*}
&\frac{1}{\alpha} \E[\sum_t \lt \lt' ] \\
& = \D_0 + c_0 \P_\perp \P_\perp' \P_0  \Lam \P_0' \P_\perp \P_\perp{}'  + c_0 \P_\perp \P_\perp' \P_0  \Lam \P_0' \P \P' + (.)'
\end{align*}
with $c_0: = \frac{\alpha_0}{\alpha}$.

From our assumption, $\|\P_\perp \P_\perp' \P_0\| \le \Delta$, $\|\P' \P_0\| \le 1$ and $\sigma_{\min}(\P' \P_0) \ge \sqrt{1-\Delta^2}$. Thus,
\[
 \| \E\left[\frac{1}{\alpha} \sum_t \lt \lt'\right] - \D_0 \| \le c_0 \|\P_\perp' \P_0\|^2 \lambda^+ + 2 c_0 \|\P_\perp' \P_0\| \lambda^+  \le 3 c_0 \Delta  \lambda^+
\]
and
\begin{align*}
&\lambda_{r}(\D_0) \\
 & = \frac{1}{\alpha} \lambda_{\min}(  ( (\alpha-\alpha_0) \Lam + (\alpha_0) \P' \P_0  \Lam \P_0' \P ) )  \\
& \ge (1-c_0) \lambda^- + c_0 \sigma_{\min}^2(\P' \P_0) \lambda^- \ge (1-c_0) \lambda^- + c_0 (1-\Delta^2) \lambda^- = (1 - c_0 \Delta^2) \lambda^-
\end{align*}

Thus, applying  Lemma \ref{sintheta}, and using $\lambda_{r+1}(\D_0) = 0$,
\begin{align*}
&\SE(\Phat,\P)  \leq  \frac{\| \D - \D_0\|}{\lambda_{r}(\D_0) - \lambda_{r+1}(\D_0) - \| \D - \D_0\|} \\

& \leq \frac{\| \left(\frac{1}{\alpha} \sum_t \lt \lt'  - \E\left[\frac{1}{\alpha} \sum_t \lt \lt'\right] \right)\| + 3 c_0 \Delta  \lambda^+ + 2\|\cross\| + \|\noise\|}{(1 - c_0 \Delta^2) \lambda^- - \mathrm{numerator}}
\end{align*}

To bound $\|\left(\frac{1}{\alpha} \sum_t \lt \lt'  - \E\left[\frac{1}{\alpha} \sum_t \lt \lt'\right] \right)\|$, we apply matrix Bernstein, see Theorem \ref{thm:matrix_bern}, with $\Z_t = \lt \lt'$. We have
\begin{align*}
\|\Z_t\| &\le \max(\|\P_0 \at \at' \P_0\|,\|\P \at \at' \P\|) = \|\at \at'\| \\
&= \|\at\|^2 \le \mu r \lambda^+ = R.
\end{align*}
Also, $\Z_t ' \Z_t = \Z_t \Z_t'$ and
\begin{align*}
&\|\sum_t \E[\Z_t \Z_t' ]\| \\
& = \|\sum_{t=1}^{\alpha_0} \P_0 \E[ \at \at' \P_0' \P_0 \at \at'] \P_0' +   \sum_{t= \alpha_0+1}^\alpha  \P \E[ \at \at' \P' \P \at \at'] \P'\| \\
& \le \max_t\|\at\|^2 \| \sum_{t=1}^{\alpha_0} \P_0 \Lam  \P_0 +   \sum_{t= \alpha_0+1}^\alpha  \P \Lam \P' \| \\
&\le R (\alpha_0 \lambda^+ + (\alpha-\alpha_0)\lambda^+)  = R \alpha \lambda^+
\end{align*}
Thus,
\[
\max( \|\frac{1}{\alpha} \sum_t \Z_t \Z_t' \|, \|\frac{1}{\alpha} \sum_t \Z_t{}' \Z_t \|) \le R \lambda^+  = \sigma^2
\]
By matrix Bernstein with $\epsilon  \equiv \epsilon \lambda^-$,  since $\alpha \ge \frac{1}{\epsilon^2} C f^2 \mu . r \log n$, w.p. at least $1 - 2 n^{-10}$,
\[
 \|\left(\frac{1}{\alpha} \sum_t \lt \lt'  - \E\left[\frac{1}{\alpha} \sum_t \lt \lt'\right] \right)\| \le \epsilon \lambda^-
\]
Thus,
\begin{align*}
\SE(\Phat,\P) & \leq \frac{3 c_0 \Delta  \lambda^+ + \epsilon \lambda^-  + 2\|\cross\| + \|\noise\|}{(1 - c_0 \Delta^2) \lambda^- - \mathrm{numerator}} \\
& \leq \frac{3 c_0 \Delta  \lambda^+ + \epsilon \lambda^-  + 4 \sqrt{\bz}q \lambda^+ + \lambda_v^+ + \epsbnd\lambda^-}{(1 - c_0 \Delta^2) \lambda^- - \mathrm{numerator}}
\end{align*}
The last bound follows using the bounds on $\cross, \noise$ from earlier.

Thus, if $4 c_0 \Delta f < 0.2$ and the bounds from the earlier result hold, then the denominator can be shown to  be greater than $0.4$. This finishes our proof.
\end{proof}

\subsection{Most General PCA Result}
Here we state our most general result for PCA in data-dependent noise.

\begin{definition}
Let
\ben
\item Let $\Lam_t = \E[\at \at{}']$, $\Lamb = \frac{1}{\tmaxpca}\sum_t \Lam_t$, $\lambda_{\max}^+ := \max_t \|\Lam_t\|$, $\lambda^-_{\avg} = \lambda_{\min}(\Lamb)$ and let $f = \lambda_{\max}^+/\lambda^-_{\avg}$ denote the ``effective condition number'' of $\Lamb$.
\item Define the following functions of $\bm\Sigma_{v,t}$:
\begin{align*}
&\lambda_{v,\P,\avg}^-:= \lambda_{\min}(\P'\bm\Sigvb \P),\\
&\Sig_{v,t,\rest} := \Sig_{v,t} - \P\P{}'\Sig_{v,t}\P\P{}',\\
& \lambda_{v,\rest,\max}^+:= \max_t \lambda_{\max}(\Sig_{v,t,\rest}),
\end{align*}
and
\[
\lambda_{v,\P,\P_\perp,\max}:= \max_t \|\P_\perp{}'\bm\Sig_{v,t}\P\|,\ \lambda_{v,\max}^+:=\max_t \|\bm\Sigma_{v,t}\|.
\]
It is easy to see that $\lambda_{v,\P,\P_\perp,\max} \le  \lambda_{v,\rest,\max}^+$. Also, $\lambda_{v,\rest,\max}^+ \le \lambda_{v,\max}^+$,  $\lambda_{v,\P,\avg}^- \le \lambda_{v,\max}^+$.

\item The following factor (noise-to-signal ratio) of uncorrelated noise will used at various places in our results:
\[
\nois: = \frac{\lambda_{v,\max}^+}{\lambda^-_{\avg}}
\]

\item We also define ``effective dimension''  for the uncorrelated noise as
\[
r_v := \max_t \|\vp_t\|^2/\lambda_{v,\max}^+
\]
\item Define $\Sig_{w,t} = \E[\wt\wt{}']$, $\Sigwb = \frac{1}{\tmaxpca}\sum_t\Sig_{w,t}$ and $\Sig_{w,l,t} := \E[\lt\wt{}' + \wt\lt{}']$, $\Sigw = \frac{1}{\tmaxpca}\sum_t\Sig_{w,l,t}$ and $\bar{\Sig}_{w,\rest} := \Sigw - \P\P{}'\Sigw\P\P{}'$.
\item Let $\Phat$ denote the matrix of top-$r$ eigenvectors of the sample-covariance matrix, $\D = \sum_t \yt \yt{}'$.
\een

\label{def1}
\end{definition}

We have the following result.
\begin{theorem}

Given data vectors $\yt := \lt + \wt + \vp_t$ where $\wt = \M_t \lt$, and $\vp_t$ and $\lt$ are uncorrelated, i.e., $\E[\lt\vp_t{}'] = 0$. Assume that there exist constants $\bz <1$, $q < 2$, and the  matrices $\M_t$ can be decomposed as $\M_t = \M_{2,t} \M_{1,t}$  with
$\M_{1,t}$ being such that
\bea
\max_t \|\M_{1,t} \P\|_2 := q <2
\eea
and
$\M_{2,t}$ being such that $\|{\bm{M}_{2,t}}\|_2 \le 1$ and
\bea

 \left\|\frac{1}{\tmaxpca} \sum_{t =1}^\tmaxpca {\bm{M}_{2,t}} {\bm{M}_{2,t}}' \right\|_2  \le \bz
\label{M2t_bnd}
\eea
\label{Mt_cond}
Then we have
\begin{align}
\label{eq:pca_thm}
&\SE(\Phat, \P) \nn \\
&\leq \frac{\frac{\lambda_{v,\P,\P_\perp,\max}}{\lambda^-_{\avg} } + \sqrt{\bz} (q + q^2) f + \epsbnd }{1  -  \frac{\lambda_{v,\rest,\max}^+ - \lambda_{v,\P,\avg}^-}{\lambda^-_{\avg}}  - 2 \sqrt{\bz} (2q + q^2) f  - \epsbnd - \epsden}

\end{align}

where
$\epsbnd$ and $\epsden$ depends on the statistical properties of the data and noise and we have

\begin{enumerate}
\item

Assume that $\at$'s are bounded s.t. $\|\at\|_2^2 \leq \eta r \lambda^+$ for a numerical constant $\eta$. And $\vp_t$'s are zero-mean, mutually independent, bounded r.v.'s (see last item of Definition \ref{def1}), have a diagonal covariance $\Sig_v$,  and are uncorrelated with $\at$'s. Then,
\begin{align*}
\epsbnd &:= C \sqrt{\eta} \max \left( qf \sqrt{\frac{r \log n}{\tmaxpca}} , \sqrt{\nois f}  \sqrt{\frac{r_v \log n}{\tmaxpca}}\right)  \\
\epsden &:= c \eta f \sqrt{\frac{r\log n}{\tmaxpca}}
\end{align*}
as long as the denominator of \eqref{eq:pca_thm} is positive.

\item If $\at$'s are sub-Gaussian r.v.'s with sub-Gaussian norms bounded by $C \sqrt{\lambda^+}$ and similarly, $\vp_t$'s are sub-Gaussian r.v.'s with sub-Gaussian norms bounded by $C \sqrt{\lambda^+_v}$ and are uncorrelated with $\at$'s.
Then with probability at least $1 - 10 \exp(-cn)$,
\begin{align*}
\epsbnd &:= C \sqrt{\nois f} \sqrt{\frac{n}{\tmaxpca}} \\
\epsden &:= c \eta f \sqrt{\frac{r + \log n}{\alpha}}
\end{align*}
\end{enumerate}

Furthermore, when the rank is unknown, we can compute $\hat{r}$ as
\bea
\hat{r}:= \arg \min \{j: \lambda_j(\D)  \ge 0.5  \lambda^-_{\avg} \}
\label{estim_r_1}
\eea
Then, with probability at least $1 - 10n^{-10}$, $\hat{r} = r$

\label{mainthm}
\end{theorem}

\subsection{Proof}
The overall proof relies on a systematic application of the standard Davis Kahan $\sin\theta$ theorem \cite{davis_kahan} summarized here.

\begin{lem}[Davis-Kahan $\sin \theta$ theorem]\label{sintheta2}
Let $\D_0$ be a Hermitian matrix whose span of top $r$ eigenvectors equals $\Span(\P)$. Let $\D$ be the Hermitian matrix with top $r$ eigenvectors  $\Phat$. Then,
\begin{align}
\SE(\Phat,\P) &\le \frac{\|(\D-\D_0)\P\|}{\lambda_r(\D_0) - \lambda_{r+1}(\D)}   \nn \\
&\le  \frac{\|\D-\D_0\|}{\lambda_r(\D_0) - \lambda_{r+1}(\D_0) - \lambda_{\max}(\D-\D_0)}

\label{sintheta_bnd_2}
\end{align}
as long as the denominator is positive. The second inequality follows from the first using Weyl's inequality.
\end{lem}

Recall that we are provided with observations $\yt = \lt + \wt + \vp_t$. Thus, $\Sig_t = \E[\yt \yt{}'] = \P\Lam_t\P{}' + \Sig_{v,t} + \Sig_{w,t} + \Sig_{w,l,t}$ where $\Sig_{w,t} = \M_t\P \Lam_t \P{}'\M_t{}'$ and $\Sig_{w,l,t} = \P\Lam_t \P{}'\M_t{}' + \M_t \P\Lam_t \P{}'$. This follows because the matrices $\M_t$ are deterministic but unknown. Since the covariance is non-stationary, we define the time-averaged covariances as $\Lamb = \frac{1}{\tmaxpca} \sum_t \Lam_t$, $\Sigb = \frac{1}{\tmaxpca}\sum_t \Sig_t$ $\Sigvb = \frac{1}{\tmaxpca} \sum_t \Sig_v$, $\Sigwb = \frac{1}{\tmaxpca} \sum_t \Sig_w$, $\Sigw = \frac{1}{\tmaxpca}\sum_t \Sig_{w,l,t}$. Then it is easy to see that $\Sigvb = (\P \P{}' + \P_{\perp} \P_{\perp}{}') \Sigvb (\P \P{}' + \P_{\perp} \P_{\perp}{}')$. Similarly, we can obtain expressions for $\Sigwb$ and $\Sigw$. After some simple algebra, it follows that we can define $\bm{D}_0 = \P[\frac{1}{\tmaxpca}\sum_t\at\at{}' + \P{}'(\Sigvb +\Sigwb + \Sigw) \P]\P{}'$ to be a Hermitian matrix with $\Phat$ as the top $r$ eigenvectors, and $\bm{D} = \frac{1}{\tmaxpca}\sum_t \yt \yt{}'$ to be a Hermitian matrix with $\Phat$ as the top $r$ eigenvectors.

Now, we apply the $\sin\theta$ theorem
\begin{align*}
&\SE(\Phat, \P) \leq \frac{\|(\D - \D_0)\P\|}{\lambda_{r}(\bm{D}_0) - \lambda_{r+1}(\bm{D})} \\
&\leq \frac{\|(\E[\D - \D_0])\P\| + \|(\D - \D_0 - \E[\D - \D_0])\P\|}{\lambda_{r}(\bm{D}_0) - \lambda_{r+1}(\bm{D})} \\
&\leq \frac{\|\P_{\perp}\P_{\perp}{}'( \Sigvb +\Sigwb + \Sigw) \P\|+\|\D - \D_0 - \E[\D - \D_0]\|}{\lambda_{r}(\bm{D}_0) - \lambda_{r+1}(\bm{D})} \\
&:= \frac{\|\P_{\perp}\P_{\perp}{}'( \Sigvb +\Sigwb + \Sigw) \P\|+ \|T_1\|}{\lambda_{r}(\bm{D}_0) - \lambda_{r+1}(\bm{D})}
\end{align*}
using Weyl's inequality, and observing that $\P{}' (\Sigw + \Sigwb)\P$ is a positive semidefinite matrix we have that
\begin{align*}
\lambda_{r}(\D_0) &\geq \lambda_r(\Lamb) + \lambda_{\min}(\P{}' \Sigvb \P) + \lambda_{\min}(\P{}'(\Sigw +\Sigwb) \P)  \\
&+ \lambda_{\min}\left(\frac{1}{\tmaxpca}\sum_t \at\at{}'- \Lamb\right) \\
&\geq \lambda^-_{\avg} + \lambda_{v, \P, \min}^- - \norm{\frac{1}{\tmaxpca}\sum_t\at\at{}' - \Lamb}
\end{align*}
we will bound the last term using Lemma \ref{hp_bnds}.

Furthermore,
\begin{align}\label{eq:weyl_bias}
\lambda_{r+1}(\D) &\leq \lambda_{r+1}(\D_0) + \lambda_{\max}(\E[\D -\D_0]) + \|T_1\| \nn \\
&= 0 + \lambda_{\max}(\bar{\Sig}_{v,\rest} + \bar{\Sig}_{w, \rest} + \bar{\Sig}_{w,l,\rest}) + \|T_1\|  \nn \\
&\leq \lambda_{\max}(\bar{\Sig}_{v,\rest}) + \lambda_{\max}(\bar{\Sig}_{w,\rest}) + \lambda_{\max}(\bar{\Sig}_{w,\rest}) + \|T_1\| \nn \\
&\leq \lambda_{v,\rest,\max}^+ + 2\|\Sigwb\| + 2\|\Sigw\| + \|T_1\|
\end{align}
Consider the numerator term
\begin{align*}
&\|\P_{\perp}\P_{\perp}{}'( \Sigvb + \Sigwb + \Sigw) \P\|  \\
&\leq \|\P_{\perp}\P_{\perp}{}'\Sigvb\P\|  + \|\P_{\perp}\P_{\perp}{}'\Sigwb\P\| + \|\P_{\perp}\P_{\perp}{}'\Sigw\P\| \\
&\leq \lambda_{v, \P, \P_{\perp}, \max}+ \|\P_{\perp}\P_{\perp}{}'\Sigwb\P\| + \|\P_{\perp}\P_{\perp}{}'\Sigw\P\|
\end{align*}
In the last term of the r.h.s. above, notice that due to the projection matrix $\P_{\perp}\P_{\perp}{}'$, the first term of $\Sigw$ is nullified, and hence we need to consider only $\Sigwb$ and the second term of $\Sigw$. Both these terms are bounded using Cauchy-Schwartz inequality for matrices as follows. Recall that $\M_t = \M_{2,t} \M_{1,t}$ with $\|\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'\| \leq \bz$ and $\|\M_{1,t} \P\| \leq q < 2$. Thus,
\begin{align}
&\norm{\frac{1}{\tmaxpca} \sum_t \M_t \P \Lam_t \P'\M_{1,t}{}' \M_{2,t}{}'}_2^2 \nn \\
 & \le  \norm{\frac{1}{\tmaxpca} \sum_t \M_{t} \P \Lam_t \P'\M_{1,t}{}'\M_{1,t}\P \Lam_t \P'\M_{t}{}'}_2  \norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'}_2 \nn \\
& \le  \max_t \|\M_{t}\P \Lam_t \P'\M_{1,t}{}' \|_2^2  \ \bz \le  (q^2 \lambda^+_{\max})^2 \bz.

\end{align}
The cross term can be bounded in a similar fashion
\begin{align}
&\norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{1,t} \P \Lam_t \P'}_2^2 \nn \\
 & \le  \norm{\frac{1}{\tmaxpca} \sum_t \P \Lam_t \P'\M_{1,t}{}'\M_{1,t}\P \Lam_t \P'}_2  \norm{\frac{1}{\tmaxpca} \sum_t \M_{2,t} \M_{2,t}{}'}_2 \nn \\
& \le \max_t \|\M_{1,t}\P \Lam_t \P'\|_2^2 \ \bz \le  (q \lambda^+_{\max})^2 \bz.

\end{align}
From these, it is easy to see that
\begin{align*}
\|\P_{\perp} \P_{\perp}{}'\Sigw\P\| + \|\P_{\perp} \P_{\perp}{}'\Sigwb\P\| \leq q \lambda^+ (1 + q) \sqrt{\bz} \leq 3 \sqrt{\bz}q\lambda^+_{\max}
\end{align*}
Finally for the denominator,
\begin{align*}
\|\Sigwb\| + \|\Sigw\| \leq q \lambda^+_{\max} (2 + q) \sqrt{\bz} \leq 4 \sqrt{\bz}q\lambda^+_{\max}
\end{align*}

Using these bounds, we conclude that
\begin{strip}
\begin{align*}
\SE(\Phat, \P)
 &\leq \frac{\lambda_{v, \P, \P_{\perp}, \max} + 3 \sqrt{\bz}q\lambda^+_{\max} + \|T_1\|}{\lambda^-_{\avg} + \lambda_{v,\P,\avg}^- - \lambda_{v, \rest,\max}^+ - 8 \sqrt{\bz}q\lambda^+_{\max} - \norm{\frac{1}{\tmaxpca}\sum_t \at\at{}' - \Lamb} - \|T_1\|} \\
&= \frac{\frac{\lambda_{v, \P, \P_{\perp},\max} + 3 \sqrt{\bz}q\lambda^+_{\max}}{\lambda^-_{\avg} + \lambda_{v,\P,\avg}^-} + \frac{\|T_1\|}{\lambda^-_\avg}}{1 - \frac{\lambda_{v, \rest,\max}^+ + 8 \sqrt{\bz}q\lambda^+_{\max}}{\lambda^-_{\avg} + \lambda_{v,\P,\avg}^-} - \frac{\norm{\frac{1}{\tmaxpca}\sum_t \at\at{}' - \Lamb} + \|T_1\|}{\lambda^-_\avg}}\\
&\leq \frac{\frac{\lambda_{v, \P, \P_{\perp}, \max}}{\lambda^-_{\avg} + \lambda_{v, \P, \min}^-} + 3 \sqrt{\bz}qf  + \frac{\|T_1\|}{\lambda^-_\avg}}{1 - \frac{\lambda_{v, \rest,\max}^+ }{\lambda^-_{\avg} + \lambda_{v,\P,\avg}^-} - 8 \sqrt{\bz}qf - \frac{\norm{\frac{1}{\tmaxpca}\sum_t \at\at{}' - \Lamb} + \|T_1\|}{\lambda^-_\avg}}
\end{align*}
\end{strip}

To bound $\|T_1\|_2$ and $\|\frac{1}{\alpha} \sum_t \at \at' - \Lamb\|_2$, we use concentration bounds from the Lemma \ref{hp_bnds}. Notice that
\begin{strip}
\begin{align*}
T_1 &= \frac{1}{\tmaxpca}\sum_t(\vp_t \vp_t{}' - \E[\vp_t\vp_t{}'])] + \frac{1}{\tmaxpca}\sum_t(\wt \wt{}' - \E[\wt\wt{}'])] \\
&+\frac{1}{\tmaxpca}\sum_t(\lt \wt{}' - \E[\lt\wt{}'])] + \frac{1}{\tmaxpca}\sum_t(\wt \lt{}' - \E[\wt\lt{}'])] + \frac{1}{\tmaxpca}\sum_t \lt \vp_t{}' + \frac{1}{\tmaxpca}\sum_t \wt \vp_t{}'  \\

&\implies \|T_1\| \leq \norm{\frac{1}{\tmaxpca}\sum_t(\vp_t \vp_t{}' - \E[\vp_t\vp_t{}'])]} + \norm{\frac{1}{\tmaxpca}\sum_t(\wt \wt{}' - \E[\wt\wt{}'])]} \\
&+ 2\norm{\frac{1}{\tmaxpca}\sum_t(\lt \wt{}' - \E[\lt\wt{}'])]} + \norm{\frac{1}{\tmaxpca}\sum_t \lt \vp_t{}'} + \norm{\frac{1}{\tmaxpca}\sum_t \wt \vp_t{}'} \\
&\leq c\sqrt{\eta}  \nois \sqrt{\frac{r_v \log n}{\tmaxpca}} \lambda^-_{\avg} + c\sqrt{\eta} q^2  f  \sqrt{\frac{r \log n}{\tmaxpca}}   \lambda^-_{\avg} + c\sqrt{\eta} q f  \sqrt{\frac{r \log n}{\tmaxpca}}     \lambda^-_{\avg}  \\
&+ c\sqrt{\eta} \sqrt{\nois f} \sqrt{\frac{ \max(r_v, r) \log n}{\tmaxpca}} \lambda^-_{\avg}  + c\sqrt{\eta} q \sqrt{\nois f} \sqrt{\frac{ \max(r_v, r) \log n}{\tmaxpca}} \lambda^-_{\avg} \\
&\leq C \sqrt{\eta} \max \left( qf \sqrt{\frac{r \log n}{\tmaxpca}} , \sqrt{\nois f}  \sqrt{\frac{r_v \log n}{\tmaxpca}}\right)  \lambda^-_{\avg} := \epsbnd\lambda^-_{\avg}
\end{align*}
\end{strip}
where the last line follows from using $q^2 \leq 2q $, $\nois \leq f$, and $r \leq r_v$. The bound on $\|\frac{1}{\alpha} \sum_t \at \at' - \Lamb\|_2$ follows directly from the first item of Lemma \ref{hp_bnds}.

\subsubsection{Sub-Gaussian data and noise}
For the setting where the data and noise are drawn from a sub-Gaussian distribution, the only thing that changes is the bounds on ``statistical errors''. We will need the following result. Its proof follows from Lemma \cite[Theorem 4.6.1]{versh_book} with one change: since the matrix is not symmetric, we use $\|\L \V{}'\| = \max_{\bm{z}_1,\bm{z}_2} |\bm{z}_1{}'\L \V{}' \bm{z}_2|$.

\begin{lem}\label{lem:cross_subg}
Let $\bx_i$, $i=1,2,\dots,N$, and $\by_i, i=1,2,\dots, N$ be zero mean sub-Gaussian random vectors with sub-Gaussian norms bounded by $K_x$ and $K_y$ respectively. Each $\bx_i, \by_i$ is in $\Re^n$. Also $\{\bx_i, \by_i\}$, $i=1,2,\dots, N$ are mutually independent.
Then,

\begin{align*}

&\Pr\left(\norm{\frac{1}{N} \sum_i \bx_i \by_i{}' - \E \left[\frac{1}{N} \sum_i \bx_i \by_i{}'\right]} \le t \right) \\
&\geq 1 - 2 \exp \left(n \log 9 - \frac{t^2 N}{16c(K_xK_y)} \right)
\end{align*}
\end{lem}

Using the above result, we get the following bounds for the statistical errors.

\begin{lem}\label{hp_bnds_subg}
Under conditions of Theorem \ref{thm1} if the data and noise follow the sub-Gaussian model, with probability at least $1 - 2 \exp(-cn)$
\begin{align*}
&\norm{\frac{1}{\tmaxpca} \sum_t \lt \vp_t{}' }_2 \leq C \sqrt{\nois f} \sqrt{\frac{n}{\tmaxpca}} \lambda^-_{\avg}\\
&\norm{\frac{1}{\tmaxpca} \sum_t \vp_t \vp_t{}' - \frac{1}{\tmaxpca}\E\left[\sum_t \vp_t \vp_t{}'\right]}_2 \leq C \sqrt{\eta} \nois \sqrt{\frac{n}{\tmaxpca}} \lambda^-_{\avg}\\
&\norm{\frac{1}{\tmaxpca} \sum_t \wt \vp_t{}'}_2 \leq  C \sqrt{\eta} q \sqrt{\nois f}  \sqrt{\frac{n}{\tmaxpca}} \lambda^-_{\avg}
\end{align*}
\end{lem}
\begin{proof}
Consider the $\lt \vp_t{}'$ term. Apply Lemma \ref{lem:cross_subg} with $\bx_t = \lt$, $\by_t = \vp_t$,  $N \equiv \tmaxpca$.  Recall that $\E[\lt \vp_t{}'] = 0$. Furthermore, for bounded r.v.'s the sub-Gaussian norm is equal to the bound thus $K_x = c\sqrt{\lambda^+_{\max}}$ and $K_y = c\sqrt{\lambda^+_{v,\max}}$, thus $K_x K_y = c \sqrt{\lambda^+_{\max}  \lambda^+_{v, \max}}$
Set $t = \epsilon_{0, v} \lambda^-_{\avg}$ with $\epsilon_{0,v}= c \sqrt{\nois f} \sqrt{\frac{n}{\tmaxpca}}$.
Then with probability at least $1- 2\exp(-c n)$
\begin{align*}
\norm{\frac{1}{\tmaxpca} \sum_t \lt \vp_t{}'}_2 \leq c \sqrt{\nois f} \sqrt{\frac{n}{\tmaxpca}} \lambda^-_{\avg}
\end{align*}

The proof for $\vp_t\vp_t{}'$ and  $\wt\wt{}'$ follows exactly in the same way.
\end{proof}

Observe that the bounds on the other terms follow in exactly the same way.

\begin{remark}[Bias and Statistical Error]
In Theorem \ref{mainthm}, notice that \eqref{eq:pca_thm} can also be written as
\begin{strip}
\begin{align*}
\SE(\Phat, \P) \leq \frac{1}{\text{denominator}}\cdot \left(\underbrace{\frac{\lambda_{v,\P,\P_\perp,\max}}{\lambda^-_{\avg} + \lambda_{v,\P,\avg}^-} + \sqrt{\bz} (q + q^2) f}_{\cred{Bias-Error}} + \underbrace{\epsbnd}_{\cred{Stat-Error}} \right)
\end{align*}
\end{strip}
where the first term denotes the bias error. This quantifies the {\em distance} between the desired subspace, and the top-$r$ eigenvectors of the population covariance matrix. The second term is the statistical error which quantifies the {\em distance} between the top-$r$ eigenvectors of the population covariance and the sample covariance. The statistical error can be made arbitrarily small by increasing the number of samples, $\tmaxpca$ whereas the bias error is a function of the data-noise model. It is not possible to completely de-couple the two terms, due to a technical reason. Doing this will come at an additional factor of $1/\epsilon^2$ when applied to NORST.
\end{remark}

\section{Theorems we use and Proofs of Auxiliary Lemmas}\label{app:concm}

\begin{proof}[Proof of Lemma \ref{lem:sumprinang}]
The proof of upper bound follows from triangle inequality as
\begin{align*}
&\SE(\Aa, \Ca) = \norm{(\I - \Aa \Aa{}') \Ca} \\
&= \norm{(\I - \Aa \Aa{}')(\I - \Ba \Ba{}' + \Ba \Ba{}') \Ca} \\
&\leq \norm{(\I - \Aa \Aa{}')(\I - \Ba \Ba{}')\Ca} + \norm{(\I - \Aa \Aa{}') \Ba \Ba{}' \Ca} \\
&\leq \norm{(\I - \Aa \Aa{}')} \SE(\Ba, \Ca) + \SE(\Aa, \Ba) \norm{\Ba{}' \Ca} \\
&\leq \Delta_1 + \Delta_2
\end{align*}
We now obtain the lower bound
\begin{align*}
&\SE(\Aa, \Ca) = \norm{(\I - \Aa \Aa{}') \Ca} \\
&= \norm{(\I - \Aa \Aa{}' - \Ba \Ba{}' + \Ba \Ba{}') \Ca} \\
&\geq \norm{(\I - \Ba \Ba{}')\Ca} - \norm{ (\Ba \Ba{}' - \Aa \Aa{}')  \Ca} \\
&\geq \SE(\Ba, \Ca)  - \norm{\Ba \Ba{}' - \Aa \Aa{}'} \\
&\geq \SE(\Ba, \Ca) - 2 \SE(\Aa, \Ba)
\end{align*}

\end{proof}

\renewcommand{\zt}{\bm{Z}_t}

\begin{theorem}[Cauchy-Schwartz for sums of matrices \cite{rrpcp_perf}] \label{CSmat}
For matrices $\bm{X}$ and $\bm{Y}$ we have
\begin{eqnarray}\label{eq:csmat}
\norm{\frac{1}{\alpha} \sum_t \bm{X}_t \bm{Y}_{t}{}'}^2 \leq \norm{\frac{1}{\alpha} \sum_t \bm{X}_t \bm{X}_t{}'} \norm{\frac{1}{\alpha} \sum_t \bm{Y}_t \bm{Y}_t{}'}
\end{eqnarray}
\end{theorem}
The following theorem is adapted from \cite{tail_bound}.
\begin{theorem}[Matrix Bernstein \cite{tail_bound}]\label{thm:matrix_bern}
Given an $\alpha$-length sequence of $n_1 \times n_2$ dimensional random matrices and a r.v. $X$. Assume the following holds. For all $X \in \mathcal{C}$, (i) conditioned on $X$, the matrices $\Z_t$ are mutually independent, (ii) $\mathbb{P}(\norm{\Z_t} \leq R | X)  = 1$,  and (iii) $\max\left\{\norm{\frac{1}{\alpha}\sum_t \ep{\left[\Z_t{}'\Z_t | X\right]}},\ \norm{\frac{1}{\alpha}\sum_t \ep{\left[\Z_t\Z_t{}' | X\right]}}\right\} \le \sigma^2$. Then, for an $\epsilon > 0$ and for all $X \in \mathcal{C}$,
\begin{align}
\mathbb{P}\left(\norm{\frac{1}{\alpha} \sum_t \Z_t} \leq \norm{\frac{1}{\alpha} \sum_t \ep{\left[\Z_t|X\right]}} + \epsilon\bigg|X\right) \nn \\
 \geq 1 - (n_1 + n_2) \exp\left(\frac{-\alpha\epsilon^2}{2\left(\sigma^2 + R \epsilon\right)} \right).
\end{align}
\end{theorem}

The following theorem is adapted from \cite{versh_book}.
\begin{theorem}[Sub-Gaussian Rows \cite{versh_book}]\label{thm:versh}
Given an $N$-length sequence of sub-Gaussian random vectors $\bm{w}_i$ in $\mathbb{R}^{n_w}$, an r.v $X$, and a set $\mathcal{C}$. Assume the following holds. For all $X \in \mathcal{C}$, (i) $\bm{w}_i$ are conditionally independent given $X$; (ii) the sub-Gaussian norm of $\bm{w}_i$ is bounded by $K$ for all $i$. Let $\bm{W}:=[\bm{w}_1, \bm{w}_2, \dots, \bm{w}_N]{}'$.
Then for an $\epsilon \in (0, 1)$ and for all $X \in \mathcal{C}$
\begin{align}
\mathbb{P}\left(\norm{\frac{1}{N}\bm{W}{}'\bm{W} - \frac{1}{N}\ep{\left[\bm{W}{}'\bm{W} | X \right]}} \leq \epsilon \bigg| X\right) \nn \\
\geq 1 - 2\exp\left({n_w} \log 9 - \frac{c \epsilon^2 N}{4K^4}\right).
\end{align}
\end{theorem}

\renewcommand{\zt}{\bm{z}_t}

\section{Obtaining a result similar to that of \cite{rrpcp_dynrpca} for NORST}\label{sec:proof_reprocs-pca-mc}

It is possible to relax the lower bound on outlier magnitudes if not all of the subspace directions change at a given subspace change time. Suppose that only $r_\ch < r$ directions change. When $r_\ch=1$, we recover the guarantee of \cite{rrpcp_dynrpca} but for NORST (which is a simpler algorithm than s-reprocs).

Let $\P_{j-1, \fx}$ denote a basis for the fixed component of $\P_{j-1}$ and let $\P_{j-1,\ch}$ denote a basis for its changing component. Thus,
$\P_{j-1} \R = [ \P_{j-1,\fx}, \P_{j-1,\ch}]$, where $\bm{R}$ is a $r \times r$ rotation matrix.
We have
\begin{align}\label{eq:rchdef1}
\P_j = [\P_{j-1,\fx}, \P_{j,\chd}]
\end{align}
where $\P_{j, \chd}$ is the changed component and has the same dimension as $\P_{j-1, \ch}$. Thus,
\begin{align}\label{eq:rchdef2}
\SE(\P_{j-1},\P_j) = \SE( \P_{j-1,\ch}, \P_{j,\chd})
\end{align}
and so $\Delta = \max_j \SE(\P_{j-1},\P_j) = \max_j \SE( \P_{j-1,\ch}, \P_{j,\chd})$.
Let $\lambda_{\ch}^+$ denote the largest eigenvalue along any direction in $\P_{j,\chd}$.
\begin{corollary}\label{cor:rch}
In Algorithm \ref{algo:auto-reprocs-pca}, replace line 17 by $\Phat_{(t)} \leftarrow \basis(\Phat_{j-1}, \Phat_{j, k})$. For basis matrices $\P_1, \P_2$, we use $\P = \basis(\P_1, \P_2)$ to mean that $\P$ is a basis matrix with column span equal to the column span of $[\P_1, \P_2]$.
Assume that  \eqref{eq:rchdef1} and \eqref{eq:rchdef2} hold. Also assume that the conditions of Theorem \ref{thm1} holds with the lower bound on $\xmint$ relaxed to $\xmint \ge C (\zz \sqrt{\eta (r - r_\ch) \lambda^+} + (\zz + \Delta) \sqrt{\eta r_\ch \lambda_\ch^+})$.
Then, all conclusions of Theorem \ref{thm1} hold.
\end{corollary}

\begin{proof}[Proof of Corollary \ref{cor:rch}]
The proof is very similar to that of Theorem \ref{thm1}. The only changes occur in the \\
\emph{(a) Projected CS step}. With the subspace change model, we define
$
\lt = \P_{(t)} \at :=
\begin{bmatrix} \P_{j-1, \fx} & \P_{j, \chd} \end{bmatrix}
\begin{bmatrix}
\atf \\
\atr
\end{bmatrix}
$
where $\atf$ is a $(r - r_\ch) \times 1$ dimensional vector and $\atr$ is a $r_\ch \times 1$ dimensional vector.
In the first $\alpha$ frames after the $j$-th subspace changes (or, the $j$-th subspace change is detected in the automatic case), recall that $\Phat_{(t)} = \Phat_{j-1}$. Thus, $\SE(\Phat_{(t)}, \P_{j-1, \fx}) =
\SE(\Phat_{j-1}, \P_{j-1, \fx}) \leq \SE(\Phat_{j-1}, \P_{j-1}) \leq \zz$ and so, the error can be bounded as
\begin{align*}
\norm{\bpsi \lt} &\leq \norm{\bpsi \P_{j-1, \fx} \atf} + \norm{\bpsi \P_{j, \chd} \atr} \\
&\leq \zz \sqrt{\eta (r - r_\ch) \lambda^+} + (\zz + \SE(\P_{j-1}, \P_j)) \sqrt{\eta r_\ch \lambda_\ch^+}
\end{align*}

In the second $\alpha$ frames, have $\Phat_{(t)} = \basis(\Phat_{j-1}, \Phat_{j,1})$. Thus $\SE(\Phat_{(t)}, \P_{j-1,\fx}) \le
\SE(\Phat_{j-1}, \P_{j-1, \fx}) \leq \SE(\Phat_{j-1}, \P_{j-1}) \leq \zz$ and $\SE(\Phat_{(t)},\P_{j, \chd}) \le  \SE(\Phat_{j,1}, \P_{j, \chd}) \leq \SE(\Phat_{j,1}, \P_{j}) \leq 0.3 \cdot (\zz + \SE(\P_{j-1}, \P_j))$. Thus, the error in the sparse recovery step in the interval after the  first subspace update is  performed is given as
\begin{align*}
\norm{\bpsi \lt} \leq \zz \sqrt{\eta (r - r_\ch) \lambda^+} + 0.3 \cdot (\zz + \SE(\P_{j-1}, \P_j)) \sqrt{\eta r_\ch \lambda_\ch^+}
\end{align*}
The rest of the proof follows as before.
The error after the $k$-th subspace update is also bounded using the above idea.

\emph{(b) Subspace Detection step}:
The proof of the subspace detection step follows exactly analogous to Lemma \ref{lem:sschangedet}. One minor observation is noting that $\SE(\P_{j-1}, \P_J) = \SE(\P_{j-1, \ch}, \P_{j, \chd})$ in the proof of part (a) of Lemma \ref{lem:sschangedet}. The rest of the argument is exactly the same.
\end{proof}


TITLE: Prove a function is differentiable
QUESTION [0 upvotes]: In general (with a text) how can I justify that for example, the function:
$$\int_1^x\left((\frac{1}{t}) * e^u\right)\,dt = F(t)$$
$u = \frac{t^2+1}{t}.$
I can say it's because the function results of operations of continuous functions but that's not enough, isn't it?
NOTE: I'm studying Calculus I I know that in Calculus II we learn a formal process to prove this...

REPLY [0 votes]: Hint: By the fundamental theorem of calculus, the integral of a continuous function is differentiable.


TITLE: Absolute Value of Cosine and Sine in $\mathbb{C}$
QUESTION [1 upvotes]: Is it generally true that $|\cos(z)|\leq1$, $|\sin(z)|\leq1$ $\forall z \in \mathbb{C}$? I think I'm missing something here (I think it does not hold, only if $z \in \mathbb{R}$). If this were not the case, then could someone give me a concrete example of this?
Thanks for the help, this question has been troubling my mind for a while.

REPLY [1 votes]: Take $z = it, t\in\Bbb R$. $\lim_{t\to\infty}\sin(it)=\cdots$


TITLE: 100 blue-eyed islanders puzzle: 3 questions
QUESTION [91 upvotes]: I read the Blue Eyes puzzle here, and the solution which I find quite interesting. My questions:

What is the quantified piece of information that the Guru provides that each person did not already have?
Each person knows, from the beginning, no fewer than 99 blue-eyed people to be on the island. Then how is considering the 1 and 2-person cases relevant, if each person can dismiss these 2 cases immediately as possibilities?
Why must they wait 99 nights if, on the first 98 or so of these nights, they're simply verifying something that they already know?

EDIT: Most answers seem to concentrate on question 1 which I understand partly: but I remain confused because of different answers.
Can someone answer questions 2 and 3?

REPLY [0 votes]: I think the rationale here is correct, but I do think the solution is wrong. I think our island critters can deduce that they should leave after 2 days.
All blue-eyed people see 99 people with blue eyes, and all brown eyed people see 100 people with blue eyes. They will reason as in the solution, based on common knowledge. However, they don't have to wait 98 days, because everybody knows that nothing will happen the first 98 days. This is based on common knowledge. So logically, they can all be skipped. So on day 1, nobody leaves, on day 2, all people with blue eyes leave.