text:
\begin{document}
\maketitle

\begin{abstract}
In this paper we establish a uniform bound for the distribution of a sum
$S^n=X_1+\cdots+X_n$ of independent non-homogeneous Bernoulli random variables
 with $\PP(X_i\!=\!1)\!=\!p_i$. Specifically, we prove that
$\sigma^n\,\PP(S^n\!=\!i)\!\leq\! M$ where
$\sigma^n$ denotes the standard deviation of $S^n$ and the constant $M\!\sim\! 0.4688$
is the maximum of
$u\mapsto\sqrt{2u}\,e^{-2u}\sum_{k=0}^\infty({u^k\over k!})^2$.
\end{abstract}

\section{Introduction}
The main goal of this paper is to establish the following:
\begin{theorem}\label{T}
Let $S^n\!=\!X_1+\cdots+X_n$ be a sum of independent non-homogeneous Bernoulli
random variables with $\PP(X_i\!=\!1)=p_i$, and let $\sigma^n\!=\!\sqrt{\sum_{i=1}^np_i(1\!-\!p_i)}$
denote its standard deviation. Then, for all $i\in\ZZ$ we have
\begin{equation}\label{bound}
\sigma^n\;\PP(S^n\!\!=\!i)\leq M
\end{equation}
with $M=\max_{u\geq 0}\sqrt{2u}\,e^{-2u}\sum_{k=0}^\infty({u^k\over k!})^2$.
This bound is sharp and the constant is approximately $M\sim 0.46882235549939533$.
\end{theorem}

The novelty lies in the uniform character of the bound (\ref{bound})
and the fact that the constant $M$ is the best possible. This result
complements the vast literature on bounds for large deviations
probabilities ---such as Markov, Chebyshev, Hoeffding, and Chernoff bounds---
which focus on finding sharp estimates for
$\PP(|S\!\!-\EE(S)|\geq t)$ when $S$ is a sum of $n$ i.i.d. random variables and $t>0$.
Such large deviations bounds \cite{ahw,alo,azu,ber,che,goh,hoe,jog,mcd,sie} are
very useful in probability and statistics, providing formulas of the type
$$\PP(|S\!\!-\EE(S)|\geq t)\leq f(nt^2)$$
with $f(0)\geq 1$ and $\lim_{x\rightarrow\infty}f(x)=0$ usually with an
exponential decay. In our particular context, this implies
that $\PP(S^n\!\!=\!i)$ tends to 0 whenever $i$ stays away from the
mean $\EE(S^n)$, a stronger conclusion which does not follow from (\ref{bound}). Thus,
the main addition of Theorem \ref{T} is that it can deal with all values of $i$,
including those which are close to the mean.

This uniform bound has already proved useful for addressing two very
different and unrelated questions: (a) to study the rate of convergence of Mann's iterates
for non-expansive linear operators (see \cite{vai2}); and (b) to give an approximation
guarantee for an algorithm in combinatorial optimization (see \cite{ccs}). We hope that the
bound may be useful in other settings as well.

In the rest of the paper we present the proof of Theorem 1. In  \S 2
this proof is split into a series of basic steps, each one using
only elementary tools that fit together in a surprisingly sharp way
to yield the announced result. In the short final section \S 3
we discuss a simple extension of the main result to the case of sums and differences
of Bernoullis, as well as limits of such variables which includes the difference of
Poisson distributions.

\section{Proof of Theorem \ref{T}}

We must show that for each $\vec{p}=(p_1,\ldots,p_n)\in [0,1]^n$ we have $R^n_i(\vec{p})\leq M$,
where $R^n_i(\vec{p})=\sigma^nP^n_i$ with $\sigma^n\!=\!\sqrt{\sum_{i=1}^np_i(1\!-\!p_i)}$ and
$$P^n_i=\PP(S^n\!=\!i)=\sum_{\stackrel{A\subset\{1,\ldots,n\}}{|A|=i}}\mbox{$\prod_{j\in A}p_j\cdot\prod_{j\not\in A}(1-p_j).$}$$
Usually $P^n_i$ is defined only for $i=0,\ldots,n$. However, $P^n_i=\PP(S^n\!=\!i)=0$
is also meaningful outside this range and allows to write the recursive formula
$$P^n_i=p_nP^{n-1}_{i-1}+(1-p_n)P^{n-1}_i.$$

\subsection{Reduction to a sum of 2 Binomial distributions}
The expressions $P^n_i$, $\sigma^n$ and $R^n_i$ are continuous symmetric
functions of $\vec{p}$. We claim that $R^n_i(\vec{p})$ is maximal when the $p_j$'s
take at most two values in $(0,1)$. In a different context, this result was
established in \cite[Vaisman]{vai} but it has not been published elsewhere.
\begin{proposition} For all $\vec{p}\in [0,1]^n$ we have
\begin{equation}\label{uno}
R^n_i(\vec{p})\leq\sup_{\vec{q}\in [0,1]^n}\{R^n_i(\vec{q}):|\{q_j:0<q_j<1\}|\leq 2\}.
\end{equation}
\end{proposition}

\proof Let $Q$ be the set of vectors $\vec{p}\in [0,1]^n$ attaining the maximum
of $R^n_i(\vec{p})$. Since $Q$ is compact we may find $\vec{q}\in Q$
minimal in the lexicographic order. We claim that $|\{q_j:0<q_j<1\}|\leq 2$
from which the result follows.

Assume by contradiction that $\vec{q}$ has 3 different entries $0\!<\!q_r\!<\!q_s\!<\!q_t\!<\!1$.

Denoting $\vec{q}_0=(q_j)_{j\neq r,s,t}$ and $\bar q_j=1-q_j$ we have
\begin{eqnarray*}
P^n_i(\vec{q})&=&q_rq_sq_tP^{n-3}_{i-3}(\vec{q}_0)+[\bar q_rq_sq_t+q_r\bar q_sq_t+q_rq_s\bar q_t]P^{n-3}_{i-2}(\vec{q}_0)\\
&&\hspace{-0.5cm}\mbox{}+[\bar q_r\bar q_sq_t+\bar q_rq_s\bar q_t+q_r\bar q_s\bar q_t]P^{n-3}_{i-1}(\vec{q}_0)+\bar q_r\bar q_s\bar q_tP^{n-3}_i(\vec{q}_0)
\end{eqnarray*}
which may be rewritten as $P^n_i(\vec{q})=F(q_r,q_s,q_t)$ where
$$F(x,y,z)=Axyz+B(xy\!+\!xz\!+\!yz)+C(x\!+\!y\!+\!z)+D$$
for appropriate constants $A,B,C,D$.
Similarly $\sigma^n(\vec{q})=\sqrt{V(q_r,q_s,q_t)}$ with
$$V(x,y,z)=x(1\!-\!x)+y(1\!-\!y)+z(1\!-\!z)+\sigma^{n-3}(\vec{q}_0)^2.~~$$
Since the maximum of $R^n_i(\cdot)=\sigma^n(\cdot)P^n_i(\cdot)$ is attained at
$\vec{q}$, it follows that $\sqrt{V(\cdot)}F(\cdot)$ is maximal at $(q_r,q_s,q_t)\in\mbox{int}([0,1]^3)$,
and therefore its gradient vanishes at this point, namely
$$\sqrt{V(q_r,q_s,q_t)}\nabla F(q_r,q_s,q_t)+\mbox{${F(q_r,q_s,q_t)\over 2\sqrt{V(q_r,q_s,q_t)}}$}\nabla V(q_r,q_s,q_t)=0,$$
so that setting $\lambda=-{F(q_r,q_s,q_t)\over 2V(q_r,q_s,q_t)}$ this gives explicitly
\begin{eqnarray*}
Aq_sq_t+B(q_s+q_t)+C&=&\lambda(1-2q_r)\\
Aq_rq_t+B(q_r+q_t)+C&=&\lambda(1-2q_s)\\
Aq_rq_s+B(q_r+q_s)+C&=&\lambda(1-2q_t).
\end{eqnarray*}
Substracting the first two equations and simplifying by $(q_s-q_r)\neq 0$
we get $Aq_t+B=2\lambda$. Similarly, the second and third
equations combined yield $Aq_r+B=2\lambda$, so that $Aq_t=Aq_r$ and since $q_r\neq q_t$
we conclude $A=0$.

