TITLE: Uniform distribution on the unit circle
QUESTION [4 upvotes]: Determine the probability density function on the unit circle $U:=\{(x,y)\in\mathbb{R}^2:x^2+y^2 =1\}$ with respect to the Lebesgue measure $\lambda$. Calculate the marginal distributions $f_X$ and $f_Y$ if the random positions on the unit circle in the euclidian coordinate system are interpreted as a two-dimensional random variable $(X,Y)$.
Now, if we set $(x,y) = (\cos\theta,\sin\theta)$, the probability density function would be $f(\theta) = \frac{1}{2\pi}$. But I cannot figure out how to determine the marginal distributions then, as this is only a one-dimensional object and with respect to $\lambda$, not $\lambda^2$.

REPLY [3 votes]: It is possibly easier to do this as a cumulative distribution function first
Clearly $\mathbb P(X\le x)=0$ for $x \le -1$ and $\mathbb P(X\le x)=1$ for $x \ge 1$
You have not specified the support of $\Theta$, though $(-\pi, \pi]$ and $[0, 2\pi)$ are common choices; either will do here
For $-1 \lt x \lt 1$ we have: $$\mathbb P(X \le x) = \mathbb P(\cos(\Theta) \le x) = 2\mathbb P(\cos^{-1}(x) \le \Theta \le \pi) = 1 - \tfrac1\pi \cos^{-1}(x)$$
Taking the derivative we get $$f_X(x) = \frac{1}{\pi\sqrt{1-x^2}}$$ for $|x| \lt 1$, and $f_X(x)=0$ for $|x| \gt 1$, and the marginal density for $Y$ is the same by symmetry


TITLE: How prove this equality $(x^2+2)(y^2+2)(z^2+2)\ge (\sqrt{y^2+yz+z^2}+\sqrt{z^2+zx+x^2}+\sqrt{x^2+xy+y^2})^2$
QUESTION [2 upvotes]: let $x,y,z>0$,and such
$$x+y+z=3$$
prove or disprove this
$$(x^2+2)(y^2+2)(z^2+2)\ge (\sqrt{y^2+yz+z^2}+\sqrt{z^2+zx+x^2}+\sqrt{x^2+xy+y^2})^2\tag{1}$$

I know this well know  inequality 1
  $$(a^2+2)(b^2+2)(c^2+2)\ge 3(a+b+c)^2$$
and we all know this inequality 2
  $$(\sqrt{b^2+bc+c^2}+\sqrt{c^2+ca+a^2}+\sqrt{a^2+ab+b^2})^2\ge 3(a+b+c)^2$$

poof 1: since
$$(b-c)^2+2(bc-1)^2\ge 0$$
so
$$(b^2+2)(c^2+2)\ge 3\left(1+\dfrac{(b+c)^2}{2}\right)$$
Use Cauchy-Schwarz inequality ,we have
$$(a^2+2)\left(1+\dfrac{(b+c)^2}{2}\right)\ge (a+b+c)^2$$
By done!
proof 2: since
$$\sqrt{b^2+bc+c^2}=\sqrt{\dfrac{3}{4}(b+c)^2+\dfrac{1}{4}(b-c)^2}\ge\dfrac{\sqrt{3}}{2}(b+c)$$
so
$$\sum_{cyc}\sqrt{a^2+ab+b^2}\ge\sqrt{3}(a+b+c)$$
then
$$(\sqrt{b^2+bc+c^2}+\sqrt{c^2+ca+a^2}+\sqrt{a^2+ab+b^2})^2\ge 3(a+b+c)^2$$
By done!
But my inequality (1) is stronger this two  inequality.Thank you

REPLY [3 votes]: $(\sqrt{y^2+yz+z^2}+\sqrt{z^2+zx+x^2}+\sqrt{x^2+xy+y^2})^2 \le 3(y^2+yz+z^2+z^2+zx+x^2+z^2+zx+x^2) \iff $
$(x^2+2)(y^2+2)(z^2+2)- 3(y^2+yz+z^2+z^2+zx+x^2+z^2+zx+x^2) \ge0 \iff x^2y^2z^2+2y^2z^2+2x^2z^2-2z^2-3yz-3xz+2x^2y^2-2y^2-3xy-2x^2+8\ge 0 $$ \tag 2$
let $3u=x+y+z,3v^2=xy+yz+xz,w^3=xyz,\to u=1\ge v \ge w$,
$(2)$ becomes:
$ w^6-24v^2w^3+3v^2+20 \ge 0  \iff w^6-24 w^3+3w^2+20\ge 0$      $ (3)$
$w^6+w^2+1\ge 3w^{\frac{8}{3}} \ge 3 w^3, 19+2w^2 \ge 21w^3 \implies $ $(3)$ is true.
the "=" will hold when $v=w=1=u \implies x=y=z=1$
QED.


TITLE: Given that $x \in \Bbb{R}^n$ and $p, q \in (1, \infty)$, maximize $||x||_q$ subject to $||x||_p = 1$
QUESTION [0 upvotes]: How do I maximize $||x||_q$ subject to $||x||_p = 1$? Are there any useful inequalities I could consider? I know that if $0 < p < q$, then $||x||_p \ge ||x||_q$, so $||x||_q \le 1$. This is attainable with $x = (1, 0, 0, ..., 0)$ so that is the maximum.
If $p = q$, then it is obviously just $1$.
The other case is $q < p$ in which case $||x||_q \ge ||x||_p = 1$. But, well, I don't know how to show it must be $\le 1$ as well. Perhaps there are some other inequalities I could use to obtain an upper bound?

REPLY [2 votes]: Using what proved here we know that $$\left \| x \right \|_q \leq n^{\frac{1}{q}-\frac{1}{p}}\left \| x \right \|_p$$
Which means that if $\left \| x \right \|_p=1$ we can get at most the value $n^{\frac{1}{q}-\frac{1}{p}}$. However, this is also the maximum itself since for $x_{opt}=n^{-\frac{1}{p}}\mathbf{1}$ of $p$-norm $1$
$$\left \| x_{\text{opt}} \right \|_q =\left ( n\cdot n^{-\frac{q}{p}} \right )^{\frac{1}{q}}=n^{\frac{1}{q}-\frac{1}{p}}$$


