text:
\section{Representation categories}
We consider the categories, $F(R)$ (and $FI(R)$), of finite rank free $R$-modules with morphisms being injections (or splittable injections resp.) for a generalized ring. Similarly, let $P(R)$ (and $PI(R)$), denote the category of finitely generated projective $R$-modules with morphisms being injection (or splittable injection resp.) for a generalized ring. In this section, we show that the categories $F(\B)$, $F(\F_\infty)$, $FI(\B)$ and $FI(\F_\infty)$ are locally Noetherian, however, the categories $P(\B)$, $PI(\B)$, $P(\F_\infty)$ and $PI(\F_\infty)$ are not locally Noetherian. This gives another illustration of the strange homological behavior of the generalized rings $\B$ and $\F_\infty$.

We start by recalling the basic definitions of \cite{samsno2017} and \cite{putman2017} concerning representation categories. Let $\CC$ be a category and $\Mod_k$ the category of (left) modules over a (left) Noetherian ring $k$. The \textbf{representation category}, $\Rep_k(\CC)$ is defined as the category whose objects are covariant functors $\CC\ra \Mod_k$ and whose morphisms are natural transformation between functors. Objects of the representation category $\Rep_k(\CC)$ are called \textbf{$\CC$-modules}. For instance, for every $X\in \Ob(\CC)$ we obtain a $\CC$-module (called the \textbf{principal project module}) defined as follows. For an object $Y\in \Ob(\CC)$, we assign the vector space generated by all maps $f:X\ra Y$ in $\CC$:
\[\Princ{X}(Y) = k[\Hom_{\mathcal{C}}(X,Y)]=\bigoplus_{f\colon X \rightarrow Y} k\cdot e_f\]
and for a morphism $g:Y\ra Z$ we assign the $k$-module morphism
\[k[\Hom_{\mathcal{C}}(X,Y)] \rightarrow k[\Hom_\CC(X,Z)]\colon e_f \mapsto e_{g\circ f}.\]
The representation category, $\Rep_k(\CC)$ is an Abelian category, with kernels, cokernels, images, direct sums, ... calculated point-wise. We say that a $\CC$-module is \textbf{finitely generated} if it is a quotient of a finite direct sum of $\Princ{X}$. This definition is equivalent to the definition given in the Introduction (see \cite{samsno2017}).

We say that the representation category $\Rep_{k}(\mathcal{C})$ is \textbf{Noetherian} if every submodule of a finitely generated $\CC$-module is also finitely generated. Similarly, we say that $\CC$ is \textbf{locally Noetherian} if the representation category $\Rep_k(\CC)$ is Noetherian for every (left-)Noetherian ring $k$.

\subsection{Negative results}
The following proposition shows that Property (G2) of \cite{samsno2017} is a necessary condition for a category to be locally Noetherian. For the sake of completeness, we provide the proof of this proposition.

\begin{proposition}\label{prop: non noetherian}
Let $\mathcal{C}$ be an essentially small category. Assume $\mathcal{C}$ contains a fixed object $X_0$ and countably infinity distinct objects $Y_i$. If for each $i$ there exists a morphism $f_i \in \Hom_{\mathcal{C}}(X_0,Y_i)$ that does not factor as $X_0 \rightarrow Y_j \rightarrow Y_i$ for some $j < i$, then $\mathcal{C}$ is not locally Noetherian.
\end{proposition}

\begin{proof}
Consider the principal projective module $\Princ{X_0} \in \Rep_k(\mathcal{C})$ and the submodule $M$ generated by $\bigcup^{\infty}_{i =1} \Princ{X_0}(Y_i)$. Suppose $M$ is finitely generated by $\{\alpha_1, \ldots, \alpha_{\ell}\}$, where $\alpha_j \in M(X_j)$ for some object $X_j \in \mathcal{C}$. By the definition of $M$, each $\alpha_j$ is equal to a finite sum of the form
\[\sum^{N_j}_{i=1} \sum_{g_{ij} \colon Y_i \rightarrow X_j} M(g_{ij})(\beta_{g_{ij}}),\]
where $\beta_{g_{ij}} \in \Princ{X_0}(Y_i)$. Hence, we conclude $M$ is also generated by $\bigcup^{N}_{i =1} \Princ{X_0}(Y_i)$, where $N = \max \{N_j \mid j \in \{1,2, \ldots, \ell\}\}$. However, by assumption $e_{f_{N+1}} \in \Princ{X_0}(Y_{N+1})$ can not be generated by these elements. We conclude that $M$ is not finitely generated and therefore that $\CC$ is not locally Noetherian.
\end{proof}

The proposition above implies that $P(\B)$, $PI(\B)$, $P(\F_\infty)$ and $PI(\F_\infty)$ are not locally Noetherian.

\begin{corollary} The categories
$P(\B)$, $PI(\B)$, $P(\F_\infty)$ and $PI(\F_\infty)$ are not locally Noetherian.
\end{corollary}

\begin{proof}
The remark below implies that it is enough to prove the statement for $P(\B)$ and $P(\F_\infty$). Finally, Proposition \ref{prop: non noetherian} combined with Proposition \ref{prop:bnonnot} and \ref{prop:fnonnot} imply that $P(\B)$ and $P(\F_\infty$) are not locally Noetherian (with $X_0$ being the projective module $\D_0$ or $\E_0$ respectively).
\end{proof}