Now, $A=0$ implies that the function $F(\cdot)$ depends only on the values of $x\!+\!y\!+\!z$
and $xy\!+\!xz\!+\!yz$, while the same holds for $V(\cdot)$ since
$$x(1\!-\!x)+y(1\!-\!y)+z(1\!-\!z)=(x\!+\!y\!+\!z)-(x\!+\!y\!+\!z)^2+2(xy\!+\!xz\!+\!yz).$$
Thus, $\sqrt{V(\cdot)}F(\cdot)$ is constant over the set defined by
$x\!+\!y\!+\!z=q_r\!+\!q_s\!+\!q_t$ and $xy\!+\!xz\!+\!yz=q_rq_s\!+\!q_rq_t\!+\!q_sq_t$,
and therefore any such vector $(x,y,z,\vec{q}_0)$ maximizes $R^n_i(\cdot)$.
Since $\vec{q}\in Q$ is lexicographically minimal, it follows that
$q_r\leq x$ and therefore the triple $(q_r,q_s,q_t)$ also solves
$$\left\{\begin{array}{l}
\min~~x\\
s.t.~~(x,y,z) \in [0,1]^3\\
\begin{array}{lcl}
       x+y+z&=&q_r+q_s+q_t\\
       xy+xz+yz&=&q_rq_s+q_rq_t+q_sq_t
      \end{array}
\end{array}\right.
$$
Since $q_r,q_s,q_t$ are different, the gradients of the two equality constraints at
this optimal point are linearly independent, while the inequality constraints are non-binding.
Hence the Mangasarian-Fromovitz constraint qualification holds and we may
find Lagrange multipliers $\alpha$ and $\beta$ to write down the following necessary
optimality conditions
\begin{eqnarray*}
1&=& \alpha+\beta(q_s+q_t)\\
0&=& \alpha+\beta(q_r+q_t)\\
0&=& \alpha+\beta(q_s+q_t).
\end{eqnarray*}
Since $q_r\neq q_s$ the two last equations imply $\alpha=\beta=0$, which is
incompatible with the first equation. This contradiction shows that the constant $A$
cannot be 0, and therefore the assumption $0<q_r<q_s<q_t<1$ was absurd.
\endproof

Removing all $q_j\in\{0,1\}$ which correspond to deterministic variables $Y_j$,
the Lemma shows that it suffices to prove (\ref{bound}) for $p_j$'s taking
at most two values, that is to say, for $S^n=U+V$ with
$U\sim B(a,\lambda)$ and $V\sim B(b,\mu)$ independent Binomials. More specifically,
denoting
$B^n_k(p)={n\choose k}p^k(1\!-\!p)^{n-k}$ the Binomial probabilities and defining the constant
\begin{equation}\label{optimal}
M=\sup_{\stackrel{\mbox{\scriptsize $ a,b,i\in\NN$}}{\lambda,\mu\in [0,1]}}\sqrt{a\lambda(1\!-\!\lambda)+b\mu(1\!-\!\mu)}\;\sum_{k=0}^iB^a_k(\lambda)B^b_{i-k}(\mu)
\end{equation}
we have the following sharp estimate
\begin{corollary}\label{coro} For all $n\in\NN$, $\vec{p}\in[0,1]^n$ and $i\in\ZZ$ we have $R^n_i(\vec{p})\leq M$.
\end{corollary}

\subsection{An upper bound for the constant $M$}
Before computing the optimal constant $M$, we establish a simpler upper bound. As a consequence of this
analysis it turns out that considering two Binomial distributions in the supremum (\ref{optimal}) is essential.
\begin{lemma} \label{cuatro}
$M\leq{1\over\sqrt e}$.
\end{lemma}
\proof Let $a,b,i\in\NN$ and $\lambda,\mu\in [0,1]$, and assume
without loss of generality that $b\mu(1\!-\!\mu)\leq a\lambda(1\!-\!\lambda)$.
Since the probabilities $B^b_{i-k}(\mu)$ are non-negative and add up at most 1,
the sum in (\ref{optimal}) may be bounded from above by the maximal $B^a_k(\lambda)$, so that
$M\leq{1\over\sqrt e}$ will follow if we prove the inequality
$$\sqrt{2a\lambda(1\!-\!\lambda)}\;B^a_k(\lambda)\leq \mbox{${1\over\sqrt e}$.}$$
For $a$ and $k$ given, the maximum in $\lambda\in [0,1]$ is attained at
$\lambda={k+{1\over 2}\over a+1}$, so that replacing this value all we must show is that
$${a\choose k}{\sqrt{2a}(k+\mbox{${1\over 2}$})^{k+{1\over 2}}(a-k+\mbox{${1\over 2}$})^{a-k+{1\over 2}}\over (a+1)^{a+1}}\leq
\mbox{${1\over\sqrt e}$}.$$
Let $C^a_k$ denote this expression. We claim that its maximum over $k$ is attained
at the extreme values $k=0$ and $k=a$.
Indeed, the quotient between $C^a_{k+1}$ and $C^a_k$ (for $0\!\leq\!k\!\leq\!a\!-\!1$)
may be expressed as
$$\mbox{${C^a_{k+1}\over C^a_k}={H(a-k)\over H(k+1)}$}$$
where $H(x)=x(x-\mbox{${1\over 2}$})^{x-\mbox{${1\over 2}$}}/(x+\mbox{${1\over 2}$})^{x+\mbox{${1\over 2}$}}$.
A simple calculus exercise shows that $H(\cdot)$ is decreasing
so that $H(a-k)\geq H(k+1)$ iff $a-k\leq k+1$.
This implies that $C^a_k$ decreases for $k\leq {a-1\over 2}$ and increases
afterwards, so that its maximum is attained at $k=0$ or $k=a$.
The conclusion follows since
$$C^a_0=C^a_a=
\mbox{$
{\sqrt{a}(a+{1\over 2})^{a+{1\over 2}} \over (a+1)^{a+1}}
=\sqrt{a\over a+{1\over 2}}\left(1-{1\over 2(a+1)}\right)^{a+1}\leq \exp(-{1\over 2})={1\over\sqrt{e}}.
$}$$

\vspace{-4ex}
\endproof

\vspace{2ex}
\noindent{\sc Remark.} The proof above shows that for a single binomial distribution
we have $\sqrt{a\lambda(1\!-\!\lambda)}B^a_k(\lambda)\leq{1\over \sqrt{2e}}\sim 0.428$.
Since we will prove that $M\sim 0.4688$, it follows that allowing $\lambda\neq\mu$ in
(\ref{optimal}) is essential.

\subsection{Exact value of the constant $M$}

Let $\psi^n(p)=\sum_{k=0}^nB^n_k(p)^2$. Considering the expression in the maximum
(\ref{optimal}) and using the Cauchy-Schwartz inequality we get
$$M\leq \sup_{\stackrel{\mbox{\scriptsize $ a,b\in\NN$}}{\lambda,\mu\in [0,1]}}
\sqrt{a\lambda(1\!-\!\lambda)+b\mu(1\!-\!\mu)}\;\sqrt{\psi^a(\lambda)\,\psi^b(\mu)}.$$
We may restate this supremum using the change of
variables $x=a\lambda(1\!-\!\lambda)$ and $y=b\mu(1\!-\!\mu)$, so that
\begin{eqnarray*}
\lambda&=&\mbox{${1\over 2}$}(1\pm\sqrt{1\!-\!4x/a}),\\
\mu&=&\mbox{${1\over 2}$}(1\pm\sqrt{1\!-\!4y/b}).
\end{eqnarray*}
Then, defining
$\varphi^n(u)=\psi^n(p^n(u))$ with\footnote{The same value $\varphi^n(u)$ is obtained if we
take the other root ${1\over 2}(1\!+\!\sqrt{1\!-\!4u/n})$.} $p^n(u)={1\over 2}(1\!-\!\sqrt{1\!-\!4u/n})$, we may
rewrite the previous bound as
\begin{equation}\label{super}
M\leq \sup_{\stackrel{\mbox{\scriptsize $a,b\in\NN$}}{\stackrel{\mbox{\scriptsize $0\!\leq\! x\!\leq\! a/4$}}{\mbox{\scriptsize $0\!\leq\! y\!\leq\! b/4$}}}}
\sqrt{x+y}\;\sqrt{\varphi^a(x)\,\varphi^b(y)}.
\end{equation}

The key property for our subsequent analysis is the following.
\begin{proposition}
$\varphi^n(u)$ increases with $n$ for $n\geq 4u$.
\end{proposition}
\proof We begin by observing that $\psi^n(p)=\PP(U\!=\!V)$ where
$U$ and $V$ are independent Binomials $B(n,p)$. Indeed, conditioning
on $V$ we get
\begin{eqnarray*}
\PP(U\!=\!V)&=&\mbox{$\sum_{k=0}^n\PP(U\!=\!V|V\!=\!k)\PP(V\!=\!k)$}\\
&=&\mbox{$\sum_{k=0}^n\PP(U\!=\!k)\PP(V\!=\!k)$}\\
&=&\mbox{$\sum_{k=0}^nB^n_k(p)^2$}.
\end{eqnarray*}

Let $\pi_k=\PP(U\!-\!V\!=\!k)$ and consider the $z$-transform of $U-V$, that is
$$\xi(z)=\EE(z^{U-V})=\mbox{$\sum_{k=-n}^n\pi_kz^k$}.$$
This map is holomorphic on $\CC\setminus\{0\}$
with a pole of degree $n$ at the origin and  constant coefficient $\pi_0=\psi^n(p)$.
Thus, integrating the function $\xi(z)/z$ along the unit circle $\mathcal{C}$
we get
\begin{equation}\label{residuos}
\psi^n(p)=\pi_0=\mbox{${1\over 2\pi i}\int_{\mathcal{C}}{\xi(z)\over z}\,dz=
{1\over 2\pi}\int_0^{2\pi}\!\xi(e^{i\theta})\,d\theta.$}
\end{equation}
The function $\xi(z)$ may be explicitly computed by expressing $U\!=\!\sum_{i=1}^nX_i$ and $V\!=\!\sum_{i=1}^nY_i$ as
sums of independent Bernoullis of parameter $p$, namely
\begin{eqnarray*}
\xi(z)&=&\mbox{$\EE[\prod_{i=1}^nz^{X_i}\cdot\prod_{i=1}^nz^{-Y_i}]$}\\
&=&[p+(1\!-\!p)z]^n\cdot[p+(1\!-\!p)z^{-1}]^n\\
&=&[p^2+(1\!-\!p)^2+p(1\!-\!p)(z+z^{-1})]^n
\end{eqnarray*}
from which it follows
$$\xi(e^{i\theta})=[p^2+(1\!-\!p)^2+2p(1\!-\!p)\cos\theta]^n.$$
Now, evaluating at $p=p^n(u)$, a simple calculation yields
$$\mbox{$\xi(e^{i\theta})=[1-{2u(1-\cos\theta)\over n}]^n$}$$
which plugged into (\ref{residuos}) gives the formula
\begin{equation}\label{for}
\varphi^n(u)=\psi^n(p^n(u))=
\mbox{${1\over 2\pi}\int_0^{2\pi}[1-{2u(1-\cos\theta)\over n}]^n\,d\theta.$}
\end{equation}
Since $n\geq 4u\geq 2u(1\!-\!\cos\theta)$, the expression under the integral sign
increases with respect to $n$, from which the conclusion follows.
\endproof

This result implies that the supremum in (\ref{super}) is attained for
$a,b\to\infty$, that it to say
\begin{equation}\label{super2}
M\leq \bar M=\sup_{x,y\geq 0}\sqrt{x+y}\;\sqrt{\varphi^\infty(x)\,\varphi^\infty(y)}
\end{equation}
where $\varphi^\infty(u)=\lim_{n\to\infty}\varphi^n(u)$. Letting $n\to\infty$ in
(\ref{for}) we get an explicit expression for this limit function
\begin{equation}\label{f1}
\mbox{$\varphi^\infty(u)={1\over 2\pi}\int_0^{2\pi}e^{-2u(1-\cos\theta)}\,d\theta.$}
\end{equation}
Alternatively, we may pass to the limit directly in the original expression
$$\mbox{$\varphi^n(u)=\sum_{k=0}^nB_k^n(p^n(u))^2$}$$
and since it is easily seen that $np^n(u)\to u$, the Binomial distribution
converges to a Poisson and we get the series representation
\begin{equation}\label{f2}
\mbox{$\varphi^\infty(u)=\sum_{k=0}^\infty({e^{-u}u^k\over k!})^2=e^{-2u}\sum_{k=0}^\infty({u^k\over k!})^2$}.
\end{equation}
Clearly, the latter could have also been obtained by a series expansion of (\ref{f1}).

\vspace{2ex}
We proceed next to show that the supremum in (\ref{super2}) is attained.
\begin{proposition} The supremum $\bar M$ is attained at a unique point
$(x^*,y^*)$ with $x^*=y^*=\bar u>0$, where $\bar u$ is the optimal solution of
$\bar M=\sup_{u\geq 0} M(u)$ with
 $$\mbox{$M(u)=\sqrt{2u}\,\varphi^\infty(u)=\sqrt{2u}\,e^{-2u}\sum_{k=0}^\infty({u^k\over k!})^2.$}$$
\end{proposition}
\proof Denoting $h(u)=\ln\varphi^\infty(u)$, it is clear that solving (\ref{super2}) is equivalent to
\begin{equation}\label{equi}
\sup_{x,y\geq 0}~\ln(x+y)+h(x)+h(y).
\end{equation}
We claim that $h(\cdot)$ is strictly concave, so that this problem has at most one
optimal solution. We will then prove that there is a point $\bar u\in(0,1)$
that maximizes $M(u)$ and therefore it satisfies ${1\over 2\bar u}+h'(\bar u)=0$,
from which it follows at once that the point $(x^*,y^*)$ with $x^*=y^*=\bar u$ is
a stationary point for (\ref{equi}) and is therefore the unique optimal solution.\\[1ex]
\underline{$h(\cdot)$ is strictly concave}.
For each $u\geq 0$ the function
$$\rho_u(\theta)=\mbox{${1\over 2\pi\psi^\infty(u)}\,e^{-2u(1-\cos\theta)}$}$$
defines a probability density on the interval $[0,2\pi]$. Moreover, using (\ref{f1}),
a direct computation  allows to express the second derivative $h''(u)$ as
$$h''(u)=-4\mbox{$[\int_0^{2\pi}(1\!-\!\cos\theta)^2\rho_u(\theta)\,d\theta-(\int_0^{2\pi}(1\!-\!\cos\theta)\rho_u(\theta)\,d\theta)^2]<0,$}$$
where the last inequality follows from Jensen's inequality applied to the strictly convex function $z\mapsto z^2$.
\\[2ex]
\underline{Existence of a unique maximizer $\bar u$ for $M(u)$}.
The strict concavity of $h(\cdot)$ implies that $M(\cdot)$ is strictly log-concave.
Since $M(0)=0$ and $M(u)>0$ for $u>0$, the existence of a unique maximizer $\bar u\in (0,1)$
will follow if we prove that $M'(1)<0$. Now, using the expression (\ref{f2}) we may readily
compute $M'(u)$ which evaluated at $u=1$ gives
$$M'(1)=\mbox{${e^{-2}\over\sqrt{2}}\left[4\sum_{k=0}^\infty{1\over k!(k+1)!}-3\sum_{k=0}^\infty{1\over (k!)^2}\right].$}$$
The first two terms of both sums cancel out, and then we conclude
$$M'(1)=\mbox{${e^{-2}\over\sqrt{2}}\sum_{k=2}^\infty{4\over (k!)^2}[{1\over k+1}-{3\over 4}]<0.$}$$

\vspace{-4ex}
\endproof

\vspace{2ex}
\noindent{\sc Remark.} Numerically we find that $\bar u\sim 0.39498892975658451$
which gives the approximate value for $\bar M\sim 0.46882235549939533$.

\vspace{2ex}
\noindent{\sc Remark.} We observe that $\sum_{k=0}^\infty({u^k\over k!})^2=B(0,2u)$
where $B(0,\cdot)$ is a modified Bessel function of the first kind, namely
the solution of $x^2y''+xy'-x^2y=0$. Thus, it seems unlikely to find simpler formulas
for $\bar M$ or $\bar u$ in terms of known constants and functions.

\vspace{2ex}
In order to complete the proof of Theorem 1, it remains to show that

\begin{proposition}
$M=\bar M$ and the bound {\em (\ref{bound})} is sharp.
\end{proposition}
\proof Both conclusions will follow simultaneously if we exhibit a family of
$S^n$'s and $i$'s for which $\sigma^n\,\PP(S^n\!=\!i)$
tends to $\bar M$. To this end let us consider for $S^n$ the particular case
of a sum of $n=2a$ Bernoullis, half of which have $p_i=\lambda$
while for the other half we take $p_i=\mu=1\!-\!\lambda$, with
$\lambda=\bar u/a$. Hence, $S^n=U+V$ with
$U\sim B(a,\lambda)$ and $V\sim B(a,1\!-\!\lambda)$ independent Binomials.
If we now take $i=a$, we get
\begin{eqnarray*}
\sigma^n\,\PP(S^n\!=\!a)&=&\mbox{$\sqrt{2a\lambda(1\!-\!\lambda)}\,\sum_{k=0}^a{a\choose k}{a\choose a-k}\lambda^{2k}(1-\lambda)^{2(a-k)}$}\\
&=&\mbox{$\sqrt{2\bar u(1\!-\!{\bar u\over a})}\,\sum_{k=0}^a{a\choose k}^2({\bar u\over a})^{2k}(1-{\bar u\over a})^{2(a-k)}$}
\end{eqnarray*}
which is easily seen to converge towards $M(\bar u)=\bar M$ when $a\to\infty$.
\endproof

\section{A simple extension and a final comment}
As a straightforward corollary of Theorem 1 we get that the bound (\ref{bound}) still holds
for any random variable $S^n\!=\!\sum_{i=1}^n\pm X_i$ that can be expressed as {\em sums and differences}
of non-homogeneous independent Bernoullis. Moreover, the bound will remain true for
limits of such variables, so that it holds in fact for all combinations of sums and differences
of Bernoulli, Binomial, and Poisson variables. We record the purely Poissonian case in the next

\begin{corollary} Let $S=X-Y$ with $X\sim\mathcal{P}(x)$ and
$Y\sim\mathcal{P}(y)$ two independent Poisson random variables.
Then for all $i\in\NN$ we have
$$\mbox{$\sigma_S\,\PP(S\!=\!i)\leq M.$}$$
The bound $M$ is attained with equality when $x=y=\bar u$ and $i=0$.
\end{corollary}
\proof The upper bound follows from the previous analysis. For the
last claim we notice that when $x=y=u$ and $i=0$ we have
$$\mbox{$\sigma_S\,\PP(S\!=\!0)=\sqrt{2u}\,\sum_{k=0}^\infty (e^{-u}{u^k\over k!})^2=M(u)$}$$
so that the bound $M$ is attained with equality if $u=\bar u$.
\endproof

\noindent{\sc Remark.} In the case of a single Poisson variable $X\sim\mathcal{P}(x)$
({\em i.e.} $y\!=\!0$), which is obtained as limit of Binomials $B(n,{x\over n})$, the
remark after Lemma \ref{cuatro} implies the stronger and sharp estimate
$\sigma_X\,\PP(X\!=\!i)=\sqrt{x}\,e^{-x}{x^i\over i!}\leq{1\over\sqrt{2e}}$.

\vspace{2ex}
A natural question arising from these observations, and which seems to be open, is
to characterize the class of distributions that can be obtained as limits
of sums and differences of Bernoullis. A fundamental result of Kintchine \cite{kin}
(see also the classical book by Gnedenko and Kolmogorov \cite[Theorem 2, p.115]{gnk})
characterizes those distributions that are obtained as limits of sums of
independent random variables. The latter may or may not be Bernoullis though, so that
this general result provides only necessary conditions for our more specific question.


TITLE: Confused by logarithmic properties
QUESTION [3 upvotes]: So I've been watching a Khan Academy video that got me confused and I really want to close my gaps so bear with me. I hope that I can understand why I'm failing to understand this.
So here are the steps:
$$\log_2 \sqrt \frac{32}{\sqrt8}$$
$$log_2(\frac{32}{\sqrt8})^\frac{1}{2}$$
Here comes my question : How can the exponent (from the second step) be put out of the parentheses? Wouldn't this indicate that = $\frac{1}{2}$ to the power of both $32$ and sroot of $8$, which wouldn't be correct because we only un-rooted $32$, not $8$.
Continuing:
$$\frac{1}{2}(log_2(\frac{32}{\sqrt8})$$
$$\frac{1}{2}(log_2{32}-log_2{\sqrt8})$$
Second confusion is at this next step:$$\frac{1}{2} (log_2{32}-\frac{1}{2}log_28)$$
Here I get completely confused because I thought we should either do this instead:$\frac{1}{2} (log_2{32})-\frac{1}{2} (log_28)$ or this:$\frac{1}{2} log_2{32}-\frac{1}{2} log_28$ so any explanation would be a relief.
The lasts steps (which I do understand except the $\frac{1}{4}$ but thats because confusion number 2:
$$Distributing: \frac{1}{2}log_2{32}-\frac{1}{4}log_2{8}$$
$$=\frac{5}{2}-\frac{3}{4}$$
Video for reference: https://www.youtube.com/watch?v=TMmxKZaCqe0 (Last part of the vid, from around minute 8:00 to around 9:58)
Thanks in advance!

REPLY [4 votes]: You're getting confused what is what.
$\log_2\sqrt{\frac {32}{\sqrt 8}}$.  Okay.  Let's let $a =\frac {32}{\sqrt 8}$ so we don't get confused in the first step.
$\log_2\sqrt{\frac {32}{\sqrt 8}} = \log_2 \sqrt{a} =$
$\log_2 (a)^{\frac 12} =$
$\frac 12 \log_2 a$.
Okay, we're done with the first step.  Let's bring back $a= \frac {32}{\sqrt{8}}$ so we can continue:
$\frac 12 \log_2 a = \frac 12 \log_2  \frac {32}{\sqrt 8}$.
Let's let $b = 32$ and $c = \sqrt 8$ so we don't get confused on the second step:
$\frac 12 \log_2  \frac {32}{\sqrt 8} = \frac 12 \log_2 \frac bc=$
$\frac 12(\log_2 b - \log_2 c)$
Let's bring $32$ and $\sqrt 8$
$=\frac 12(\log_2 32 - \log_2 \sqrt 8)$
Let's let $d= 32; e= 8$ then (so we don't get confused on the third step)
$=\frac 12(\log_2 d - \log_2 \sqrt e)=$
$\frac 12(\log_2 d - \log_2 e^{\frac 12}) =$
$\frac 12(\log_2 d - \frac 12 \log_2 e)$.
Okay,  let's bring in the $32$ and $8$ back:
$= \frac 12(\log_2 32 - \frac 12 \log_2 8)$
Here we can finish:
$= \frac 12(5 - \frac 32) = \frac 74$.


TITLE: A question about the proof in functional analysis
QUESTION [2 upvotes]: I'm now reading Pazy's book about the semi-group operator. To prove the existence of the solution of KdV equation. He define the Hilbert space $H^s(\mathbb{R})$
$$
\Vert u\Vert_s=\left(\int(1+\xi)^s|\widehat{u}(\xi)|^2d\xi\right)^{\frac{1}{2}}$$
the inner product
$$(u,v)_s=\int(1+\xi)^s\widehat{u}(\xi)\overline{\widehat{v}}(\xi)d\xi)$$
where $\widehat{u}$ is the Fourier Transform of $u$.
In  his book, I have the following question,when $s\geq 3$:
1.If $u\in H^s(R)$,why $Du\in H^{s-1}(\mathbb{R})$? ($Du$ denote $\frac{d}{dx}$)
2.Why $Du\in L^{\infty}(\mathbb{R})$? And $ \Vert Du \Vert_{\infty}\leq C \Vert Du \Vert_{s-1}\leq C  \Vert u \Vert_s$?

REPLY [1 votes]: The norm should be defined as $\lVert u\rVert_s^2:=\int_{\mathbb R}(1+\xi^2)^s|\widehat u(\xi)|^2d\xi$.

We use the fact that $\widehat{Du}(\xi)=i\xi\widehat{u}(\xi)$. Then
\begin{align}
\lVert Du\rVert_{s-1}^2&=\int_{\Bbb R}(1+|\xi|^2)^{s-1}|\xi|^2|\widehat u(\xi)|^2d\xi\\
&\leq \int_{\Bbb R}(1+|\xi|^2)^{s}\widehat u(\xi)|^2d\xi\\
&=\lVert u\rVert_s^2.
\end{align}
We use the inversion formula for Fourier transform.
\begin{align}
|Du(x)|&=C\left|\int_{\Bbb R}e^{itx}it\widehat u(t)dt\right|\\
&\leq C\int_{\Bbb R}|\xi||\widehat u(\xi)|d\xi\\
&=C\int_{\Bbb R}\sqrt{|\xi|}(1+\xi^2)^{-(s-1)/2}|\sqrt{|\xi|}\widehat u(\xi)|(1+\xi^2)^{(s-1)/2}d\xi\\
&\leq C\sqrt{\int_{\Bbb R}\xi(1+\xi^2)^{-(s-1)}d\xi}\lVert Du\rVert_{s-1}
\end{align}
(the last integral is convergent as $2(s-1)-1>1$).


TITLE: Probability that a word contains at least 3 same consecutive letters?
QUESTION [7 upvotes]: Assume we have a word of length $n$ and an alphabet of length $26$ (the small letters a through z, if you want so.
How likely is it that this word contains at least $k := 3$ consecutive letters of any type?
Examples that match:
aaabababab
aoeuuuuuuu
aaaaaaaaaa

Examples that do not match:
ababababab
banananana
abcdefghij

REPLY [3 votes]: The probability of no 3 consecutive letters in a word of length $n$ is $$\frac{(1-p)^2}{a-b}\,\left(\frac{a^{n-1}}{1-a}-\frac{b^{n-1}}{1-b}\right),$$ where $$a=\frac{p+\sqrt{p(4-3p)}}2,\quad b=\frac{p-\sqrt{p(4-3p)}}2,\quad p=1-\frac1{26}.$$ In particular, when $n\to\infty$, the probability of no 3 consecutive letters in a word of length $n$ is equivalent to $$\frac{13}{25\sqrt{29}}(5+\sqrt{29})\,\left(\frac{5}{52}(5+\sqrt{29})\right)^n\approx1.00281\times(0.99857)^n.$$
For $n=100$, $n=500$ and $n=1000$, this predicts approximate probabilities of 3 consecutive letters in a word of length $n$ of $13\%$, $51\%$ and $76\%$ respectively, to be compared to the exact values in @Byron's answer. Probabilities for higher values of $n$ are direct with our formula and become difficult to evaluate using summation formulas.


TITLE: Fitch system, or alternatives?
QUESTION [2 upvotes]: Is there a good resource for how to understand the rules of a Fitch proof system, or an alternative? I'm currently trying to get a sense or how things are proved in natural deduction, which differs in that context changes are allowed / assumptions can be introduced and discharged, and so on.
Can you still make a proof using the line-by-line approach like you could in a Hilbert system? I don't really understand the usefulness of the Fitch system when it's hard to type and present outside of a handwritten diagram. Is there an "equivalent" way we can represent what's going on, perhaps, so that the Fitch system is easier to understand?
I get that an indentation level is a "new context" or an "introduced assumption" but I don't know what we're allowed to write on which lines in general, when we're allowed to discharge an assumption, when we know when we've proven something, when we are finished, etc.

REPLY [2 votes]: A reference that might rapidly get you past concerns with using Fitch-style natural deduction is the forallx Calgary Remix: An Introduction to Formal Logic text and the corresponding general-use, Fitch-style proof checker. See links below.
For example, consider a proof of disjunctive syllogism: $¬A, A ∨ B ∴ B$.
Here is how the proof checker might allow you to prove this:

There are two options: TFL (Truth Functional Logic) and FOL (First Order Logic). They work for general purpose questions and not only the problems in the text. The software resolves formatting issues with the indented subordinate proofs and provides an ability to check along the way to make sure mistakes have not been made.
The text provides a slightly different proof in section 19.2 as well as providing an introduction to the other rules available in natural deduction along with an introduction to formal logic.

Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker http://proofs.openlogicproject.org/
P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Winter 2018. http://forallx.openlogicproject.org/


TITLE: A strange application of the Heine-Borel lemma (Ahlfors)
QUESTION [4 upvotes]: In Ahlfors' Complex Analysis text, pages 289-290, the author discusses analytic continuation along arcs. Among other things, he proves the equivalence with analytic continuation using a chain of function elements $(f_k ,\Omega_k)$.
The fact that two function elements being related by a chain of direct analytic continuations implies that an appropriate analytic continuation along an arc is possible is clear to me. However, in page 290 Ahlfors is trying to prove the converse. Namely, that the arc from the analytic continuation can be "followed" by a chain of direct analytic continuations, from the initial point of the arc to its endpoint.
His words are:

Conversely, if $\bar{\gamma}$ is given, we can find a chain of direct analytic continuations which follows the arc $\gamma$ in the same way as in the preceding construction. In fact, by Heine-Borel's lemma the parametric interval $[a,b]$ can be subdivided into $[a,t_1], [t_1,t_2], \dots , [t_{n-1},b]$ such that $\bar{\gamma}(t)$ = $(f_k,\gamma(t))$ in $[t_{k-1},t_k]$ for suitably chosen function elements $(f_k,\Omega_k)$. Although $(f_k,\Omega_k)$ and $(f_{k+1},\Omega_{k+1})$ need not be direct analytic continuations of each other, they are at least direct continuations of their common restrictions to a neighborhood of $\gamma(t_k)$.

I'm having a hard time understanding this. As far as I know the Heine Borel lemma characterises compact subsets of Euclidean space alone as bounded and compact ones. The only set I see here which lies in Euclidean space is the parameter interval $[a,b]$ of the arc. But, even if that's where the lemma is applied, the outcome should be a finite open subcover of $[a,b]$, while the intervals $\{[t_{k-1},t_k]\}$ are only closed.
Can anyone please help me understand this proof? Thanks!
P.S. Here $\bar{\gamma}:[a,b] \to \mathfrak{S_0}(\mathbf{f})$ takes values on some Riemann surface, and $\gamma= \pi \circ \bar{\gamma}:[a,b] \to \mathbb C$ is its projection.

REPLY [3 votes]: This could be called  "partition form of the Heine-Borel theorem", just as there is a "separation form of the Hahn-Banach theorem". All the ingredients are the same, they are just packaged into a different shape, which is more convenient for certain uses. In the paper Applications of full covers in real analysis, the [undergraduate] authors give the partition form a separate name, "Thomson's lemma". I don't think this is going to catch on, seeing as the paper by Thomson is dated by 1980 rather than   19th century. As the authors say,

Thomson’s lemma is similar in concept and execution to the version of the Heine–Borel theorem

Then they go on to reprove some theorems in real analysis using the partition form.


TITLE: Does this sequence of operators converge in norm or strongly?
QUESTION [7 upvotes]: Let $H$ be a Hilbert space and $\mathcal{L}(H)$ the set of all bounded linear operators $L:H\to H$, equiped with the usual norm $\|\cdot\|_{\mathcal{L}}$.
Let $T:D(T)\subset H\to H$ be a densely-defined linear operator and $(\lambda_n)$ a sequence in $\rho(T)$ (the resolvent set of $T$).
Suppose that there exists $\lambda\in\rho(T)$ such that $\lambda_n\to \lambda$.
What is it possible to conclude about the sequence $(S_n)$ of bounded linear operators given by
$$S_n=(\lambda_nI-T)^{-1}?$$
Is it possible to prove that $\|S_n-(\lambda I-T)^{-1}\|_{\mathcal{L}}\to 0$?
Is it possible to prove that $\|S_nx-(\lambda I-T)^{-1}x\|_H\to 0$ for all $x\in H$?
Thanks.

REPLY [0 votes]: This sequence does converge in the operator norm (actually, $\lambda \mapsto (T-\lambda I)^{-1}$ is analytic! See this link for a short proof). Note that operator convergence implies strong convergence, so we only have to prove your first claim.
The proof uses the ever helpful resolvent identity:
$$
(A-\lambda I)^{-1} - (A-\mu I)^{-1} = (\lambda-\mu)(A-\lambda I)^{-1}(A-\mu I)^{-1}
$$
See this page for more details as well as the other resolvent identity.
Now, we can start proving. $(T-\lambda_n I)^{-1} \to (T-\lambda I)^{-1}$. Begin by noticing that by replacing $T$ with $T-\lambda I$, we can assume without loss that $\lambda = 0$. Recall that $\|AB\|\leq \|A\|\,\|B\|$ for any operators $A$ and $B$. By the resolvent identity above,
$$
\|S_n - (T)^{-1}\| = |\lambda_n|\,\|S_n(T)^{-1}\|\leq |\lambda_n|\, \|S_n\|\,\|T^{-1}\|
$$
So it suffices to prove that $\|S_n\|$ is bounded.
$$
\|S_n\| = \|T^{-1}T(T-\lambda_n I)^{-1}\| \leq \|T^{-1}\|\,\|(I-\lambda_nT)^{-1}\|
$$
We now come to the main trick. When $\lambda_n$ is small enough, $\|\lambda_nT\| <1/2$ so
$$
(I-\lambda_nT)^{-1} = \sum_{i=0}^\infty (\lambda_nT)^i
$$
analogously to the geometric series from 1 dimension. So, using that $\|AB\| \leq \|A\|\|B\|$,
$$
\|(I-\lambda_nT)^{-1}\| \leq \sum_{i=0}^\infty \|(\lambda_nT)^i\| \leq  \sum_{i=1}^\infty (1/2)^n = 1
$$
Now we can conclude with $\|S_n\| \leq \|T^{-1}\|$ for $n$ large enough.


TITLE: Condition for existence of a continuous function realizing a partition
QUESTION [4 upvotes]: Let $\{U_i\}_{i=1}^{I}$ be a non-empty and finite collection of non-empty, disjoint, open, (and obviously bounded) subsets of $[0,1]^n$.  Suppose also that $[0,1]^n=\cup_{i =1 }^{ I} \overline{U_i}$.  Under what condition does there exist a continuous function $f:[0,1]^n\rightarrow [0,1]^I$ such that
$$
x\in U_i \Leftrightarrow \|f(x)-e_i\|< \min_{\tilde{i}\neq i}\|f(x)-e_{\tilde{i}}\|
;
$$
where $\{e_i\}_{i=1}^I$ is the standard basis of $\mathbb{R}^I$.

What I have tried:

In the case where each $U_i$ is convex: If $U_i$ is convex then there it is star-shaped so there is an $x_i\in U_i$ for which every $x \in U_i$ can be reached by a line segment emanating from $x_i$ and contained within $U_i$.  Note, since $U_i$ is convex then such a line segment must stay within $U_i$.  Thus, for any $x'\in \cup_{i\in I} (0,1)^N$,
$
\|x-x_i\|<\min_{\tilde{i}\neq i} \|x-x_{\tilde{i}}\|.
$  So we set:
$$
f(x)= \left(\|x-x_i\|
e_i
\right)_{i=1}^I.
$$
Is this reasoning correct?

For the general case, I was trying to use Urysohn's Lemma but alas, to no avail..

REPLY [2 votes]: For $x \in U_i$ let $f(x) = r e_i$ where $r = \min_{y \notin U_i} |x - y|$, i.e. the radius of the largest open ball centered on $x$ and contained in $U_i$. If $x$ is not in any $U_i$ let $f(x) = 0$. Note that $|f(x) - f(y)| \leq |x - y|$


TITLE: Solving pseudo arithmetic-geometric sequence
QUESTION [0 upvotes]: Let $p \in \mathbb{R}$ and $u_0 = 1$.
$$\forall k\in \mathbb{N}, u_{k+1} = (-2p+1)u_k + (p-2)(-1)^k$$
I would like to get an explicit formula for $u_k$.
Classical arithmetic-geometric sequences in the form $u_{k+1} = a u_k + b$ can be solved using the property that $u_{k+1}-u_k$ is a geometric sequence. But this doesn't work well since the $b$ term here depends on $k$.
I have similar problem with the following sequence, $v_{k+1} = (-2p+1)v_k - p(-1)^k$ with $v_0=0$.
The two sequences satisfy the coupled relations :
$$u_{k+1} = -(p+1)u_k-(p-2)v_k$$
$$v_{k+1} = -pu_k-(p-1)v_k$$

REPLY [0 votes]: Another method using the coupled equations,
Let $X_k = {(u_k\:v_k)}^T$, then $X_{k+1} = -A X_k$ with $A$ the following matrix:
\begin{pmatrix}
p+1 & p-2 \\
p & p-1
\end{pmatrix}
Diagonalize the matrix with it characteristic polynomial $(X+p+1)(X+p-1) + p(p-2)$ and apply the change of basis:
$X_{k+1} = -A X_k = -P^{-1}DP X_k$, then $X_k$ is a geometric sequence.
It suffice to compute $A^k = P^{-1}D^kP$ to obtain $X_k=(-1)^kP^{-1}D^kP X_0$.


text:
\section{Application: Classification of closed star products}
\label{sec:applications}
This application of cyclic formality has already been proposed by Shoikhet in \cite{shoikhet}. We repeat it here briefly.
\begin{defi}
Let $M$ be a smooth manifold. We call an associative $\hbar$-linear product $\star$ on $C^\infty(M)[[\hbar]]$ a \emph{star product} if
\[
f \star g = fg+\sum_{j\geq 1} \hbar^j m_j(f,g)
\]
for bidifferential operators $m_j$ and all $f,g\in C^\infty(M)$. Two star products $\star$, $\star'$ are \emph{gauge equivalent} if there is a formal series of differential operators
\[
D = 1 + \sum_{j\geq 1} \hbar^j D_j
\]
such that $f\star g=D^{-1}(D(f)\star' D(g))$ for all $f,g\in C^\infty(M)$.
Let now $M$ be oriented with volume form $\omega$. The star product $\star$ is \emph{closed} if for any three compactly supported $f,g,h\in C_c^\infty(M)$
\[
\int_M f(g\star h) \omega = \int_M g(h\star f)\omega.
\]
Two closed star products $\star$, $\star'$ are called \emph{gauge equivalent} if there is a $D$ as above such that $f\star g=D^{-1}(D(f)\star' D(g))$ and
\[
\int_M fg \omega = \int_M D(f)D(g) \omega
\]
for all $f,g\in C_c^\infty(M)$.
\end{defi}

\begin{defi}
A formal series of degree $1$ elements of $T_{poly}^{\bullet+1}[u]$
\[
\pi = \sum_{j\geq 0} \hbar^j (\pi_j+u f_j)
\]
is called \emph{formal unimodular Poisson structure} if $u \dv \pi +\frac{1}{2} \co{\pi}{\pi}_{S}=0$. Two such $\pi$, $\pi'$ are \emph{gauge equivalent} if there is a formal series of vector fields
\[
\xi = \sum_{j\geq 1} \hbar^j \xi_j
\]
such that
\[
\pi' = e^{ad_\xi} \pi + u \frac{1-e^{ad_\xi}}{ad_\xi} \dv\xi
\]
where $ad_\xi (\cdot):= \co{\xi}{\cdot}_{S}$.
\end{defi}

The above notions of gauge equivalence obviously define equivalence relations on the sets of closed star products and formal unimodular Poisson structures. There is a map $\Phi$ between the two sets, mapping a formal unimodular Poisson structure $\pi$ to the (closed) star product $\star$ such that
\[
f\star g = fg + \sum_{j\geq 1} \frac{\hbar^j}{j!} \morphU_j(\pi\odot \cdots \odot \pi)(f,g)
\]

\begin{thm}
The map $\Phi$ is a bijection between the set of gauge equivalence classes of formal unimodular Poisson structures and the set of gauge equivalence classes of closed star products.
\end{thm}
\begin{proof}
Kontsevich has shown in \cite{kontsevich} that an $L_\infty$-quasi-isomorphism between dglas $\alg{g}\to \alg{g}'$ induces in the above manner a bijection between the gauge equivalence classes of solutions to the Maurer-Cartan equations in the pro-nilpotent Lie algebras $\hbar \alg{g}[[\hbar]]$ and $\hbar \alg{g}'[[\hbar]]$. Applying this to $\alg{g}=T_{poly}(M)[u]$ and $\alg{g}'=(D_{poly}(M))^\sigma$ yields the result.
\end{proof}

\begin{rem}
In case the top cohomology of $M$ vanishes, i.e., $H^d(M)=0$, one can see that any formal unimodular Poisson structure is gauge equivalent to a divergence free Poisson structure.
\end{rem}

config: arxiv


TITLE: Existence and unicity of a constant $c$ such that $\lim_{x \rightarrow \pi} \frac {x + c}{\sin x}$ is finite
QUESTION [5 upvotes]: Supposing $c = - \pi$. Then, the quotient will assume the form $0/0$. Using L'Hospital
$$\displaystyle \lim_{x \rightarrow \pi} \dfrac {x-\pi}{\sin x} = \lim_{x \rightarrow \pi} \dfrac {1}{\cos x} = -1$$
So, for $c= - \pi$, $ \dfrac {x + c}{\sin x}$ tends to a finite limit when x $ \rightarrow \pi$.
What argument could I use to prove that that's the only value for c such that the limit is finite?

REPLY [1 votes]: Since $x \to \pi$, you may write $x=\pi-\epsilon$ with $\epsilon \to 0$ and using the Taylor expansion for $\epsilon$ near $0$, you have
$$
\sin x =\sin (\pi-\epsilon)= \epsilon+\mathcal{O}(\epsilon^3)
$$ you obtain
$$
\begin{align}
\frac {x + c}{\sin x}&=\frac {\pi-\epsilon+c}{\sin (\pi - \epsilon)}\\\\
&=\frac {\pi+c-\epsilon}{\epsilon+\mathcal{O}(\epsilon^3)}\\\\
&=\frac {\pi+c}{\epsilon}-1+\mathcal{O}(\epsilon)\\\\
\end{align}
$$ and the latter expression, as $\epsilon \to 0$, is finite if and only  if $\pi+c=0$, as announced.


TITLE: Parametric Equation for Great Circle
QUESTION [10 upvotes]: So I've been doing a lot of searching and haven't found exactly what I'm looking for.  My math skills are a bit rusty, so I haven't had luck deriving this on my own.
What I'm looking for is an equation (or set of equations) where I can plug in starting and ending spherical coordinates, plus a percentage (ie [0,1]) and output spherical coordinates of some point in between (ie, progress along a great circle).
The idea is basically to chart the progress of a plane between two cities and draw it on a globe or map.
Inputs:

lat1,lon1
lat2,lon2
r (radius)
p (progress, from 0->1)

Output:

lat_x,lon_x (point in-between)

REPLY [8 votes]: Perhaps the most succinct and easiest answer is (as quoted from here)

You are given two points $u$ and $v$ on the unit sphere. Think of them as position vectors $\vec u$ and $\vec v$ . It is easy enough to calculate cross products. Calculate $\vec w = (\vec u \times \vec v)\times\vec u$. Then $\vec w$ and $\vec u$ are unit vectors perpendicular to each other and in the plane of the circle. So a parameterization of the circle is $$\vec R (t)=\vec u \cos t+\vec w \sin t.$$

Correction: $\vec w$ is only a unit vector if $\vec u$ and
$\vec v$ are perpendicular.


text:
chapter \<open>A monad for generating fresh names\<close>

theory Fresh_Monad
imports
  "HOL-Library.State_Monad"
  Term_Utils
begin

text \<open>
  Generation of fresh names in general can be thought of as picking a string that is not an element
  of a (finite) set of already existing names. For Isabelle, the \<^emph>\<open>Nominal\<close> framework
  @{cite urban2008nominal and urban2013nominal} provides support for reasoning over fresh names, but
  unfortunately, its definitions are not executable.

  Instead, I chose to model generation of fresh names as a monad based on @{type state}. With this,
  it becomes possible to write programs using \<open>do\<close>-notation. This is implemented abstractly as a
  @{command locale} that expects two operations:

  \<^item> \<open>next\<close> expects a value and generates a larger value, according to @{class linorder}
  \<^item> \<open>arb\<close> produces any value, similarly to @{const undefined}, but executable
\<close>

locale fresh =
  fixes "next" :: "'a::linorder \<Rightarrow> 'a" and arb :: 'a
  assumes next_ge: "next x > x"
begin

abbreviation update_next :: "('a, unit) state" where
"update_next \<equiv> State_Monad.update next"

lemma update_next_strict_mono[simp, intro]: "strict_mono_state update_next"
using next_ge by (auto intro: update_strict_mono)

lemma update_next_mono[simp, intro]: "mono_state update_next"
by (rule strict_mono_implies_mono) (rule update_next_strict_mono)

definition create :: "('a, 'a) state" where
"create = update_next \<bind> (\<lambda>_. State_Monad.get)"

lemma create_alt_def[code]: "create = State (\<lambda>a. (next a, next a))"
unfolding create_def State_Monad.update_def State_Monad.get_def State_Monad.set_def State_Monad.bind_def
by simp

abbreviation fresh_in :: "'a set \<Rightarrow> 'a \<Rightarrow> bool" where
"fresh_in S s \<equiv> Ball S ((\<ge>) s)"

lemma next_ge_all: "finite S \<Longrightarrow> fresh_in S s \<Longrightarrow> next s \<notin> S"
by (metis antisym less_imp_le less_irrefl next_ge)

definition Next :: "'a set \<Rightarrow> 'a" where
"Next S = (if S = {} then arb else next (Max S))"

lemma Next_ge_max: "finite S \<Longrightarrow> S \<noteq> {} \<Longrightarrow> Next S > Max S"
unfolding Next_def using next_ge by simp

lemma Next_not_member_subset: "finite S' \<Longrightarrow> S \<subseteq> S' \<Longrightarrow> Next S' \<notin> S"
unfolding Next_def using next_ge
by (metis Max_ge Max_mono empty_iff finite_subset leD less_le_trans subset_empty)

lemma Next_not_member: "finite S \<Longrightarrow> Next S \<notin> S"
by (rule Next_not_member_subset) auto

lemma Next_geq_not_member: "finite S \<Longrightarrow> s \<ge> Next S \<Longrightarrow> s \<notin> S"
unfolding Next_def using next_ge
by (metis (full_types) Max_ge all_not_in_conv leD le_less_trans)

lemma next_not_member: "finite S \<Longrightarrow> s \<ge> Next S \<Longrightarrow> next s \<notin> S"
by (meson Next_geq_not_member less_imp_le next_ge order_trans)

lemma create_mono[simp, intro]: "mono_state create"
unfolding create_def
by (auto intro: bind_mono_strong)

lemma create_strict_mono[simp, intro]: "strict_mono_state create"
unfolding create_def
by (rule bind_strict_mono_strong2) auto

abbreviation run_fresh where
"run_fresh m S \<equiv> fst (run_state m (Next S))"

abbreviation fresh_fin :: "'a fset \<Rightarrow> 'a \<Rightarrow> bool" where
"fresh_fin S s \<equiv> fBall S ((\<ge>) s)"

context includes fset.lifting begin

lemma next_ge_fall: "fresh_fin S s \<Longrightarrow> next s |\<notin>| S"
by (transfer fixing: "next") (rule next_ge_all)

lift_definition fNext :: "'a fset \<Rightarrow> 'a" is Next .

lemma fNext_ge_max: "S \<noteq> {||} \<Longrightarrow> fNext S > fMax S"
by transfer (rule Next_ge_max)

lemma next_not_fmember: "s \<ge> fNext S \<Longrightarrow> next s |\<notin>| S"
by transfer (rule next_not_member)

lemma fNext_geq_not_member: "s \<ge> fNext S \<Longrightarrow> s |\<notin>| S"
by transfer (rule Next_geq_not_member)

lemma fNext_not_member: "fNext S |\<notin>| S"
by transfer (rule Next_not_member)

lemma fNext_not_member_subset: "S |\<subseteq>| S' \<Longrightarrow> fNext S' |\<notin>| S"
by transfer (rule Next_not_member_subset)

abbreviation frun_fresh where
"frun_fresh m S \<equiv> fst (run_state m (fNext S))"

end

end

end

subset_name: curated


TITLE: How can I test the Lipschitz condition for a second order system?
QUESTION [0 upvotes]: I have the second order autonomous system
$$x_1 '= ax_1 - bx_1x_2
\\
x_2 '= -cx_2 + dx_1x_2$$
How can I apply the Lipschitz condition to this second order system?
Can anyone explain step by step how to apply the condition in this case?
Regards
Keiver

REPLY [1 votes]: Hints: You can write the right hand side of the system as:
$$f(x,y)= (ax-bxy,-cy+dxy)^T$$
Think about what the Lipschitz condition means for a function $f:\mathbb{R}^2 \rightarrow \mathbb{R}^2$. Remember that in the one variable case, it suffices to check that $\bigg{|}\cfrac{\partial f}{\partial x}\bigg{|}\leq L_0$ on some compact and convex set $D_0$, i.e. the derivative of $f$ with respect to $x$ is bounded on some subset of the real line. This follows from the mean value theorem (MVT), as you can check.
Now for two variables, what is the derivative of $f$ with respect to the vector $(x,y)^T$? This is the Jacobian matrix.
To show that $f$ is Lipschitz, it is sufficient to find a uniform bound given your favorite norm of the Jacobian matrix. Any two norms on a finite dimensional vector space are equivalent, so you're free to choose any norm.
Computint the Jacobian we get:
$$Df(x)=\begin{pmatrix}a-by&-bx \\ dy &-c+dx \end{pmatrix} $$
Now use this to find a uniform bound for $Df$. Another hint is to recall the definition of the operator norm of $A:E \rightarrow F$:
$$||A|| = \sup_{||x||_{E}=1}{||A(x)||_{F}}$$
Here, $E$ and $F$ are the the "source" and "target" vector spaces of the operator $A$, which in this case are both $\mathbb{R}^2$.
Pick any matrix (as an operator on $\mathbb{R}^2$) norm you want to find a suitable upper bound, e.g. the $\ell_1$ matrix norm. That is, $$||A||_{\ell_1}= \max_{1 \leq j \leq n} \sum_{i=1}^{m}|a_{ij}|$$
This is the maximum value of the sum of absolute values of the columns of $A$. Analogously, you can define the $\ell_{\infty}$ matrix norm as the maximum value of the sum of absolute values of the rows of $A$.
I hope this helps in at least getting started. You should be able to take it from here.
Note: The function may not be globally Lipschitz, but only locally Lipschitz. In other words, it is Lipschitz only on some open and connected set $D \subset \mathbb{R}^2$.


TITLE: Uniform Circular Motion Confusion
QUESTION [0 upvotes]: Having some problems when calculating this problem:
A fly lands on an old record player, while a 7'' O.D. 45 RPM record is playing. If the fly lands on the edge of the record, determine the records period of rotation.
I do not understand how to calculate (T) tau.
w = (2*PI*R)(#cycles/sec) = (2*PI*V)
T = 1/V
R is 7.0 in (or 0.18 meters)
45 RPM is 4.72 radians/second
Therefore to find w:
w = (2*PI)(0.18m)(4.72rad/s) = 5.33 meters*radians/second
Please notice that I have meters * radians when this should be only radians and seconds.
I am just looking to calculate Tau (T)

REPLY [2 votes]: I'm confused as to why the $7$ inches and the fly landing on the very edge of the record is relevant. Period is simply the time it takes for the record to go through one complete revolution. Because the record spins with a frequency of $45rpm$ we can find period directly by:
$$ T = {1 \over f} = {1 \over 45 {rev \over min}} = .022min$$
Equivalently, by multiplying by $60$ you can convert to seconds:
$$ .022min*{60sec \over 1min} = 1.3sec$$


TITLE: Why is it necessary for a circuit to be complete?
QUESTION [0 upvotes]: Can electrons not flow through a load if they do not have a path to flow to the positive terminal of the battery? Why is it absolutely necessary for electrons to end up at the positive terminal?

REPLY [0 votes]: It is not that it is just necessary. Electron flow, in the first place, OCCURS due to the potential difference between the 2 terminals - negative and positive terminals.
Emf or potential difference is the driving force of the electrons in the electric circuit which causes the electrons to flow from the negative terminal to the positive terminal.
If the circuit is not closed, electrons will not flow.
EDIT: As per the comment by brucesmitherson ;  In an open circuit, the driving force is not absent, it is just that it is not strong enough to make electrons jump outside of the metal, which requires a lot of energy.


TITLE: Is $\mathbb{C}[x,e^x]$ Noetherian?
QUESTION [2 upvotes]: I want to know how to show that the ring $\mathbb{C}[x,e^x]$ is Noetherian (I know the answer is yes, it is Noetherian, but I'm unable to prove it!).
My initial thoughts were to construct some isomorphism $\mathbb{C}[x,y]\rightarrow \mathbb{C}[x,e^x]$ such as $f(x,y)\mapsto f(x,e^x)$, and use the fact that $\mathbb{C}[x,y]$ is Noetherian by the Hilbert Bases Theorem. Such a mapping is a well-defined surjective ring homomorphism, but I'm struggling to prove injectivity in this case: if $f$ is in the kernel then $f(x,e^x)$ is identically zero, and hypothetically we could substitute in $y=e^x$ to give us that $f(x,y)$ identically zero for $y>0$ - the problem being that this is only true for $y>0$!
Please could someone help me figure this out? (Or let me know if I'm barking up at the wrong tree entirely!) Thanks :-)

REPLY [2 votes]: To prove your ring is Noetherian, PrudiiArca provided an answer.
If you want to know how to prove that the kernel of your map is trivial: this is in fact equivalent to proving that $e^X$ is transcendental over $\mathbf{C}[X]$. See this or this answer.


TITLE: Constructing an increasing sequence of numbers from a set
QUESTION [0 upvotes]: I have an infinite set $A$ of real numbers and I wish to construct a strictly increasing sequence using elements of $A$. This is what came to my mind -
Pick any element from $A$ and name it $a_1$. Pick a different element from $A$. If this is greater than $a_1$, call it $a_2$. If not, rename the first element $a_2$ and the new one $a_1$. Suppose I have chosen $a_1<a_2<…<a_n$. Pick an element $a$ different from all these. If $a>a_n$, name it $a_{n+1}$. If $a<a_1$, rename $a_i$ as $a_{i+1}$ for all $i$, and $a$ as $a_1$. If $a_k<a<a_{k+1}$, rename $a$ to $a_{k+1}$ and $a_i$ to $a_{i+1}$ for $i\geq k+1$. This way I have $a_1<a_2<…<a_n<a_{n+1}$. Then by induction I have my increasing sequence $(a_n)$.
Am I allowed to do this? Did I invoke any axiom while doing this?

REPLY [2 votes]: This proves you can create an increasing sequence of any finite length (because if a sequence of length $n$ can be made, then a sequence of length $n+1$ can be made) but not an increasing sequence of infinite length (because for any $n$ you can "go one more" to length $n+1$ but adding one will never get you to length $\infty$) .
It's a subtle but important point that induction can give you a conclusion for all natural values but not for a countable infinite value.[1]
In this case it will be possible that for an infinite number of attempts we will find a number $<$ than $a_1$ and thus a new $a_1$ will be assigned an infinite number of times and there will be no "final" $a_1$ for the infinite sequence.
As Tony Ks answer shows  the set is $\{-1,-2, -3, ....\}$ then the first sequence will be $\{a_1\} = \{-1\}$ and the second sequence will be $\{a_1, a_2\} = -2, -1$, and so on.  Then $n$ sequence will be $\{a_1, ....  a_n\} = \{-n, -n+1, ...., -1\}$.  But each sequence will always have a different $a_1$ and there will be no "agreed upon" $a_1$ for an infinite sequence.
[1]  A false proof that all real numbers between $0$ and $1$ is rational:  If every decimal with $n$ places is rational then a decimal with $n+1$ spaces $0.a_1a_2....a_na_{n+1} = 0.a_1a_2.....a_n + \frac {a_{n+1}}{10^{n+1}}$ is the sum of two rational numbers and hence rational.  So by induction every decimal with any number of places is rational.  As every real number between $0$ and $1$ can be written a decimal with some number (possibly infinite) places, every such real number is rational.
The catch is that induction only proves something about decimals with finite number of places.  Not infinite number of places.  Although we can "add $1$" an infinite number of times to get an infinite number of numbers, those numbers are all finite.  We can never "add $1$" and ever get $\infty$.


TITLE: Equivalent measures and independence
QUESTION [1 upvotes]: Suppose that $\mu$ and $\lambda$ are two equivalent measures in a probability space $(\Omega, \mathscr F)$. Suppose that random variables $\xi_1,..,\xi_n$ in $(\Omega, \mathscr F)$ are independent according to $\mu$, does this imply that they are independent also according to $\lambda$ ?

REPLY [3 votes]: No, let $\xi_1,\xi_2$ uniformly distributed on the unit square i.e. $\xi_1,\xi_2$ are random variables on $(\Omega, \mathscr F) = ([0,1] \times [0,1], \mathscr F)$. So they are independent with respect to the Lebesgue measure.
Now, take the following common density instead
$$f_{\xi_1,\xi_2}(x,y)=x+y, \,\,\, 0\le x\le 1, 0\le y\le 1.\tag 1$$
With respect to this common distribution the two random variables are not independent.
$$f_{\xi_1}(x)=x+\frac12,\,\,0\le x \le 1$$
and
$$f_{\xi_2}(y)=y+\frac12,\,\,0\le y \le 1.$$
So,
$$f_{\xi_1,\xi_2}(x,y)\not=f_{\xi_1}(x)f_{\xi_2}(y).$$
At the same time the two measures (the Lebesgue measure and the one defined by $(1)$) are equivalent. They are absolute continuous with respect to each other.