TITLE: If we know that $\sum_{n=1}^\infty a_n$ converges, can we conclude that $\sum_{n=1}^\infty \frac{1}{a_n}$ diverges?
QUESTION [0 upvotes]: Suppose that we have $a_n > 0$.  Then if we know that $\sum_{n=1}^\infty a_n$ converges, can we conclude that $\sum_{n=1}^\infty \frac{1}{a_n}$ diverges?
On the contrary, if we know that $\sum_{n=1}^\infty a_n$ diverges, can we conclude that $\sum_{n=1}^\infty \frac{1}{a_n}$ converges?

REPLY [3 votes]: $$\sum_{n=1}^\infty a_n\text{ converges}\implies \lim_{n\to\infty}a_n=0$$
$$\implies\lim_{n\to\infty}\frac1{a_n}\ne0\implies \sum_{n=1}^\infty\frac1{a_n}\text{ diverges}$$


TITLE: Maybe a question of the Mean-value theorem of the Integral
QUESTION [0 upvotes]: $\phi(x)$ is bounded on $I_n=[\xi-\epsilon_n,\xi+\epsilon_n]$ and $\phi(\xi)\neq0$ ,where $\phi$ is continue at $\xi$, and $\epsilon_n=o(1)$ .
$h(x)\in C^2$ is continous ,and $\xi$ is the only maximum point of $h(x)$.
How does this come ?:
$$\int_{I_n}\phi(x)e^{n(h(x)-h(\xi))}dx$$
$$=(1+o(1))\phi(\xi)\int_{I_n}e^{n(h(x)-h(\xi))}dx$$
as $n\rightarrow \infty$