\textbf{Remark:} If the category $\CC$ is a full subcategory of $\DD$, and $\CC$ satisfies the conditions of Proposition \ref{prop: non noetherian}, then $\DD$ also satisfies the conditions of Proposition \ref{prop: non noetherian} with the same objects. Similarly, if $\CC$ is a faithful subcategory of $\DD$ containing the objects $X_0$, the $Y_i$ and the morphisms $f_i:X_0\ra Y_i$ so that $\DD$ satisfies the conditions of Proposition \ref{prop: non noetherian}, then $\CC$ also satisfies the conditions of Proposition \ref{prop: non noetherian}. As an easy consequence, we obtain that the category of finite posets with injections and the category of finite lattices with injections are also not locally Noetherian (see, for instance, \cite{wiejar09}). Similarly, we obtain that the category of all finitely generated $\B$-modules (or $\F_\infty$-modules) with injection is also not locally Noetherian.

\subsection{Positive results}

We conclude the paper by showing that the category of free $\B$-modules (or $\F_\infty$-modules) of finite rank with (splittable) injections is locally Noetherian. We will only prove the statement for $\B$-modules, the same proof applies for $\F_\infty$-modules with minimal changes. The proof is similar to the proofs of Theorem 8.3.1. in \cite{samsno2017} and of Theorem C in \cite{putman2017}, we only highlight the key steps.

\begin{proposition}
The category of free $\B$-modules of finite rank with (splittable) injections is locally Noetherian.
\end{proposition}

\begin{proof}

We first show the statement in the case of splittable injections. Let $FS$ denote the category of finite sets with morphisms being surjections. By Theorem 8.1.2 in \cite{samsno2017}, the opposite category $FS^{\op}$ is quasi-Gröbner. Consider the essentially surjective functor $\Phi\colon FS^{\op} \rightarrow F(\B) \colon S \mapsto \B[S]^* = \Hom_{\B}(\B[S],\B)$.

Let $\B^n$ be a free $\B$-module and let $f \colon\B^n \rightarrow\B[S]^*$ be a splittable injection for a finite set $S$.

The dual surjection $f^*\colon\B[S] \rightarrow (\B^n)^*$ factorises as $\B[S] \rightarrow \B[T] \rightarrow (\B^n)^*,$ where the first map is induced by a surjection of finite sets.

As a consequence, $\Phi$ satisfies Property (F) of \cite{samsno2017} implying that $FI(\B)$ is locally Noetherian.

Now, we turn our attention to prove that $F(\B)$ is also locally Noetherian. Note that any map $f:\B^n\ra \B^m$ can be given by an $[m\times n]$ matrix, $A$, whose entries are $0$ or $1$. Let $l$ denote the number of distinct rows of this matrix.

Note, that $l\leq 2^n$ and we obtain a map $\B^n\ra \B^l$ of $f$, given by the matrix $B$ consisting of the distinct rows of $A$. Moreover, we have a map $\B^l \ra \B^m$ sending the standard bases vector indexed by a row of $B$ to the sum of standard bases vector indexed by the equal rows in $A$. This map is a splittable injection and the two maps above yield a factorisation $\B^n\ra \B^l\ra \B^m$ of $f$. As a result, the forgetful functor $FI(\B)\ra F(\B)$ satisfies Property (F). Since this functor is also essentially surjective, we obtain that $F(\B)$ is also locally Noetherian.

\end{proof}


TITLE: Understanding Conditional Probability with Intersections of Events
QUESTION [1 upvotes]: I am attempting to ensure I understand conditional probability, so I came up with the following problem which seems to be posing some issues with regards to my understanding.  Say we have a deck of 16 cards.  There are four red, four green, four blue, four yellow cards.  Every color has a version with a star, circle, square, and triangle, so in total we have sixteen unique cards.  John has some random four of these sixteen cards.
Say we know John has the red circle card.  What is the probability he has 2 circle cards total?
Attempt at solution:
We are given that John has the red circle card, so we can look at this as
$Pr[A|B]$, where A is the event John has 2 circle cards and B is the given event, that he has a red circle card.
I expanded this to:
$$\frac{Pr[A\cap B]}{Pr[B]}$$
The top portion represents all of the combinations where John has 2 circle cards, and one of them must be the red circle card.  This should be divided by the possible combinations of four cards we can have. So
$$Pr[A\cap B] = \frac{\binom{1}{1}\binom{3}{1}\binom{12}{2}}{\binom{16}{4}}$$
We choose 1 of the 1 red circle cards, 1 of the 3 other circle cards, and 2 from the remaining cards to form our group of 4.  We divide this by the cases of all combinations of 4 cards we can have, 16 choose 4, which is 1820.  We divide this whole equation by $Pr[B]$, the probability of the given, that we have 1 red circle card, which is $1/16$ if I am not mistaken. However, when I evaluate, I reach a value larger than 1, which I know is impossible in a probability scenario.  At what point does my logic fail here?

REPLY [1 votes]: Event $B$ corresponds to having the red circle card among four cards randomly drawn without replacement from the $16$ cards.  This probability is not simply $1/16$:  it is $$\Pr[B] = \frac{\binom{1}{1}\binom{15}{3}}{\binom{16}{4}} = \frac{1}{4}.$$  This is because, in the deck with one such card (red circle), there is $\binom{1}{1}$ way to select one card that is the desired card, and $\binom{15}{3}$ ways to select the other three cards that are not the desired card.
The same logic applies to the numerator event $\Pr[A \cap B]$ which is the probability of selecting a red circle card and any other circle card.  This can be done in $\binom{1}{1}\binom{3}{1}\binom{12}{2}$ ways as you correctly calculated.  Therefore, the desired conditional probability is $$\Pr[A \mid B] = \frac{\binom{3}{1}\binom{12}{2}}{\binom{15}{3}} = \frac{198}{455}.$$
Notice that once written this way, it becomes clear that the conditional probability is itself hypergeometrically distributed, and that this makes sense:  once the red circle card is chosen, it is fixed, and the problem becomes simply a matter of the probability of selecting exactly one of the three remaining circle cards, and two of the 12 non-circle cards, out of a total of three cards chosen without replacement from the set of 15 cards that exclude the red circle card.
The takeaway here is that you actually enumerated the more difficult joint probability correctly but overlooked the easier marginal probability calculation because it was deceptively simple.  Take care to think through your calculation and not take shortcuts or "intuitive" arguments.


