TITLE: Expected value of lognormal distribution.
QUESTION [2 upvotes]: Hi I'm stuck on this question:
Recall that $X$ is said to have a lognormal distribution with parameters $\mu$ and $\sigma^2$ if $\log(X)$ is normal with mean $\mu$ and variance $\sigma^2$.
Suppose $X$ is such a lognormal random variable.

Find $\mathrm{E}[X]$.
Find $\mathrm{Var}(X)$.

I know that the approach is to find the moment generating function and take the first derivative for the expected value and the second derivative for the variance (I think), but I can't seem to figure it out.  Thanks in advance.

REPLY [4 votes]: No.  The lognormal distribution doesn't have a moment generating function, so you can't use that approach.
Instead, suppose $Y = \log X$.  Then $Y \sim \operatorname{Normal}(\mu, \sigma^2)$ by definition, and $X = e^Y$.  Therefore for a positive integer $k$, $$\operatorname{E}[X^k] = \operatorname{E}[e^{kY}] = M_Y(k),$$ where $M_Y(k)$ is the moment generating function of $Y$.  This hint should now make it trivial to obtain the expectation and variance of $X$.


TITLE: Comparison trees
QUESTION [1 upvotes]: You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and whether or not it's light or heavier than the rest?

I had this question on a quiz the other day in my discrete math class. The answer was shown to be $\lceil \log_3 120\rceil$, which is 5.
A second question was asked:

If you know the coin is lighter than the rest and you had the same number (60), how many comparisons, worst case, would be needed?

which was $\lceil \log_3 60\rceil$, which is 4.
I was wondering if someone could explain to me why this is the correct answer. Why $\log_3$?

REPLY [1 votes]: In the one-coin-lighter case: Divide the 60 coins into three sets of 20.  But one of the three groups in one pan of the balance and another in the other pan.  If their weights are different, you know which group of 20 contains the lighter coin, and if they're the same, then you also know which group (the one that's not being weighed).
Divide the remaining 20 into two sets of 7 and one set of 6.  Weigh the two sets of 7 against each other.  Then you have either a set of 6 or a set of 7.
If the latter then in the next weighing if you use two sets of three, with one not weighed, you could narrow it to one coin and you're done, but it you narrow it to three, you need one more weighing, with one coin in each pan.  If you use two sets of two, with three coins not weighed, then no matter what the outcome you'll need one more weighing.
Four weighings are enough.
Now notice what's happened: each time you cut the number of coins in the pan down to $1/3$ of the previous number, possibly rounding up to the nearest integer.
$60/3=20$.  Then $20/3 \approx 7$.  Then $7/3\approx 3$.  Then $3/3=1$.  The number of times you can divide by 3 is the number of 3s you need to multiply to get 60, i.e. it's the base-3 logarithm.


TITLE: Is there a connection between the theory of motives and homotopy theory?
QUESTION [1 upvotes]: I have read that motives were designed to be the common part of the many homology theories, a way of unifying them. But as I understand it: homotopy is closely related to homology, there is only 1 homotopy theory, and homotopy groups contain more information than homology groups. Is there a relationship between motives and homotopies?

REPLY [9 votes]: In algebraic topology, there is a close relationship between stable homotopy theory and the study of (generalized) cohomology theories. Basically, all the cohomology theories become representable on the stable category of spectra and so, from the point of view of stable homotopy theory, the study of cohomology theories can be viewed as the study of their representing spectra.
More recently it has been discovered (through the work of Voevodsky and others) that there is an analogous situation in algebraic geometry.
Keywords to look up: motivic homotopy theory, $\mathbb{A}^1$-homotopy theory.
Basically, we can construct a homotopy theory for algebraic varieties and a suitable homotopy category which plays a role analogous to the stable category of spectra in topology. One thing this gives us is that it enables us to define new cohomology theories for algebraic varieties by describing their representing spectra ("motivic spectra"). For example, motivic cohomology, algebraic K-theory, and algebraic cobordism can be constructed in this way. This whole circle of ideas is closely related to recent work on motives and motivic cohomology. For example, Voevodsky's construction of a "derived category of mixed motives" is closely related to this work.
The following is a very easy-going introduction to the idea of motivic homotopy theory and is understandable even by an undergraduate:

Motivic Homotopy Theory: Lectures at a Summer School in Nordfjordeid, Norway, August 2002 by Bjørn Dundas, Marc Levine, Paul Østvær, Oliver Röndigs and Vladimir Voevodsky

It is also worth reading Voevodsky's 1998 ICM address:

Vladimir Voevodsky - A^1-homotopy theory (Proceedings of the 1998 ICM)

There is a lot more that could be said about this very interesting area of mathematics.


text:
\begin{document}

\newcommand{\blind}{0}

\title{Dual Control of Testing Errors in High-Dimensional Data Analysis}
\author{X. Jessie Jeng and Yifei Hu \\
	\vspace{0.1in}
	Department of Statistics, North Carolina State University}

\if0\blind
{
	\title{\bf
		High-Dimensional Inference for Unidentifiable Signals with False Negative Control
		\thanks{Address for correspondence: X. Jessie Jeng, Department of Statistics, North Carolina State University, SAS Hall, 2311 Stinson Dr., Raleigh, NC 27695-8203, USA. E-mail: xjjeng@ncsu.edu.
		}\hspace{.2cm}}
	\author{X. Jessie Jeng and Yifei Hu \\
		Department of Statistics, North Carolina State University\\
	}
	\maketitle
} \fi

\if1\blind
{
	\bigskip
	\bigskip
	\bigskip
	\begin{center}
		{\LARGE\bf Dual Control of Testing Errors in High-Dimensional Data Analysis \\}
	\end{center}
	\medskip
} \fi

\begin{abstract}
False negative errors are of major concern in applications where missing a high proportion of true signals may cause serious consequences.  False negative control, however, raises a bottleneck challenge in high-dimensional inference when signals are not identifiable at individual levels. We develop a new analytic framework to regulate false negative errors under measures tailored towards modern applications with high-dimensional data. A new method is proposed in realistic settings with arbitrary covariance dependence between variables.
We explicate the joint effects of covariance dependence and signal sparsity on the new method and interpret the results using a phase diagram. It shows that signals that are not individually identifiable can be effectively retained by the proposed method without incurring excessive false positives.
Simulation studies are conducted to compare the new method with several existing methods.
The new method outperforms the others in adapting to a user-specified false negative control level.
We apply the new method to analyze an fMRI dataset to locate voxels that are functionally relevant to saccadic eye movements. The new method exhibits a nice balance in retaining signal voxels and avoiding excessive noise voxels.

\medskip

\textit{Keywords}: False negative proportion; Signal proportion estimation; Sparse signal;  Unnecessary false positives

\end{abstract}

\section{Introduction}

False negative errors are of major concern in applications where missing true signals may cause serious consequences. For example, failures to detect active cases of highly contagious diseases may cause delayed treatment and large-scale epidemic spreading.
More examples in medical, psychological, economic, and legal studies can be found in \cite{petticrew2000false}. In modern applications with high-dimensional data, false negative control is a pressing challenge as finding true signals are often as difficult as finding needles in a haystack.

In the past decade, significant contributions have been made towards two foundational challenges in high-dimensional sparse inference. One is the detection of mixture models, which addresses the problem of ``detecting" the existence of sparse signals without specifying their exact locations. The second is the identification of sparse signals, which considers the problem of ``identifying" signals at individual levels.
Figure \ref{fig:phase} modified from \cite{donoho2015special} illustrates the theoretical demarcation on the difficulty levels of these two problems in the setting where all variables are independent and signal variables are relatively sparse compared to the number of noise variables. Given a sparsity level, signal intensity needs to be large enough (above the undetectable region) for the signals to be detectable by a global testing procedure. For the signals to be identifiable at individual levels with multiple testing, signal intensity needs to be even larger (entering the identifiable region). It can be seen that signals in the middle region of Figure \ref{fig:phase} can only be detected for their existence by global testing but are not identifiable at individual levels using multiple testing. Such signals commonly exist in high-dimensional data analysis and play vital roles in modern applications. Providing the capacity for retaining such signals can alleviate critical issues such as missing important signals in underpowered studies and lack of replicability across multiple samples.  Despite its importance, how to effectively retain detectable yet unidentifiable signals raises a bottleneck challenge. New developments are needed to expand the frontier of
high-dimensional sparse inference  and bridge the methodological gap.
\begin{figure}[!h]
	\centering
	\includegraphics[height = 0.33\textwidth]{plot/phase}
	\caption{Phase diagram for signal detection
		and identification under independence. Signals in the middle region are only detectable for their existence but not identifiable at individual levels.} \label{fig:phase}
\end{figure}

In this paper, we propose a novel analytic framework to regulate false negative errors under measures tailored towards modern applications with high-dimensional data. More specifically, the method controls the false negative proportion (FNP $=$ number of false negatives/number of alternative cases)  at a user-specified level and, at the same time, regulates the amount of unnecessary false positives to achieve the FNP level.
We have found that, in real data analyses, researchers often
have different tolerance levels for false negative errors depending on their scientific inquiries. Our procedure estimates and controls FNP at a user-specified level under conditions weak enough to allow for unidentifiable signals.
Moreover, its adaptivity to a given FNP level, such as $0.1$, allows the method to exclude a certain amount of the weakest signals to reduce possibly a large number of false positives.

The new method is developed in the realistic setting with arbitrary covariance dependence between variables.
We propose to calibrate the overall dependence strength through a parameter whose scale is compatible with the existing parameter space in high-dimensional sparse inference. Utilizing the new calibration, we are able to explicate the joint effect of covariance dependence and signal sparsity on the new method and interpret the results using a new phase diagram, which extends the phase diagram in \autoref{fig:phase} to include dependence effect.
Our theoretical findings are supported in simulation examples where the data are generated under various dependence structures.

Extensive simulation studies are conducted to compare the new method with existing methods in both one-dimensional and two-dimensional examples. The new method outperforms the others in adapting to a user-specified FNP control level.
We apply the new method to analyze fMRI data from the saccade experiment in the Individual Brain Charting project \citep{pinho2018individual}. Compared to the other methods, results of the new method exhibit a nice balance in identifying brain regions that are functionally relevant to saccadic eye movement and avoiding the scattered or isolated voxels that are not functionally relevant to saccades.

The rest of the paper is organized as follows. \autoref{sec:method} introduces the new method and justify its FNP control property in theory. \autoref{sec:example_1d} provides several illustrative examples under different dependence structures. The proposed method with the estimated number of signals is studied in \autoref{sec:estimatedS}, and additional simulation examples are presented in \autoref{sec:simulation}. \autoref{sec:application} applies the new method to fMRI data analysis. \autoref{sec:conclusion} provides conclusion and further discussion. All the technical proofs are presented in the Appendix.

\section{Method and Theory} \label{sec:method}

We consider a model with continuous null distribution $F_0$.
Suppose that the test statistics
\begin{equation*}
X_j \sim F_0 \cdot1\{j\in I_0\}+ F_j \cdot1\{j\in I_1\}, \qquad j=1,...,p,
\end{equation*}
where $I_0$ is the set of indices for noise variables, $I_1$ is the set of indices for signal variables, and $F_j$ are the signal distributions.
All $I_0$, $I_1$, and $F_j$ are unknown. One can perform inverse normal transformation as $Z_j = \Phi^{-1}(F_0(X_j))$, where $\Phi^{-1}$ is the inverse of the standard normal cumulative distribution. Then, we have
\begin{equation} \label{def:model}
Z_j \sim \Phi \cdot1\{j\in I_0\}+ G_j \cdot1\{j\in I_1\}, \qquad j=1,...,p,
\end{equation}
where $G_j$ are the unknown signal distributions after the transformation. For presentation simplicity,  we assume that
$G_j(t) < \Phi(t)$ for all $t \in \mathbb{R}$. i.e., signal variables tend to show larger values than noise variables. This assumption can be easily generalized to signals with two-sided effects.

Consider a selection rule with threshold $t$. Define the numbers of selected cases, false positives, and false negatives as
\[
\text{R}(t)=\sum_{j=1}^p1_{\{z_j>t\}}, \quad \text{FP}(t)=\sum_{j\in I_0}1_{\{z_j>t\}}, \quad  \text{FN}(t)=\sum_{j\in I_1}1_{\{z_j\leq t\}}.
\]
Note that R$(t)$ can be directly observed from the data. FN$(t)$ and FP$(t)$ are unknown because $I_0$ and $I_1$ are unknown.
A generalization to two-sided signal effects can be accommodated by replacing $z_j$ with $|z_j|$ and only allowing $t>0$.
Next, define FNP with respect to $t$ as
\begin{equation} \label{def:FNP(t)}
    \text{FNP}(t)=\text{FN}(t)/s,
\end{equation}
where $s$ denotes the number of signal variables, i.e. $s =|I_1|$. FNP$(t)$ may be regarded as the empirical type II error that is non-decreasing with respect to $t$.

\subsection{Estimation of False Negative Proportion} \label{sec:estimation}

The new method is based on consistent estimation of FNP. By the fact that $s = \text{FN}(t)+ \text{TP}(t)$ and R$(t) = \text{FP}(t) + \text{TP}(t)$, we have
\begin{equation} \label{def:FNP}
\text{FNP}(t)= \text{FN}(t)/s= 1- (\text{R}(t)-\text{FP}(t))/s,
\end{equation}
where R$(t)$ is directly observable from the data. Because the noise distribution of $Z_j$ is $N(0,1)$ and there are $p-s$ noise variables, FP$(t)$ can be approximated by its mean value $E(\text{FP}(t)) = (p-s) \bar \Phi(t)$, where $\bar{\Phi}(t)=1- \Phi(t)$. For illustration purpose, we first assume that the true value of $s$ is known and construct an estimator for FNP$(t)$ as
\begin{equation} \label{def:hatFNP}
\widehat{\text{FNP}}(t)= \max\{1-\text{R}(t)/s+ (p-s) \bar{\Phi}(t)/s, ~0\}.
\end{equation}
$\widehat{\text{FNP}}(t)$ with an estimated $s$ will be discussed in \autoref{sec:estimatedS}.
Note that $\widehat{\text{FNP}}(t)$ is not the mean value of $\text{FNP}(t)$, and its construction does not require information of the signal distribution $G$. If two-sided signal effects are under consideration, we can simply modify $\widehat{\text{FNP}}(t)$ by replacing $(p-s)$ with $2(p-s)$.

