TITLE: Struggling with a Bayes theorem/conditional probability question
QUESTION [0 upvotes]: The question:
You are playing a card game where the dealer selects three cards from a playing deck; 1 red and two black. The dealer shuffles the three cards and lays them face down next to each other, so that only he knows the position of the red card. He then asks you to guess where the red card is; but he does not turn over your selected card. You win the game if you guess correctly which card is the red card. After your choice of card is made, the dealer turns over one of the cards you did not select, which is a black card (every time the game is played, the card that the dealer will turn over at this stage of the game is a black card). Now the dealer asks if you would like to change your mind. Are you better to change your mind, stick to your first selection, or doesn't it matter? Your answer must be fully justified with mathematical working. Hint: To get a feel for this question, think about the case where there are many cards (say 1000), but still only 1 red card and the dealer overturns all but 2 (998 cards).
--
Now I'm confused with how to approach this problem. I have a feeling that you need to gather the probabilities from before the event of the dealer putting the cards face down, and then after choosing a card and having to choose whether or not to change your mind.
Can anyone help me on approaching this question? Would be very appreciative. Thanks.

REPLY [0 votes]: There are three cards; 1 red, 2 black, but shuffled and face down.
You either pick a red or you don't; but the result is not revealed.   At least one of the remaining cards is black, and this is turned over.   The last card will either be red or it won't.   What is the probability that it is red?
Warning: The answer is counterintuitive, so think about it.   It may not be what you first suspect.
Hint: Construct a probability tree to help you decide.
Hint 2 Search term: "Monty Hall Problem"

 PS: Since you know this is a conditional probability problem, you should know about the law of total probability.   Let $R_p$ be the probability that you pick a red card. Let $R_o$ be the probability that the last card is red.   You want: $$\Bbb P(R_o) = \Bbb P(R_p)\,\Bbb P(R_o\mid R_p)+ \Bbb P(\neg R_p)\,\Bbb P(R_o\mid \neg R_p)$$


TITLE: Suppose an entire function $f$ is real if and only if $z$ is real. Prove that $f$ has at most $1$ zero.
QUESTION [6 upvotes]: Let $f$ be an entire function. Suppose $f(z)$ is real if and only if $z$ is real. Prove that $f$ has at most $1$ zero. How to prove? Totally I have no idea... Please give the solution in detail since I do not understand.