text:
\begin{document}
	\section{Appendix}
			\subsection{Preliminaries}\label{sec:apx:pre}
				In this section we give proofs to known inequalities that we use.
				Let $ N, M $ be integers such that $ M < N $.
				Using the Sterling inequality, stated as
				$$
				\sqrt{2\pi}N^{N+\frac{1}{2}}e^{-N}\leq N! \leq eN^{N+\frac{1}{2}}e^{-N},
				$$
				we get the following:
				\begin{lem}
					\label{lem:appendix:binomial}
					For $ N $ and $ M $ as the above, it holds that
					$$
					{N \choose M}
					\le  \left(\frac{eN}{M} \right)^M
					$$
				\end{lem}
				\begin{proof}

					$$
					{N \choose M}
					\leq \frac{N^M}{M!}
					\leq \frac{N^M}{\sqrt{2\pi M}(M/e)^M}
					\leq \left (\frac{eN}{M}\right )^M
					$$
				\end{proof}
				Consider the Binomial random variable $ X \sim B\left(N, \nicefrac{1}{2}\right) $.
				Using the Sterling inequality we get also that
				\begin{equation}\label{eq:apendix:choose}
				\begin{split}
				\Pr [X=M]
				& = {N \choose M} 2^{-N} \\
				& = \frac{N!}{M!(N-M)!} 2^{-N} \\
				& \leq \frac{e}{2\pi}
				\sqrt{\frac{N}{M(N-M)}}
				\left(\frac{N}{M}\right)^M
				\left(\frac{N}{N-M}\right)^{N-M}
				2^{-N}\\
				& = \frac{e}{2\pi}
				\sqrt{\frac{N}{M(N-M)}}
				\left(\frac{N}{2M}\right)^M
				\left(\frac{N}{2(N-M)}\right)^{N-M}.
				\end{split}
				\end{equation}

				\begin{lem}\label{lem:binomial-2n-n}
					Let $ X_1,X_2, \sim B\left (N, \nicefrac{1}{2}\right ) $. The following holds:
					$$
					\Pr\left[ X_1 = X_2 \right]= {2N \choose N}2^{-2N} \leq \frac{e}{ \pi\sqrt{2 N}}
					$$
				\end{lem}
				\begin{proof}
					Define the random variable $ \bar{X}_1 = N - X_1 $. Note that $ \bar{X}_1 $ is also distributed as $ B\left( N, \nicefrac{1}{2} \right) $ and that $ X_1 = X_2 $ if and only if $ \bar{X}_1 + X_2 = N $.
					Therefore, for $ \bar{X}_1 + X_2 =  Y \sim B\left (2N, \nicefrac{1}{2}\right ) $ we have
					$$
					\Pr\left[ Y = N \right] = \Pr [X_1 = X_2].
					$$
					By (\ref{eq:apendix:choose}) we have that:
					$$
					\Pr [Y=N]
					= {2N \choose N}2^{-2N}
					\leq \frac{e}{2\pi}
					\sqrt{\frac{2N}{N^2}}
					\left(\frac{2N}{2N}\right)^N
					\left(\frac{2N}{2N}\right)^N
					=  \frac{e}{ \pi\sqrt{2 N}}
					$$
				\end{proof}
			\subsection{Information theoretic lower bound} \label{appendix:tlb}
				We now provide a proof sketch for the lower bound in equation \ref{intro:eq:info-theortic-bound-sublinear}.
				We need at least $ \log {n \choose k} \sim k\lognk$ bits to express all possible subsets $ \D \subseteq [n] $ of cardinality $ k $.
				A test outcome can have $ k+1 $ different values.
				However, a typical test outcome is of distance $ O (\sqrt k ) $ from its expectation.
				Therefore to encode all of the typical outcomes we need $\sim \frac{1}{2}\log {k} $ bits.
				(Sometimes a test solution is not in the typical range, but this has negligible effect on the bounds. Further details omitted.)
				We conclude that if the number of tests is below $ \sim 2k \frac{\lognk}{\log k} $ there is not enough information to express all possible subsets $ \D $.
			\subsection{Information theoretic threshold} \label{appendix:tub}
				\begin{lem}
					\label{intro:lem:tup}
						For QGT problem in the sublinear regime, the information-theoretic threshold on the number of tests is
						\begin{equation}
						\Mqgt < \tub.
						\end{equation}
				\end{lem}
				\begin{proof}[Proof of Lemma \ref{intro:lem:tup}]
					\newcommand{\far}{far}
					Recall that $ k = n^\theta $ for some constant $ \theta \in (0,1) $.
					In the following, because $ A $ is a random Bernoulli matrix, we assume w.l.o.g that $ x $ is a fixed vector of Hamming weight $ k $.
					Let $ l \in [k-1]$ be an integer and let $ z \in \{0,1\}^n $ be a vector of Hamming weight $ k $. We say that $ z $ is \emph{$ l $-\far} from $ x $ if $ x $ and $ z $ are of Hamming distance $ 2l $ (i.e., $ z $ has $ l $ different coordinates $ i\in [n] $ such that $ z_i = 1 $ but $ x_i = 0 $ ). Denote by $ \mathcal{L}_l $ the set of all vectors $ v \in \{0,1\}^n $ of Hamming weight $ k $ that are {$ l $-\far} from $ x $. By using a union bound, the probability that there exists a solution other than $ x $ is upper bounded by:
					\begin{equation}\label{eq:lem:tup:mission}
					\sum_{l=1}^{k} \sum_{z \in \mathcal{L}_l} \Pr [Az = y]
					\end{equation}

					Next, we provide an upper bound on the probability that a vector $ z \in \mathcal{L}_l $ is a solution.
					Note that the event $ Az = y $ occurs if for every test $ j\in[m] $, it holds that $ (Ax)_j = (Az)_j $.
					Because $ A $ is a random Bernoulli matrix, the probability of this event to occur is exactly as that $ m $ times, two Binomial random variables $ X_1,X_2 \sim B(l, \nhalf) $ have the same value.
					By Lemma \ref{lem:binomial-2n-n}, we have that each of these $ m $ events happens with probability of at most $ \frac{e}{\pi \sqrt{2l}} $. Hence, for a fixed $ z\in \mathcal{L}_l $ we have
					$$
					\Pr_A \left[ Az=y \right] \leq \left(\frac{e}{\pi \sqrt{2l}} \right)^m.
					$$
					From the above and because $ \mathcal{L}_l $ is of cardinality $ {k \choose k-l}{{n - k} \choose {l}} $, we have that for each $ l \in [k-1] $ it holds that
					\begin{equation}\label{eq:lem-tub:l-overlap-bound}
					\sum_{
						z \in \mathcal{L}_l
					}
					\Pr \left[Az=y \right]
					\leq
					{k \choose k-l}
					{{n - k} \choose {l}}
					\left(\frac{e}{\pi \sqrt{2l}} \right)^m
					\leq
					{k \choose l}
					{{n} \choose {l}}
					\left(\frac{e}{\pi \sqrt{2l}} \right)^m.
					\end{equation}

					From Lemma \ref{lem:appendix:binomial} we have that
					\begin{equation*}
						{k \choose l}{{n} \choose {l}}
						\le \left(\frac{ek}{l}\right)^l \left(\frac{en}{l}\right)^l
						=\left(\frac{e^2kn}{l^2}\right)^l.
					\end{equation*}

					We will show that for every $ l\in [k] $ it holds that
					\begin{equation}\label{appendix:eq:lem-tub:sub-mission}
					k \sum_{
						z \in \mathcal{L}_l
					}
					\Pr \left[Az=y \right]
					\leq
						k\left(\frac{e^2kn}{l^2}\right)^l \left(\frac{e}{\pi \sqrt{2l}} \right)^m = o(1)
					\end{equation}

					Denote by $ l_0 \in [k] $ the index which maximizes (\ref{appendix:eq:lem-tub:sub-mission}).
					Note that this expression for $ l_0 $ bounds from above (\ref{eq:lem:tup:mission}) and therefore by proving this we are done.

					We first show that there exists $ \alpha \in (0,1) $ that depends only on $ \theta $ such that for all $ 1\le l \le \alpha \frac{k}{\log k} $ equation (\ref{appendix:eq:lem-tub:sub-mission}) holds.

					Assuming that $ m > 2k\frac{\log \frac{e^2 n}{k}}{\log k} = (1+o(1))2k\frac{\lognk}{\log k}$,
					\begin{equation*}
						\begin{split}
						k\cdot \left(\frac{e^2kn}{l^2}\right)^l \cdot \left(\frac{e}{\pi \sqrt{2l}} \right)^m
						& \le k \cdot \left(e^2 n^{1+\theta} \right)^l \cdot 2^{-\frac{m}{2}} \\
						& \le k \cdot \left(e^2 n^{1+\theta} \right)^l \cdot \left(e^2 n^{1-\theta}\right)^{-\frac{k}{\log k}} \\
						& \le k e^{2(l-\frac{k}{\log k})} \cdot \left(n^{1+\theta} \right)^{l-\frac{1-\theta}{1+\theta}\frac{k}{\log k}}.
						\end{split}
					\end{equation*}
					Note that there exists $ \alpha \in (0,1) $ that depends only on $ \theta $ such that for all $ 1\le l \le \alpha \frac{k}{\log k} $ we have $ l-\frac{k}{\log k} < 2\log k $ and such $ l-\frac{1-\theta}{1+\theta}\frac{k}{\log k} < 0 $. We are left to show that (\ref{appendix:eq:lem-tub:sub-mission}) holds for $ \alpha \frac{k}{\log k} \le l \le k $.

					Assume that
					$$ m > 2k\frac{\log \left(\frac{{\log (k)} ^2 e^2}{\alpha^2} \frac{n}{k}\right)}{\log \left(\frac{\alpha k}{\log k}\right)} = (1+o(1))2k\frac{\lognk}{\log k}.$$
					We have that
					\begin{equation*}
					\begin{split}
						k \cdot \left(\frac{e^2kn}{l^2}\right)^l \cdot \left(\frac{e}{\pi \sqrt{2l}} \right)^m
						& \le k \cdot \left(\frac{{\log (k)} ^2}{\alpha^2} \frac{e^2kn}{k^2}\right)^l \cdot \left(\frac{\log k}{\alpha k}\frac{e^2}{\pi^2 2 } \right)^\frac{m}{2}  \\
						& \le k \cdot 2^{-\frac{m}{2}} \left(\frac{{\log (k)} ^2}{\alpha^2} \frac{e^2kn}{k^2}\right)^{l-k} \\
						& = o(1).
					\end{split}
					\end{equation*}
				\end{proof}
	\subsection{Binomial random variable tail bound}
		\label{sec:appendix:binomial-tail-bound}
		\begin{lem} \label{lem:binomial-n/2+k}
			Let $ N, t $ be integers such that $ t < \frac{N}{2} $ and consider the Binomial random variable $ X \sim B\left(N, \nicefrac{1}{2}\right) $.
			We have that:
			$$
			\Pr\left[ X = \frac{N}{2} + t \right]
			\leq
			\frac{e}{2\pi}
			\sqrt{\frac{N}{\frac{N^2}{4}-t^2}} e^{-\frac{2t^2}{N}}.
			$$
		\end{lem}
		\begin{proof}
			Recall that $ h(p):= -p \log(p)-(1-p)\log(1-p) $ is the binary entropy function.
			By (\ref{eq:apendix:choose}) we have that:
			\begin{equation*}
			\begin{split}
			\Pr [X=\frac{N}{2} + t]
			& \leq \frac{e}{2\pi}
			\sqrt{\frac{N}{\left(\frac{N}{2} + t\right)\left(\frac{N}{2} - t\right)}} \\
			& \cdot \left(\frac{N}{\frac{N}{2} + t}\right)^{\frac{N}{2} + t}
			\left(\frac{N}{\frac{N}{2} - t}\right)^{\frac{N}{2} - t}2^{-N} \\
			& = \frac{e}{2\pi}
			\sqrt{\frac{N}{\frac{N^2}{4} - t^2}}
			2^{N(h(\frac{1}{2}+\frac{t}{N}) -1)}.
			\end{split}
			\end{equation*}
			The Taylor series of the binary entropy function in a neighborhood of $ \frac{1}{2} $ is
			\begin{equation*}
			h(p)=1 - \frac{1}{2\ln 2} \sum^{\infty}_{i=1} \frac{(1-2p)^{2i}}{i(2i-1)}.
			\end{equation*}
			Hence,
			\begin{equation*}
			h\left (\frac{1}{2}+\frac{t}{N}\right )-1
			= - \frac{1}{2\ln 2} \sum^{\infty}_{i=1} \left (\frac{2t}{N}\right )^{2i}\frac{1}{i(2i-1)}
			\le -\frac{1}{\ln 2}\cdot \frac{2t^2}{N^2}.
			\end{equation*}
			Therefore, the proof follows.
		\end{proof}

		The proof of Lemma \ref{lem:pr-of-bernoulli-not-in-center} follows by applying Lemma \ref{lem:binomial-n/2+k} to the following crude inequality (for a tighter bound see \cite{klar2000bounds})
		\begin{equation*}
			\Pr[X\ge \frac{N}{2}+t] \le O\left(\frac{N}{t}\right)\Pr[X= \frac{N}{2}+t].
		\end{equation*}
	\subsection{Proof of Lemma \ref{lem:f2-space-rank-bound}} \label{sec:apx:lem-space-rank-bound}
		In the proof of Lemma \ref{lem:f2-space-rank-bound} we denote $ M := m_1 $ for convenience.
		\begin{proof}[Proof of Lemma \ref{lem:f2-space-rank-bound}]
			Recall that by Lemma \ref{SSA:lem:X-in-V} the probability of a uniformly random binary vector $ X \sim \{0,1\}^M $ to belong a deterministic subspace $ V \subseteq \mathbb{R}^M $ with dimension of at most $ t $ is bounded above by
			\begin{equation}\label{lem_proof_f2_vec}
			\Pr[x \in V] \le 2^{t-M}.
			\end{equation}
			Next, observe that
			the event
			$ \dim\left(V \cup U\right) < k_2 $
			occurs if and only if there exists a subset $ S \subseteq \{ u_1 ,u_2, \ldots, u_l\} $ of cardinality $ l - (k_2 - k1) + 1 $ of vectors that are linearly dependent on other vectors. We may assume w.l.o.g. that the set $ S $ is such that for each $ u_i \in S $ it holds that $ u_i \in V \cup \langle u_1,u_2, \ldots, u_{i-1} \rangle $. Therefore we have that:
			\begin{equation}\label{lem_proof_f2_sums}
			\Pr\left[
			\dim\left(
			V \cup U
			\right)
			< k_2
			\right]
			\leq
			\sum_{S}\Pr[\forall u_i \in S \text{ } u_i \in V \cup \langle u_1, u_2, \ldots, u_{i-1}\rangle],
			\end{equation}
			where the sum is taken over all subsets $ S $ of the required cardinality.
			We only need to bound events such that $ \dim(V \cup \langle u_1, u_2, \ldots, u_{i-1}\rangle) \le k_2 -1 $.
			Therefore from \ref{lem_proof_f2_vec},
			$$
			\Pr[\forall u_i \in S \text{ } u_i \in V \cup \langle u_1, u_2, \ldots, u_{i-1}\rangle] \le (2^{k_2-1-M})^{|S|}=2^{(k_2-1-M)(l-(k_2-k_1)+1)}
			$$
			We sum over exactly $ l \choose {l-(k_2-k_1)+1} $ possible subsets, and the proof follows.
		\end{proof}