Next, we study the estimation consistency of $\widehat{\text{FNP}}(t)$. It is a challenging problem because the denominator $s$ is often much smaller than $p$, which can explode the scale of the ratio and hence the approximation error. This causes fundamental differences in analyzing the consistency of FNP estimation and FDP estimation.
Specifically, we adopt the existing calibration in sparse inference for $s$ as
\begin{equation} \label{def:beta}
s = s_p = p^{1-\gamma}, \qquad \gamma \in (0, 1].
\end{equation}
It can be seen that when $\gamma >0$, $s$ is of a smaller order than the data dimension $p$, and when $\gamma=1$, the number of signals does not change with $p$.

We are particularly interested in FNP estimation under general covariance dependence. To this end, we assume that
\begin{equation} \label{def:multiNorm}
(Z_1, \ldots, Z_p) \sim N_p(\mu, \mathbf{\Sigma}),
\end{equation}
where $\mu$ is a p-dimensional vector with $\mu_j= A_j \cdot 1\{j\in I_1\}$, $A_j > 0$, and $\mathbf{\Sigma}$ is an arbitrary correlation matrix. Define
\begin{equation*}
\bar{\rho}=\lVert\mathbf{\Sigma}\rVert_1/p^2,
\end{equation*}
where $\lVert\mathbf{\Sigma}\rVert_1 = \sum_{ij} |\sigma_{ij}|$. In high-dimensional data analysis with large $p$, $\bar \rho$ is often very close to zero because not every variable is correlated to all the other variables. For example, $\bar \rho$ of the $\mathbf{\Sigma}_{p \times p}$ from an autoregressive model has the order of $p^{-1}$. In order to  calibrate the dependence effect in a scale that is compatible with the existing parameter space in sparse inference, we introduce parameter $\eta$ through the following re-parameterization:
\begin{equation} \label{def:eta}
\bar \rho = \bar \rho_p = p^{-\eta} , \qquad \eta \in [0, 1].
\end{equation}
The parameter $\eta$ is in a constant scale and decreases with $\bar \rho$. $\eta=0$ corresponds to the extremely dependent case where every variable is correlated to all the other variables, and, at the opposite end, $\eta=1$ corresponds to the independent case.

With $\gamma$ and $\eta$ representing signal sparsity and overall strength of covariance dependence, respectively, we discover a lower bound of $t$ for the estimation consistency of $\widehat{\text{FNP}}(t)$, which is presented as follows:
\begin{equation} \label{def:t_min}
\mu_{min}= \min\{\mu_1, ~\mu_2\},
\end{equation}
where
\[
\mu_1 = \sqrt{2\gamma \log{p}} \qquad \text{and} \qquad \mu_2 = \sqrt{(4\gamma-2\eta)_{+} \log{p} + 4 \log \log p}.
\]
The lower bound $\mu_{min}$ takes the value of either $\mu_1$ or $\mu_2$, depending on whichever is lower. It can be seen that $\mu_2<\mu_1$ when $\eta$ is large enough or, in other words, when covariance dependence is weak enough. As dependence gets stronger and $\eta$ gets smaller, $\mu_1< \mu_2$ and the lower bound equals to $\mu_1$ and stops to change with $\eta$. The term $\log\log p$ is a technical term for asymptotic analysis.
We have the following theorem to summarize the estimation result.

\begin{theorem} \label{lemma:consistency}
Consider model (\ref{def:multiNorm}). When $t \ge \mu_{min}$, where $\mu_{min}$ is defined in (\ref{def:t_min}), $\widehat{\text{FNP}}(t)$ constructed in (\ref{def:hatFNP}) consistently estimates $\text{FNP}(t)$, i.e.
\begin{equation} \label{eq:consistency}
  |\widehat{\text{FNP}}(t) - \text{FNP}(t)|=o_P(1).
\end{equation}
\end{theorem}
One can see that the consistency of $\widehat{\text{FNP}}(t)$ is achieved with $t$ increasing with $p$ in a $\sqrt{\log p}$ scale. This is substantially different from the analysis in FDR studies, where the consistency of FDR/FDP estimation is studied with $t$ as a constant.
The result explicates the interesting relationship between covariance dependence ($\eta$) and signal sparsity ($\gamma$) in determining the consistency of $\widehat{\text{FNP}}(t)$ for varying $t$.

\subsection{Controlling FNP at a User-Specified Level} \label{sec:FNPcontrol}

In real studies, researchers may have different tolerance levels for false negative errors. The proposed method allows a user-specified control level on FNP and efficiently selects a subset of candidates to achieve the control level.
Moreover, its adaptivity to a pre-specified low FNP level, such as $0.1$, allows the method to exclude a small percent of the weakest signals to reduce possibly a large number of false positives.

Our method is constructed based on the estimator $\widehat{\text{FNP}}$ developed in Section \ref{sec:estimation}. Given a user-specified constant $\beta (>0)$, we determine the selection threshold as
\begin{equation} \label{def:hat_t}
\hat{t}(\beta)=\sup{\{t:\widehat{\text{FNP}}(t) < \beta\}},
\end{equation}
and select all the candidates with $z_j > \hat t (\beta)$. We refer to this procedure as a dual control method.
It can been seen that when all variables are ranked such that $z_{(1)} \ge z_{(2)} \ge \ldots \ge z_{(p)}$, the dual control method selects the smallest subsets from the top whose estimated FNP is less than $\beta$.
If two-sided signal effects are considered, all candidates with $|z_j| > \hat t (\beta)$ will be selected.

The following theorem presents the dual control property of the proposed method which is to regulate both the FNP at a pre-specified $\beta$ level and the associated false positives.

\begin{theorem}\label{thm:FNPcontrol}
Consider model (\ref{def:multiNorm}) and a user-specified control level $\beta$ of FNP. Assume $A_j - \mu_{min} \to \infty, \forall j \in I_1$, where $\mu_{min}$ is defined in (\ref{def:t_min}), then the dual control method with threshold $\hat{t}(\beta)$ efficiently controls the true FNP at the level of $\beta$, i.e.,
\begin{equation} \label{eq:FNPcontrol_1}
    P(\text{FNP}(\hat{t}(\beta)) \le \beta)\rightarrow 1,
\end{equation}
and, for any smaller set of variables associated with threshold $\tilde{t} > \hat{t}(\beta)$,
\begin{equation} \label{eq:FNPcontrol_2}
P\{\text{FNP}(\Tilde{t})>\beta -\delta) \rightarrow 1
\end{equation}
for arbitrarily small constant $\delta>0$.
\end{theorem}

\autoref{thm:FNPcontrol} shows efficiency of the dual control method in selecting the smallest subset of variables to achieve FNP control at the $\beta$ level. In other words, the method does not incur unnecessary false positives to achieve the FNP control level.
The condition on signal intensity ($A_j$) specifies the joint effect of covariance dependence and signal sparsity on the dual control method.
Recall $\mu_{min} = \min\{\mu_1, \mu_2\}$, where $\mu_1$ only relies on signal sparsity ($\gamma$), and $\mu_2$ replies on both signal sparsity  ($\gamma$) and covariance dependence ($\eta$). The condition says that the difficulty of dual control increases as dependence gets stronger, but only to a certain degree that depends on the signal sparsity.

The parameterization of covariance dependence through $\eta$ allows us to present the signal intensity condition using a phase diagram similar to \autoref{fig:phase}. More specifically, let $\min_{j \in I_1} A_j = \sqrt{2 r \log p}$, $r > 0$. The condition on $A_j$ in \autoref{thm:FNPcontrol} can be transformed to $r > \min\{\gamma, ~2\gamma - \eta\}$ and demonstrated in a two-dimensional phase diagram with $\gamma$ as the x axis and $r$ as the y axis. The lower bound  $\min\{\gamma, ~2\gamma - \eta\}$  is illustrated in \autoref{fig:phase_fnp} by the red solid line that moves with the dependence parameter $\eta$. Signals in the area above the red solid line can be efficiently retained by the dual control method at a pre-specified level. Recall \autoref{fig:phase}, which implies that under independence, signals in the region between the two dashed lines are only detectable for their existence but not identifiable at individual levels. The special case of our results under independence ($\eta =1$) shows that many of the unidentifiable signals can be efficiently retained by the new method.

\begin{figure}[!h]
	\centering
	\includegraphics[height = 0.5\textwidth, width=0.5\textwidth]{plot/phase_fnp}
	\caption{Dual control region under covariance dependence. Signals in the area above a solid red line can be retained by the dual control method at a pre-specified FNP level. The area increases with $\eta$ as the dependence get weaker. } \label{fig:phase_fnp}
\end{figure}

\section{Examples} \label{sec:example_1d}

In this section, we present simulation examples with different dependence structures to illustrate the performance of the new method. We first evaluate the estimator $\widehat{\text{FNP}}(t)$ from (\ref{def:hatFNP}), then demonstrate finite sample results of the dual control method.
These examples help understand the foundation of the new method. Additional simulation studies are provided in \autoref{sec:simulation}.

We generate a series of test statistics
\begin{equation} \label{eq:Z}
(Z_1, \ldots, Z_p)^T \sim N((\mu_1, \ldots, \mu_p)^T, \mathbf{\Sigma}),
\end{equation}
where $p=2000$, $\mu_j = A \cdot 1\{j \in I_1\}$, and $I_1$ is a set of indices randomly sampled from $\{1,..., p\}$ with cardinality $s = |I_1| = p^{1-\gamma}$. We set $\gamma = 0.3$, which corresponds to $s=205$, i.e. there are 205 signal variables with elevated mean values randomly located among 1795 noise variables. The signal intensity varies with $A=3$ and 2. . We consider three different dependence structures:
\begin{itemize}
	\item Model 1 [Autoregressive]: $\mathbf{\Sigma}=(\sigma^{(1)}_{ij})$, where $\sigma^{(1)}_{ij}=\lambda^{|i-j|}$ for $1\leq i,j\leq p$.
	\item Model 2 [Block dependence]: $\mathbf{\Sigma}=\mathbf{I}_{p/k}\otimes\mathbf{D}$, where $\mathbf{D}$ is a $k\times k$ matrix with diagonal entries 1 and off-diagonal entries $r$.
	\item Model 3 [Factor model]: $\mathbf{\Sigma}=(\sigma^{(3)}_{ij})$, where $\sigma^{(3)}_{ij}=V_{ij}/\sqrt{V_{ii}V_{jj}}$ for $1\leq i,j\leq p$, $\mathbf{V}=\tau\mathbf{h}\mathbf{h}^T+\mathbf{I}_p$ with $\tau \in (0, 1)$ and $\mathbf{h}\sim N(\mathbf{0}, \mathbf{I}_p)$.
\end{itemize}

In this section, we set $\lambda=0.2, k=40, r=0.5$, and $\tau=0.5$, so that the dependence parameter $\eta$ decreases from 0.95 in Model 1 to 0.57 in Model 2 to 0.23 in Model 3. Correspondingly, dependence among test statistics increases from very weak in Model 1 to moderately strong in Model 2 to very strong in Model 3.

It has been derived in \autoref{sec:estimation} that $\mu_{min}$, as the boundary value  for estimation consistency, is the minimum of $\mu_1$ and $\mu_2$, where $\mu_1$ depends on signal sparsity through $\gamma$ and $\mu_2$ depends on both signal sparsity and dependence through $\gamma$ and $\eta$.
In these examples, $(\mu_1=2.14, \mu_2=1.69)$ for Model 1,  $(\mu_1=2.14, \mu_2=2.92)$ for Model 2, and $(\mu_1=2.14, \mu_2=3.69)$ for Model 3. Consequently, $\mu_{min} = 1.69$ for Model 1 but remains the same at $2.14$ for Model 2 and 3. These values of $\mu_{min}$ are illustrated as the solid vertical lines in \autoref{fig:approx}. The dotted vertical lines represent $\mu_1$ or $\mu_2$ whichever is larger.
The dotted curves represent the absolute difference between the estimated $\widehat{\text{FNP}}(t)$ and the true FNP$(t)$ from 100 replications.

It can be seen  that the estimation accuracy of $\widehat{\text{FNP}}(t)$ increases with $t$, and the majority of the replicated differences are close to $0$ after passing $\mu_{min}$, which support $\mu_{min}$ as the boundary value for estimation consistency under very different dependence structures.

\begin{figure}[!h]
	\centering
	\includegraphics[height = 0.31\textwidth]{plot/diff_auto}
	\includegraphics[height = 0.31\textwidth]{plot/diff_block}
	\includegraphics[height = 0.31\textwidth]{plot/diff_factor}
	\caption{Estimation accuracy of $\widehat{\text{FNP}}(t)$ based on 100 replications. Plots from left to right are generated under Model 1 - 3. The solid vertical lines represent the boundary value $\mu_{min} = \min\{\mu_1, \mu_2\}$. Model 1 has very weak dependence with $\eta = 0.95$ and $\mu_{min}= \mu_2 = 1.69$. Model 2 has moderately strong dependence with $\eta = 0.57$ and $\mu_{min}= \mu_1 = 2.14$. Model 3 has very strong dependence with $\eta = 0.23$ and $\mu_{min}= \mu_1 = 2.14$.} \label{fig:approx}
\end{figure}

Next, we demonstrate the finite sample performance of the dual control method, which is denoted as DCOE (acronym for Dual Control Of Errors)
in \autoref{tab:compare}. We present the mean values and standard deviations of the realized FNP of DCOE with different $\beta$ levels from 100 replications.
The results of DCOE are compared with those of the classical BH-FDR procedure \citep{benjamini1995} with different nominal levels. For illustrative purposes, we also present the mean values of the realized false discovery proportion (FDP) of the two methods.