REPLY [0 votes]: Let $M_n=\max_{I_n} \phi(x)$ and $m_n=\min_{I_n} \phi(x)$.
Then for the integral
$$  m_n \int_{I_n} e^{n(h(x)-h(\xi))} dx \leq \int_{I_n} \phi(x) e^{n(h(x)-h(\xi)} dx
\leq M_n \int_{I_n} e^{n(h(x)-h(\xi))} dx $$
and
$$ m_n\int_{I_n} e^{n(h(x)-h(\xi))} dx \leq \phi(\xi) \int_{I_n}  e^{n(h(x)-h(\xi)} dx
\le M_n \int_{I_n} e^{n(h(x)-h(\xi))} dx $$
but since  $(M_n-m_n)= \phi(\xi)+o(1)$ due to the continuity of $\phi$,
we get  it.


TITLE: Why does water keep dripping out of the bucket even after the faucet is turned off?
QUESTION [2 upvotes]: So I just noticed that when I filled my bucket with water until it overflowed and then I turned the faucet off, the water kept dripping for like 20 seconds. Why does this happens? Shouldn't it have stopped dripping sooner after I turned the faucet off?

REPLY [1 votes]: There are two possible scenarios here, which I don't know which it is unless I have more details.
One is where you fill slowly until overflow just begins to happen; this results in Adrian's answer, which I will elaborate on a bit:
The surface tension of water means that the water level can rise above the level of the bucket edge by forming a "bubble" above the lip; Laplace pressure, pressure due to the curvature of such a surface (surface geometry looks like the illustration here), counteracts gravitational pressure, preventing the water from spilling. Once you overfill enough, this pressure is no longer sufficient, the surface breaks, and water begins to spill; once it does, the vertical curvature at the overflow point reduces (to form the outflow stream), weakening the Laplace pressure, which results in the water continuing to spill out until the level lowers enough that the gravitational pressure is lower than the new, lowered Laplace pressure.
The other scenario is where you fill the water fast. Here, it's just due to the inertial and viscosity forces of the fluid; there must be a surface level imbalance for fluid with weight/viscosity to flow (think a river, flowing from high to low), which means there is a gradient in surface level from where you're filling the bucket to where it is spilling out (flow requires a pressure gradient, which results in a surface level gradient); once you stop the inflow, the fluid will leak until the surface is level, which takes some time. At low flows, the surface level gradient is rougly proportional to flow, which means that technically, without any other effects, the flow will only exponentially decay rather than actually stop; however, surface tension as mentioned above will eventually cause water to abruptly stop flowing.


TITLE: Forcing and antichains
QUESTION [2 upvotes]: What would be a good way to show:
If $p \Vdash (\exists\alpha)  \phi(\alpha)$, then there is an antichain $A$ maximal below $p$, and a set of ordinal $\{\gamma_{q} | q \in A\}$ s.t. $(\forall q \in A$) $q \Vdash \phi(\gamma_{q})$

REPLY [2 votes]: Use the mixing lemma to conclude that there exists a name $\dot x$ such that $p\Vdash\dot x\in\check{\sf Ord}$ such that $p\Vdash\phi(\dot x)$.
Now consider $\{q\leq p\mid\exists\alpha\in{\sf Ord}:q\Vdash\check\alpha=\dot x\}$.
This is a dense [and open] set, so we immediately have that there is only a set of possible ordinal values for $\dot x$, and by thinning it out to a maximal antichain we have as wanted.


TITLE: understanding if a point is inside or outside a Koch fractal curve
QUESTION [5 upvotes]: I continue this post because i have a problem: understand if a point is inside or outside a Koch curve.
I can find the third point of a equilateral triangle (and i need it for build a koch curve) but i have 2 solution: now i have to decide which one is the best (the one that is outside the koch curve)!
this figure explain better:

the little equilateral triangle in the red circles have the wrong direction.
Some ideas?

REPLY [2 votes]: (Assuming this is related to programming, as the link indicates.)
If you give each segment a consistent orientation (just a choice of ordering on the two endpoints), then you will always be able to tell 'inside' from 'outside'. For example, suppose I have a segment oriented ($a$, $b$), where $a$ and $b$ are endpoints.  Then I want to introduce trisecting points $a'$ and $b'$ (so the order I have in mind is $a$, $a'$, $b'$, $b$), then I choose $c$ not on the segment so that $a'c$ has the same length as $b'c$.  Of course there are two such points $c$ (hence the question, right?).  Let $\mathbf{u} = \vec{ab}$ and $\mathbf{v} = \vec{ac}$.  We must choose $c$ so that the acute angle between $\mathbf{u}$ and $\mathbf{v}$ is swept out from $\mathbf{u}$ to $\mathbf{v}$ in a counterclockwise direction.  One way to do this is to consider $\mathbf{u}, \mathbf{v}$ as 3-dimensional vectors with 0 component in the $z$ direction.  Then take the cross product $\mathbf{u} \times \mathbf{v}$.  If the result has a positive $z$-component, then the choice of $c$ was correct, while if it is negative, then other choice of $c$ was incorrect -- choose the other one.  Note, since both $\mathbf{u}, \mathbf{v}$ live on the $xy$-plane, their cross product will only have a $z$-component.  Also note, it is essential to know the order of $a$ and $b$ for this to work.  To prepare for the next iteration, orient the new segments thus: $(a, a'), (a', c), (c, b'), (b', b)$.
Hope this helps!


text:
\section{Stochastic Search for Online GEV}

For GEV, we propose a fully stochastic primal-dual algorithm to solve \eqref{eqn:minimax}, which only requires access to the stochastic approximations of $A$ and $B$ matrices. This is very different from other existing semi-stochastic algorithms that require to access the exact $B$ matrix~\citep{ge2016efficient}. Specifically, we propose a stochastic variant of the generalized Hebbian algorithm (GHA), also referred as Sanger's rule in existing literature \citep{sanger1989optimal}, to solve \eqref{eqn:minimax}. For online setting, accessing the exact $A$ and $B$ is prohibitive and we only get $A^{(k)}\in\RR^{d \times d}$ and $B^{(k)}\in\RR^{d \times d}$ that are independently sampled from the distribution associated with $A$ and $B$ at the $k$-th iteration. Our proposed SGHA updates primal and dual variables as follows:

\begin{align}
 \text{Primal Update: } &X^{(k+1)} \gets X^{(k)}-\eta\cdot \hspace{-0.25in}\underbrace{\left(B^{(k)} X^{(k)} Y^{(k)} -  A^{(k)} X^{(k)} \right),}_{\textrm{Stochastic Approximation of $\nabla_{X}\cL(X^{(k)},Y^{(k)})$}} \label{alg:primal_update}\\
 \text{Dual Update: }
&Y^{(k+1)}  \gets \hspace{-0.45in}\underbrace{X^{(k)\top}  A^{(k)} X^{(k)},}_{\textrm{Stochastic Approximation of $X^{(k)\top}AX^{(k)}$}} \label{alg:dual_update}
\end{align}
where $\eta >0$ is a step size parameter.  Note that the primal update is a stochastic gradient descent step, while the dual update is motivated by the KKT conditions of \eqref{eqn:minimax}. SGHA is simple and easy to implement. The constraint is naturally handled by the dual update. Further, motivated by the the landscape of GEV, we analyze the algorithm by diffusion approximations and obtain the asymptotical sample complexity.

\subsection{Numerical Evaluations}
We first provide numerical evaluations to illustrate the effectiveness of SGHA, and then provide an asymptotic convergence analysis of SGHA. We choose $d=500$ and select three different settings:

\begin{itemize}[leftmargin=*]
\item {$\boldsymbol{\textrm{\bf Setting} (1): }$}  $\eta=10^{-4}$, $r=1$, $A_{ii} = 1/100$~~$\forall i \in [d]$, $A_{ij} = 0.5/10$ and $B_{ij}=0.5^{|i-j|}/3$~~$\forall i\neq j$;
\item {$\boldsymbol{\textrm{\bf Setting} (2): }$} $\eta=5\times 10^{-5}$, $r=3$, and randomly generate an orthogonal matrix $U\in\RR^{d\times d}$ such that $A= U\cdot\diag(1,1,1,0.1,...,0.1)\cdot U^\top$ and $B=U\cdot\diag(2,2,2,1,...,1)\cdot U^\top$;
\item {$\boldsymbol{\textrm{\bf Setting} (3): }$} $\eta=2.5\times 10^{-5}$, $r=3$, and randomly generate two orthogonal matrices $U,V\in\RR^{d\times d}$ such that $A= U\cdot\diag(1,1,1,0.1,...,0.1)\cdot U^\top$ and $B=V\cdot \diag(2,2,2,1,...,1)\cdot V^\top$.
\end{itemize}

\begin{figure}
	\centering
	\subfigure[Setting (1)]{
		\includegraphics[width=0.3\textwidth]{./figure/Exp1}\label{setting-1}
	}
	\subfigure[Setting (2)]{
		\includegraphics[width=0.3\textwidth]{./figure/Exp2}\label{setting-2}
	}
	\subfigure[Setting (3)]{
		\includegraphics[width=0.3\textwidth]{./figure/Exp3}\label{setting-3}
	}
	\caption{Plots of the optimization error $\norm{B^{1/2}X^{(t)}X^{(t)\top}B^{1/2}-B^{1/2}X^{*}X^{*\top}B^{1/2}}_{\rm F}$ over SGHA iterations on synthetic data of 20 random data generations under different settings of parameters.}
\label{numerical-results}
\end{figure}

At the $k$-th iteration of SGHA, we independently sample $40$ random vectors from $N(0,A)$ and $N(0,B)$ respectively. Accordingly, we compute the sample covariance matrices $A^{(k)}$ and $B^{(k)}$ as the approximations of $A$ and $B$. We repeat numerical simulations under each setting for $20$ times using random data generations, and present all results in Figure \ref{numerical-results}. The horizontal axis corresponds to the number of iterations, and the vertical axis corresponds to the optimization error $$\norm{B^{1/2}X^{(t)}X^{(t)\top}B^{1/2}-B^{1/2}X^{*}X^{*\top}B^{1/2}}_{\rm F}.$$ Our experiments indicate that SGHA converges to a global optimum in all settings.

\subsection{Convergence Analysis for Commutative $A$ and $B$}

As a special case, we first prove the convergence of SGHA for GEV with $r=1$, and $A$ and $B$ are commutative. We will discuss more on noncommutative cases and $r>1$ in the next section. Before we proceed, we introduce our assumptions on the problem.
\begin{assumption}\label{assmp}
We assume that the following conditions hold:
\begin{itemize}[leftmargin=*]
\item {\bf (a):} $A^{(k)}$'s and $B^{(k)}$'s are independently sampled from two different distributions $\cD_A$ and $\cD_B$ respectively, where $\EE A^{(k)} = A$ and $\EE B^{(k)}=B \succ 0$;
\item{\bf(b):} $A$ and $B$ are commutative, i.e., there exists an orthogonal matrix $O$ such that $A = O\Lambda^{A}O^\top$ and $B = O\Lambda^{B}O^\top$, where $\Lambda^A=\diag(\lambda_1,...,\lambda_d)$ and $\Lambda^B=\diag(\mu_1,...,\mu_d)$ are diagonal matrices with $\lambda_j\neq 0$;
\item {\bf(c):} $A^{(k)}$ and $B^{(k)}$ satisfy the moment conditions, that is, for some generic constants $C_0$ and $C_1$, $\EE {\norm{A^{(k)}}_2^2}\leq C_0$ and $\EE {\norm{B^{(k)}}_2^2}\leq C_1$.
\end{itemize}
\end{assumption}
Note that (a) and (c) in \eqref{assmp} are mild, but (b) is stringent. For convenience of analysis, we combine \eqref{alg:primal_update} and \eqref{alg:dual_update} as
\begin{align}\label{update}
 X^{(k+1)} \gets  X^{(k)} - \eta \big(B^{(k)} X^{(k)} X^{(k)\top} \hspace{-0.035in}- I_d \big) A^{(k)} X^{(k)}.
\end{align}
We remark that \eqref{update} is very different from existing optimization algorithms over the generalized Stiefel manifold. Specifically, computing the gradient over the generalized Stiefel manifold requires $B^{-1}$, which is not allowed in our setting. For notational convenience, we further denote
\begin{align*}
\Lambda=(\Lambda^B)^{-\frac{1}{2}} \Lambda^A (\Lambda^B)^{-\frac{1}{2}}=\diag\left(\frac{\lambda_1}{\mu_1},...,\frac{\lambda_d}{\mu_d}\right)=:\diag(\beta_1,\cdots,\beta_d).
\end{align*}
Without loss of generality, we assume $ \beta_1>\beta_2 \geq \beta_3 \geq\cdots\geq\beta_d,$ and $\beta_i\neq 0~~\forall i\in[d]$. Note that $\mu_i$ and $\lambda_i$, however, are not necessarily to be monotonic. We denote
\begin{align*}
\mu_{\min}=\min_{i \neq 1} \mu_i,\quad \mu_{\max}=\max_{i\neq 1} \mu_i,\quad \textrm{and}\quad {\sf gap}=\beta_1-\beta_2.
\end{align*}
 Denote $W^{(k)}=(\Lambda^{B})^\frac{1}{2}O X^{(k)}$.  One can verify that \eqref{update} can be rewritten as follows:
\begin{align}\label{equivalent}
 W^{(k+1)}&\gets W^{(k)}-\eta\Big((\Lambda^B)^{\frac{1}{2}}\hat{\Lambda}_B^{(k)}(\Lambda^B)^{-\frac{1}{2}}\cdot W^{(k)}W^{(k)\top} - \Lambda^B \Big) \cdot\tilde{\Lambda}^{(k)}W^{(k)},
\end{align}
where $\hat{\Lambda}_B^{(k)}= O^{\top} B^{(k)}O$ and $\tilde{\Lambda}^{(k)}=O^{\top} B^{-\frac{1}{2}} A^{(k)}B^{-\frac{1}{2}}O.$ Note that $W^*=(1,\underbrace{0,0,...,0}_{(d-1)})^\top$ corresponds to the optimal solution of \eqref{eqn:original}.

By diffusion approximation, we show that our algorithm converges through three Phases:
\begin{itemize}[leftmargin=*]
\item{\bf Phase I:} Given an initial near a saddle point, we show that after rescaling of time properly, the algorithm can be characterized by a stochastic differential equation (SDE). Such an SDE further implies our algorithm can escape from the saddle fast;
\item{\bf Phase II:}  We show that away from the saddle, the trajectory of our algorithm can be approximated by an ordinary differential equation (ODE);
\item{\bf Phase III:} We first show that after Phase II, the norm of solution converges to a constant. Then, the algorithm can be characterized by an SDE, like Phase I. By the SDE, we analyze the error fluctuation when the solution is within a small neighborhood of the global optimum.
\end{itemize}
Overall, we obtain an asymptotic sample complexity.

\noindent{\bf ODE Characterization:} To demonstrate an ODE characterization for the trajectory of our algorithm, we introduce a continuous time random process
\begin{align*}
w^{(\eta)}(t):=W^{(k)},
\end{align*}
where $k=\lfloor \frac{t}{\eta}\rfloor$ and $\eta$ is the step size in \eqref{update}. For notational simplicity, we drop $(t)$ when it is clear from the context. Instead of showing a global convergence of $w^{(\eta)}$, we show that the quantity
\begin{align*}
v^{(\eta)}_{i,j}=\frac{(w^{(\eta)}_i)^{\mu_j}}{(w^{(\eta)}_j)^{\mu_i}}
\end{align*} converges to an exponential decay function, where $v^{(\eta)}_i$ is the $i$-th component (coordinate) of $w^{(\eta)}$.

\begin{lemma}\label{lem:ode}
	Suppose that Assumption~\ref{assmp} holds and the initial solution is away from any saddle point, i.e., given pre-specified constants, $\tau>0$ and $\delta<\frac{1}{2}$, there exist $i,j$ such that
\begin{align*}
i\neq j, \quad |w^{(\eta)}_j|> \tau, \quad \textrm{and}\quad |w^{(\eta)}_i|>\eta^{\frac{1}{2}+\delta}.
\end{align*}
 As $\eta \rightarrow 0$, $v^{(\eta)}_{k,j}$ weakly converges to the solution of the following ODE:
\begin{align}\label{equ:ode}
	d x_{k,j} = x_{k,j} \cdot \left( \mu_j\mu_k ( \beta_k-\beta_j)\right)d t~~\forall k\neq j.
\end{align}
\end{lemma}
The proof of Lemma~\ref{lem:ode} is provided in Appendix~\ref{pf:lem:ode}. Lemma~\ref{lem:ode} essentially implies the global convergence of SGHA. Specifically, the solution of \eqref{equ:ode} is
\begin{align*}
x_{k,j}(t)=x_{k,j}(0)\cdot\exp\left( \mu_j\mu_k \left(\beta_k-\beta_j\right)t \right)~~\forall k\neq j,
\end{align*}
where $x_{k,j}(0)$ is the initial value of $v^{(\eta)}_{k,j}$. In particular, we consider $j=1$. Then, as $t\rightarrow \infty$, the dominating component of $w$ will be $w_1$.

The ODE approximation of the algorithm implies that after long enough time, i.e., $t$ is large enough, the solution of the algorithm can be arbitrarily close to a global optimum. Nevertheless, to obtain the asymptotic ``convergence rate'', we need to study the variance of the trajectory at time $t$. Thus, we resort to the following SDE-based approach for a more precise characterization.

\noindent{\bf SDE Characterization:}
We notice that such a variance with order $\cO(\eta)$ vanishes as $\eta \rightarrow 0$. To characterize this variance, we rescale the updates by a factor of $\eta^{-\frac{1}{2}}$, i.e., by defining a new process as $z^{(\eta)}=\eta^{-\frac{1}{2}}w^{(\eta)}$. After rescaling, the variance of $z^{(\eta)}$ is of order $\cO(1)$.
The following lemma characterizes how the algorithm escapes from the saddle, i.e., $w^{(\eta)}(0)\approx e_i$, where $i\neq 1$, in Phase I.
\begin{lemma}\label{lem:sadd}
Suppose Assumption~\ref{assmp} holds and the initial is close to a saddle point , i.e., $z^{(\eta)}_j(0) \approx \eta^{-\frac{1}{2}}$ and $z^{(\eta)}_i(0) \approx 0$ for $i\neq j$. Then for any $C>0,$ there exist $\tau>0$ and $\eta'>0$ such that
\begin{align}\label{sde:con}
\sup_{ \eta<\eta'}\PP(\sup_t |z^{(\eta)}_i(t)|\leq C)\leq 1-\tau.
\end{align}

\end{lemma}
Here we provide the proof sketch and leave the whole proof of Lemma~\ref{lem:sadd} in Appendix~\ref{pf:lem:sadd}.
\begin{proof}[Proof Sketch]
 We prove this argument by contradiction. Assume the conclusion does not hold, that is there exists a constant $C>0,$ such that for any  $\eta'>0$ we have $$\sup_{\eta\leq \eta'}\PP(\sup_t |z^{(\eta)}_i(t)|\leq C)=1.$$ That implies there exists a sequence $\{\eta_n\}_{n=1}^\infty$ converging to $0$ such that
\begin{align}\label{eq_contra}
\lim_{n\rightarrow\infty}\PP(\sup_t |z^{(\eta_n)}_i(t)|\leq C)= 1.
\end{align}
Then we show  $\{z^{(\eta_n)}_i(\cdot)\}_n$ is tight and thus converges weakly. Furthermore, $\{z^{(\eta_n)}_i(\cdot)\}_n$ weakly converges to a stochastic differential equation,
	\begin{align}\label{equ:sadd}
	d z_j(t) =\left( -\beta_j\mu_i \cdot z_i +\lambda_i z_i \right)dt+\sqrt{G_{j,i}}d B(t)~~\textrm{for $j\in[d]\backslash\{i\}$,}
	\end{align}
	where ${G_{j,i}}=\EE\Big(\big(\hat{\Lambda}_B^{(k)}\big)_{j,i}\cdot \sqrt{\mu_j/ \mu_i}\cdot \tilde{\Lambda}_{i,i}-\mu_j\tilde{\Lambda}_{j,i}\Big)^2$ and $B(t)$ is a standard Brownian motion.
We compute the solution of this stochastic differential equation and then show \eqref{sde:con} holds.
\end{proof}

 Note that \eqref{equ:sadd} is a Fokker-Plank equation, whose solution is an Ornstein-Uhlenbeck (O-U) process \citep{doob1942brownian} as follows:
\begin{align}\label{O-U process-1}
&z_j(t)=\Big[\underbrace{z_j(0)+\sqrt{G_{j,i}}\int_0^t \exp\left[\mu_j \left(\beta_i -\beta_j \right)s\right] dB(s)}_{Q_1}\Big]\cdot \exp\left[ -\mu_j \left(\beta_i- \beta_j \right)t \right].
\end{align}
We consider $j=1$. Note that $Q_1$  is essentially a random variable with mean $z_{j}(0)$ and variance smaller than $\frac{G_{1,i}\mu_1}{2(\beta_1-\beta_i)}$. However, the larger $t$ is, the closer its variance gets to this upper bound. Moreover, the term $\exp\big[\mu_1(\beta_1-\beta_i)t\big]$ essentially amplifies $Q_1$ by a factor exponentially increasing in $t$. This tremendous amplification forces $z_{1}(t)$ to quickly get away from $0$, as $t$ increases, which indicates that the algorithm will escape from the saddle. Further, the following lemma characterizes the local behavior of the algorithm near the optimal.

\begin{lemma}\label{lem:sde}
	Suppose that Assumption~\ref{assmp} holds and the initial solution is close to an optimal solution, that is, given pre-specified constants $\kappa$ and $\delta<\frac{1}{2}$, we have $\frac{|w^{(\eta)}_1|^2}{\norm{w^{(\eta)}}_2^2}>1-\kappa \eta^{1+2\delta}$. As  $\eta \rightarrow 0$, then we have $\norm{w^{(\eta)}(t)}_2\xrightarrow{t\rightarrow \infty} 1$ and $z^{(\eta)}_i$ weakly converges to the solution of the following SDE:
	\begin{align}\label{equ:sde}
	d z_i(t) =\left( -\beta_1\cdot \mu_i z_i +\lambda_i z_i \right)dt+\sqrt{G_{i,1}}d B(t)~~\textrm{for $i\neq 1$,}
	\end{align}
	where $G_{i,1}=\EE\big((\hat{\Lambda}_B )_{i,1}\cdot \sqrt{\mu_i/\mu_1}\cdot \tilde{\Lambda}_{1,1}-\mu_i\Lambda_{i,1}\big)^2$, and $B(t)$ is a standard Brownian motion.
\end{lemma}
The proof of Lemma~\ref{lem:sde} is provided in Appendix~\ref{pf:lem:sde}. The solution of \eqref{equ:sde} is as follows:
\begin{align}\label{O-U process-2}
&z_i(t)=\sqrt{G_{i,1}}\int_0^t \exp\left[\mu_i\left(\beta_1  -\beta_i \right)\left(s-t\right)\right] dB(s)+z_i(0) \cdot \exp\left[  -\mu_i\left(\beta_1  -\beta_i \right)t \right].
\end{align}
Note the second term of the right hand side in \eqref{O-U process-2} decays to 0, as time $t\rightarrow \infty$. The rest is a pure random walk. Thus, the fluctuation of $z_i(t)$ is essentially the error fluctuation of the algorithm after sufficiently long time.

Combining Lemma~\ref{lem:ode},~\ref{lem:sadd}, and~\ref{lem:sde},
we obtain the following theorem.

\begin{theorem}\label{thm:num-iter-step-size}
Suppose Assumption~\ref{assmp} holds. Given a sufficiently small error $\epsilon>0$,~$\phi=\sum_{i=1}^dG_{i,1}$, and
\begin{align*}
\eta \asymp \frac{\epsilon \cdot \mu_{\min}\cdot{\sf gap}}{\phi},
\end{align*}
we need
\begin{align}\label{num}
T\asymp\frac{\mu_{\max}/\mu_{\min}}{\mu_1\cdot\sf{gap}}\log\left(\eta^{-1}\right)
\end{align}
such that with probability at least $\frac{5}{8}$, $\norm{w(T)-W^*}_2^2\leq \epsilon$, where $W^*$ is the optima of \eqref{eqn:original}.
\end{theorem}
The proof of Theorem~\ref{thm:num-iter-step-size} is provided in Appendix~\ref{pf:thm:num-iter-step-size}. Theorem~\ref{thm:num-iter-step-size} implies that asymptotically, our algorithm yields an iterations of complexity:
\begin{align*}
N\asymp \frac{T}{\eta}\asymp\frac{\phi\cdot \mu_{\max}/\mu_{\min}}{\epsilon\cdot\mu_1\cdot\mu_{\min}\cdot\sf{gap}^2}\log\left(\frac{\phi}{\epsilon\cdot\mu_{\min}\cdot \sf{gap}}\right),
\end{align*}
which not only depends on the gap, i.e., $\beta_1-\beta_2$, but also depends on $\frac{\mu_{\max}}{\mu_{\min}}$, which is the condition number of $B$ in the worst case. As can be seen, for an ill-conditioned $B$, the problem~\eqref{eqn:original} is more difficult to solve.

config: arxiv


TITLE: Time to find first copy of a duplicate
QUESTION [5 upvotes]: Consider a random process which samples uniformly with replacement from [n]. The expected time to find a duplicate is a constant factor times $\sqrt{n}$. This is a version of the famous Birthday Problem. How can one find the expected time to find the first copy of the first duplicate? This will obviously occur some time before. Also, what is the distribution of this time?
If you fix the position of the later copy of the duplicate then the earlier copy seems to occur uniformly before it but I am not sure how helpful that is to answer the questions.
By time I simply mean that each sample takes one unit of time so the time is just the number of samples at that point. This is not a question about algorithms or computation.

REPLY [1 votes]: Call $2\leqslant D_n\leqslant n+1$ the time of the first duplicate and $1\leqslant C_n\leqslant D_n-1$ the time of the first copy of the first duplicate.
As you noted, for each $2\leqslant k\leqslant n+1$, conditionally on the event $[D_n=k]$, $C_n$ is uniformly distributed on $\{1,2,\ldots,k-1\}$ hence $\mathbb E(C_n\mid D_n=k)=\frac12k$. Thus, $\mathbb E(C_n)=\frac12\mathbb E(D_n)$ and each asymptotics on $\mathbb E(D_n)$ when $n\to\infty$ translates into an asymptotics on $\mathbb E(C_n)$.
Likewise, for every $1\leqslant i\leqslant n$, decomposing the event $[C_n=i]$ into its intersections with the events $[D_n=k]$ for $i+1\leqslant k\leqslant n+1$, one gets
$$
\mathbb P(C_n=i)=\sum_{k=i+1}^{n+1}\frac{\mathbb P(D_n=k)}{k-1}.
$$
Recall finally that,  for every $2\leqslant k\leqslant n+1$,
$$
\mathbb P(D_n\geqslant k)=\prod_{\ell=1}^{k-2}\frac{n-\ell}n,
$$
hence, for every $1\leqslant i\leqslant n$,
$$
\mathbb P(C_n=i)=\frac1n\sum_{k=i}^{n}\prod_{\ell=1}^{k-1}\frac{n-\ell}n=\frac{n!}{n^{n+1}}\sum_{k=0}^{n-i}\frac{n^k}{k!}.
$$
Edit: Let $N_n$ denote a Poisson random variable with parameter $n$, then
$$
\mathbb P(C_n=i)=\frac{n!\mathrm e^n}{n^{n+1}}\mathbb P(N_n\leqslant n-i).
$$
Asymptotics follow from this identity since the prefactor $n!\mathrm e^n/n^{n+1}$ is equivalent to $\sqrt{2\pi/n}$ when $n\to\infty$, and $(N_n-n)/\sqrt{n}$ converges in distribution to a standard normal random variable. Thus, if $i_n/\sqrt{n}\to x$,
$$
\mathbb P(C_n=i_n)\sim\sqrt{\frac{2\pi}n}\Phi(-x)=\frac1{\sqrt{n}}\int_x^{+\infty}\mathrm e^{-s^2/2}\mathrm ds.
$$
Summing these yields
$$
\mathbb P(C_n\geqslant i_n)\sim\int_x^{+\infty}(s-x)\mathrm e^{-s^2/2}\mathrm ds=\int_0^{+\infty}s\mathrm e^{-(s+x)^2/2}\mathrm ds.
$$
In other words, $C_n/\sqrt{n}$ converges in distribution to a random variable $C$ whose probability density function $f_C$ is defined, for every $x\geqslant0$, by
$$
f_C(x)=\int_x^{+\infty}\mathrm e^{-s^2/2}\mathrm ds.
$$


TITLE: Properties of Weak Convergence of Probability Measures on Product Spaces
QUESTION [5 upvotes]: EDIT:
For the Bounty, I made a substantial edit revision concerning the structure of the question, to make it more readable (hopefully). Moreover I added a question on problem 2.7 of  Billingsley’s book.

I have two problems concerning weak convergence of probability measures in product spaces, that arose from Billingsley’s classic  “Convergence of Probability Measures” (Chapter I, Section 2, Subsection “Product Spaces”).
Below there are the part of the book that made me wonder, the numbered questions I have, plus my thoughts (hidden, in order to lighten the overall immediate reading of the question).
Notation: $P$ is a probability measure on $T = S' \times S''$, $P_n \Rightarrow P$ denotes weak convergence, while a $P$-continuity set is the family of those sets $A \in \mathcal{S}$ such that $P(\partial A)= 0$, where $\mathcal{S}$ denotes the Borel $\sigma$-algebra of $S$, and $\partial A$ denotes the boundary of $A$. Concerning product spaces, $\mathcal{T} :=  \mathcal{S}' \times \mathcal{S}''$ is the $\sigma$-algebra of $T$, while $P’$ is the marginal distribution on $\mathcal{S}’$ of $P$ on $\mathcal{T}$, defined as $P’ (A) := P(A \times S’’)$ (and the same applies to $P’’$).

I PART
The first problem is with the following Billingsley’s statement in bold.
[Theorem 2.8.ii. should be a sort of a partial converse of the – trivial – following proposition, here named in the following way:
Proposition 1: If $P_n \Rightarrow P$, then $P^{'}_n \Rightarrow P'$, and $P^{''}_n \Rightarrow P’’$.]

Therefore, we have the following theorem, in which (ii) is an obvious consequence of (i).
Theorem 2.8.
(i) If $T = S' \times S''$ is separable, then $P_n \Rightarrow P$ if and only if $P_ n (A’ \times A’’) \to P(A' \times  A'')$ for each $P’$-continuity set $A’$ and each $P’’$-continuity set $A''$.
(ii) If $T$ is separable, then $P^{'}_n \times P^{''}_n \Rightarrow P’ \times P’’$ if and only if $P^{'}_n \Rightarrow P'$ and $P^{''}_n \Rightarrow P’’$.

II PART
The Second problem concerns problem 2.7 in the book, that reads:

Problem 2.7: The uniform distribution on the unit square and the uniform distribution on its diagonal have identical marginal distributions. Relate this to Theorem 2.8.

Questions:

How do we prove (ii)?
1.a. How do we prove the ($\Leftarrow$) direction of (ii)?
1.b. How do we actually use (i) to prove (ii), as Billingsley suggests?
1.c. Is my way of addressing the problem below sound?

How do we actually relate problem 2.7 to theorem 2.8?
2.a. Do we actually have to use the setting in the problem to come up with some measure that works as a counterexample of Proposition 1, or
2.b. It is enought to notice that the weak limit is now not unique, and hence the converse of proposition 1 does not hold anymore?

Here my thoughts on question 1:

 Attempted proof of (ii):
(only if) Assume that $P^{'}_n \times P^{''}_n \Rightarrow P' \times P’’$. Thus, by taking the marginals $P'$, and $P''$ on  $P^{'}_n \times P^{''}_n \Rightarrow P' \times P''$, we obtain that $P{'}_n \Rightarrow P’$, and $P{''}_n \Rightarrow P''$.
(if) Assume that $P^{'}_n \Rightarrow P'$, and $P^{''}_n \Rightarrow P''$. Let $A' \in \mathcal{S}'$, $A'' \in \mathcal{S}'$ be arbitrary, such that $A'$ is a $P'$-continuity set, and $A''$ is a $P''$-continuity set. [… and here it ends. I thought that we could use the Portmanteau theorem to get somewhere from the fact that $P^{'}_n \Rightarrow P'$, and $P^{''}_n \Rightarrow P''$, but I really don't know.]