\end{document}

config: arxiv


TITLE: What sequence satisfies this liminf property?
QUESTION [0 upvotes]: I am thinking about a sequence such that the following holds (noticed > not $\geq$)
$\liminf_{n \to \infty} (a_n + b_n) > \liminf_{n \to \infty} a_n + \liminf_{n \to \infty} b_n$
I am not sure if this is allowed, but I tried doing something like
$a_n = \left \{2....-1,1,-1,1,-1,1 \right \}$
$b_n = \left \{2....1,-1,1,-1,1, -1\right \}$
I know the example doesn't work, but can you actually write down the limsup (the end term) like this? Or is this as erroneous as writing $1/0$?

REPLY [2 votes]: No, what you’ve written for $a_n$ and $b_n$ simply doesn’t make sense. The sequences that you’re to construct are ordinary infinite sequences $\langle a_1,a_2,\dots\rangle$ and $\langle b_1,b_2,\dots\rangle$, with no last elements.
HINT: Take $a_n=(-1)^n$, so that $\liminf_na_n=-1$. Can you find another sequence $\langle b_1,b_2,\dots\rangle$ such that $\liminf_nb_n$ is also $-1$, but $\langle a_1+b_1,a_2+b_2,\dots\rangle$ is constant with a value greater than $-1$?