\begin{table}[!h]
	\caption{Mean values and standard deviations (in brackets) of the realized FNP and FDP of the proposed DCOE method with different nominal levels and the existing BH-FDR procedure with different nominal levels.
	} \label{tab:compare}
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{ll l| c c }

			& & & FNP & FDP   \\
			\hline
			A=3 & Autoregressive & DCOE(${\bf \beta= 0.2}$) & {\bf 0.198} (0.023) &  0.149 (0.035) \\
			& & DCOE($\beta={\bf 0.1}$) & {\bf 0.101} (0.037)  & 0.307 (0.084) \\

			& & BH-FDR($\alpha={\bf 0.05}$) & 0.378 (0.040)  & {\bf 0.044} (0.018) \\
			& & BH-FDR($\alpha={\bf 0.2}$) & 0.166 (0.028) & {\bf 0.183} (0.028) \\
			\cline{2-5}
			& Block dependence & DCOE($\beta={\bf 0.2}$) & {\bf 0.170} (0.086) & 0.259 (0.247) \\
			& & DCOE($\beta={\bf 0.1}$) & {\bf 0.089} (0.074) & 0.444 (0.268) \\
			& & BH-FDR($\alpha={\bf 0.05}$) & 0.387 (0.071) & {\bf 0.047} (0.036) \\
			& & BH-FDR($\alpha={\bf 0.2}$) & 0.169 (0.049)  & {\bf 0.180} (0.070) \\
			\cline{2-5}
			& Factor model & DCOE($\beta={\bf 0.2}$) & {\bf 0.160} (0.099) &  0.262 (0.215) \\
			& & DCOE($\beta={\bf 0.1}$) & {\bf 0.084} (0.104) &  0.533 (0.227) \\

			& & BH-FDR($\alpha={\bf 0.05}$) & 0.400 (0.043) & {\bf 0.041} (0.049) \\
			& & BH-FDR($\alpha={\bf 0.2}$) & 0.176 (0.049)  & {\bf 0.170} (0.113) \\
			\hline
			\hline
				A=2 & Autoregressive & DCOE(${\bf \beta= 0.2}$) & {\bf 0.201} (0.069) & 0.576  (0.073) \\
				& & DCOE($\beta={\bf 0.1}$) & {\bf 0.114} (0.069)  & 0.688 (0.085) \\
				& & BH-FDR($\alpha={\bf 0.05}$) & 0.889 (0.035)  & {\bf 0.040} (0.043) \\
				& & BH-FDR($\alpha={\bf 0.2}$) & 0.630 (0.050)  & {\bf 0.181} (0.044) \\
				\cline{2-5}
				& Block dependence & DCOE($\beta={\bf 0.2}$) & {\bf 0.193} (0.132)  & 0.607 (0.161) \\
				& & DCOE($\beta={\bf 0.1}$) & {\bf 0.132} (0.116) & 0.685 (0.152) \\
				& & BH-FDR($\alpha={\bf 0.05}$) & 0.894 (0.058)  & {\bf 0.055} (0.070) \\
				& & BH-FDR($\alpha={\bf 0.2}$) & 0.647 (0.097)  & {\bf 0.182} (0.093) \\
				\cline{2-5}
				& Factor model & DCOE($\beta={\bf 0.2}$) & {\bf 0.188} (0.169) &  0.642 (0.107) \\
				& & DCOE($\beta={\bf 0.1}$) & {\bf 0.156} (0.159) & 0.693 (0.098) \\
				& & BH-FDR($\alpha={\bf 0.05}$) & 0.886 (0.088) & {\bf 0.032} (0.061) \\
				& & BH-FDR($\alpha={\bf 0.2}$) & 0.659 (0.088)  & {\bf 0.160} (0.123) \\
				\hline
		\end{tabular}}
	\end{table}

It can be seen that for Model 1 [Autoregressive], the mean values of FNP for DCOE with $\beta=0.2$ and $0.1$ are  fairly close to their corresponding nominal levels. Specifically, when $A=3$  we have 0.198 and 0.101 respectively, and when $A=2$, we have 0.201 and 0.114 respectively.

In the more challenging cases generated by Model 2 [Block dependence] and 3 [Factor model], the boundary value $\mu_{min}$ required for estimation consistency increases from $1.69$ to $2.14$; and the differences between realized FNPs of DCOE and the nominal levels increase slightly.
These observations agree with the theoretical results in Sections \ref{sec:FNPcontrol}.

For illustrative purposes, we also present the results of the classical BH-FDR procedure. The nominal levels of BH-FDR are set at $\alpha = 0.05$ and $0.2$. \autoref{tab:compare} shows that the mean values of the realized FDP of BH-FDR are fairly close to their corresponding nominal levels of $\alpha$.
However, the mean values of FNP for BH-FDR are generally larger than those of DCOE, especially when signal intensity is relatively weak. It is true that one can always increase the nominal level of BH-FDR to reduce FNP, but it is unclear by how much we should increase $\alpha$ to achieve a target level of FNP. For example, when $A=3$, BH-FDR with $\alpha=0.2$ has the mean values of FNP in the range of 0.166-0.176 for the three dependence models, which seem to be comparable to the FNP range of DCOE with $\beta=0.2$.
However, when $A=2$, BH-FDR with $\alpha=0.2$ has much bigger mean values of FNPs in the range of 0.63 - 0.66.

These results demonstrate the fundamental differences between multiple testing procedures and the proposed dual control method as they serve for very different purposes. The proposed method aims to retain more signals with a target FNP level, for which the multiple testing methods cannot achieve. On the other hand, the new method pays the price of having a higher FDP. Additional simulation examples illustrating the efficiency of the new method compared to other false negative control methods are presented in Section \ref{sec:simulation}

\section{FNP control with estimated number of signals} \label{sec:estimatedS}

Implementation of the new method requires information of the number of signals ($s$) which, in real applications, is often unknown. Existing studies for the estimation of $s$ usually assume independence among variables \citep{GW04, MR06, cai2007estimation, cai2010optimal}, and most of them are for relatively dense signals. We are interested in finding an estimator of $s$ that works in our setting with arbitrary covariance dependence. Recent study in \cite{jeng2021estimating} introduces an estimator for the signal proportion $\pi (= s/p)$ with the form $\hat \pi_{} = \max\{\hat \pi_\delta, \delta \in \Delta\}$, where $\Delta$ is a set of functions that render the most powerful consistent estimators
in a family of estimators under different dependence scenarios. More specifically, the family of estimators are defined as
\begin{equation} \label{def:MR}
\hat{\pi}_{\delta}=\sup_{t > 0}{\frac{ R(t)/p-2\bar{\Phi}(t)-c_{p, \delta}\delta \left( t\right) }{1-2\bar{\Phi}(t)}},
\end{equation}
where $\delta(t)$ is a strictly positive function on $(0, \infty)$ and
$c_{p, \delta}$ is its corresponding bounding sequence. It is discovered that  $\delta(t) = [\bar \Phi(t)]^{1/2}$ and $\delta(t) =\bar \Phi(t)$ result in powerful $\hat{\pi}_{\delta}$ under different dependence scenarios, and a new estimator is developed as
\begin{equation} \label{def:_pi}
\hat \pi_{} = \max\{\hat \pi_{0.5}, \hat \pi_{1}\},
\end{equation}
where $\hat \pi_{0.5}$ denotes $\hat \pi_{\delta}$ with $\delta = [\bar \Phi(t)]^{1/2}$, and $\hat \pi_{1}$ denotes $\hat \pi_{\delta}$ with $\delta = \bar \Phi(t)$. Details about the selection of  $\delta(t)$, the construction of $c_{p, \delta}$, and the properties of  $\hat{\pi}_{\delta}$ and $\hat \pi_{}$ can be found in \cite{jeng2021estimating}.

We extend the results in \cite{jeng2021estimating} to our setting with $\gamma$ and $\eta$ representing signal sparsity and overall covariance strength, respectively, so that the conditions for the consistency of  $\hat \pi_{}$ and the conditions for the FNP control of our proposed method can be unified. Because the theoretical analysis in \cite{jeng2021estimating} is conducted on a discretized version ($\hat \pi_{\delta}^*$) of $\hat \pi_{\delta}$, which is defined by replacing $\sup_{t>0}$ in (\ref{def:MR}) with $\max_{t \in \mathbb{T}}$, where $\mathbb{T} = [1, \sqrt{5 \log p}] \cap \mathbb{N}$, we present the unified conditions for the discretized version of  $\hat \pi_{}$ as well and define it as  $\hat \pi_{}^* = \max\{\hat \pi^*_{0.5}, \hat \pi^*_{1}\}$.

\begin{proposition} \label{prop:estimated_s}
	Assume the same conditions as in Theorem \ref{thm:FNPcontrol}.
	Then, for any constant $\epsilon>0$,
	\begin{equation} \label{eq:hat_pi}
	P((1-\epsilon) < \hat \pi_{}^*/\pi  < 1)\rightarrow 1.
	\end{equation}
	Replace $s$ in (\ref{def:hat_t}) with the estimator $\hat s = p \cdot \hat \pi_{}^*$ and denote the selection threshold as $\hat t_{\hat s}(\beta)$. We have
	\begin{equation} \label{eq:FNPcontrol_1s}
	P(\text{FNP}(\hat{t}_{\hat s}(\beta)) \le \beta)\rightarrow 1
	\end{equation}
	and, for any threshold $\tilde{t} > \hat{t}_{\hat s}(\beta)$,
	\begin{equation} \label{eq:FNPcontrol_2s}
	P\{\text{FNP}(\Tilde{t})>\beta -\delta) \rightarrow 1
	\end{equation}
	for arbitrarily small constant $\delta>0$.
\end{proposition}

\autoref{prop:estimated_s} shows that the same set of conditions are sufficient for both the consistency of $\hat \pi_{}^*$ and the efficient FNP control of the proposed method implemented with $\hat \pi_{}^*$. This result can also be interpreted by the phase diagram in \autoref{fig:phase_fnp}, where the solid red line that moves with the dependence level $\eta$ now indicates the required signal intensity for both $s$ estimation and FNP control. In other words, for signals above the solid red line, although they may not be individually identifiable,
we can still perform meaningful inference by not only estimating their total numbers but also effectively retaining them at a target FNP level.

Generally speaking, if we want to derive information of sparse signals from a dataset, a condition on the signal intensity is unfortunately unavoidable. When signal intensity is too low, no methods can even detect their existence \citep{donoho2004higher, arias2011global, tony2011optimal}, let along the more challenging tasks of FNP estimation and control.
When the condition on signal intensity does not hold, the estimator $\hat \pi_{}$ tends to underestimate  because of its lower bound property \citep{jeng2021estimating}. Consequently, the dual control method implemented with $\hat s = p \cdot \hat{\pi}_{}$ tends to have a threshold higher than the ideal threshold that achieves the target level of $\beta$, which results in conservative variable selection with inflated FNP and correspondingly less false positives. This tendency is observed in simulation examples with low signal-to-noise ratio in \autoref{sec:simulation-1D}.

We conclude the section with numerical algorithms to calculate the bounding sequence $c_{p, \delta}$ and the proportion estimator $\hat \pi$ in (\ref{def:MR}), and to select variables by the dual control method.

\begin{algorithm}[H]
	\caption{Bounding Sequence $c_{p, \delta}$}\label{alg}
	\begin{algorithmic}[1]
		\Statex {\bf Input:} N sets of $\{w_1, \ldots, w_p\}$ generated by the joint null distribution of $\{z_1, \ldots z_p\}$
		\Statex {\bf Output:} bounding sequences $c_{p, 0.5}$ and $c_{p, 1}$
		\State {\bf for} $a=1, 2\ldots, N$ {\bf do}
		\Statex Rank the $a$-th set of $\{w_1, \ldots, w_p\}$ such that $w_{(1)} > w_{(2)} > \ldots > w_{(p)}$
		\Statex Compute
		\[
		V_{0.5, a} = \max_{1 \le j \le p} {|j / p - \bar \Phi(w_{(j)})| \over \sqrt{\bar \Phi(w_{(j)})}} \qquad \text{and} \qquad V_{1, a} = \max_{1 \le j \le p} {|j / p - \bar \Phi(w_{(j)})| \over \bar \Phi(w_{(j)})}
		\]
		\State {\bf end for}
		\State Compute $c_{p, 0.5}$ and $c_{p, 1}$ as the $(1-1/\sqrt{\log p})$-th quantiles of the empirical distributions of $V_{0.5, a}$ and $V_{1, a}$, respectively
	\end{algorithmic}
\end{algorithm}

Note that the computation of  $c_{p, \delta}$ requires input of statistics generated by the joint null distribution. When the joint null distribution is unknown in  real applications, we often can simulate such statistics non-parametrically.
For example, when$\{z_1, \ldots z_p\}$ are a set of test statistics for associations between a set of explanatory variables and a response variable, we may randomly shuffling only the sample of the response variable to remove the potential associations and then calculate the test statistics.