REPLY [10 votes]: The argument principle is useful to solve this problem. There are two ways you can think about the argument principle. One way is you use an integral formula over a closed curve and a number pops out, representing  $2\pi i$ times the number of zeros minus the number of poles. The other way is to think about how given a curve $\gamma$, not necessarily closed, the integral $\int_{\gamma}{\frac{f'(z)}{f(z)}dz}$ represents the increase in argument of $f$ along $\gamma$, i.e. how much the image of the path $\gamma$ winds around the origin. And this last number need not be an integer multiple of $2\pi i$.
Of course, these two ways of thinking are really the same, but if you are having trouble evaluating an integral, or you prefer to use a more geometric argument, it can be helpful to think about it the second way. In Gamelin's Complex Analysis p227, there is a nice example illustrating this technique:
We want to find the number of zeros of the polynomial $p(z) = z^6 + 9z^4 + z^3 + 2z + 4$ in the first quadrant. So what we do is to take a curve $\gamma$ that starts at $0$ and goes out to $R$ along the real axis, then moves counter-clockwise along the arc ${|z|=R}$ a quarter of a circle until $iR$, and then moves down the imaginary axis back to $0$. If we determine the increase in argument of $f$ along each of the three pieces of the curve, it will tell us how many zeros there are in that quarter slice. Along the real axis, $p(z) > 0$, so the argument of $f\circ\gamma$ is constant. If we have chosen $R$ large enough, the $z^6$ term will dominate the polynomial around the quarter-circle, so the increase in argument of $f\circ\gamma$ will be approximately $6$ times that of $\gamma$: $6(\frac{\pi}{2}) = 3\pi$. Then we can examine $f\circ\gamma$ for the last segment of our curve and find it contributes an additional $\pi$ to the argument. So we have a total increase of about $4\pi$ in the argument of $f$ along $\gamma$, which means there are $2$ zeros in the first quadrant.
So now to apply this idea to your problem. Let $\gamma$ be a circle of radius $R$ around $0$. The integral $\frac{1}{2\pi i}\int_{\gamma}{\frac{f'(z)}{f(z)}dz}$ will equal the number of zeros contained inside the curve, which will equal the number of zeros of $f$ on the real interval $[-R,R]$, since our hypothesis tells us the zeros can only occur on the real axis. How much can the argument of $f$ increase along $\gamma$? First consider the increase around the upper half of the circle. $\gamma(t) \in \mathbb{R}$ exactly when $t$ equals $0$ or $\pi$, so by our hypothesis, these are the only times $f\circ\gamma$ can cross the real axis. So from $t$ equals $0$ to $\pi$, the argument can only increase by exactly $\pi$ or $-\pi$. Then the same argument applies to the bottom half of the circle $\gamma$. So as $\gamma$ goes counter-clockwise around the origin, $f\circ\gamma$ will have an increase in argument of $2\pi$, $0$, or $-2\pi$. But the last possibility is excluded because our function has no poles.


text:
\paragraph{Context.}

When the outcome of interest is generated by a black box model which cannot be easily evaluated, a well-spread technique is to build a surrogate model allowing to reproduce the behavior of the true model while being computationally cheaper. This approach, known as \textit{response surface}, is popular in many fields of engineering such as \textit{reliability analysis} \citep{bucher1990fast}, \textit{aerospace science} \citep{forrester2009recent}, \textit{energy science} \citep{nguyen2014review}, or electromagnetic dosimetry \citep{azzi2019surrogate}, to name a few. In addition, the response surface methodology is useful in applied mathematics, for instance, in \textit{optimization} when the objective function is difficult to evaluate \citep{jones:2001} and in \textit{Monte Carlo integration}, where a surrogate function can be used to reduce the variance of the Monte Carlo estimate with the help of control variates \citep{portier+s:2019}. For a general presentation of the response surface methodology, we refer to \citet{myers2016response}.

\paragraph{Framework.}

The statistical framework of a response surface is as follows. Consider a real-valued function $f$ defined on a state space $\Xc$, that is, $f:\Xc \to \reals$. In many applications, the function $f$ is a black box and difficult to evaluate.  For instance, a request to $f$ might be obtained by running a heavy computer program. In such a situation, one can afford only a few requests to $f$, that is, one can obtain $f(X_1),\ldots, f(X_n)$, where $n\in \N$ and $X_1,\ldots, X_n$ is an independent sample of $\Xc$-valued random variables with distribution $P$, called the inputs or the covariates. Based on those evaluations, the goal is to build a \textit{surrogate model}, that is, an approximation of $f$ which is easier to calculate than $f$ itself.

Many different methods can be used to build a surrogate model. The simplest one consists in learning $f$ as a linear combination of the covariates by minimizing the sum of squared errors. A well spread extension is to fit a polynomial function instead of a linear one as presented in \citet{myers2016response} or \citet{konakli2016polynomial}.
Since building a response surface consists in the same task as regression, any regression method might be used in principle. Popular methods include moving least-squares \citep{breitkopf2005}, Gaussian processes \citep{frean2008using} or neural nets \citep{bauer2019estimation}. For surrogate models, the approximation method needs to be sufficiently flexible to fit the black box function $f$ well and simple enough to require only a small amount of computations. It is perhaps due to its connection to the regression framework that the problem of building surrogate models has received little specific attention in the statistical learning literature. Our purpose is to address the question of learning many surrogate models simultaneously from a single, random design.

\paragraph{Learning several models simultaneously.}

The fundamental question raised in this paper deals with the ability of building several, possibly infinitely many, surrogate models such that (a) they share the same quality and (b) they are constructed with the help of a single input sample.
From a theoretical standpoint, it relates to the question of \textit{uniformity} over the tasks: can a broad family of models be learnt with a uniform level of accuracy?
From a more practical point of view, by working with the same inputs to solve multiple tasks simultaneously, one benefits from a certain computational advantage, as explained below.

Consider a broad class $\Fc$ of black box models $f$. For each such model $f$, a least-squares estimate is obtained out of the linear span of the components of the $d$-dimensional feature map $h = (h_1,\ldots, h_d)^\T : \Xc \to \Rd$, where ${}^\T$ denotes matrix transposition. The feature map $h$ should be known and easy to evaluate. Define the ordinary least squares estimate
\[
	\hat{\beta}_f \in \argmin_{b\in \Rd}  \sum_{i=1}^n \{ f(X_i) -  h(X_i)^\T b \} ^2 .
\]
The surrogate model for $f$ is then defined as $x \mapsto \hat{f}(x) = h(x)^\T \hat{\beta}_f$.

This approach is known as \textit{series estimators} or simply as \textit{least squares estimators} \citep{hardle1990applied, gyorfi2006distribution}. It is quite general as several basis functions might be considered such as polynomials, indicators, spline functions or the Fourier basis. In the regression framework, series estimators have been studied for instance in \citet{newey1997convergence} and \citet{belloni2015some}. Series estimators are a convenient way to include shape constraints on $f$, as for instance when $f$ is partially linear. They also facilitate the computation of derivatives \citep{zhou2000derivative}. In this respect, series estimators can help to build \textit{easy-to-interpret} models, a desirable feature when one is in need of some knowledge about the effects of certain inputs on the black box model $f$.

One motivation for the use of series estimators is the computational advantage they provide when several models are to be learnt at the same time. When a large number $m$ of such surrogate models $f$ are built with different covariates, running $m$ least-squares algorithms, for instance using the Cholesky decomposition, requires $\Oh(m n d^2)$ operations \citep[Section~3.5]{friedman2001elements}, assuming that $d = \Oh(n)$. In our framework of a single training sample, however, the Cholesky decomposition needs to be done only once, and the time needed to compute $m$ least squares estimates is rather $\Oh( n d^2 + m n d)$.

\paragraph{Uniform convergence rate in random design with increasing dimension.}

For a given model $f \in \Fc$, the error made by a surrogate model $x \mapsto h(x)^\T b$ with coefficient vector $b \in \Rd$ is measured through the $L^2(P)$-risk
\begin{equation*}
	L_f (b)
	= \int_{\Xc} \{f(x) - h(x)^\T b\}^2 \, \diff P(x)
	= \expec [ \{ f(X) -  h(X)^\T b \}^2],
\end{equation*}
where the $\Xc$-valued random variable $X$ has distribution $P$. We place ourselves in the random design setting and study the risk $L_f(\hat{\beta}_f)$ of the least squares estimator $\hat{\beta}_f$. This risk is a random variable whose randomness stems from the one of the training sample $X_1, \ldots, X_n$.

The main result of the paper concerns the \textit{excess risk} $L_f(\hat{\beta}_f) - \min_{b \in \Rd} L_f(b)$ when $n \to \infty$ and $d\to \infty$, uniformly over $f \in \Fc$. That is, we study the convergence rate to zero of the random variable $\supf \{ L_f(\hat{\beta}_f) -  \min_{b\in\Rd}  L_f(b) \}$. A key quantity is the \emph{leverage function} $q : \Xc \to [0, \infty)$ defined by
\[
	\forall x \in \Xc, \qquad
	q(x) = h(x)^\T  G^{-1}  h(x) ,
	\]
	where $G = \expec[h(X) h(X)^\T]$ is the $d \times d$ Gram matrix of the feature map.
The leverage function is the population version of the \textit{statistical leverage} of a feature vector $h(X_i)$ in the linear regression model. It plays an important role when analyzing regression with random design \citep{hsu+etal:2014}. Note that $q$ does not change if the feature map is composed with an invertible linear transformation.
Let $\eps_f = f - h^\T \beta_f$ be the error function, with $\beta_f = \argmin_{b \in \Rd} L_f(b)$ the risk-minimizing coefficient vector. Our main result, expressed in Corollary~\ref{cor:simple-rate}, is that
\[
		\sup_{f \in \Fc} \left\{ L_f(\hat{\beta}_f) - \min_{b\in\Rd}  L_f(b) \right\}
		= \Op\left( \frac{\log n}{n} \supf \expec [ q(X)  \eps_{f}^2(X)] \right), \qquad n \to \infty.
\]
Apart from the fact that the obtained bound is invariant under invertible linear transformations of the feature map, this result is remarkable for the three following reasons. First, the dimension $d$ of the feature space is allowed to tend to infinity with the input sample size $n$ at a speed which depends on the leverage function $q$ via Condition~\ref{cond:qn}. Second, in case the class $\mathcal F$ contains only a single response function $f$, a simple analysis leads to a bound for the excess risk that scales as $  \expec [ q(X)  \eps_{f}^2(X)] / n $, see Eq.~\eqref{eq:gamma}, a bound that matches the one of our main result up to a logarithmic term. Third, the quantity $ \expec [ q(X)  \eps_{f}^2(X)] $ takes over the role of the quantity $\sigma_f^2 d$ in the fixed-design setting, where $\sigma_f^2$ is the variance of the error variable in the linear model.

The uniformity in $f \in \Fc$ is achieved by a decomposition of a quadratic form in terms of a sample mean and a U-statistic in combination with a concentration inequality for the suprema of such statistics. The analysis is focused on the ordinary least squares estimator, whereas the extension to ridge regression as in \citet{hsu+etal:2014} is left for further research.

\paragraph{Application to Monte Carlo integration with control variates.}

The past few years, Monte Carlo integration has received increasing interest because of its simplicity and its success facing complex high-dimensional approximation problems. The standard Monte Carlo error has a convergence rate of $1/\sqrt n $, independently of the dimension---see \cite{novak2016} for a review of deeper results around this point. Although a dimension-free convergence rate is comfortable, $1/\sqrt n $ is still relatively slow and some difficulties might arise in situations where we can only make a limited number of requests to the integrand.
The use of control variates \citep{owen:13,glasserman:2013} has then represented an interesting avenue as it allows to reduce the variance of the standard Monte Carlo estimate without requiring additional evaluations of the integrand.
Recently, it has been shown \citep{oates+g+c:2017,portier+s:2019} that control variates allow to accelerate the $1/\sqrt n $ convergence rate substantially.
However, whether this acceleration occurs when the error is measured uniformly over a class of integrand functions is, to the best of our knowledge, still unknown.
Motivated by several applications in which uniform results are needed (see Section~\ref{sec:MC} for details), we obtain, as a by-product of the bound in Corollary~\ref{cor:simple-rate}, a uniform convergence rate for control variate Monte Carlo estimates. The fact that the rate established is faster than the standard Monte Carlo rate furnishes an additional argument for the use of control variates in Monte Carlo methods.

\paragraph{Paper outline.}

The mathematical background is presented in Section~\ref{sec:set-up}. The main result and a sketch of its proof are presented in Sections~\ref{sec:thm} and~\ref{sec:proof}, respectively.
The application to control variate Monte Carlo methods is considered in Section ~\ref{sec:MC}.
Detailed proofs are deferred to the appendices.

config: arxiv


TITLE: Is an open subset of a compact surface with connected boundary completely determined by its fundamental group?
QUESTION [4 upvotes]: Is an open, connected subset of a compact surface with connected boundary  determined (up to homeomorphism) by its fundamental group?

If we weaken the hypotheses, I can see how this can fail:

A cylinder and circle are both subsets of the torus with $F_1$ as their fundamental group, so the requirement that the subset be open is necessary.
A torus with a point removed and a twice-puntured disk both have $F_2$ as their fundamental group, so the result can fail if we allow subsets with disconnected boundaries.
Since a disconnected spaces does not generally have a single uniquely defined fundamental group (we have to specify where the base point lies), requiring connectedness seems reasonable.

It seems like open subsets of a compact surface with a connected boundary are sufficiently 'nice' that this result could hold.
This question came to me when I was answering this question: if it were true, then we could enumerate the possible faces of a graph embedding in any surface $S$ by simply enumerating the subgroups of $S \setminus \{p\}$.

REPLY [3 votes]: I interpret your question as "if $X$ is an open subset of a closed surface, and has only one end, is it determined by its fundamental group?"
Yes. In fact, a surface $\Sigma$ with one end and fundamental group $F_{2g}$ is homeomorphic to the punctured genus $g$ surface, and this is the only possible fundamental group. To prove this use the observation of this answer and exploit the fact that, because $\Sigma$ is an open subspace of a closed surface, it cannot have infinite genus.


TITLE: Given odd positive integer, $n=2m-1$, $n \equiv 1 \pmod 4 \implies m \equiv 1 \pmod 2$
QUESTION [1 upvotes]: $n=2m-1\implies n+1=2m$. So, $n\equiv 1\pmod 4, 2m=n+1\equiv 2\pmod 4\implies 2m=n+1\equiv 0\pmod 2$ $\implies n\equiv -1\pmod 2\implies n\equiv 1\pmod 2$. But, how to find $m$ from this last line of equivalence relations is not clear.

REPLY [1 votes]: $$n = 2m-1\equiv 1\pmod{4}\quad\Rightarrow\quad
  2m \equiv 2\pmod{4}.$$
Now, note that in general, if $k\ne 0$ and $ak\equiv bk\mod{ck}$, this means that $ak$ is $bk$ plus a multiple of $ck$, say $rck$:
$$ak = bk + rck.$$
Dividing through by $k$ gives $a = b+cr$, so that $a\equiv b\mod c$. Applying this to $2m\equiv 2\mod{(4 = 2\cdot 2)}$ gives
$$m\equiv 1\pmod{2}.$$


TITLE: prove that $2 < [\bar{F} : F] < \infty$ is impossible
QUESTION [1 upvotes]: Let $F$ be a Field, and $\bar{F}$ be an algebraic closure of $F$
I want to prove that $2 < [\bar{F} : F] < \infty$ is impossible.
For $[\bar{F}:F]=2$, I know there is Artin-Schreire theorem  which characterized this special case and classify such $F$
It seems to me that $[\bar{F} : F]=\infty$ gives $\bar{F} \simeq F^{\infty}$...
How this is possible?

REPLY [2 votes]: This is exactly the Artin–Schreier theorem:

If a field $F$ is not algebraically closed but its algebraic closure $C$ is a finite extension of $F$, then $C = F (i)$ with $i^2=-1$.

For a proof, see an exposition by Keith Conrad.


TITLE: Empty Space - Could we exist without it?
QUESTION [1 upvotes]: I have been giving empty space much thought. I imagined reaching the edge of the Universe and thought of 2 scenarios(focusing on 1):

There is no more empty space
1.1 Would space extend with me if say I just crossed over?
1.2 Could anything exist without empty space? Time?
More empty space - nothing else

I'm working(in thought process) on a conjecture. Maybe I'm on to something, maybe not.

I love thought experiments.

REPLY [2 votes]: "Empty Space" is a name that is a little misleading from the standpoint of modern physics.
Suppose we evacuate a vessel, and clad it in impenetrable radiation shielding, so that there are no molecules or atoms within, and there are no gammas or cosmic rays. In everyday speech, we would say that the vessel has "empty space within it".
However, modern physics thinks of space and time to be made of quantum fields: a handful of them. So, our everyday statement would more accurately be rendered: in this region of space, the electron field is in its ground state, the electromagnetic field is in its ground state, and so forth. The quantum fields are in their ground states, but they most assuredly are still there. The process of the vessel's evacuation can now be thought more accurately as the driving of the quantum fields into their ground states, rather than an "emptying process".
Likewise for the question about the "edge of the Universe". We can only exist in spacetime that is already there. We can't reach an "edge" and "make" spacetime as we cross it. It is quite possible that the Universe is topologically compact, meaning roughly that one can in principle follow a "constant direction" path (this notion has some fiddly technicalities, but think of following a great circle on a spherical balloon) and not keep going forever, but rather return to one's beginning point. There are no edges to such a spacetime. Moreover, there is not an "outside" to the Universe: such a thing simply does not exist by definition of the "Universe". It is possible that the universe is finite and compact without edges, or it could indeed be infinite. If the former, there is still no "outside".
So "empty space" really is a kind of "stuff" that can have inhomogeneous properties: in General Relativity, one can quite definitely say that this piece of spacetime over here can have different geometrical properties from another piece over there.
In answer to your title: we, just like empty space, are made of quantum fields, so we couldn't exist without there at least being the possibility of quantum fields in their ground state, i.e. the existence of empty space is a necessary condition for our existence.