As always, thank you for your time.

REPLY [3 votes]: The direction that $P_n'\times P_n'' \Rightarrow P'\times P''$ implies the weak convergence $P_n' \Rightarrow P'$ and $P_n'' \Rightarrow P''$ is a special case of Proposition 1, since the marginals of a product measure are the respective factors. We could give a simpler proof for this special case, but I doubt that that would be very enlightening.
To show the other direction, we assume $P_n' \Rightarrow P'$ and $P_n'' \Rightarrow P''$. We use part $(i)$, which tells us that for all $P'$-continuity sets $A'$ and $P''$-continuity sets $A''$ we need to check
$$(P_n'\times P_n'')(A'\times A'') \to (P'\times P'')(A'\times A'').\tag{1}$$
But by our assumption and the Portmanteau theorem, we have $P_n'(A') \to P'(A')$ and $P_n''(A'') \to P''(A'')$, and by limit algebra it follows that
$$(P_n'\times P_n'')(A'\times A'') = P_n'(A')\cdot P_n''(A'') \to P'(A')\cdot P''(A'') = (P'\times P'')(A'\times A''),\tag{1'}$$
so indeed $(i)$ tells us that under our assumption $P_n'\times P_n'' \Rightarrow P'\times P''$.
Without using part $(i)$, we would have to show that $(P_n'\times P_n'')(A) \to (P'\times P'')(A)$ for all $(P'\times P'')$-continuity sets $A$, and there are generally a lot of $(P'\times P'')$-continuity sets that aren't products. Thus $(i)$ reduces the required work, and leaves only the case of product sets to be considered.
I think that answers 1.a. and 1.b. Concerning 1.c., in the "only if" part you should mention that you use Proposition 1, it's better to be explicit. In the "if" part, you have the right idea to use the Portmanteau theorem, but you didn't recognise how to use it.
Problem 2.7. is rather hard, since it's not clear what Billingsley expected there. I think the thing to take away is that a probability measure on a product space is in general not determined by its marginal measures. (But if all but possibly one of the marginal measures of $P$ are point masses, then $P$ is the product of its marginals.) That's in fact not hard to see once you think about it, but it's a tempting mistake.
Let's try to relate it, though. By theorem 2.8., if $P_n$ is a sequence of probability measures on the unit square converging weakly to the uniform distribution $U_{\Delta}$ on the diagonal of the unit square, then the product of the marginals, $P_n' \times P_n''$, converges weakly to the uniform distribution $U_{\square}$ on the unit square. In particular, from $P_n' \Rightarrow P'$ and $P_n'' \Rightarrow P''$ we can not conclude that $P_n \Rightarrow P$. The theorem only gives that conclusion if we additionally know that $P_n$ and $P$ are product measures, i.e. $P_n = P_n' \times P_n''$ and $P = P' \times P''$.
Ad 2.a.: We don't get counterexamples to proposition 1, since that proposition is true. What we get are counterexamples to the naïve converse of proposition 1, which would be "If $P_n' \Rightarrow P'$ and $P_n'' \Rightarrow P''$ then $P_n \Rightarrow P$". We can find counterexamples to that not only in the exact setting of problem 2.7 of course, all we need is a measure $P$ that is not a product measure, or a sequence of not-product measures whose marginals converge weakly. That can be constructed as soon as both factor spaces have more than one point.
Ad 2.b.: The weak limit - if it exists - is still unique. The point is that unlike for sequences in $\mathbb{R}^n$, the (weak) convergence of all marginals (analogous to the coordinate projections in $\mathbb{R}^n$) is no longer sufficient to deduce the (weak) convergence of the original sequence - consider $P_{2n} = U_{\Delta}$ and $P_{2n+1} = U_{\square}$ - nor, if the sequence is weakly convergent, to determine the weak limit.


TITLE: How to obtain the following definite integral?
QUESTION [5 upvotes]: I have no idea how to obtain the answer to the following problem:
$$I=\int_{0}^{1}\frac{dx}{\sqrt{8-x^2-x^3}}$$
The answer has been given as
$$\sin^{-1} \frac{1}{2\sqrt{2}}< I < \frac{1}{\sqrt{2}}\sin^{-1} \frac{1}{2}$$
Any help will be appreciated. Thanks in advance.

REPLY [6 votes]: Hint: Consider
$$\frac{1}{\sqrt{8-x^2}}\leq\frac{1}{\sqrt{8-x^2-x^3}}\leq \frac{1}{\sqrt{8-2x^2}} = \frac{1}{\sqrt{2}} \frac{1}{\sqrt{4-x^2}}$$

REPLY [4 votes]: $I$ is an elliptic integral, accurate approximations can be deduced from convexity. Over $(0,1)$ we clearly have $8-x^2-x^3 > 8-2x^2$, hence
$$ I < \int_{0}^{1}\frac{dx}{\sqrt{8-2x^2}} = \frac{\pi}{6\sqrt{2}} \tag{Ub}$$
but we also have $\frac{1}{\sqrt{8-x^2-x^3}}>\frac{1}{2\sqrt{2}}\left(1+\frac{x^2+x^3}{16}\right)$, hence
$$ I > \int_{0}^{1}\frac{1}{2\sqrt{2}}\left(1+\frac{x^2+x^3}{16}\right)\,dx = \frac{199}{384\sqrt{2}}\tag{Lb}$$
and by combining the upper bound and the lower bound
$$ 0.3664 < I < 0.3703. \tag{B} $$
$(\text{Lb})$ can be improved through Jensen's inequality:
$$ I > \frac{1}{2\sqrt{2}\sqrt{1-\int_{0}^{1}\frac{x^2+x^3}{8}\,dx}}=\sqrt{\frac{12}{89}}>0.36719 $$
and $(\text{Ub})$ can be improved through the Cauchy-Schwarz inequality:
$$ I < \sqrt{\int_{0}^{1}\frac{dx}{8-x^2-x^3}}<0.36841 $$
such that $I=\color{green}{0.36}77\pm 0.0008$.