\begin{algorithm}[H]
\caption{Signal Proportion Estimator}\label{alg}
\begin{algorithmic}[1]
\Statex {\bf Input:} test statistics $\{z_1, \ldots z_p\}$ and bounding sequences $c_{p, 0.5}$ and $c_{p, 1}$
\Statex {\bf Output:} a proportion estimate $\hat \pi$
\State Rank the variables by their test statistics so that $z_{(1)} > z_{(2)} > \ldots > z_{(p)}$
\State Compute
\[
\hat{\pi}_{0.5}= \max_{1 \le j \le p}{\frac{ j/p-\bar{\Phi}(z_{(j)})-c_{p,0.5} \sqrt{\bar \Phi(z_{(j)})}} {1-\bar{\Phi}(z_{(j)})}} \qquad \text{and} \qquad \hat{\pi}_{1}= \max_{1 \le j \le p}{\frac{ j/p-\bar{\Phi}(z_{(j)})-c_{p,1} \bar \Phi(z_{(j)})} {1-\bar{\Phi}(z_{(j)})}}
\]
\State Obtain $\hat \pi = \max\{\hat{\pi}_{0.5}, \hat{\pi}_{1}\}$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[H]
\caption{Dual Control Procedure }\label{alg}
\begin{algorithmic}[1]
\Statex {\bf Input:} test statistics $z_1, \ldots z_p$, a user-specified $\beta$, and a proportion estimate $\hat \pi$
\Statex {\bf Output:} a set of selected variables
\State Rank the variables by their test statistics so that $z_{(1)} > z_{(2)} > \ldots > z_{(p)}$
\State Compute $\hat s = \hat \pi p$
\State For $j=1, 2, \ldots, p$, compute
\[
\widehat{FNP}(z_{(j)})= \max\{1 - j/\hat s + (p-\hat s) \bar \Phi(z_{(j)})/\hat s, ~0\}
\]
\State Let $k=1$
\Statex {\bf while}  $ \widehat{FNP}(z_{(k)})
	\ge \beta$ {\bf do}  $k = k+1$
\Statex {\bf end while}
\State Obtain variables ranked at $1, \ldots, k-1$
\end{algorithmic}
\end{algorithm}

\section{Simulation}  \label{sec:simulation}

In this section,  We compare the empirical performances of the new method (DCOE) with existing false negative control methods. Such methods are relatively limited and have only appeared recently.
For example, the AFNC method in \cite{jeng2016rare} was proposed to control the so-called signal missing rate to detect rare variants in genome-wide association study \citep{jeng2016rare};
the MDR method in \cite{cai2016optimal} was proposed to control the so-called missed discovery rate using an empirical Bayesian approach \citep{cai2016optimal};
the AdSMR method in \cite{jeng2019efficient} focuses on controlling a FNP-based exceedance probability; and the FNC-Reg approach in \cite{JengChen2019} considers FNP control in linear regression. Among these methods, AFCN, MDR, and FNC-Reg are more comparable to DCOE because they all require the input of a user-specified control level. However, AFNC and MDR were developed under the independent assumption, and FNC-Reg considered specific dependence and signal sparsity conditions to facilitate accurate precision matrix estimation and bias mitigation. All of these methods require estimates of the number of signals. For a fair comparison, we implement the same estimator $\hat s = p \cdot \hat \pi_{}$ to all the methods.

\subsection{One-dimensional problems} \label{sec:simulation-1D}

In this section, we generate the test statistics by (\ref{eq:Z}) with a covariance matrix that has 20 diagonal blocks with block sizes randomly generated from 10 to 100. The non-zero off-diagonal correlations are set at 0.5. The dependence parameter $\eta$ varies from sample to sample due to the random block size. In the first set of examples, signal sparsity is fixed with $\gamma = 0.3$, and signal intensity (A) increases from $3$ to $5$.
In the second set of examples, signal intensity is fixed and signal sparsity varies as $\gamma = 0.3$ and $0.5$.

The performances of the methods are evaluated by three measures. The first two measures, FNP and FDP are the same as in \autoref{tab:compare}.  The last measure is the Fowlkes-Mallows index \citep{fowlkes1983method, halkidi2001clustering}, which summarizes the measures of FNP and FDP by calculating the geometric mean of ($1-$FNP) and ($1-$FDP), i.e.,
\[
\text{FM-index} = \sqrt{(1-\text{FNP}) \times (1-\text{FDP})}.
\]
Higher values of the FM-index indicate better classification results. The FM-index is a sensible summary measure in high-dimensional settings with sparse alternative cases because the scale of its FDP component is more comparable to that of its FNP component than the classical false positive proportion (FPP = number of false positives/number of null cases). Because the methods compared in this section all focus on false negative control, it is appropriate to use FM-index to evaluate their relative efficiency.

Results of the first set of examples are summarized in \autoref{tab:compare_mu}. First, because the estimation boundary $\mu_{min}$ remains at $2.14$ in these examples, the condition $ A_j - \mu_{min} \to \infty$  in \autoref{thm:FNPcontrol} is not well supported for smaller $A_j$ ($= A$ in these examples). Also, because the estimator $\hat s$ underestimates the true $s$ when signal intensity is not strong enough, DCOE implemented with $\hat s$ selects less variables than actually needed to reach the nominal level of $\beta$. These result in inflated realized FNP as seen in \autoref{tab:compare_mu}.
Further, as $A$ increases, the mean value of FNP of DCOE gets closer to the nominal level of $\beta$, which agrees with the claims in (\ref{eq:FNPcontrol_1s}) and (\ref{eq:FNPcontrol_2s}) in \autoref{prop:estimated_s}.
Among the three methods presented in \autoref{tab:compare_mu}, DCOE shows a clear tendency to adapt to the nominal level of $\beta$ as $A$ increases, which is not observed for the other two methods. DCOE also has the lowest FNP values. In terms of the FM-index, DCOE generally outperforms the other two methods especially when signal intensity gets stronger.

\begin{table}[!h]
	\caption{Effect of signal intensity on different FN control methods with estimated s. Mean values and standard deviations (in brackets) of the realized FNP, FDP, and the FM-index are presented for the proposed DCOE method and two existing methods, AFNC and MDR from 100 replications. }\label{tab:compare_mu}
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{l c| c c c}
			& &  FNP & FDP & FM-index \\
			\hline
			$A=3$  & DCOE($\beta={\bf 0.1}$) & {\bf 0.28} (0.12) &  0.13 (0.14) & {\bf 0.78} (0.04) \\
			& AFNC($\beta={\bf 0.1}$) &  0.19 (0.11)  &  0.22 (0.18) & 0.78 (0.07) \\
		    & MDR($\beta={\bf 0.1}$) &  0.09 (0.08) & 0.49 (0.26) &  0.65 (0.15)  \\
			\hline
			$A=4$ & DCOE($\beta={\bf 0.1}$)  & {\bf 0.16} (0.07) & 0.06 (0.12) &  {\bf 0.88} (0.05) \\
			& AFNC($\beta={\bf 0.1}$) & 0.07 (0.04) &  0.14 (0.18) & 0.89 (0.10) \\
			& MDR($\beta={\bf 0.1}$) &  0.06 (0.05) & 0.37 (0.32) & 0.74 (0.18) \\
			\hline
			$A=5$ & DCOE($\beta={\bf 0.1}$) &  {\bf 0.10} (0.04)  & 0.04 (0.12)  & {\bf 0.93} (0.06) \\
			& AFNC($\beta={\bf 0.1}$) & 0.01 (0.01)  & 0.36 (0.35) & 0.75 (0.26) \\
			& MDR($\beta={\bf 0.1}$) & 0.04 (0.04) & 0.36 (0.33)  & 0.75 (0.19) \\
			\hline
		\end{tabular}}
	\end{table}

The second set of examples have $\gamma$ increased from 0.3 to 0.5, so that the number of signals deceases from 205 to 45. The nominal level of $\beta$ also varies. The signal intensity $A$ is fixed at $5$. Results summarized in \autoref{tab:compare_beta} show that when signals get sparser with larger $\gamma$, the performances of all three methods deteriorate by including more noise variables. However, DCOE continues to outperform the other two methods in adapting to different nominal levels and incurring less false positives. Its advantage seems to be more prominent when signals get more sparse.

\begin{table}[!h]
	\caption{Effect of nominal level and signal sparsity on different FN control methods with estimated s. Same notations as in \autoref{tab:compare_mu} are used. }\label{tab:compare_beta}
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{l c|ccc}
			&  & FNP & FDP & FM-index \\
			\hline
			$\gamma=0.3$   & DCOE($\beta={\bf 0.1}$) &  {\bf 0.10} (0.04)  & 0.04 (0.12)  & {\bf 0.93} (0.06) \\
			& AFNC($\beta={\bf 0.1}$)  & 0.01 (0.01)  & 0.36 (0.35) & 0.75 (0.26) \\
			& MDR($\beta={\bf 0.1}$) & 0.04 (0.04) & 0.36 (0.33)  & 0.75 (0.19) \\
			\cline{2-5}
			 & DCOE($\beta={\bf 0.2}$)  & {\bf 0.19} (0.06) & 0.02 (0.08) & {\bf 0.89} (0.03) \\
			 & AFNC($\beta={\bf 0.2}$)  & 0.01 (0.01) & 0.21 (0.29) & 0.86 (0.20) \\
			 & MDR($\beta={\bf 0.2}$)  & 0.08 (0.09) & 0.26 (0.28) & 0.80 (0.14) \\
			\hline
			$\gamma=0.5$ & DCOE($\beta={\bf 0.1}$) & {\bf 0.09} (0.05) & 0.15 (0.29) & {\bf 0.85} (0.18) \\
			& AFNC($\beta={\bf 0.1}$) & 0.00 (0.01) & 0.73 (0.28) & 0.44 (0.27) \\
			& MDR($\beta={\bf 0.1}$)  & 0.03 (0.05) & 0.56 (0.44) & 0.54 (0.34) \\
			\cline{2-5}
			& DCOE($\beta={\bf 0.2}$)  & {\bf 0.16} (0.09) & 0.12 (0.27) & {\bf 0.83} (0.15) \\
			& AFNC($\beta={\bf 0.2}$)  & 0.01 (0.02) & 0.60 (0.36) & 0.55 (0.31) \\
			& MDR($\beta={\bf 0.2}$)  & 0.07 (0.10) & 0.54 (0.45) & 0.54 (0.32) 	\\
			\hline
		\end{tabular}}
\end{table}

\vspace{-0.1in}

\subsection{A Two-dimensional example}

In this example, we simulate a $100\times 100$ two-dimensional grid graph with the signal region demonstrated in \autoref{fig:2D_signal}. The signal region covers $994$ nodes, i.e. $s=994$.
At each node, test statistic $Z_{ij}$ is generated independently from  $N(A_{ij}, 1)$, where $A_{ij} \sim$ Uniform$[1, 2.5]$ if $(i,j)$ is in the signal region, and $A_{ij}=0$ otherwise.

We apply the proposed DCOE method with different nominal levels and compare the results with those of BH-FDR, AFNC, and MDR. \autoref{fig:2D_bh} shows the selected nodes of BH-FDR with $\alpha=0.05$ in a single trial,
\autoref{fig:2D_afnc} and \autoref{fig:2D_mdr} show the results of AFNC and MDR with $\beta=0.1$, respectively, and \autoref{fig:2D_new01} and \autoref{fig:2D_new05}  show the results of DCOE with $\beta=0.1$ and $0.5$, respectively.
It can be seen that DCOE identifies more true signals and delineates the signal region better than BH-FDR even when $\beta$ is as large as $0.5$. On the other hand, it pays the price with some more false positives. Compared to AFNC and MDR, DCOE has less false positives and less true positives, which does not seem to impair its ability to delineate the signal region much.

 \begin{figure} [!h]
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_signal}
 		\caption{Pure Signals}
 		\label{fig:2D_signal}
 	\end{subfigure}
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_bh}
 		\caption{BH-FDR($\alpha=0.05$)}
 		\label{fig:2D_bh}
 	\end{subfigure}
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_afnc.png}
 		\caption{AFNC($\beta=0.1$)}
 		\label{fig:2D_afnc}
 	\end{subfigure}
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_mdr.png}
 		\caption{MDR($\beta=0.1$)}
 		\label{fig:2D_mdr}
 	\end{subfigure}
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_new01.png}
 		\caption{DCOE($\beta=0.1$)}
 		\label{fig:2D_new01}
 	\end{subfigure}
 	\begin{subfigure}{.55\textwidth}
 		\centering
 		\includegraphics[width=.8\linewidth]{plot/2d_new05.png}
 		\caption{DCOE($\beta=0.5$)}
 		\label{fig:2D_new05}
 	\end{subfigure}
 \caption{Comparison results from a single trial. The clustered signals are shown in plot (a). Plots (b) - (f) demonstrate the results of different methods. }
 \label{fig:2D}
 \end{figure}

\section{Application} \label{sec:application}

We obtained the fMRI data from the Individual Brain Charting (IBC) Project, which is a publicly available  high-resolution fMRI dataset for cognitive mapping \citep{pinho2018individual}. The dataset refers to a cohort of 12 participants performing different tasks, addressing both low- and high- level cognitive functions. We focus on the data from the saccade experiment for spatial cognition, in which ocular movements were performed according to the displacement of a fixation cross from the center toward peripheral locations in the image displayed.

The data were collected using a Gradient-Echo (GE) pulse, whole-brain Multi-Band (MB) accelerated Echo-Planar Imaging (EPI) T2$^\star$-weighted sequence with Blood-Oxygenation-Level-Dependent (BOLD) contrasts, and preprocessed using {\it PyPreprocess}, a collection of python tools for preprocessing fMRI data.  In order to assess the statistical significance of the differences among evoked BOLD responses, test statistics are computed at every voxel for each contrast using General Linear Model (GLM). All images are confined to an average mask of the gray matter across subjects, which yields 371,817 voxels at the chosen resolution. More details about the dataset can be found in \cite{pinho2018individual}.

We apply the proposed method (DCOE), the popular BH-FDR procedure, and the existing AFNC and MDR methods to the statistical maps of 12 participants. The numbers of selected voxels for each participant are reported in \autoref{tab:fmri}.
Among all the methods, BH-FDR selects the least voxels and MDR selects the most voxels. DCOE selects more than BH-FDR and less than AFNC and MDR.