text:
\section{Equivalence of Definitions of Arborescence}
Tags: Arborescences

\begin{theorem}
Let $G = \struct {V, A}$ be a [[Definition:Directed Graph|directed graph]].
Let $r \in V$.
{{TFAE|def = Arborescence}}
\end{theorem}

\begin{proof}
=== Definition 1 implies Definition 3 ===
Let $G$ be an [[Definition:Arborescence/Definition 1|$r$-arborescence by definition 1]].
Let $v \in V$ such that $v \ne r$.
Then there is exactly one [[Definition:Directed Walk|directed walk]] $w$ from $r$ to $v$.
Since $v \ne r$, either:
:$w = \tuple {r, v}$
or:
:$\exists m \in V: w = \tuple {r, \ldots, m, v}$
Thus $v$ is the [[Definition:Final Vertex of Arc|final vertex]] of the [[Definition:Arc of Digraph|arc]] $r v$ or the [[Definition:Arc of Digraph|arc]] $m v$.
{{AimForCont}} that $v$ is the [[Definition:Final Vertex of Arc|final vertex]] of [[Definition:Distinct|distinct]] [[Definition:Arc of Digraph|arc]] $x v$ and $y v$.
Then there exist [[Definition:Directed Walk|directed walks]] $w_1$ and $w_2$ from $r$ to $x$ and $r$ to $y$ respectively.
But appending $v$ to $w_1$ and to $w_2$ yields [[Definition:Distinct|distinct]] [[Definition:Directed Walk|directed walks]] from $r$ to $v$.
This [[Definition:Contradiction|contradicts]] the fact that there is [[Definition:Unique|exactly one]] such [[Definition:Directed Walk|directed walk]].
Thus $v$ is the [[Definition:Final Vertex of Arc|final vertex]] of [[Definition:Unique|exactly one]] [[Definition:Arc of Digraph|arc]].
{{qed|lemma}}
{{AimForCont}} that $r$ is the [[Definition:Final Vertex of Arc|final vertex]] of an [[Definition:Arc of Digraph|arc]] $x r$.
By [[Definition:Arborescence/Definition 1|Definition 1]], there is a [[Definition:Directed Walk|directed walk]] $w$ from $r$ to $x$.
But then $w$ appended to $w$ is a [[Definition:Directed Walk|directed walk]] from $r$ to $x$ which is not equal to $w$.
This [[Definition:Contradiction|contradicts]] [[Definition:Arborescence/Definition 1|definition 1]].
Thus we conclude that $r$ is not the [[Definition:Final Vertex of Arc|final vertex]] of any [[Definition:Arc of Digraph|arc]].
It follows immediately from [[Definition:Arborescence/Definition 1|definition 1]] that there is a [[Definition:Directed Walk|directed walk]] from $r$ to each [[Definition:Vertex of Graph|vertex]] $v \ne r$.
Thus $G$ is an [[Definition:Arborescence/Definition 3|$r$-arborescence by Definition 3]].
{{qed|lemma}}
=== Definition 3 implies Definition 1 ===
Suppose that $G$ is an $r$-arborescence by [[Definition:Arborescence/Definition 3|Definition 3]].
Let $v \in V$.
We must show that there is a [[Definition:Unique|unique]] [[Definition:Directed Walk|directed walk]] from $r$ to $v$.
If $v = r$, then $\tuple r$ is a [[Definition:Directed Walk|directed walk]] from $r$ to $v$.
Since $r$ is not the [[Definition:Final Vertex of Arc|final vertex]] of any [[Definition:Arc of Digraph|arc]], $\tuple r$ is the only such [[Definition:Directed Walk|directed walk]].
If $v \ne r$, then there exists some [[Definition:Directed Walk|directed walk]] $w$ from $r$ to $v$.
Suppose that $z$ is a [[Definition:Directed Walk|directed walk]] from $r$ to $v$.
Since $v \ne r$, $v$ is the [[Definition:Final Vertex of Arc|final vertex]] of exactly one [[Definition:Arc of Digraph|arc]] $x v$.
If $x = r$, then $z$ must end with $\tuple {r, v}$.
But $r$ is not the [[Definition:Final Vertex of Arc|final vertex]] of any [[Definition:Arc of Digraph|arc]].
So in fact:
:$z = \tuple {r, v}$
If $x \ne r$, then:
:$z = \tuple {r, \ldots, x, v}$
Continuing inductively from $x$ proves that $z = w$.
{{explain|set up the induction more formally, or less formally, or something. This is messy.}}
Thus for each $v \in V$ there is [[Definition:Unique|exactly one]] [[Definition:Directed Walk|directed walk]] from $r$ to $v$.
So $G$ is an [[Definition:Arborescence/Definition 1|$r$-arborescence by Definition 1]].
{{qed|lemma}}
=== Definitions 1 and 3 imply Definition 2 ===
Let $G$ be an [[Definition:Arborescence/Definition 1|$r$-arborescence by Definition 1]].
From the above, $G$ is then also an [[Definition:Arborescence/Definition 3|$r$-arborescence by Definition 3]].
Let $T = \struct {V, E}$ be the [[Definition:Simple Graph|simple graph]] corresponding to $G$.
That is, for $x, y \in V$, let $\set {x, y} \in E$ {{iff}} $\tuple {x, y} \in A$ or $\tuple {y, x} \in A$.
We will show that $G$ is an [[Definition:Orientation (Graph Theory)|orientation]] of $T$ and that $T$ is a [[Definition:Tree (Graph Theory)|tree]].
By [[Definition:Arborescence/Definition 1|Definition 1]], there is [[Definition:Unique|exactly one]] [[Definition:Directed Walk|directed walk]] from $r$ to each [[Definition:Vertex (Graph Theory)|vertex]] $v$.
Let $x, y \in V$ and suppose [[Proof by Contradiction|for the sake of contradiction]] that $\tuple {x, y} \in A$ and $\tuple {y, x} \in A$.
Let $w_x$ be the [[Definition:Directed Walk|directed walk]] from $r$ to $x$.
Then appending $y$ to $w_x$ yields a [[Definition:Directed Walk|directed walk]] $w_x + y$ from $r$ to $y$.
But then appending $x$ to $w_x + y$ yields a [[Definition:Directed Walk|directed walk]] $w_x + y + x$ from $r$ to $x$, contradicting the fact that $w_x$ is unique.
Thus $A$ is [[Definition:Asymmetric Relation|asymmetric]].
So $G$ is an [[Definition:Orientation (Graph Theory)|orientation]] of $T$.
We must now show that $T$ is a [[Definition:Tree (Graph Theory)|tree]].
By [[Equivalence of Definitions of Reachable]], each [[Definition:Vertex of Graph|vertex]] $v$ of $G$ is [[Definition:Reachable|reachable]] from $r$.
Let $x, y \in V$.
By [[Definition:Arborescence/Definition 1|Definition 1]], there is [[Definition:Unique|exactly one]] [[Definition:Directed Walk|directed walk]] from $r$ to $x$ and [[Definition:Unique|exactly one]] [[Definition:Directed Walk|directed walk]] from $r$ to $y$.
Thus there is a [[Definition:Walk (Graph Theory)|walk]] $w_x$ in $T$ from $r$ to $x$ and a [[Definition:Walk (Graph Theory)|walk]] $w_y$ from $r$ to $y$.
Reversing $w_x$ and then appending $w_y$ to it (eliding the duplicate $r$) yields a [[Definition:Walk (Graph Theory)|walk]] from $x$ to $y$.
Thus $T$ is [[Definition:Connected Graph|connected]].
Next we show that $G$ has no [[Definition:Directed Walk|directed]] [[Definition:Cycle (Graph Theory)|cycle]].
{{AimForCont}} that $x_0, x_1, \dots, x_n$ is a [[Definition:Directed Walk|directed walk]] with $n \ge 2$ and $x_0 = x_n$.
By [[Definition:Arborescence/Definition 1|Definition 1]], there is a [[Definition:Unique|unique]] [[Definition:Directed Walk|directed walk]] $w$ from $r$ to $x_0$.
But then $w + \tuple {x_1, \dots, x_n}$ is another [[Definition:Directed Walk|directed walk]] from $r$ to $x_0$, contradicting [[Definition:Unique|uniqueness]].
Thus $G$ has no [[Definition:Directed Walk|directed]] [[Definition:Cycle (Graph Theory)|cycles]].
{{AimForCont}} that $T$ has a [[Definition:Cycle (Graph Theory)|cycle]] $\tuple {x_0, x_1, \dots, x_n}$, where $x_0 = x_n$ and $n \ge 2$.
Since $G$ has no [[Definition:Directed Walk|directed]] [[Definition:Cycle (Graph Theory)|cycles]], the [[Definition:Arc of Digraph|arcs]] corresponding to the [[Definition:Edge of Graph|edges]] in this [[Definition:Cycle (Graph Theory)|cycle]] cannot all go in the same direction around the [[Definition:Cycle (Graph Theory)|cycle]].
But this implies that some [[Definition:Vertex of Graph|vertex]] of $x_0, x_1, \dots, x_n$ is the [[Definition:Final Vertex of Arc|final vertex]] of two different [[Definition:Arc of Digraph|arcs]], contradicting [[Definition:Arborescence/Definition 3|Definition 3]].
{{explain}}
Thus $T$ has no [[Definition:Cycle (Graph Theory)|cycles]].
As $T$ is [[Definition:Connected Graph|connected]], it is a [[Definition:Tree (Graph Theory)|tree]].
Thus we have shown that $G$ is an [[Definition:Orientation (Graph Theory)|orientation]] of $T$ and that $T$ is a [[Definition:Tree (Graph Theory)|tree]].
{{qed|lemma}}
=== Definition 2 implies Definition 1 ===
Let $G$ be an [[Definition:Arborescence/Definition 2|$r$-arborescence by Definition 2]].
That is, let $G$ be an [[Definition:Orientation (Graph Theory)|orientation]] of a [[Definition:Tree (Graph Theory)|tree]] $T$ and that every [[Definition:Vertex of Graph|vertex]] of $G$ is [[Definition:Reachable|reachable]] from $r$.
Let $v \in V$.
By the definition of [[Definition:Reachable/Definition 2|reachable]], there exists a [[Definition:Directed Walk|directed walk]] $w$ from $r$ to $v$.
We must show that $w$ is the [[Definition:Unique|only]] [[Definition:Directed Walk|directed walk]] from $r$ to $v$.
{{AimForCont}} that $z$ is a [[Definition:Directed Walk|directed walk]] from $r$ to $v$ and $z \ne v$.
Then either $z$ extends $w$, $w$ extends $z$, or there is some $k$ such that $w_k \ne z_k$.
First suppose that $z$ extends $w$.
So $w = \tuple {x_0, \ldots, x_n}$ and $z = \tuple {x_0, \ldots, x_n, \ldots, x_m}$.
Then $p = \left({x_n, \dots, x_m}\right)$ is a [[Definition:Directed Walk|directed walk]] from $v$ to $v$ with more than one [[Definition:Vertex of Graph|vertex]].
By [[Directed Circuit in Simple Digraph forms Circuit]], the [[Definition:Vertex of Graph|vertices]] of $p$ form a [[Definition:Circuit|circuit]], contradicting the fact that $T$ is a [[Definition:Tree (Graph Theory)|tree]].
Thus there exists $k$ such that $w_k \ne z_k$.
It follows from the [[Well-Ordering Principle]] that there must be some [[Definition:Smallest Element|smallest]] $k$ such that $w_k \ne z_k$.
Since $w$ and $z$ both end at $v$, it follows from the [[Well-Ordering Principle]] that:
:there must be some [[Definition:Smallest Element|smallest]] $n > k$ such that there exists $m > k$ such that $w_n = z_m$
:and that there exists a [[Definition:Smallest Element|smallest]] such $m$.
Then $\tuple {w_{k - 1}, w_k, \ldots, w_n, z_{m - 1}, \dots, z_k, z_{k - 1} }$ forms a [[Definition:Cycle (Graph Theory)|cycle]], contradicting the fact that $T$ is a [[Definition:Tree (Graph Theory)|tree]].
{{explain}}
{{qed}}
[[Category:Arborescences]]
3313oj1kghruvj5qbb8ynvtui1llsm8
\end{proof}