\begin{table}[h]

	\caption{Numbers of selected voxels by different methods.} \label{tab:fmri}
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{c|c|c|c|c}
			\hline
			Subject
			& BH-FDR($\alpha=0.05$) & DCOE($\beta=0.1$) &
			AFNC($\beta=0.1$) & MDR($\beta=0.1$)  \\
			\hline
			\hline
			sub-1 & 18500  & 19379  & 24837  & 27793 \\
			sub-2 & 44902  & 52614  & 70981  & 78288 \\
			sub-4 & 15291  & 31852  & 44893  & 60356 \\
			sub-5 & 8623   & 23236  & 37333  & 62976 \\
			sub-6 & 17778  & 29298  & 40537  & 47812 \\
			sub-7 & 25011  & 51405  & 76931  & 88407 \\
			sub-8 & 35463  & 47467  & 65238  & 74915 \\
			sub-9 & 20846  & 35662  & 50516  & 63989 \\
			sub-11 & 28586  & 32989  & 43147 & 48892 \\
			sub-12 & 20469  & 27388  & 36256  & 38353 \\
			sub-13 & 21365  & 44094  & 63192  & 74508 \\
			sub-14 & 21067  & 58494  & 85889  & 96651 \\
			\hline
		\end{tabular}}
	\end{table}

\autoref{fig:fmri} illustrates the selected voxels of each method in the image of a single participant (sub-5) from posterior, superior, and left views. The figure is generated using the Multi-image Analysis GUI (http://ric.uthscsa.edu/mango/).
We look into several regions that are known to be associated with saccadic eye movements.
First, the visual cortex (VC) on occipital lobe in the posterior region of the brain, as indicated in \autoref{fig:fnpc_p}, is the primary cortical region that receives, integrates, and processes visual information \citep{bodis1997functional}.
We can see that all four methods have identified voxels in VC. However, the results of DCOE, AFNC and MDR seem to match the VC region much better than that of BH-FDR.
From the superior and left views, it shows that BH-FDR has only a few or no discoveries in the frontal eye fields (FEF) located in Brodmann area 8, the supplementary eye fields (SEF) located in Broadmann area 6, and the posterior parietal cortex (PPC). The locations of FEF, SEF, and PPC are indicated in \autoref{fig:fnp_s} and  \autoref{fig:fnp_l}.
FEF and SEF are believed to play important roles in visual attention and eye movements as electrical
stimulation of these areas evokes eye movements \citep{bruce1985primateI, bruce1985primateII}. PPC, on the other hand,  is related to decision making and saccades \citep{goldberg2002role, schluppeck2005topographic}.
It can be seen that DCOE, AFNC, and MDR have better power for identifying signal voxels in FEF, SEF, and PPC.
Among these three methods, DCOE selects the least scattered or isolated voxels that are not functionally relevant to saccades.

\begin{figure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FDR_p.png}
		\caption{BH-FDR (posterior)}
		\label{fig:sfig1}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FDR_s.png}
		\caption{BH-FDR (superior)}
		\label{fig:sfig2}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FDR_l.png}
		\caption{BH-FDR (left)}
		\label{fig:sfig3}
	\end{subfigure}

	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FNP_p.png}
		\caption{DCOE (posterior)}
		\label{fig:fnpc_p}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FNP_s.png}
		\caption{DCOE (superior)}
		\label{fig:fnp_s}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/FNP_l.png}
		\caption{DCOE (left)}
		\label{fig:fnp_l}
	\end{subfigure}

	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/AFNC_p.png}
		\caption{AFNC (posterior)}
		\label{fig:sfig7}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/AFNC_s.png}
		\caption{AFNC (superior)}
		\label{fig:sfig8}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/AFNC_l.png}
		\caption{AFNC (left)}
		\label{fig:sfig9}
	\end{subfigure}

	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/MDR_p.png}
		\caption{MDR (posterior)}
		\label{fig:sfig10}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/MDR_s.png}
		\caption{MDR (superior)}
		\label{fig:sfig11}
	\end{subfigure}
	\begin{subfigure}{.32\textwidth}
		\centering
		\includegraphics[width=.8\linewidth]{plot/MDR_l.png}
		\caption{MDR (left)}
		\label{fig:sfig12}
	\end{subfigure}
	\caption{The selected voxels from BH-FDR, DCOE, AFNC, and MDR for a single participant (sub-05).}
	\label{fig:fmri}
\end{figure}

\section{Conclusion and Discussion} \label{sec:conclusion}

In this paper, we develop a new analytic framework to perform inference on signals that are detectable yet unidentifiable. A new dual control method is proposed to control FNP at a user-specified level and, at the same time, regulate the unnecessary false positives to achieve the target FNP level.
The new method is developed under arbitrary covariance dependence calibrated through a dependence parameter whose scale is compatible with the existing formulation in sparse inference. Utilizing the new calibration, we are able to explicate the joint effects of covariance dependence and signal sparsity and interpret the results using a phase digram to gain important insight.

We demonstrate the finite sample performance of the dual control method
in simulation and apply the method to identify functionally relevant regions for saccadic eye movement using fMRI data. Its results are compared with those of other methods and with regions that are known to be associated with saccade. The new method seems to benefit from its dual control property and exhibits a good balance in identifying signal voxels in the functionally relevant regions and avoiding the scattered noise voxels.

This new method will be useful in, for example, pre-surgical fMRI data analysis, where efficient false negative control is of vital importance because neurosurgical patients are likely to experience significant harm from mistakenly deeming a region to be functionally uninvolved and subsequently resecting critical tissues.
In a broad sense, our study expands the frontier of high-dimensional sparse inference by bridging an important methodological gap.

\section{Appendix}

This section provides the proofs of \autoref{lemma:consistency},  \autoref{thm:FNPcontrol}, and \autoref{prop:estimated_s}, as well as additional simulation results.  We will frequently use the following result on Mill's ratio:
\[
\bar \Phi(x) \le x^{-1} \phi(x) \qquad \text{for any} \quad x>0.
\]
The symbol $C$ denotes a genetic, finite constant whose value can be different at different occurrences.

\subsection{Proof of \autoref{lemma:consistency}}

For notation simplicity, let
\begin{equation} \label{def:B(t)}
B(t) = 1-\text{R}(t)/s+ (p-s) \Bar{\Phi}(t)/s.
\end{equation}
Then $\widehat{\text{FNP}}(t) = \max\{B(t), ~0\}$, and it is sufficient to show that
\begin{equation} \label{01}
|B(t) - \text{FNP}(t)| = o_ p(1) \qquad \text{when} \quad B(t) \ge 0
\end{equation}
and
\begin{equation} \label{02}
\text{FNP}(t) = o_ p(1)  \qquad \text{when} \quad B(t) < 0.
\end{equation}

Consider (\ref{01}) first. By the definitions of $B(t)$ and $\text{FNP}(t)$,
\[
|B(t) - \text{FNP}(t)| = |s^{-1}(\text{R}(t)-(p-s)\Bar{\Phi}(t)) - s^{-1}(\text{R}(t)-\text{FP}(t))| = s^{-1}|\text{FP}(t) - (p-s)\Bar{\Phi}(t)|.
\]
Therefore, it is sufficient to show
\begin{equation} \label{0}
s^{-1}|\text{FP}(t) - (p-s)\Bar{\Phi}(t)| = o_P(1).
\end{equation}
Recall the definition of $\mu_1$ and $\mu_2$ in (\ref{def:t_min}). The following proof is composed of two parts. The first part assumes $t \ge \mu_1$ and the second part assumes $\mu_2 \le t < \mu_1$.

Consider the first part. It's sufficient to show $s^{-1}\text{FP}(t)=o_P(1)$ and $s^{-1} (p-s) \Bar{\Phi}(t)=o(1)$ with $t \ge \mu_1$. By Mill's ratio and the re-parameterization of $s$ in $\gamma$,
\begin{equation*}
s^{-1}(p-s)\Bar{\Phi}(t)\leq \frac{Cpe^{-t^2/2}}{ts} \le  \frac{C} {\sqrt{ \log{p}}}=o(1).
\end{equation*}
On the other hand, for a fixed constant $a>0$,
\begin{equation*}
P(s^{-1}\text{FP}(t)>a) \leq \frac{E(\text{FP}(t))}{as} \leq \frac{p \max_{j\in I_0}P( z_j >t)}{as} \le   \frac{Cp\Bar{\Phi}(t)}{s} = o(1).
\end{equation*}
Therefore, the claim in (\ref{0}) is justified for $t \ge \mu_1 = \sqrt{2\gamma \log{p}}$.

Next we present the second part of the proof with $\mu_2 \le t < \mu_1$. Define
\begin{equation*}
D_p=s^{-2}e^{-t^2/2}\lVert\mathbf{\Sigma}\rVert_1\log{p}.
\end{equation*}
By the condition $t \ge \mu_2 $ and the re-parameterizations of $\lVert\mathbf{\Sigma}\rVert_1$ in $\eta$ and $s$ in $\gamma$,  it can be shown that
\begin{eqnarray*}
	D_p  = p^{2\gamma-\eta}e^{-t^2/2} \log{p} \le \log ^{-1} p = o(1).
\end{eqnarray*}
Then, (\ref{0}) is implied by
\begin{equation} \label{0.1}
s^{-1}|\text{FP}({t})-(p-s)\Bar{\Phi}(t)| = o_P(\sqrt{D_p}).
\end{equation}
Apply Chebyshev's inequality,
\begin{equation} \label{0.2}
P(s^{-1}|\text{FP}(t)-(p-s)\Bar{\Phi}(t)|>\sqrt{D_p})
\leq\frac{ Var(\text{FP}(t))}{s^2D_p}.
\end{equation}
We have the following lemma for the order of $Var(\text{FP}(t))$ under dependence. The proof is essentially the same as that of Lemma 5.2 in
\cite{jeng2021estimating}. We omit the details to save space.

\begin{lemma}\label{lemma:Var(FP)}
	Consider  model (\ref{def:multiNorm}). Denote $\mathbf{\Sigma}_0$ as the correlation matrix of $Z_j, j \in I_0$. We have
	\begin{equation*}
	Var(\sum_{j \in I_0} 1_{\{z_j>t\}})=O(e^{-t^2/2}\lVert\mathbf{\Sigma_0}\rVert_1).
	\end{equation*}
\end{lemma}

Therefore, $Var(\text{FP}(t))=Var(\sum_{j\in I_0}1_{\{z_j >t\}}) \le C e^{-t^2/2}\lVert\mathbf{\Sigma}_0\rVert_1 \le  C e^{-t^2/2}\lVert\mathbf{\Sigma}\rVert_1$, and it follows that
\begin{equation} \label{0.3}
\frac{Var(\text{FP}(t))}{s^2D_p}=o(1)
\end{equation}
by the definition of $D_p$. Combining (\ref{0.2}) and (\ref{0.3}) gives (\ref{0.1}), which justifies the claim in (\ref{0}) for $\mu_2 \le t < \mu_1$.

Finally, consider (\ref{02}). It can be shown that $B(t) <0$ implies  $1-\text{FP}(t)/s - \text{TP}(t) / s + (p-s) \Bar{\Phi}(t)/s <0$, which, combined with FNP$(t) = 1- \text{TP}(t)/s$, further implies
\[
\text{FNP}(t) < s^{-1}(\text{FP}(t) - (p-s)\Bar{\Phi}(t)).
\]
Since the order of the right hand side has been derived in (\ref{0}), (\ref{02}) follows.
\qed \\

\subsection{Proof of \autoref{thm:FNPcontrol}}

First, by Markov's inequality, for a fixed constant $a>0$,
\begin{eqnarray*}
P(\text{FNP}(\mu_{min})>a) & = & P( s^{-1}\sum_{j\in I_1}1_{\{z_j \leq \mu_{min}\}} > a) \le \frac{1}{as}\sum_{j\in I_1} P(Z_j \le \mu_{min}) \\ & \leq & \frac{1}{a} \max_{j\in I_1} P(N(0,1) \le \mu_{min}- A_j)=o(1),
\end{eqnarray*}
where the last step is by the condition on $A_j$. Therefore, $\text{FNP}(\mu_{min})=o_P(1)$. By \autoref{lemma:consistency}, we have  $|\widehat{\text{FNP}}(\mu_{min})-\text{FNP}(\mu_{min})|=o_P(1)$, which implies  $\widehat{\text{FNP}}(\mu_{min})=o_P(1)$. Then,  by the construction of $\hat{t}(\beta)$,
we have $P(\hat{t} (\beta) \geq \mu_{min})\rightarrow 1$. Consequently, since $\hat{t} (\beta)$ is random,
\begin{eqnarray*}
& & \lim_{p\to \infty} P(|\widehat{\text{FNP}}(\hat{t}(\beta))- \text{FNP}(\hat{t}(\beta))| >a) \\
& = & \lim_{p\to \infty} E\left[ E\left( 1\{|\widehat{\text{FNP}}(\hat{t}(\beta))- \text{FNP}(\hat{t}(\beta))| >a\} | \hat{t}(\beta)\right)\right] \\
& = & E\left[ \lim_{p\to \infty}  E\left( 1\{|\widehat{\text{FNP}}(\hat{t}(\beta))- \text{FNP}(\hat{t}(\beta))| >a\} | \hat{t}(\beta)\right)\right] = 0,
\end{eqnarray*}
where the second step above is by dominated convergence theorem and the last step is by \autoref{lemma:consistency}. Therefore, $|\widehat{\text{FNP}}(\hat{t}(\beta))- \text{FNP}(\hat{t}(\beta))|=o_P(1)$. Now, since $\widehat{\text{FNP}}(\hat{t}(\beta))<\beta$ almost surely by the construction of $\hat{t}(\beta)$, claim in (\ref{eq:FNPcontrol_1}) follows.

Next, let's consider the claim in (\ref{eq:FNPcontrol_2}). Because $\tilde{t} > \hat{t}(\beta)$, the construction of  $\hat{t}(\beta)$ implies that $\widehat{\text{FNP}}(\tilde{t}) \ge \beta$ almost surely. On the other hand, because
$\tilde{t} > \hat{t}(\beta) \ge \mu_{min}$ with probability tending to 1, similar arguments as the above lead to   $|\widehat{\text{FNP}}(\tilde{t})- \text{FNP}(\tilde{t})|=o_P(1)$. Therefore, the claim in (\ref{eq:FNPcontrol_2}) follows.
\qed  \\

\subsection{Proof of \autoref{prop:estimated_s}}

The consistency of $\hat \pi_{}^*$ is based on the following two lemmas, which are implied by Theorem 2.2 and 2.3 in \cite{jeng2021estimating}.

\begin{lemma} \label{lemma:discrete05}
		Consider model (\ref{def:multiNorm}). Let $\delta(t) = [\bar \Phi(t)]^{1/2}$. Then, there exists a bounding sequence
		$c_{p, \delta}^* = O\left(\sqrt{\bar \rho \cdot  \log p}\right)$,
		and the corresponding estimator $\hat{\pi}^*_{\delta}$  satisfies $ P(\hat \pi^*_{\delta} < \pi) \to 1$. Moreover, for $\pi$ satisfying $0 < \pi \ll  1$,
		if $\tau = \min_{j \in I_1} A_j \gg 1$ and
		\begin{equation} \label{cond:theta_05}
		\tau - \bar \Phi^{-1}\left( {\pi^2 \over \bar \rho \cdot \log p } \right) \to \infty,
		\end{equation}
		then $P(\hat \pi^*_{\delta} > (1-\epsilon) \pi) \to 1$ for any constant $\epsilon>0$.
\end{lemma}

\begin{lemma} \label{lemma:discrete1}
	Consider model (\ref{def:multiNorm}).
	Let $\delta(t) = \bar \Phi(t)$. Then, there exists a bounding sequence $c_{p, \delta}^* = O(\sqrt{\log p})$, and the corresponding estimator $\hat{\pi}^*_{\delta}$ satisfies $ P(\hat \pi^*_{\delta} < \pi) \to 1$. Moreover, for $\pi$ satisfying $0 < \pi \ll  1$,  if $\tau = \min_{j \in I_1} A_j \gg 1$ and
	\begin{equation} \label{cond:theta_1}
	\tau - \bar \Phi^{-1}\left({\pi \over \sqrt{\log p} }\right) \to \infty.
	\end{equation}
	then $P(\hat \pi^*_{\delta} > (1-\epsilon) \pi) \to 1$ for any constant $\epsilon>0$.
\end{lemma}

Recall that $\pi = p^{-\gamma}$, $\gamma \in (0, 1]$, and $\bar \rho = p^{-\eta}, \eta \in [0,1]$. Recall $\mu_1$ and $\mu_2$ in (\ref{def:t_min}). Direct calculation shows that when $\tau - \mu_2 \to \infty$, the condition in (\ref{cond:theta_05}) is satisfied, and when  $\tau - \mu_1 \to \infty$, the condition in (\ref{cond:theta_1}) is satisfied. Therefore, given $\tau = \min_{j \in I_1} A_j - \mu_{min} \to \infty$, the consistency of the estimator  $\hat \pi_{}^* = \max\{\hat \pi_{0.5}, \hat \pi_{1}\}$  holds as in (\ref{eq:hat_pi}).

Next consider the claims in (\ref{eq:FNPcontrol_1s}) and (\ref{eq:FNPcontrol_2s}). Similar arguments as in the proof of \autoref{thm:FNPcontrol} can be applied, and we only need to show that \autoref{lemma:consistency} continues to hold with $\widehat{\text{FNP}}(t)$ replaced by $\widehat{\text{FNP}}_{\hat s}(t)$. Given the result in (\ref{eq:consistency}), it is sufficient to show
$|\widehat{\text{FNP}}_{\hat s}(t) - \widehat{\text{FNP}}(t) | = o_P(1)$ for $t \ge \mu_{min}$, which is implied by
\begin{equation} \label{3}
|B_{\hat s}(t) - B(t) | = o_P(1)  \quad \text{for} \quad t \ge \mu_{min},
\end{equation}
given the definition of $B(t)$ in (\ref{def:B(t)}).
By direct calculation,
\begin{eqnarray} \label{3.0}
|B_{\hat s}(t) - B(t) | & = & |(\hat s^{-1} - s^{-1}) (\text{R}(t) - p \bar \Phi(t))| \nonumber \\
& \le & |\hat s^{-1} - s^{-1}| \cdot \text{TP}(t) + |\hat s^{-1} - s^{-1}| \cdot |\text{FP}(t) - p \bar \Phi(t)|.
\end{eqnarray}
Given $P((1-\delta) < \hat s/s  < 1)\rightarrow 1$ for any $\delta>0$, it can be shown that
\[
P(|\hat s^{-1} - s^{-1}| < \frac{\delta}{1-\delta} s^{-1}) \to 1.
\]
On the other hand, $TP(t) \le s$ almost surely. Then it follows that the first term in (\ref{3.0}),
\[
|\hat s^{-1} - s^{-1}| \cdot \text{TP}(t) = o_p(1).
\]
For the second term in (\ref{3.0}),
\[
|\hat s^{-1} - s^{-1}| \cdot |\text{FP}(t) - p \bar \Phi(t)| < \frac{\delta}{1-\delta} s^{-1} |\text{FP}(t) - p \bar \Phi(t)|) \le \frac{\delta}{1-\delta} \left(s^{-1} |\text{FP}(t) - (p-s) \bar \Phi(t)|) + \bar \Phi(t)\right)
\]
with probability tending 1, where $\bar \Phi(t) = o(1)$ for $t \ge \mu_{min}$, and it has been shown as for (\ref{0}) that
$s^{-1}|\text{FP}(t) - (p-s)\Bar{\Phi}(t)| = o_P(1)$ for $t \ge \mu_{min}$. Then it follows that
\[
|\hat s^{-1} - s^{-1}| \cdot |\text{FP}(t) - p \bar \Phi(t)| = o_P(1).
\]
Summing up the above gives (\ref{3}).
\qed \\

\bibliographystyle{chicago}
\bibliography{FNP_reference}

\end{document}

config: arxiv


text:
\begin{document}

\hyphenation{non-mea-su-ra-ble}

\maketitle

\begin{abstract} In this paper we investigate the action of Polish groups (not necessary abelian) on an uncountable Polish spaces. We consider two main situations. First, when the orbits given by group action are small and the second when the family of orbits are at most countable. We have found  some subgroups which are not measurable with respect to a given $\sigma$-ideals on the group and the action on  some subsets gives a completely nonmeasurable sets with respect to some $\sigma$-ideals with a Borel base on the Polish space.  In most cases the general results are consistent with ZFC theory and are strictly connected with cardinal coefficients. We give  some suitable examples, namely the subgroup of isometries of the Cantor space where the orbits are suffitiently small. In a opposite case we give an example of the group of the homeomorphisms of a Polish space in which there is a large orbit and we have found the subgroup without  Baire property and a subset of the mentioned space such that the action of this subgroup on this set is completely nonmeasurable set with respect to the $\sigma$-ideal of the subsets of first category.
\end{abstract}

\section{Notation and Terminology}

In this paper we will use standard set theoretic notation folowing \cite{Jech}. In particular, for any set $X$ and any cardinal $\kappa$ a set $[X]^{<\kappa}$ denotes the family of all subsets of $X$ with size less than $\kappa$. Moreover, $\scr{P}(X)$ denotes the power set of $X$.

Let $X$ be any uncountable Polish space. By $\scr{B}(X)$ we denote the $\sigma$-algebra of all Borel subsets of $X$.

$I\subseteq \cp(X)$ is an ideal on $X$ if $I$ is closed under taking subsets and under finite unions. We assume that $I$ is nontrivial meaning that $I\neq \emptyset$ and $X\notin I.$ If for every sequence $(A_n)_{n\in\omega}$ of elements of $I$ we have that $\bigcup_{n\in\omega}A_n\in I$ then $I$ is called $\sigma$-ideal.

Let us recall that $\scr{F}\subset I$ is a base of $I$ iff
$$
(\forall Y\in I)(\exists B\in\scr{F})\;\; Y\subset B.
$$
If, additionally $\scr{F}$ consists of Borel sets then we say that $\scr{F}$ is a Borel base of $I.$

We will use the following cardinal coeficients:
\begin{definition}Let $I\subset \scr{P}(X)$ be a $\sigma$-ideal on a Polish space $X$. Assume that $I$ has Borel base. Set

$$
cov(I)=min\{ |\scr{A}|:\; \scr{A}\subset I\land \bigcup \scr{A} = X\},
$$
$$
cov_h(I)=min\{ |\scr{A}|:\; (\scr{A}\subset I)\land (\exists B\in \scr{B}(X)\setminus I)\;(\bigcup \scr{A}= B)\},
$$
$$
cof(I)=min\{ |\scr{A}|:\; \scr{A}\subset I\land \scr{A}\text{ is a  Borel base of } I\}.
$$
\end{definition}

\begin{definition}\label{pis} We say that a pair $(X,I)$ is a Polish ideal space iff
\begin{itemize}
 \item $X$ is uncountable Polish space,
 \item $I\subset\scr{P}(X)$ is a $\sigma$-ideal containing singletons and having Borel base.
\end{itemize}

\end{definition}

Let us remark that a classical example of Polish ideal space is $(X,\cm)$, where $X$ is an uncountable Polish space without isolated points and $\cm$ stands for $\sigma$-ideal of meager sets i.e. $\sigma$-ideal generated by closed nowhere dense sets.

The cardinal coeficients connected to $\cm$ does not depend on $X$ (see e.g. \cite{Kechris}). Moreover $cov(\cm)=cov_h(\cm).$

By $\scr{B}^+_I(X)$ we denote the set $\scr{B}(X)\setminus I$ of all $I$-positive Borel subsets of the space $X$.

Let us notice that similarly as in the context of ideals we can define a base of $\scr{B}^+_I(X).$ In this case we say that $\scr{F}\subseteq \scr{B}^+_I(X)$ is a base if
$$
(\forall A\in\scr{B}^+_I(X))(\exists B\in\scr{F})( B\subseteq A).
$$

The base of $\scr{B}^+_I(X)$ consists of Borel sets, so it is always of size smaller or equal to continuum.

\begin{definition}
Let $(X,I)$ be Polish ideal space. Assume that $C\subseteq D\subseteq X.$
We say that $C$ is completely $I$-nonmeasurable in $D$ iff
$$(\forall B\in\scr{B}^+_I(X))\left(B\cap D\notin I\then (B\cap C\notin I\wedge B\cap(D\setminus C)\notin I)\right).$$
\end{definition}

Let us remark that this notion was studied e.g. in papers \cite{rz1}, \cite{rz2}, \cite{cmrrz}, \cite{rsz}, \cite{z}.

\begin{definition}
We say that a pair $(G,\cdot)$ is a Polish group if $(G,\cdot)$ is a topological group and $G$ with its topology is a Polish space. Neutral element of the group $(G,\cdot)$ will be denoted by $e$. If $X$ is any set and $(G,\cdot)$ is a group then a mapping $F: G\times X\to X$ is called an  action of a group $G$ on $X$ iff the following conditions are fulfilled:
\begin{enumerate}
 \item $(\forall x\in X) F(e,x)=x$,
 \item $(\forall x\in X)(\forall g,h\in G)\;\; F(g,F(h,x))=F(gh,x)$.
\end{enumerate}
For the reader's convenience $F(g,x)$ is denoted by $gx$ and $(G,\cdot)$ by $G$.
\end{definition}

In the same fashion as in Definition \ref{pis} we define a notion of Polish ideal group.
\begin{definition} We say that a triple $(G,\cdot, \cj)$ is a Polish ideal group iff $(G,J)$ is Polish ideal space and $(G,\cdot)$ is a Polish group,
\end{definition}

 \begin{definition} Let $G$ be any group and $X$ be any set. Let $A\subset X$ be any subset of the $X$ then the set
$$
GA=\{ gx\in X:\;\; (g,x)\in G\times A\}
$$
is called an orbit of the set $A$ by the group $G$ and whenever $A=\{ x\}$ is singleton then we will write $G{x}$ instead of $G{\{ x\}}$ for convenience.
\end{definition}

Of course the family $\{ Gx: x\in X\}$ forms a partition of $X$. Each set of the form $Gx$ can be viewed as an abstract class with respect to the following equivalence relation:
$$
 (x\sim y)\iff ((\exists g\in G)\; (y=gx))
$$

Let $A\subset G$ be any subset of the group $G$ then $\< A\>_G$ denotes the subgroup of $G$ generated by the set $A$. Let us observe that for any nonempty subset $A\subset G$ we have
$$
\< A \>_G= \bigg\{ \prod_{i\in n} f(i)^{g(i)}\in G:\;\; n\in\omega\land f\in A^n\land g\in \bbz^n\bigg\}.
$$
Here $h^0=e\in G$ whenever $h\in G$.

\section{Results }

First, let us consider the situation when the set of orbits of singletons is quite large.
\begin{theorem} Let $(X,I)$ be Polish ideal space and $(G,\cdot)$ be any Polish group acting on $X.$ Assume that the following condition is fulfilled:
$$
(\forall B\in \scr{B}_I^+(X))\; cof(I)\le |\{ Gb:\; b\in B\}|.
$$
Then there exists a subgroup $H\le G$ and a subset $A\subset X$ such that $A$ and $HA$ are completely $I$-nonmeasurable subsets of $X$. Moreover if $(G,J)$ is a Polish space and there exists Borel bases $\scr{B}_G\subset \scr{B}_J^+(G)$ and $\scr{B}_X\subset \scr{B}_I^+(X)$ with
$$
|\scr{B}_G|=|\scr{B}_X|\le |\{ Gb:\; b\in B\}|,
$$
then $H$ is completely $J$-nonmeasurable in the group $G$.
\end{theorem}
\begin{proof}
Let us enumerate bases $\scr{B}_G=\{ C_\alpha:\alpha<\lambda\}$ and $\scr{B}_X=\{ B_\alpha:\alpha<\lambda\}$ where $\lambda\le |\{ Gb:\; b\in B\}|$. Now let assume that we are in $\alpha<\lambda$ step construction with the following transfinite sequence:
$$
\< (a_\xi,d_\xi,h_\xi,c_\xi)\in B_\xi\times B_\xi\times C_\xi\times  C_\xi:\;\; \xi<\alpha\>
$$
with the following conditions:
\begin{enumerate}
 \item the collection of orbits $\{ G{a_\xi}:\xi<\alpha\}\cup \{ G{d_\xi}:\xi< \alpha\}$ is pairwise disjoint,
 \item $\< h_\xi:\; \xi<\alpha\>_G\cap \{ c_\xi:\xi<\alpha\}=\emptyset$.