config: wiki


TITLE: Does $\sup_{n \ge m} Y_n < \infty \ \text{a.s.}$ imply $\sup_{n \ge 1} Y_n < \infty \ \text{a.s. ?}$
QUESTION [0 upvotes]: Suppose $Y_1, Y_2, ...$ are independent random variables and $\exists m \ge 1$ s.t.
$$\sup_{n \ge m} Y_n < \infty \ \text{a.s.}$$
Does this mean
$$\sup_{n \ge 1} Y_n < \infty \ \text{a.s. ?}$$

I was thinking say $m = 2$ and $Y_1 = \infty$, then $\sup_{n \ge m} Y_n < \infty$, but $\sup_{n \ge 1} Y_n = \infty ?$
I have a feeling either the independence or the 'a.s.' is needed here.
My guess is that $\sup_{n \ge 1} Y_n = \infty $ but $\sup_{n \ge 1} Y_n < \infty \ \text{a.s. ?}$

REPLY [2 votes]: I was thinking say $m = 2$ and $Y_1 = \infty$, then $\sup_{n \ge m} Y_n < \infty$, but $\sup_{n \ge 1} Y_n = \infty ?$

You almost answered you own question. You need further assumption for $Y_n$ with $n\geq 2$ though. Say, $Y_n\equiv 1$ for each $n$. Then the $Y_n$'s are independent. (Why?) Then you can check that the quoted statement is not true.