\end{enumerate}
By assumption we can find
$$
a_\alpha,d_\alpha \in B_\alpha\setminus \bigcup(\{ G{a_\xi}:\xi<\alpha\}\cup \{ G{d_\xi}:\xi< \alpha\})
$$
and $h_\alpha \in C_\alpha\setminus \< h_\xi:\; \xi<\alpha\>_G$ because $|\< Z \>_G|\le \aleph_0\cdot |Z|$ for any set $Z\subset G$. Then $\alpha$ step is finished.

Now let us take the following sets: $H=\< h_\alpha\in G:\alpha<\lambda\>_G$, $A=\{ a_\alpha\in X:\alpha<\lambda\}$ and $D=\{ d_\alpha\in X:\; \alpha<\lambda\}.$ Then by our transfinite construction $H$ is completely J-nonmeasurable subgroup of $G$, $A$ and $D$ are completely I-nonmeasurable subsets of the Polish space $X$. Moreover by the following inclusion
$$
A\subset HA\subset D^c
$$
we see that $HA$ is completely I-nonmeasurable subset of $X$.
\end{proof}

By a simple modification of the proof of the previous Theorem (by double transfinite induction) we can derive a stronger result:

\begin{theorem}
\label{many_orbits} Let $(X,I)$ be Polish ideal space and $(G,\cdot)$ be any group acting on $X$. If the following condition is fulfilled:
$$
(\forall B\in \scr{B}_I^+(X))\; cof(I)\le |\{ Gb:\; b\in B\}|.
$$
Then there exists subgroup $H\le B$ and the pairwise disjoint family $\{A_\alpha:\alpha< cof(I)\}\subset \scr{P}(X)$ such that:
\begin{enumerate}
 \item $(\forall \alpha< cof(I))\; A_\alpha, H{A_\alpha}$ are completely $I$-nonmeasurable in $X$,
 \item $(\forall \alpha,\beta)\alpha<\beta< cof(I) \then H{A_\alpha}\cap H{A_\beta}=\emptyset$.
\end{enumerate}
Moreover if $(G,J)$ is a Polish space and there exists Borel bases $\scr{B}_G\subset \scr{B}^+_J(G)$ and $\scr{B}_X\subset \scr{B}_I^+(X)$ with
$$
|\scr{B}_G|=|\scr{B}_X|\le |\{ Gb:\; b\in B\}|,
$$
then $H$ is completely $J$-nonmeasurable in the group $G$.
\end{theorem}

Now, let us now consider the situation when, in contrast to previous theorems, there exists only one orbit.

\begin{theorem}\label{gg}
Let $(G,\cdot)$ be any group and let $(X,I)$ be a Polish ideal space. If for some (every) $x\in X$ $Gx=X$ and
$$
(\exists \lambda<2^\omega)(\forall x,y\in X)\; x\ne y\then |G_{x,y}|\le \lambda
$$
where $G_{x,y}=\{ g\in G:\; y=gx\}$ then there exists a subgroup $H\le G$ and a subset $A\subset  X$ such that $A$ and $HA$ are complete I-nonmeasurable sets in $X$. Moreover, if $(G,J)$ forms Polish ideal space then our $H$ is completely $J$-nonmeasurable in $G$.
\end{theorem}
\begin{proof}
Let us enumerate the Borel bases in the group $G$ and space $X$, $\scr{B}_G=\{ C_\alpha:\alpha<2^\omega\}$ and $\scr{B}_X=\{ B_\alpha:\alpha<2^\omega\}$.
Let us supouse that we are in the $\alpha$-step of recursive construction:
$$
\< (a_\xi,d_\xi,h_\xi,c_\xi)\in B_\xi\times B_\xi\times C_\xi\times C_\xi:\xi<\alpha\>
$$
with the following conditions:
$$
{H_\alpha}{A_\alpha}\cap D_\alpha=\emptyset,\text{ and } H_\alpha\cap F_\alpha=\emptyset,
$$

where $H_\alpha=\< \{ h_\xi:\xi<\alpha\}\>_G$, $F_\alpha=\{ c_\xi:\xi<\alpha\}$, $A_\alpha=\{ a_\xi:\xi<\alpha\}$ and $D_\alpha=\{ d_\xi:\xi<\alpha\}$.

Now let us choose any element  $a_\alpha\in B_\alpha\setminus D_\alpha$.
Set $W_\alpha$ to be the following set
$$
\{ h\in G: \exists \xi<\alpha\exists n\in\omega\exists f\in (\{ h\}\cup H_\alpha)^n\exists g\in\bbz^\omega\; d_\xi=\prod_{i\in n}f(i)^{g(i)}\; a_\alpha\}
$$
By our assumption  $W_\alpha$ has the cardinality less or equal to $\aleph_0|H_\alpha|$. Let us choose any $h_\alpha\in C_\alpha\setminus W_\alpha$. It is possible because $C_\alpha$ contains some uncountable perfect set.
Now choose any element $c_\alpha\in C_\alpha\setminus \< \{ h_\alpha\}\cup H_\alpha\>_G$ by the same argument. Finally we can choose any element $d_\alpha\in B_\alpha\setminus \< \{ h_\alpha\}\cup H_\alpha\>_{ \{ a_\alpha\}\cup A_\alpha}$ what is possible because we have the following cardinal inequality:
$$
|\< \{ h_\alpha\}\cup H_\alpha\>_{\{ a_\alpha\}\cup A_\alpha}|\le |\< \{ h_\alpha\}\cup H_\alpha\>\cup \{ a_\alpha\}\cup A_\alpha|\le |\xi|\aleph_0<2^\omega.
$$
Then our construction is done by transfinite induction Theorem. Let us observe that the following sets
$$
A=\{ a_\alpha:\alpha<2^\omega\}, D=\{ d_\alpha:\alpha<2^\omega\}, H=\< h_\alpha:\alpha<2^\omega\>_G=\bigcup_{\alpha<2^\omega} H_\alpha.
$$
fulfills assertion of this Theorem because $A\subset HA\subset D^c$. So, the proof is finished.
\end{proof}

With a little more afford we can prove the analogous theorem in the case when the set of all orbits is small and those orbits are $I$-measurable subsets of $X$ (which means that belong to the $\sigma$-algebra $\scr{B}[I]$ generated by sets which are Borel or belongs to the ideal $I$). Namely, we have the following result.

\begin{theorem}\label{few_orbits} Let $(X,I)$ is a Polish ideal space and $(G,\cdot)$ be any group acting on $X$. Assume that $X=\bigcup \{   G{x_n}:n\in\omega\}$ is a union of the countable many $I$-positive and $I$-measurable orbits. Suppose that
$$
(\exists \lambda<2^\omega)(\forall x,y\in X)\; x\ne y\then |G_{x,y}|\le \lambda,
$$
where $G_{x,y}=\{ g\in G:\; y=gx\}.$ Then there exists a subgroup $H\le G$ and countably many families $\scr{A}_n$ such that for every $n\in\omega$ $\scr{A}_n=\{ A_\alpha^n:\alpha< 2^\omega\}$ $n\in\omega$ is a family of continuum many pairwise disjoint subsets of $X$ with the following conditions:
$$
(\forall n\in\omega)(\forall \alpha<2^\omega) A_\alpha^n, H{A_\alpha^n}\text{ is completely }I-\text{nonmeasurable in }G{x_n}.
$$
Moreover, if $(G,J)$ forms Polish ideal space then our $H$ is completely $J$-nonmeasurable in $G$.
\end{theorem}

\begin{theorem}\label{hghg}
Let $(G,\cdot,\cj)$ be a Polish ideal group which acts on the Polish ideal space $(X,\ci)$. Let us assume that
\begin{enumerate}
    \item $cov_h(\cj)=cov_h(\ci)=cof(\ci)=cof(\cj)$,
    \item for any $n\in\omega$, $s\in \bbz^n$ there exists $G'\subseteq G$ such that $G\setminus G'\in J$ and for every $g\in G'$, $a\in G'^n$ the following condition holds
    $$
    \{ h\in G:\; \prod_{i\in n} a_i\cdot h^{s_i} = g\} \in\cj.
    $$
\end{enumerate}
Then there is a completely $\cj$-nonmeasurable subgroup $H$ in $G$  and completely $\ci$-nonmeasurable subset $A\subseteq X$ such that $HA$ is completely $\ci$-nonmeasurable in the space $X$.
\end{theorem}
\begin{proof} Let us enumerate the collections of $\ci$ positive Borel bases in $G$ and $X$ $\{ P_\xi:\xi< cof(\cj)\}$, $\{ B_\xi:\xi< cof(\ci)\}$ respectively. Then by transfinite recursion we define sequence of the length $\kappa=cof(\ci)$:
$$
\< (H_\xi,A_\xi,g_\xi,d_\xi):\ \xi<\kappa\>
$$
such that for any $\xi,\eta<\kappa$, we have
\begin{enumerate}
    \item $H_\xi\le G$ and $H_\xi\cap P_\xi\ne\emptyset$,
    \item $A_\xi\in\scr{P}(X)$ and $A_\xi\cap B_\xi\ne\emptyset$,
    \item if $\xi\le \eta$ then $H_\xi\subseteq H_\eta$ and $A_\xi\subseteq A_\eta$,
    \item whenever $\xi\le \eta$ then $g_\xi\notin H_\eta$ and $d_\xi\notin H_{\eta}{A_{\eta}}$.
\end{enumerate}
The sets $H=\bigcup_{\xi<\kappa} H_\xi$ and $A=\bigcup_{\xi<\kappa} A_\xi$ gives required assertion.

Let us consider $\alpha$-th setp of our transfinite induction. Let $H=\bigcup_{\xi<\alpha} H_\xi$, the sets $\{ g_\xi: \xi<\alpha\}$ and $\{ d_\xi: \xi<\alpha\}$ have  size less than $cov_h(\cj)=cov_h(\ci)$. Then by the second assumption of the our theorem we can find  some elements $h,g \in P_\alpha\cap G'$ such that $\<H\cup\{ h\}\>\cap (\{ g_\xi:\xi<\alpha\}\cup\{ g\})=\emptyset$ and $\< H\cup\{ h\}\>A\cap \{ d_\xi: \xi<\alpha\}=\emptyset$ where $A=\bigcup_{\xi<\alpha} A_\xi$. Then we can find  some $a,d\in B_\alpha$ such that $\< H\cup\{ h\}\>(A\cup\{a\})\cap (\{ d_\xi: \xi<\alpha\}\cup\{ d\})=\emptyset$. Let us set $H_\alpha=\< H\cup\{ h\}\>$, $A_\alpha=A\cup\{ a\}$, $g_\alpha=g$ and $d_\alpha=d$, what finishes construction at $\alpha$-th step of induction.
\end{proof}

The condition (2) from the previous Theorem looks artificially. However, we can consider a natural situation, where  $J$ is the ideal of meager sets $\cm.$
In such case we have the following proposition

\begin{proposition}\label{meager}
Let $(G,\cdot)$ be a Polish space. Fix $n\in\omega$, $s\in \bbz^n.$ Then there exists comeager $G'\subseteq G$ such that  for every $g\in G'$, $a\in G'^n$ the following set
    $$
    \{ h\in G:\; \prod_{i\in n} a_i\cdot h^{s_i} = g\}
    $$
is meager.
\end{proposition}
\begin{proof} Let $M=\{(h,g,a_0,\ldots,a_{n-1})\in G^{n+2}:\; \prod_{i\in n} a_i\cdot h^{s_i} = g\}.$ $M$ is a closed subset of $G^{n+2}.$ Moreover, its interior is empty. So, $M$ is a closed nowhere dense set. By Kuratowski-Ulam theorem  comeager many first sections of $M$ are meager. Using Kuratowski Ulam theorem, a set $\{ h\in G:\; \prod_{i\in n} a_i\cdot h^{s_i} = g\}$ is meager for $(g,a_0,\ldots,a_{n-1})\in C$, where $C\subseteq G^{n+1}$ is comeager. Using Kuratowski-Ulam theorem $n$-many times we can find $G'$ -- comeager subset of $G$ such that $G'^{n+1}\subseteq C.$ $G'$ is the required set.
\end{proof}

\begin{theorem} Let $(X,\ci)$ be a Polish ideal space and  $non(\ci)<cov_h(\ci)$. Assume that $(G,\cdot)$ is a group which acts on $X$. If $H\le G$ and $A\in\ci$ are such that $HA$ contains a Borel set $B\notin\ci$ then there is a subgroup $H'\le H$ such that $H'A$ is  completely $\ci$-nonmeasurable in  some $\ci$-positive Borel set.
\end{theorem}
\begin{proof} Let $B\in \scr{B}^+_I(X)$ be a $\ci$-positive Borel set such that $B\subseteq HA.$ Let us find a set $T\subset B$ witness of $non(\ci)$. Then let $F:T\to H$ be such that  $t\in F(t)A$ holds for any $t\in T$. Let $H'=\< F[T]\>$ be a subgroup of $H$ generated by $F[T].$ Then
$$
|H'|=|F[T]|\le|T|=non(\ci)<cov_h(\ci).
$$
We have that $T\subseteq F[T]A\subseteq H'A.$ So, $H'A\notin\ci$. Notice that $H'A=\bigcup\cf,$ where  family $\cf=\{ hA:\; h\in H'\}\subseteq\ci$ of sets from $\sigma$-ideal $\ci$ has size less than $cov_h(I).$ It shows that any $\ci$-positive Borel set can not be covered by the family $\cf$.
\end{proof}

\section{Applications}
In investigations of topological spaces $X$ the crucial role is played by the space of all homeomorphisms $\ch(X)$ on the space $X$. $\ch(X)$ is endowed with so-called compact-open topology which is generated by the following subbase
$$
\{ V(K,U):\;K\subseteq X\text{ is compact and }U\subseteq X\text{ is open in }X\},
$$
where
$$
V(K,U)=\{ f\in\ch:\; f[K]\subseteq U\}).
$$
In the case when $X$ is a compact metric space, $\ch(X)$ is also metrizible. A metric on $\ch(X)$ can be defined for every $f,\ g\in\ch(X)$ by the following formula
$$
 d(f,g)=\sup_{x\in X}\{ d(f(x),g(x))\} + \sup_{y\in X} d(f^{-1}(y),g^{-1}(y)).
$$
When $X$ is compact Polish space then $\ch(X)$ is also Polish one, see \cite{Chapman} for example.

Let us now consider a natural context, when a Polish group G acts on itself by left shifts. As a consequence of Theorem \ref{gg} we get the following result.

\begin{cor}
Let $(G,\cdot,J)$ be a Polish ideal group. Then there exists $H<G$ and $A\subseteq G$ such that $H,\, A,\, HA$ are completely $J$-non\-mea\-su\-ra\-ble.
\end{cor}
\begin{proof}
It is enough to check that the assumptions of Theorem \ref{gg} are fulfilled.

Naturally $Ge=\{ge:\ g\in G\}=G.$

Notice that if $x\neq y$, $x,y\in G$ then
$$
G_{x,y}=\{g\in G:\ y=gx\}=\{yx^{-1}\},
$$
so, it has size 1.
\end{proof}

Now, let us consider a situation when a group of homeomorphisms $\scr{H}(X)$ acts in a natural way on a compact Polish space $X.$

\begin{cor}
Assume that $cov(\cm)=cof(\cm).$ Let $X$ be a compact Polish space without isolated points. Then there exist a completely $\cm$-nonmeasurable subgroup $H<\scr{H}(X)$ and a completely $\cm$-non\-mea\-su\-ra\-ble subset $A\subseteq X$ such that $HA$ is completely $\cm$-nonmeasurable.
\end{cor}
\begin{proof}
We will use Theorem \ref{hghg}. The assumptions are fulfilled, what follows from Proposition  \ref{meager}.
\end{proof}

From the other side the following example is a simple corollary from Theorem \ref{many_orbits} when we can find many different orbits.
\begin{cor} If $G$ is a subgroup of the group of all isometries on the Cantor space $2^\omega$ defined as follows
$$
G=\{ T_X:\; X\in \scr{P}(\{ n\in\omega:\; n\equiv 0\mod 2\})\}
$$
where for any $x\in 2^\omega$ and $n\in\omega$
$$
T_X(x)(n)=\begin{cases}
x(n)    &\text{when }n\notin X\\
1-x(n)  &\text{when }n\in X.
\end{cases}
$$
Then there is a subgroup $H$ of $G$ and uncountable many pairwise disjoint subsets $\{ A_\alpha\subset 2^\omega:\; \alpha< cof(\cm)\}$ such that $HA_\alpha$ are completely $\cm$-nonmeasurable in the Cantor space $2^\omega$ for any $\alpha < cof(\cm)$. Moreover,  $\{ HA_\alpha:\alpha< cof(\cm)\}$ forms a pairwise disjoint family of subsets of the Cantor space.
\end{cor}


TITLE: How many paths in an NFA
QUESTION [0 upvotes]: Suppose there is a simple NFA, with 3 states (p,r,q) where p is the start and r is the final.
Such that
$\delta$ =   (p,a,q), (p,b,q),
(p,a,r), (p,b,r),
(q,a,p), (q,b,p),
(q,a,r), (q,b,r),
(r,a,p), (r,b,p),
(r,a,q), (r,b,q)
Is there a formula that can calculate the number of paths for a particular string?
I have tried just tracing for a small string such as "aaa", but when it gets larger, it becomes difficult.

REPLY [1 votes]: For a string $w$ of length $n$ in the language, consider the states through which the NFA will be in when processing $w$. Each such path must start in state $p$ and end in the accepting state $r$, and may not have adjacent instances of the same state. Thus $w$ will give rise to all possible sequences $\langle\,s_1, s_2, \dotsc s_{n+1}\,\rangle$ where $s_i \in \{p,q,r\}$, $s_1=p, s_{n+1}=r$ and $s_i\ne s_{i+1}$ for all $1\le i\le n$.
Now suppose we look at the number of paths of length $n$ regardless of whether they end in $r$. Let the triple $(P,Q,R)$ count the number of length-$n$ paths that end in states $p,q,r$, respectively. The length-$0$ path, $\langle\,p\,\rangle$ will have count tuple $(1,0,0)$. The length-$1$ paths, $\langle\,p,q\,\rangle, \langle\,p,r\,\rangle$ will give the tuple $(0,1,1)$, since the two paths end once at $q$ and once at $r$.
Now comes the cute part: the length-$n$ count, $(P,Q,R)$ must come from the length-($n-1$) count $(P',Q',R')$ where $P=Q'+R', Q=P'+R', R=P'+Q'$, so, for example, the first few count tuples must be
$$\begin{align}
n=0: &\quad (1,0,0)\\
n=1: &\quad (0,1,1)\\
n=2: &\quad (2,1,1)\\
n=3: &\quad (2,3,3)\\
n=4: &\quad (6,5,5)\\
\end{align}$$
Since we're interested in the counts for strings in the language, we're only interested in the last count element and we find that $r(n)$ is the sequence
$$
r(0) = 0\quad r(1)=1\quad r(2)=1\quad r(3)=3\quad r(4)=5\quad r(5)=11
$$
and after a bit of looking we may spot the recurrence $r(n)=2r(n-1)+(-1)^{n+1}$, which has the nice closed form
$$
r(n) =\frac{1}{3}\left(2^n-(-1)^n\right)
$$
which is the answer we sought: the number of paths through the NFA for any accepted word of length $n$.


text:
\section{Gibbardian Collapse in {\sf QCC/TT}

}\label{sec:TriQ}

The logics {\sf DF/TT} and {\sf CC/TT} solve a large set of problems related to the indicative conditional, but they also have important limitations.  First, both \cctt\ and \dftt\ validate the  Linearity principle $(A\to B) \vee (B\to A)$ for arbitrary $A$ and $B$. This schema was famously criticized by \citet{maccoll1908if}: neither of ``if John is red-haired, then John is a doctor'' and ``if John is a doctor, then he is red-haired'' seems acceptable in ordinary reasoning. So it is unclear on which basis we should accept, or declare as true, the disjunction of both sentences. Imagine, for example, that John is a black-haired doctor or a red-haired carpenter.

In a similar vein, some highly plausible conjunctive sentences can never be true on \dftt\ or \cctt. The schema $(A \to A) \wedge (\neg A \to \neg A)$ (``if A, then A; and if $\neg$A, then $\neg$A'') is always classified as neither true nor false, although each of the conjuncts is a \dftt{}- and \cctt{}-theorem.\footnote{We are indebted to Paolo Santorio for this example.} Likewise, an ensemble of conditional predictions of the form $(A \to B) \wedge (\neg A \to C)$ will always be indeterminate or false \citep[][368--370]{Bradley2002}. However, a sentence such as:

\begin{exe}
\ex If the sun shines tomorrow, Paul will go to the office by bike; and if it rains, he will take the metro. \label{ex:beach}
\end{exe}

seems to be true (with hindsight) if the sun shines tomorrow and Paul goes to the office by bike.

\begin{table}[ht]
\[
\begin{tabular}{c|ccc}
$f'_{\wedge}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
\hline
$1$ & $1$ & $1$ & $0$\\
$\nicefrac{1}{2}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
$0$ & $0$ & $0$ & $0$\\
\end{tabular}
\hspace{10pt}
\begin{tabular}{c|ccc}
$f'_{\vee}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
\hline
$1$ & $1$ & $1$ & $1$\\
$\nicefrac{1}{2}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
$0$ & $1$ & $0$ & $0$\\
\end{tabular}
\hspace{10pt}
\begin{tabular}{c|ccc}
$f'_{\supset}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
\hline
$1$ & $1$ & $0$ & $0$\\
$\nicefrac{1}{2}$ & $1$ & $\nicefrac{1}{2}$ & $0$\\
$0$ & $1$ & $1$ & $1$\\
\end{tabular}
\]
\caption{\footnotesize Truth tables for trivalent quasi-conjunction and quasi-disjunction and the material conditional based on quasi-disjunction, as advocated by \citet{cooper1968propositional}.}\label{tab:quasi}
\end{table}

A principled reply to these challenges consists in modifying the truth tables for trivalent conjunction and disjunction, as proposed by \citet{cooper1968propositional}

(see also \citealt{dubois1994conditional} and \citealt{calabrese2002deduction}). In these truth tables, reproduced in  Table \ref{tab:quasi}, the conjunction of

value $1$ and

value $\nicefrac{1}{2}$
is

value $1$, and vice versa for disjunction. This is coherent with the idea that a conditional assertion with two components (e.g., in Bradley's examples) should be classified as true if one of the assertions came out true, and the other one void. Notably, the material conditional $A \supset C$ (definable as $\neg A\vee B$ or as $\neg (A\wedge \neg B)$) of a {\sf TT-}logic based on these quasi-connectives blocks the paradoxes of material implication ($\neg A \not{\models} A \supset C$, $C \not{\models} A \supset C$), in line with the failure to validate Disjunction Introduction.

 Adopting ``quasi-conjunction'' and ``quasi-disjunction'' \citep[the terminology is due to][]{Adams1975} invalidates Linearity and gives non-trivial truth conditions for ensembles or partitions of conditional assertions. In particular, $(A \to A) \wedge (\neg A \to \neg A)$ is always true, and so is $(A \to B) \wedge (\neg A \to C)$ when one of its conjuncts is true. We call the resulting logics  {\sf QDF/TT} and {\sf QCC/TT}.\footnote{{\sf QCC/TT} is almost identical to Cooper's logic {\sf OL}, except that Cooper requires valuations to be bivalent on atomic formulae.}  However, when paired with \dftt, quasi-conjunction leads to a violation of Import-Export, but not so in \cctt. So the system of interest for us in this section is {\sf QCC/TT}.

How does  {\sf QCC/TT} then fare with respect to the five premises of Gibbard's proof?

\begin{itemize}
\itemsep=0pt

\item Assumption (i) holds since both sides of the Law of Import-Export receive the same truth value in any {\sf QCC}-evaluation.

\item Assumption (ii) \textit{fails} since the (quasi-)material conditional is strictly stronger than the indicative conditional. The valuation $v(A) = 1$ and $v(B) = \nicefrac{1}{2}$ is a model of $A \to B$, but not of $A \supset B$, which takes the same truth values as $\neg A \vee B$.

\item Assumption (iii) and (v) \textit{fail} with the same countermodels as in {\sf CC/TT}.

\item Assumption (iv) holds: it is independent of the interpretation of the standard connectives and the proof for {\sf CC/TT} can be transferred.
\end{itemize}
In {\sf QCC/TT}, two steps of Gibbard's proof are blocked, corresponding to the failure of  assumptions (ii) and (v). Like before, the failure of (iii) is inessential since the proof just requires Conjunction Elimination instead of the more general property of Supraclassicality.

\begin{table}[ht]
\[
\begin{tabular}{c|ccccccc|ccc}
Condition & (i) & (ii) & (iii) & CE & (iv) & (v) & TRM & $\equiv$? & $\leftrightarrow$? & $\bim$?  \\ \hline
\dftt\ & \cmark & \cmark & \cmark & \cmark & \xmark & \xmark & \cmark & \cmark & \cmark & \cmark\\
\cctt\ & \cmark & \cmark & \xmark & \cmark & \cmark & \xmark & \cmark & \xmark & \xmark & \cmark\\
\qcctt\ & \cmark & \xmark & \xmark & \cmark & \cmark & \xmark & \cmark & \xmark & \xmark & \xmark\\
\end{tabular}\]
\captionsetup{singlelinecheck=off}
\caption[]{\footnotesize Overview of which premises of Gibbard's proof are satisfied by the logics \dftt, \cctt and \qcctt. CE = conjunction elimination (=a sufficient surrogate for (iii)), TRM = transitivity, monotonocity and reflexivity of the logic. $\equiv, \leftrightarrow, \bim$ concern whether logical, indicative, or material equivalence holds between $\supset$ and $\to$.

}
\end{table}

Since the material conditional is strictly stronger than the indicative in \qcctt, Gibbardian collapse does not happen, and moreover, neither the material nor the indicative conditional declares the two connectives equivalent:

\begin{lem}
For every $A, B \in {\sf For}(L)$:
\begin{align*}
A \supset B & \models_{\sf QCC/TT} A \rightarrow B \hspace{5pt} \text{ but } \hspace{5pt} A \to B \not{\models}_{\sf QCC/TT} A \supset B \\
& \not{\models}_{\sf QCC/TT} (A \supset B) \bim (A \rightarrow B) & & \\
& \not{\models}_{\sf QCC/TT} (A \supset B) \leftrightarrow (A \rightarrow B) & &
\end{align*}
\end{lem}
In \qcctt, the connectives are thus more distinct than in \dftt\ (where they are logically and materially equivalent) and \cctt\ (where they are not logically, but still materially equivalent). The way out provided by \qcctt\ is notable for another reason, too. Most theorists react to Gibbardian collapse either by giving up or restricting Import-Export (e.g., Stalnaker, Kratzer), or by endorsing a material implication analysis of the indicative conditional (e.g., Grice, Lewis, Jackson). Denying that $\supset$ satisfies the classical laws in a logic of conditionals---the road taken by \cctt---is already less common. However,
Cooper's

original approach is probably unique in entertaining the possibility of an indicative conditional that is strictly weaker than the material conditional. The explanation is probably that bivalent logic has been the default framework for formal work on conditionals and the material conditional represents, in that framework, the weakest possible conditional connective.

The logic \qcctt\ thus shows an original and surprising way of defining the relationship between the two connectives.