TITLE: Show that $\sup (A\cdot B)=\max\{\sup A\cdot\sup B, \sup A\cdot\inf B,\inf A\cdot\sup B,\inf A\cdot\inf B\}$
QUESTION [0 upvotes]: Given nonempty subsets $A$ and $B$ of positive real numbers, define
  $$A\cdot B=\{z=x\cdot y:x\in A,\,y\in B \}$$
  show that if $A$ and $B$ are bounded sets of real numbers, then $$\sup(A\cdot B)=\max\{\sup A\cdot\sup B, \sup A\cdot\inf B,\inf A\cdot\sup B,\inf A\cdot\inf B\}$$

For this question, I know that $\sup(A\cdot B)=\sup(A)\cdot\sup(B)$. Do I need to compare all elements in the set then show $\sup(A\cdot B)=\sup(A)\cdot\sup(B)$?
Am I on the right way? If not, can anyone give a hit or a suggestion to start? Thanks.

REPLY [1 votes]: Let the inf and sup of $A$ be $a_1,a_2$ and of $B$ be $b_1,b_2.$ Now let $R$ denote the rectangle $R=[a_1,a_2]\times [b_1,b_2],$ and we seek the sup of $p=xy$ over $R.$
We first assume that $A,B$ are the entire closed intervals between their respective inf and sup, and say later why this is OK. Note first that the only critical point of $p$ is at the origin. If this critical point happens to lie interior to $R$ then each of $a_2,b_2$ are positive, and since they are sups, there are sequences approaching them, so that the sup we seek is at least $a_2b_2>0,$ which means the sup of $p$ is positive, so the maximum of $p$ on $R$ does not occur at the critical point of $p$.
So the max of $p$ must occur at a boundary point of $R,$ and focusing on any of the four edges of $R$ then shows $p$ cannot have its max at an interior point of an edge of $R.$ This leaves only the four vertices of $R$ as candidates for the max of $p$ over $R.$ So by the usual method of maximizing a two variable differentiable function over a compact domain, the maximum of $p$ over $R$ is the greatest product among $a_1b_1,\ a_1b_2,\ a_2b_1,\ a_2b_2$ which in our notation is the desired supremum of $p.$ Call this amount $M.$
Slight correction: If an edge of $R$ happens to be along the $x$ or $y$ axis, then $p$is constant ($p=0$) on that edge. So above, instead of saying the max of $p$ cannot occur at an interior point of an edge, I should have said more correctly something like "The max of $p$ is taken on at an endpoint of the edge (and perhaps at interior points, if the edge is along an axis)."
Now of course the given sets $A,B$ need not be intervals, but by the above argument the product $p$ taken at any point $(x,y) \in A \times B$ will be at most $M$. We can be sure the supremum is actually equal to $M$ since whichever "corner" of the rectangle is chosen, there are sequences in $A,B$ approaching the coordinates of that corner.


TITLE: Difference of 2 roots
QUESTION [0 upvotes]: $2003^2x^2 - (2002)(2004)x - 1 = 0$
$x^2+2002x - 2003 = 0$
What is the difference of the 1st equation's larger root and the smaller root of the 2nd equation?
I did not know how to approach this, so I used the quadratic formula but could not easily simplify the expressions. What properties will be used ?

REPLY [1 votes]: \begin{align*}
2003^2x^2-2002(2004)(x)-1&=2003^2x^2-(2003-1)(2003+1)x-1\\
&=2003^2(x^2-x)+x-1\\&=(x-1)(2003^2x-1)
\end{align*}
\begin{align*}
x^2+2002x-2003=(x-1)(x+2003)
\end{align*}