text:
\section{Regret Analysis}
\label{sec: regret}
 In this section, we study the performance of the proposed anytime pMHE iteration scheme. Recall the  performance  criterion  of the original estimation problem (\ref{condensed}), which   is  to minimize at each time instant $k$ the sum of stage costs  $f_k$.   In order to characterize the overall performance of  Algorithm~\ref{alg: eta changes},  \rev{we investigate the accumulation of losses $f_k$ over 	the considered simulation time $T\in \mathbb{N}_+$ given by}
\begin{align}
\label{accCost}
\sum_{k=1}^{T}\quad \min_{0 \leq i \leq \mathrm{it}(k) } f_k (   \mathbf{\hat{z}}^{i}_{k} ) .
\end{align}
Note that the $\min$ operator in (\ref{accCost}) follows from the fact that the generated sequence  of iterates  $\lbrace \mathbf{\hat{z}}^{0}_{k},\cdots,  \mathbf{\hat{z}}^{ \mathrm{it}(k)}_{k}  \rbrace$ does not  necessarily  produce $f_k(\mathbf{\hat{z}}^{0}_{k}) \geq  \cdots \geq f_k(\mathbf{\hat{z}}^{ \mathrm{it}(k)}_{k}) $. \rev{Hence, given $\lbrace \mathbf{\hat{z}}^{0}_{k},\cdots,  \mathbf{\hat{z}}^{ \mathrm{it}(k)}_{k}  \rbrace$, we have to choose a suitable  $\mathbf{\hat{z}}^{i}_{k}$ whose function value is then used in the performance analysis. Following the literature on mirror descent algorithms \cite{beck2003mirror},} we select the iterate  with the minimal cost as our estimate, i.e., $\mathbf{\hat{z}}_k^{i_o(k)}$ with $i_o(k)=\mathrm{arg} \min_{0 \leq i \leq \mathrm{it}(k) } f_k (   \mathbf{\hat{z}}^{i}_{k} )$. \rev{One advantage of this selection is that it allows us to adapt many tools used in the convergence proof of the mirror descent algorithm to the regret analysis.} Further, we choose $\mathrm{j}(k)=\mathrm{it}(k)$ in Algorithm~\ref{alg: eta changes}.
Any other choice is in principle possible, but one has to adapt the subsequent analysis accordingly. \\
Our goal is to ensure that (\ref{accCost}) is not much larger than the total loss  $\sum_{k=1}^{T}  \,  f_k (   \mathbf{z}_{k}^c )$ incurred by any comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace$ satisfying $\mathbf{z}_{k}^c \in \mathcal{S}_k$. In other words, we aim to obtain a  low \textit{regret}, which we define as
\begin{align}
\label{regretNew}
R(T) & \coloneqq \sum_{k=1}^{T} \, \min_{0 \leq i \leq \mathrm{it}(k) } f_k (   \mathbf{\hat{z}}^{i}_{k} ) - \sum_{k=1}^{T}  \,  f_k (   \mathbf{z}_{k}^c ) .
\end{align}
By computing an upper bound for the regret, \rev{we can design suitable step sizes that yield a sublinear regret, i.e., the  regret bound $\mathcal{O}(\sqrt{T})$. This is a meaningful regret bound and well-known in the context of online convex  optimization since it implies that the average regret $ R(T)/T$ tends to zero for $T \rightarrow \infty$ and hence that the proposed algorithm performs well, on average as well as the comparator \cite{mokhtari2016online}. This property of the algorithm is especially desirable when the regret is used to} evaluate how well the pMHE iteration scheme performs compared to an estimation scheme that knows the optimal solutions  $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace$. Hence, we measure the real-time regret of our algorithm that carries out only finitely many optimization iterations
(due to limited hardware resources and/or minimum required sampling rate)
relative to a comparator algorithm that gets instantaneously an optimal solution from some oracle.
 \subsection{Regret with respect to arbitrary comparator sequences}
In this section, we  establish  bounds on the regret generated by Algorithm~\ref{alg: eta changes}.  Similar to \cite{hall2013dynamical}, we derive regret bounds that  depend on the variation of the comparator sequence with respect to the dynamics $\Phi_k$ defined in (\ref{Adap: warm}):
\begin{align}
  C_{T}(\mathbf{z}_{1}^c,\cdots, \mathbf{z}_{T}^c)  &\coloneqq \sum_{k=1}^{T} \left\Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert. \label{compSeq}
\end{align}
Moreover, we define the following notations:
\begin{align*}
G_f &\coloneqq\max_{\mathbf{z} \in \mathcal{S}_k, k > 0} \,\Vert \nabla  f_k(\mathbf{z} ) \Vert \\
 M_1 &\coloneqq   \max_{ \mathbf{z} \in  \mathcal{S}_k, k > 0} \left\Vert \nabla  \psi(\mathbf{z}) \right\Vert,  \quad \,  M_2  \coloneqq   \max_{ \mathbf{z} \in  \mathcal{S}_k, k > 0} \left\Vert \nabla  \psi(\Phi(\mathbf{z})) \right\Vert    \\
  M&\coloneqq   M_1 + M_2, \hspace{1.35cm}     D_{\max}  \coloneqq \max_{\mathbf{z}_1,\mathbf{z}_2 \in  \mathcal{S}_k, k > 0} D_\psi(\mathbf{z}_1,\mathbf{z}_2) ,
\end{align*}
where we assume that the maximum in each definition is well-defined. Our first main result is stated next.
\begin{theorem}
\label{theorem_iTadap}
Consider  Algorithm \ref{alg: eta changes} with $  \mathrm{j}(k)= \mathrm{it}(k) $ and any comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace $ with $\mathbf{z}_{k}^c \in \mathcal{S}_k$.  Let Assumptions  \ref{ass: S closed}, \ref{ass: f convex}   and \ref{ass: Bregman} hold true.  If we choose the Bregman distance $D_\psi$ such that
 \begin{align}
 \label{BregDistanceNonneg}
D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})    \leq 0
\end{align}
and employ  non-increasing sequences
\begin{align}
\label{thm: non-incr sequences}
\sum_{i=0}^{\mathrm{it}(k+1)-1}\eta_{k+1}^{i} \leq \sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i},
\end{align}
then  Algorithm \ref{alg: eta changes} gives the following regret bound
\begin{align}
\label{regretGenBound}
R(T)
 \leq & \frac{D_{max}}{\sum_{i=0}^{\mathrm{it}(T)-1}\eta_{T}^{i}} + \frac{   G_f^2 }{2  \sigma  }\sum_{k=1}^{T}    \frac{\sum_{i=0}^{\mathrm{it}(k)-1}    (\eta_k^{i})^2  }{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}} \\ & \qquad      + \frac{M  }{\sum_{i=0}^{\mathrm{it}(T)-1}\eta_T^{i}} \sum_{k=1}^{T} \left\Vert   \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert \nonumber .
\end{align}
\end{theorem}
The proof of this result relies on the next lemma.
\begin{lem}
\label{regret_betweeniT}
Consider  Algorithm \ref{alg: eta changes} with  $  \mathrm{j}(k)= \mathrm{it}(k) $  and any comparator sequence  $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace $  with $\mathbf{z}_{k}^c \in \mathcal{S}_k$.  Suppose Assumptions~\ref{ass: S closed},~\ref{ass: f convex} and~\ref{ass: Bregman} hold.  Then for a given iteration step~$i$ and a time instant $k>0$, we have that
\begin{align}
\label{result: regret_betweeniT}
  \eta_k^i &\left(f_k(\mathbf{\hat{z}}_{k}^i) - f_k( \mathbf{z}_{k}^c) \right) \\ &\leq  D_\psi( \mathbf{z}_{k}^c,\mathbf{\hat{z}}_{k}^{i}) - D_\psi(\mathbf{z}_{k}^c, \mathbf{\hat{z}}_{k}^{i+1}) +   \frac{ ( \eta_k^i)^2}{2 \sigma} \Vert \nabla f_k\left(\mathbf{\hat{z}}_{k}^{i}\right) \Vert^2. \nonumber
\end{align}
Moreover, if  we choose the Bregman distance $D_\psi$ such that
 \begin{align}
 \label{Dcontadap}
D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})    \leq 0 ,
\end{align}
then
 \begin{align}
 \label{result: regret_iTasap}
    \min_{0 \leq i \leq \mathrm{it}(k) } &f_k (  \mathbf{\hat{z}}_k^{i} )  -  f_k (\mathbf{z}_{k}^c )    \\& \enskip \leq \frac{1}{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}} \Big( D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right)  \nonumber \\&\quad   +  \frac{G_f^2}{2 \sigma}  \sum_{i=0}^{\mathrm{it}(k)-1}   (\eta_k^{i})^2  +         M \Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c  \right) \Vert   \Big) \nonumber.
  \end{align}
\end{lem}
The proof of Lemma \ref{regret_betweeniT} can be found in Appendix \ref{proof: Lemma  regret_betweeniT}.
We are now in a position to prove the theorem.
\begin{proof}[Proof of Theorem~\ref{theorem_iTadap}]
The proof is similar to the proof of  \cite[Theorem 4]{hall2013dynamical} which derives a regret upper bound for the dynamic mirror descent in the context of online convex optimization. For ease of notation, we employ $\sum \eta_k^{i} $ to refer to the sum of all the step sizes used within the time instant $k$, i.e. to $\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}$.\\
By Lemma \ref{regret_betweeniT}, (\ref{result: regret_iTasap}) holds true.
Summing  (\ref{result: regret_iTasap})  over $k~=~1,\cdots,T$ yields
\begin{align}
\label{thm: regret_iTadapPr}
R(T) &= \sum_{k=1}^{T} \min_{0 \leq i \leq \mathrm{it}(k)} f_k (   \mathbf{\hat{z}}_k^{i} )  - \sum_{k=1}^{T}  f_k (\mathbf{z}_{k}^c   )    \\
& \leq \sum_{k=1}^{T} \frac{1}{\sum\eta_k^{i}} \Big(D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right)  \nonumber \\&    \qquad \qquad    +  \frac{G_f^2}{2 \sigma}  \sum  (\eta_k^{i})^2  +         M  \Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c  \right) \Vert   \Big) \nonumber.
\end{align}
Using~\eqref{thm: non-incr sequences}, i.e. the fact that $\sum\eta_{k+1}^{i} \leq \sum\eta_k^{i}$, we have
\begin{align}
\label{sumDiffBreg}
&\sum_{k=1}^{T} \frac{1}{\sum\eta_k^{i}} \, \left( D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right) \right)  \\
&\quad= \frac{D_\psi \left(   \mathbf{z}_{1}^c  , \mathbf{\hat{z}}^0_{1} \right)}{\sum\eta_{1}^{i}}  -\frac{D_\psi \left(  \mathbf{z}_{T+1}^c ,  \mathbf{\hat{z}}^0_{T+1} \right)}{\sum\eta_{T}^{i}} \nonumber \\ &\qquad+ D_\psi \left(   \mathbf{z}_{2}^c  ,  \mathbf{\hat{z}}^0_{2} \right)    \left( \frac{1}{\sum \eta_{2}^{i}} -  \frac{1}{\sum\eta_{1}^{i}} \right) + \cdots \nonumber\\& \qquad   +D_\psi \left( \mathbf{z}_{T}^c ,  \mathbf{\hat{z}}^0_{T} \right)   \left( \frac{1}{\sum\eta_{T}^{i}} -  \frac{1}{\sum\eta_{T-1}^{i}}  \right)      \nonumber \\
& \quad\leq \frac{D_{max}}{\sum\eta_{1}^{i}}   + D_{max}  \left( \sum_{k=1}^{T-1} \frac{1}{\sum\eta_{k+1}^{i}} -  \frac{1}{\sum\eta_{k}^{i}}  \right)  =  \frac{D_{max} }{\sum\eta_{T}^{i}}  .  \nonumber
\end{align}
Moreover,  since $\frac{1}{\sum\eta_{1}^{i}} \leq \cdots \leq \frac{1}{\sum\eta_T^{i}}$, we compute
\begin{align}
\sum_{k=1}^{T}  \frac{M }{\sum\eta_k^{i}}  & \left\Vert  \mathbf{z}_{k+1}^c \!  - \!  \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert  \leq \frac{M }{\sum\eta_T^{i}}     \sum_{k=1}^{T} \left\Vert  \mathbf{z}_{k+1}^c \!  - \!  \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert  .
\end{align}
 Hence, substituting the latter  bounds into (\ref{thm: regret_iTadapPr}) yields
\begin{align}
R(T)   \leq    \frac{D_{max}}{\sum \eta_{T}^{i}} &+ \frac{   G_f^2 }{2  \sigma  }\sum_{k=1}^{T}    \frac{\sum    (\eta_k^{i})^2  }{\sum\eta_k^{i}}   \\
 &   +   \frac{ M }{\sum\eta_T^{i}} \sum_{k=1}^{T} \left\Vert   \mathbf{z}_{k+1}^c  -  \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert, \nonumber
\end{align}
finishing the proof.
\end{proof}
Note that condition (\ref{BregDistanceNonneg}) can be  satisfied if we choose, for instance, the quadratic Bregman distance (\ref{quadBregm}) with a  weight matrix $P\in \mathbb{S}_{+\!+}^n$  that fulfills (\ref{LMIBregman}).
We discuss in the following an important implication  of Theorem \ref{theorem_iTadap}. If we execute a single iteration per time instant, i.e.,    set $\mathrm{it}(k)=1$ for all $k> 0$, we get $ \sum_{i=0}^{\mathrm{it}(k)-1} \eta_k^i = \eta_k^0 \eqqcolon \eta_k$  in (\ref{regretGenBound}).  \rev{In this case, the condition \eqref{thm: non-incr sequences} on the step size becomes $\eta_{k+1} \leq \eta_k$ and the regret	bound \eqref{regretGenBound} is as follows}
 \begin{align}
 \label{regretBoundit1}
R(T)
&\leq \frac{D_{max}}{\eta_T} + \frac{   G_f^2 }{2  \sigma  }\sum_{k=1}^{T}  \eta_k    + \frac{ M}{\eta_T} \sum_{k=1}^{T} \left\Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert.
\end{align}
\rev{This regret bound is very similar to the bound derived for the dynamic mirror descent \cite{hall2013dynamical}.} Moreover, by choosing $\eta_k= \frac{1}{\sqrt{T}}$, Algorithm~\ref{alg: eta changes} with a single optimization iteration per time instant \rev{yields
\begin{align}
\hspace{-0.35cm}	R(T)  \!
	&\leq\!  \sqrt{T}\left(\!D_{\max} + \frac{   G_{\mathrm{f}}^2 }{2  \sigma  }   +  M \sum_{k=1}^{T} \left\Vert \mathbf{z}_{k+1}^{\mathrm{c}} - \Phi_k\left(\mathbf{z}_{k}^{\mathrm{c}} \right) \right\Vert\! \right)
\end{align}}
and achieves therefore a  regret bound $\mathcal{O}\big(\sqrt{T}(1+  C_{T})\big)$, \rev{where $C_T$ is defined in (\ref{compSeq}). Furthermore, if the comparator sequence is such that   $ 	C_{T}(\mathbf{z}_{1}^{\mathrm{c}},\cdots, \mathbf{z}_{T}^{\mathrm{c}})= \sum_{k=1}^{T}\left\Vert \mathbf{z}_{k+1}^{\mathrm{c}} - \Phi_k\left(\mathbf{z}_{k}^{\mathrm{c}} \right) \right\Vert =~0$, then  Algorithm \ref{alg: eta changes} achieves in this case the desired regret bound $\mathcal{O}(\sqrt{T})$ and the average regret $R(T)/T$   tends to zero when $T$ goes to infinity. }

In our second main result, we specify conditions under which Algorithm~\ref{alg: eta changes} attains the regret bound $\mathcal{O}\big(\sqrt{T}(1+  C_{T})\big)$  as well as GES of the estimation error.
\begin{theorem}
\label{theorem_stab_regret}
Consider  Algorithm \ref{alg: eta changes} with $  \mathrm{j}(k)= \mathrm{it}(k) $   and any comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace $ with $   \mathbf{z}_{k}^c  \in \mathcal{S}_k$.  Let Assumptions  \ref{ass: S closed}-\ref{ass: Bregman} hold true.  Suppose that the Bregman distance $D_\psi$ satisfies
 \begin{align}
 \label{BregmaniTvar}
D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})    \leq  - c \, \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2
\end{align}
 and that $\mathrm{it}(k+1) \leq \mathrm{it}(k)$. Let
\begin{align}
\label{StepiTvar}
\eta_k^{i} =  \frac{\sigma }{L_f} \frac{1}{\,\sqrt{k}},
\end{align}
 for all $i=0,\dots, \mathrm{it}(k)-1$ and $k> 0$. Then,  the estimation error is GES and we have that
 \begin{align}
 \label{RegretiTvar}
R(T)    \leq \frac{\sqrt{T}}{\mathrm{it}(T)} \frac{ L_f }{\sigma} \Big(&  D_{max}    +    M      \sum_{k=1}^{T} \left\Vert  \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right)\right\Vert \Big).
\end{align}
\end{theorem}
The proof of this result relies on the next lemma.
\begin{lem}
\label{regret_betweeniT_eta}
Consider  Algorithm \ref{alg: eta changes} with $  \mathrm{j}(k)= \mathrm{it}(k) $   and any comparator sequence  $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace $ with $   \mathbf{z}_{k}^c  \in \mathcal{S}_k$.  Let Assumptions  \ref{ass: S closed}-\ref{ass: Bregman} hold true. If we choose the step size
 \begin{align}
\eta_k^{i} =  \frac{\sigma }{L_f} \frac{1}{\,\sqrt{k}},
\end{align}
then for a given iteration step $i$ and time $k>0$, we have that
\begin{align}
\label{result: regret_betweeniT_eta}
 \hspace{-0.3cm} \eta_k^i \left( f_k \left(\mathbf{\hat{z}}_{k}^{i+1}   \right) \! - \!  f_k(\mathbf{z}_{k}^c) \right) \leq     D_\psi \big(\mathbf{z}_{k}^c,\mathbf{\hat{z}}_{k}^i\big) \!    -    \!    D_\psi \big(\mathbf{z}_{k}^c, \mathbf{\hat{z}}_{k}^{i+1} \big)   .
\end{align}
Moreover, if we choose the Bregman distance $D_\psi$ such that
 \begin{align}
 \label{Dcontadap_eta}
D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})    \leq 0,
\end{align}
then
 \begin{align}
 \label{result: regret_iTasap_eta}
&   \min_{0 \leq i \leq \mathrm{it}(k)} f_k (  \mathbf{\hat{z}}_k^{i} )  -  f_k (\mathbf{z}_{k}^c )    \\& \quad\leq \frac{1}{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}} \Big( D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right)  \nonumber \\&  \hspace{3cm}+      \!  M \Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c  \right) \Vert   \Big) \nonumber.
  \end{align}
\end{lem}
The proof of Lemma \ref{regret_betweeniT_eta} can be found in Appendix \ref{proof: Lemma  regret_betweeniT_eta}.
We are now in a position to prove  Theorem~\ref{theorem_stab_regret}.
\begin{proof}[Proof of Theorem~\ref{theorem_stab_regret}]
GES of the estimation error follows, since  $\eta_k^{i}$ in (\ref{StepiTvar}) satisfies  (\ref{stepSizeadap}), i.e.  $\eta_k^{i} \leq \frac{\sigma}{L_f}$.
Note that, by Lemma \ref{regret_betweeniT_eta}, i.e. (\ref{result: regret_iTasap_eta}),
\begin{align}
R(T) &= \sum_{k=1}^{T} \min_{0 \leq i \leq \mathrm{it}(k) } f_k (   \mathbf{\hat{z}}_k^{i} )  - \sum_{k=1}^{T}  f_k (\mathbf{z}_{k}^c   )    \\
& \leq \sum_{k=1}^{T} \frac{1}{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}} \Big(D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right)  \nonumber \\&  \hspace{3.2cm} +        M \Vert \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c  \right) \Vert   \Big) \nonumber.
\end{align}
Since $\mathrm{it}(k+1) \leq \mathrm{it}(k)$,  we have that
\begin{align}
\label{StepSizeIneq}
\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}   =  \frac{\sigma}{L_f} \frac{\mathrm{it}(k)}{\sqrt{k}} & \geq  \frac{\sigma}{L_f} \frac{\mathrm{it}(k+1)}{\sqrt{k+1}} = \sum_{i=0}^{\mathrm{it}(k+1)-1}\eta_{k+1}^{i}.
\end{align}
Hence,~\eqref{thm: non-incr sequences} holds and as a consequence, we can derive an upper bound, similar to~\eqref{sumDiffBreg}, to obtain
\begin{align}
\label{comb1}
&\sum_{k=1}^{T} \frac{1}{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}} \, \left( D_\psi \left(  \mathbf{z}_{k}^c , \mathbf{\hat{z}}_k^0 \right) - D_\psi \left( \mathbf{z}_{k+1}^c ,   \mathbf{\hat{z}}_{k+1}^0\right) \right)  \\& \leq  \frac{D_{max} }{\sum_{i=0}^{\mathrm{it}(T)-1}\eta_{T}^{i}} =   \frac{D_{max} L_f \sqrt{T}}{ \mathrm{it}(T) \sigma} .  \nonumber
\end{align}
Moreover, given (\ref{StepSizeIneq}), we have that
\begin{align}
\label{comb2}
\sum_{k=1}^{T} & \frac{M}{\sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}}    \left\Vert  \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert \\ & \leq \frac{M }{\sum_{i=0}^{\mathrm{it}(T)-1}\eta_T^{i}}     \sum_{k=1}^{T} \left\Vert  \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert \nonumber
\\ & =\frac{ML_f \sqrt{T} }{  \mathrm{it}(T) \sigma}     \sum_{k=1}^{T} \left\Vert  \mathbf{z}_{k+1}^c - \Phi_k\left(\mathbf{z}_{k}^c \right) \right\Vert \nonumber.
\end{align}
Combining (\ref{comb1}) and (\ref{comb2})  completes the proof.
\end{proof}
A direct consequence of Theorem \ref{theorem_stab_regret} is that fixing  the number of optimization iterations $\mathrm{it}(k)=\mathrm{it}(k+1) \eqqcolon \mathrm{it}$ \rev{and increasing $\mathrm{it}$ lead to a smaller regret bound. This allows for a trade-off between computational effort and performance}. In fact, if the comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace$ follows the dynamics described by the a priori estimate operator $\Phi_k$ closely, and if we let $ \mathrm{it} \rightarrow \infty$, then the bound in Theorem \ref{theorem_stab_regret} vanishes and we obtain an algorithm with zero regret, \rev{i.e., $\lim\limits_{\mathrm{it} \rightarrow \infty} R(T)  \rightarrow 0$.}
\\
We also remark that the condition $\mathrm{it}(k+1) \leq \mathrm{it}(k)$ requires that we employ a smaller or equal number of optimization iterations each time we receive a new measurement. This condition is in line with the intuitive observation that it is  preferable to execute more  iterations at the beginning of the pMHE iteration scheme,
since our regret measure is aggregated over time and thus memorizes initially  poor estimates.

\begin{table*}[!t]
	\caption{Summary of  results.  We employ the following notation for abbreviation:  $\Delta_{\Phi_k} D_\psi (\mathbf{z},\mathbf{\hat{z}})   \coloneqq D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})$ and $
		\sum_{i}\eta_k^{i}  \coloneqq \sum_{i=0}^{\mathrm{it}(k)-1}\eta_k^{i}$.}
	\label{Table: results}
	\begin{center}
		{\setlength{\extrarowheight}{4pt}
			\begin{tabular}{ l  l  l  l}
				\hline
				Theorem & Assumptions  & Step size &  Result \\ [1ex]
				\hline
				Thm. \ref{prop: Stabadap} &   \begin{tabular}{@{}l@{}}   A1 - A4       \\ $  \Delta_{\Phi_k} D_\psi (\mathbf{z},\mathbf{\hat{z}}) \leq  - c \, \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2   $\end{tabular}    & $ \eta_k^i \leq \frac{ \sigma }{L_f}$  &   Stability \\[3ex] \hline
				Thm. \ref{theorem_iTadap}    &    \begin{tabular}{@{}l@{}}   A1, A2, A4       \\ $  \Delta_{\Phi_k} D_\psi (\mathbf{z},\mathbf{\hat{z}}) \leq 0  $\end{tabular}  &  $ \sum\limits_{i}\eta_{k+1}^{i}   \leq \sum\limits_{i}\eta_k^{i}   $       & Regret: {$\!\begin{aligned}   R(T)
						\leq & \frac{D_{max}}{\sum_{i}\eta_{T}^{i}} + \frac{   G_f^2 }{2  \sigma  }\sum_{k=1}^{T}    \frac{\sum_{i}   (\eta_k^{i})^2  }{\sum_{i}\eta_k^{i}}      + \frac{M }{\sum_{i}\eta_T^{i}} C_T
					\end{aligned}$}  \\[3ex]    \hline
				Thm. \ref{theorem_stab_regret}  &    \begin{tabular}{@{}l@{}}   A1 - A4       \\  $  \Delta_{\Phi_k} D_\psi (\mathbf{z},\mathbf{\hat{z}}) \leq  - c \, \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2   $ \\ $      \mathrm{it}(k+1) \leq \mathrm{it}(k) $ \end{tabular} & $\eta_k^i= \frac{\sigma}{L_f} \frac{1}{\sqrt{k}}  $ &  Stability + Regret: {$\!\begin{aligned} R(T)
						&\leq \frac{\sqrt{T}}{ \mathrm{it}(T)}  \frac{ L_f}{\sigma } \Big(   D_{max}  +  M     C_T  \Big)
					\end{aligned}$}   \\[4ex]  \hline
				Thm. \ref{thm: constantReg}  &  \begin{tabular}{@{}l@{}}   A1 - A5     \\ $  \Delta_{\Phi_k} D_\psi (\mathbf{z},\mathbf{\hat{z}}) \leq  - c \, \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2   $\end{tabular}   &    ${  \eta_k^i }\leq { {\frac{\sigma }{L_f}}}  $  &  \begin{tabular}{@{}l@{}}   Stability + Regret: \\   {$\!\begin{aligned}
							R(T)   \leq  \frac{L_f}{2}\,  \frac{\alpha^2\,  \beta^2 }{1 -\beta^2  } \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2   +  \frac{L_f}{2}\,  \frac{ \alpha_c^2 \, \beta_c^2}{1 -\beta_c^2  } \Vert   \mathbf{z}_{0}-\mathbf{z}^c_0 \Vert^2
						\end{aligned}$} \end{tabular}    \\ [3ex]
				\hline
		\end{tabular}}
	\end{center}
\end{table*}
 \subsection{Regret with respect to exponentially stable comparator sequences}
 As we mentioned before, in general, there is no requirement that  the comparator sequence converges to the true state. This being said, it is reasonable to restrict the class of comparator sequences to sequences that converge exponentially fast to the true state.
    We study this case in this subsection by imposing  the following  additional assumption.
    \begin{ass}[Exponentially stable comparator sequence]  \label{convComp}   The comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace$ with initial guess $\mathbf{z}_{0}^c$ is generated from a state estimator that yields GES error dynamics. More specifically, there exists   positive constants $\alpha_c \geq 1$ and $0\leq \beta_c <1$ such that
\begin{align}
 \Vert \mathbf{z}_{k}  - \mathbf{z}_{k}^c \Vert \leq \alpha_c \enskip  \beta_c^{k} \enskip \Vert  \mathbf{z}_{0}  - \mathbf{z}_{0}^c \Vert
\end{align}
holds for each $0 <  k \leq T$.  Here, $\mathbf{z}_{k}^c = \begin{bmatrix}  x_{k-N}^c \\[0.1cm] \mathbf{\hat{w}}_{k}^c   \end{bmatrix}$.
    \end{ass}
    Notably, when the comparator sequence satisfies the exponential stability assumption, Algorithm~\ref{alg: eta changes} leads to constant  regret, as our next result shows.
 \begin{theorem}
 \label{thm: constantReg}
Consider  Algorithm \ref{alg: eta changes}  and let Assumptions  \ref{ass: S closed}-\ref{ass: Bregman} hold true. Suppose that a comparator sequence $  \left\lbrace  \mathbf{z}_{1}^c,   \mathbf{z}_{2}^c, \dots,   \mathbf{z}_{T}^c \right\rbrace  $  is generated from a GES  estimator with
initial guess $\mathbf{z}_{0}^c$, as in Assumption \ref{convComp}.
 If the Bregman distance $D_\psi$ satisfies
 \begin{align}
 \label{BreAss}
D_\psi(\Phi_k(\mathbf{z}), \Phi_k(\mathbf{\hat{z}})) - D_\psi(\mathbf{z},\mathbf{\hat{z}})  \leq  - c \Vert \mathbf{z} - \mathbf{\hat{z}}   \Vert^2,
\end{align}
for all $ \mathbf{z},\mathbf{\hat{z}} \in \mathbb{R}^{(N+1)n}$ and  $\eta_k^i \leq \frac{ \sigma }{L_f} $, then the estimation error is GES and
\begin{align}
R(T)  & \leq  \frac{L_f}{2}\,   \frac{\alpha^2\,  \beta^2 }{1 -\beta^2  } \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2  +      \frac{L_f}{2}\,  \frac{ \alpha_c^2 \, \beta_c^2}{1 -\beta_c^2  } \Vert   \mathbf{z}_{0}-\mathbf{z}^c_0 \Vert^2 ,
\end{align}
with  $ \beta \coloneqq \sqrt{ 1 - \frac{2c}{\gamma}} \in [0,1) $ and $\alpha \coloneqq {\sqrt{ \gamma / \sigma}}$.
\end{theorem}
\begin{proof}
In view of Theorem \ref{prop: Stabadap}, GES holds since the Lyapunov function $
 V\big(  \mathbf{z}_{k}, \mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}\big)  = D_\psi\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k}\big)$
 satisfies
\begin{align}
\Delta V &= V\big( \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}\big) - V\big(  \mathbf{z}_{k-1},\mathbf{\hat{z}}^{ \mathrm{j}(k-1)}_{k-1}\big)   \\& \leq -c \big\Vert  \mathbf{z}_{k-1}-\mathbf{\hat{z}}^{\mathrm{j}(k-1)}_{k-1} \big\Vert^2  \nonumber.
\end{align}
In particular, this implies based on (\ref{toreplace})  that
\begin{align}
 \label{decreaseIT}
 D_\psi\big(    \mathbf{z}_{k},\mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k}  \big) \leq \beta_e^{k} \, D_\psi\big( \mathbf{z}_{0},\mathbf{\bar{z}}_0\big),
\end{align}
where $\beta_e \coloneqq 1 - \frac{2c}{\gamma} \in [0,1)$.  Given that $D_\psi$ is strongly convex and strongly smooth, we have that
\begin{align}
\big\Vert  \mathbf{z}_{k} -\mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}     \big\Vert^2
& \leq \frac{2 }{\sigma}\, \beta_e^{k} \, D_\psi\big(    \mathbf{z}_{0},\mathbf{\bar{z}}_0  \big) \leq \frac{\gamma}{\sigma}\, \beta_e^{k} \,  \big\Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0   \big\Vert^2.
\end{align}
With $\beta \coloneqq \sqrt{\beta_e}=\sqrt{1-2c/\gamma} \in [0,1)$ and  $\alpha \coloneqq{\sqrt{ \gamma / \sigma}} \geq 1$, we obtain that
\begin{align}
\label{lemTh4result}
\big\Vert  \mathbf{z}_{k} -\mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}     \big\Vert
& \leq \alpha \,\beta^{k} \, \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert.
\end{align}
The regret can be upper bounded as follows
\begin{align}
R(T) &= \sum_{k=1}^{T} \quad \min_{0 \leq i \leq \mathrm{it}(k) } f_k (  \mathbf{\hat{z}}^{i}_{k} ) - \sum_{k=1}^{T}  \,  f_k (   \mathbf{z}_{k}^c ) \\
 &\leq  \sum_{k=1}^{T} f_k  \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big)  - \sum_{k=1}^{T}  \,  f_k \big( \mathbf{z}_{k}^c \big). \nonumber
\end{align}
Furthermore,
\begin{align}
\label{fDiff}
    f_k  \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big) \! - \!    f_k \big( \mathbf{z}_{k}^c \big) &=  f_k  \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big)\! - \! f_k  \big( \mathbf{z}_{k}   \big)  +  f_k  \big( \mathbf{z}_{k}   \big) \! -  \!  f_k \big( \mathbf{z}_{k}^c \big)\nonumber \\
     & \leq  \big\vert  f_k  \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big) - f_k  \big( \mathbf{z}_{k}   \big)  \big\vert \nonumber  \\& \hspace{1.5cm}  +  \big\vert     f_k \big( \mathbf{z}_{k}^c \big) -  f_k  \big( \mathbf{z}_{k}   \big) \big\vert.
\end{align}
By Assumption  \ref{ass: f strngSmooth}, we have that for any  $\mathbf{z} \in \mathbb{R}^{(N+1)n}$
\begin{align}
\label{lipTrue}
 f_k ( \mathbf{z}   )  \leq  f_k ( \mathbf{z}_{k}   ) &+\nabla f_k  ( \mathbf{z}_{k}    )^\top   ( \mathbf{z} -\mathbf{z}_{k} )     + \frac{L_f}{2}  \Vert  \mathbf{z}_{k} - \mathbf{z}  \Vert^2.
\end{align}
Since $f_k$ achieves its minimal value at $ \mathbf{z}_{k} $ by Assumption \ref{ass: f convex}, $\nabla f_k \big( \mathbf{z}_{k}   \big) = 0$ and we obtain in (\ref{lipTrue}) for $\mathbf{z}=\mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}  $
\begin{align}
0 \leq f_k \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big) -  f_k \big( \mathbf{z}_{k}   \big)  \leq \frac{L_f}{2} \big\Vert  \mathbf{z}_{k} -  \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big\Vert ^2.
\end{align}
Similarly, we have for $\mathbf{z}= \mathbf{z}_{k}^c$    in (\ref{lipTrue})
\begin{align}
0 \leq f_k \big(\mathbf{z}_{k}^c   \big) -  f_k \big( \mathbf{z}_{k}   \big)  \leq \frac{L_f}{2} \big\Vert  \mathbf{z}_{k} - \mathbf{z}_{k}^c   \big\Vert ^2.
\end{align}
Substituting the latter two inequalities into (\ref{fDiff}) yields
\begin{align}
 f_k  \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big)  -     f_k \big( \mathbf{z}_{k}^c \big) \leq  \frac{L_f}{2} \big\Vert \mathbf{z}_{k} -  \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k}   \big\Vert ^2 +\frac{L_f}{2} \big\Vert  \mathbf{z}_{k} - \mathbf{z}_{k}^c   \big\Vert ^2.
\end{align}
By Assumption \ref{convComp} and (\ref{lemTh4result}), we obtain
\begin{align}
f_k \big( \mathbf{\hat{z}}^{\mathrm{j}(k )}_{k} \big) \! - \! f_k  \big( \mathbf{z}_{k}^c  \big) &    \leq \frac{L_f}{2} \,  \alpha^2 \,\beta^{2k} \, \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2 \\& \hspace{1cm} +  \frac{L_f}{2} \,  \alpha_c^2 \enskip  \beta_c^{2k} \enskip \Vert  \mathbf{z}_{0}  - \mathbf{z}_{0}^c \Vert^2  \nonumber.
\end{align}

Hence,
\begin{align}
\label{regretKappa}
\hspace{-0.2cm} R(T)  & \!\leq \sum_{k=1}^{T} \!   \frac{L_f}{2}\, \alpha^2 \,\beta^{2k} \, \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2  \! + \frac{L_f}{2}  \, \alpha_c^2 \enskip  \beta_c^{2k} \enskip \Vert  \mathbf{z}_{0}  - \mathbf{z}_{0}^c \Vert^2  .
\end{align}
Since  $ \beta \in [0,1)$, $ \beta^2 \in [0,1)$   and we have
\begin{align}
\sum_{k=1}^{T}  (\beta^2)^k = \frac{\beta^2- \beta^{2(T+1)}  }{1 -\beta^2  } \leq \frac{\beta^2 }{1 -\beta^2  }.
\end{align}
Therefore, it holds that
\begin{align}
  \sum_{k=1}^{T}  \frac{L_f}{2}\, \alpha^2 \,\beta^{2k} \, \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2  &\leq   \frac{L_f}{2}  \Vert   \mathbf{z}_{0}-\mathbf{\bar{z}}_0 \Vert^2 \frac{ \alpha^2\,\beta^2 }{1 -\beta^2 }.
\end{align}
By carrying out a similar analysis for the second sum in (\ref{regretKappa}), the desired regret upper bound can be obtained.
\end{proof}
We summarize the obtained results of the paper in Table~\ref{Table: results}.


TITLE: Is it possible for the Higgs Field strength, to increase with time?
QUESTION [0 upvotes]: Magnetic fields are created when an electric current flows: the greater the current, the stronger the magnetic field.
What influences could affect the Higgs Field?
If the Higgs field grew in strength, how might this effect the mass of a particle or particles?
The big question I'm asking, is the universe really expanding?  Could the observed redshift from distant galaxies be something, far less complicated?

REPLY [2 votes]: No. To make a long story short, if the Higgs field changed its coupling to particles with time then particles in the distant past would have different masses. This would mean atomic spectra of distant galaxies would has differences from spectra now here on Earth. No such change is observed.

REPLY [1 votes]: A time dependent coupling would mean that this coupling is in fact a field in its own right. This field would correspond to some new particle that would need to be very heavy, otherwise it would have been detected in experiments directly or indirectly by modifying the way the known standard model particles interact with each other . But if the particle associated with this field is very heavy, then the coupling would be frozen to some fixed value.


TITLE: How to rewrite $x-y=\frac{x}{y}$ so that it become $y=$ (something...)?
QUESTION [0 upvotes]: For example, $x+y=x\times y$ is easy to express as $y=\frac{x}{x-1}$, how about $x-y=\frac{x}{y}$?
I tried multiply both sides by $y$ and become
$y^2-xy+x=0$
but up to this step I don't know how to continue, can anyone help?

REPLY [0 votes]: It cannot be done, because, as you correctly noticed, the expression (if $y\neq 0$) is equivalent to the expression
$$y^2 - xy + x = 0$$
This expression can have, for a fixed value of $x$, two solutions, one solution, or even no real solution.
For example, if $x=1$, then there is no real value of $y$ that satisfies the equality, but if $x=-1$, there are two such values of $y$.


TITLE: variance tends to zero implies boundedness in probability
QUESTION [2 upvotes]: Given a sequence of random variables $X_n$ with $Var(X_n) \to 0$ as $n\to \infty$.
Does ist follow that $X_n$ is bounded in probability, i.e., $X_n = O_P(1)$?

REPLY [2 votes]: No. Take $X_n=n$ for all $n$ for a counterexample. However if you assume that $EX_n=0$ for all $n$ the result is true and it follows by Chebychev's inequality.

REPLY [2 votes]: This is true if the means of $\{X_n\}$ are uniformly bounded - this is a consequence of Chebyshev's inequality. Let $\sigma_n$ denote the standard deviation of $X_n$. For any $\varepsilon > 0$, there exists $M^2 = \frac{1}{\varepsilon}$ such that
$$ \mathbb{P}\left( \lvert X_n - \mu_n \rvert  > M\sigma_n \right) \leq \frac{\mathbb{E}(X_n - \mu_n)^2}{M^2 \cdot \sigma^2_n} = \varepsilon$$
Otherwise, it is not true by the counterexample in the other answer.


TITLE: Average distance to roots of unity
QUESTION [2 upvotes]: Let $z$ be a number in the unit disc. I would like to know a lower bound of the form
$$\frac{1}{N}\sum_{k=1}^N|z-\omega^k|\geq |z|+c$$
when $\omega$ is a primitive $N$'th root and $N>3$, where $c$ is independent of $z$ and $N$. The lower bound $|z|$ follows from the triangle inequality.

REPLY [3 votes]: Such bound exists for certain $c>0$, but I do not know which $c$ is optimal.
Denote $$f_n(z):=\frac{1}{n}\sum_{k=1}^n|z-\omega^k|,$$
then $f$ is 1-Lip as the average of 1-Lip functions.
Denote $y=z/|z|$ (or $y=1$ if $z=0$), then $|y|=1$, $|z-y|=1-|z|$ and $f_n(z)-|z|\geqslant f_n(y)-|z-y|-|z|=f_n(y)-|y|$, thus it suffices to consider $z$ with $|z|=1$. For such values of $z$ our sum is the integral sum for $\frac1{2\pi}\int_0^{2\pi}|1-e^{it}|dt=\frac4{\pi}>1$. Therefore for any fixed $c_0\in (0,4/\pi-1)$ the inequality $f_n(z)\geqslant 1+c_0$ holds whenever $|z|=1$ and $n$ is large enough. For finitely many small values of $n$ we note that $f_n(z)>1$ for all $z$ with $|z|=1$ by triangle inequality, and by compactness there exists certain $c_1>0$ such that $f_n(z)>1+c_1$ for all $z$ with $|z|=1$ and all these $n$. Then $c=\min(c_0,c_1)$ works.


TITLE: Distribution of prime numbers. Can one find all prime numbers?
QUESTION [3 upvotes]: I want to know if it is possible to find a formula that gives all the prime numbers? or can one find the distribution of prime numbers?
I know that there is a set of ongoing research on prime numbers. I know that there is already lot of results in prime numbers, the gap between primes, a lot of theorems starting from Euclid's one. My question is simple: Is it possible for someone to find explicit formula that gives all prime numbers (explicit function $f(x)$ is a prime for any natural number $x$)? or that gives the distribution of them?
If it is not possible. Suppose that someone prove that factoring is an easy problem. Still not possible?
I mean, is there a theorem, logic, something that says that it is impossible to get all the primes or that all primes can be calculated based on condition $1$, $2$, $\dotsc$?
I hope that I make my question clear. I hope that it is a valid question.
Thank you very much for your help. Any reference or ideas would be appreciated.

REPLY [0 votes]: Asymptotically, the probability of prime is $1/\log(n)$. As n increases, a random integer n becomes less and less likely to be a prime.
Intuitively, in approximate terms, $1/2$ of numbers are eliminated as multiples of $2$; $1/3$ eliminated as multiples of $3$; $1/4$ eliminated as multiples of $4$... So the probability is $(1-1/2) * (1-1/3) * (1-1/4) * (1-1/5)$... for any prime less than $n$.


TITLE: $S$ be a collection of subsets of $\{1,...,100\}$ ; any two sets in $S$ has non-empty intersection , what is the maximum possible value of $|S|$?
QUESTION [12 upvotes]: Let $S$ be a collection of subsets of $\{1,2,...,100\}$ such that any two sets in $S$ has non-empty intersection . Then what is the maximum possible cardinality of $S$ ?

REPLY [11 votes]: Consider the collection $S_1$ of all subsets that contain the number $1.$ It satisfies the condition and its cardinality is $2^{99}.$
On the other hand let $S$ be such a collection and consider the partition into two subcollections $S_y$ and $S_n$ of sets according to whether they do, or do not, contain the number $1.$
$S_n$ has at most $2^{99}$ elements because those elements are subsets of $\{2,\ldots,100\}.$
But $S_y$ cannot contain the complement of any set in $S_n$, which rules out exactly $2^{99}-|S_n|$ possibilities.
Therefore $S=S_y\cup S_n$ has at most $2^{99}$ elements.


TITLE: How can one think intuitively about (linear) algebra?
QUESTION [4 upvotes]: This may sound like a philosophical question, but it’s intended as a very practical question.
Broadly, I have two ways of doing math:

blindly following definitions and shifting equations around.
having a deep understanding of the meaning of terms and why theorems hold, allowing me to see immediately why a conjecture must hold, or what the solution to a problem will look like. I may not even need to do any formal derivations, and if I do, they flow immedaitely from my intuitive understanding.

With respect to linear algebra (and abstract algebra, though this question focuses more on linear algebra), I am to a large extent in (1), and I want to get to (2).
Mainly due to watching a 3blue1brown series, I have an intuitive understanding of

what an eigenvalue and eigenvector is geometrically
that a matrix represents geometrically, a linear operation on e.g. a Euclidean vector space
other basic stuff

But when it comes to other concepts, whenever I use them I am really just shifting equations around mindlessly:

matrices can be decomposed into a diagonal matrix and two other matrices that are inverses of eachother
what a quadratic form represents geometrically
that symmetric positive definite matrices have symmetric square roots, but positive definite matrices don’t necessarily have symmetric square roots.
that symmetric matrices have real eigenvalues
The sum of eigenvalues of a matrix are equal to its trace, and the product of eigenvalues equal to the determinant.
etc etc

Alot of these things I can prove by mindlessly sequencing equations like a computer-based theorem prover, but I cannot immediately see why they are or are not true.
What can I do >>practically<< to gain this type of intuition quickly about lots of these linear algebra questions?
I feel like just doing more theorems, and solving more problems, won’t help. Are there good books that treat these things intuitively? Or a collection of methods to use?
(Note that I am entirely self-taught in this and have no formal math degree).

REPLY [0 votes]: You ask some good questions - basically, you want to express things in a coordinate independent way. The following books
Linear Algebra Done Right by Axler and
Linear Algebra Done Wrong by Sergei Treil
both try to emphasize linear transformations point of view and that matrices arise when coordinates are chosen, although I don’t know if they answer
For example SVD saying
$A=U\Sigma V^T$
intuitively to me can be interpreted to that after rotation of domain and codomain, every linear transformation is scaling appropriate axis by the singular values. Orthogonal diagonalization of symmetric matrix has a similar interpretation.


TITLE: How does quantization solve UV catastrophe in black body radiation? What would happen if there was no Planck constant $h$?
QUESTION [2 upvotes]: Planck's Law is $$I(\nu,T)=\frac{8\pi\nu^3}{c^2}\cdot\frac{1}{e^{h\nu/kT}−1}$$
This solves the UV catastrophe. For higher frequencies, intensity goes to zero.
It does so because of $e^\nu$ not because there is a $h$ constant. If we remove $h$ parameter from the equation, it still goes to zero for higher frequencies. Right?
So why is "UV catastrophe is solved by quantization" said?
Note: I'm not saying if h = 0. I'm saying if there was no h constant. Like this:
$$I(\nu,T)=\frac{8\pi\nu^3}{c^2}\cdot\frac{1}{e^{\nu/kT}−1}$$

REPLY [0 votes]: Putting aside the ridiculous attempt of user50322 for normalizing Physics Units System to make h=1. He still makes a point when he keeps nagging about Plank Law not being a discrete math equation.
(8π(ν^3)/c^2) / (Exp(hν/kT)-1) is a continuous function with a singularity when ν=0. It does not indicate just by itself the quantum nature of light. It may be said that it is the result of a probability distribution that makes unlikely that very high frequency photons be emitted by a hot black body.
The explanation user50322 is looking for is that :  For a large ν, a hν energy amount is  difficult to reach for the oscillators (atoms) of a black body at any given high Temperature T. In other words, the random disturbance commotion originated by the Temperature in the walls of the black body has a low probability of energizing any of its oscillators at at-least hν if ν is large, and if the oscillator is short of hv, no photon will be emitted (there the quantization of the damn thing), so just a few photons are emitted at a large frequency ν in comparison with a not so large frequency.
The black body walls will have very few regions where by chance the commotion accumulates energy that surpasses hν.


text:
\begin{document}

\title[A note on Lagrangian intersections and Legendrian Cobordism]{A note on Lagrangian intersections \\and Legendrian Cobordism.}

\author{Lara Simone Su\'arez}
\address{Ruhr-Universität Bochum, Fakultät für Mathematik, Universitätsstraße 150, 44801 Bochum, Germany}
\email{lara.SuarezLopez@rub.de}

\begin{abstract} Let $\Lambda, \Lambda'$ be a pair of closed Legendrian submanifolds in a closed contact manifold $(Y, \xi = Ker(\alpha))$ related by a Legendrian cobordism $W\subset (\C\times Y, \tilde{\xi}=Ker(-y \d dx +\alpha))$. In this note, we show that in the hypertight setting, if $\Lambda$ intersects a closed, weakly exact or monotone pre-Lagrangian $P\subset Y$ for reasons of Floer homology, then so does $\Lambda'$.
\end{abstract}
\maketitle

\section{Introduction}
Let $(Y,\xi)$ be a co-oriented closed contact manifold.
In this paper we consider pairs $(P,\Lambda)$ consisting of a closed Legendrian submanifold $\Lambda \subset Y$ and a closed pre-Lagrangian $P\subset Y$ (see Definition \ref{DefPreLag}). A usual question in symplectic topology is that of the displaceability of Lagrangian submanifolds by Hamiltonian isotopy. In contact topology, this question can be interpreted as the search for pairs $(P, \Lambda)$ with the so called \textit{intersection property} as defined by Eliashberg-Polterovich in \cite{ElPo}.
A pair $(P,\Lambda)$ of $(Y,\xi)$ has \textit{the intersection property}, if for every contactomorphism $\phi \in Cont_{0}(Y,\xi)$\footnote{The $0$ here stands for the connected component of the identity.} the intersection $P\cap \phi(\Lambda)$ is non-empty.
A tool to find such pairs was introduced by Eliashberg-Hofer-Salamon in \cite{EHS}. It is a Floer homology group $HF(P,\Lambda;\Z_2)$ for pairs $(P, \Lambda)$, that is invariant under Legendrian isotopy. In some special cases, this group is isomorphic to the homology of the Legendrian $\Lambda$. This is the case in the following examples from \cite{EHS}, which are the first examples of pairs with the intersection property:
\begin{enumerate}
    \item Let $X$ be a closed manifold and $P^{+}(T^*X)$ the space of co-oriented contact elements with the canonical contact structure. If there is a non-singular closed one form $\beta$ on $X$ then there is a pre-Lagrangian $P$ associated to $ \text{graph}(\beta)$. If moreover, $P$ is foliated by closed Legendrians and $\Lambda$ is any Legendrian leaf, then the pair $(P, \Lambda)$ has the intersection property.
    \item Let $(M,\omega)$ be a closed symplectic manifold with $[\omega]\in H^{2}(M;\Z)$. In a prequantization space $QM$ of $(M,\omega)$, if there is a closed Lagrangian submanifold $L\subset(M,\omega)$ that satisfies the Bohr-Sommerfeld condition and $\pi_2(M,L)=0$ then the corresponding pre-Lagrangian $P$ in $QM$ and a flat Legendrian lift $\Lambda$ of $L$ is a pair with the intersection property. This last example was independently  discovered by Ono \cite{On}.
\end{enumerate}

In \cite{ElPo} Eliashberg-Polterovich also defined the \textit{stable} intersection property of a pair, meaning that in the stabilized setting $(T^*S^1\times Y, Ker(rdt +\alpha))$ the pair $(S^1 \times \{0\}\times P, S^1\times \{0\}\times \Lambda)$ has the intersection property. They showed that the previous examples have the stable intersection property.
The (stable) intersection property is related to the orderability of the contact manifold. In fact in \cite[Theorem 2.3.A]{ElPo} they proved that having a pair with this property implies that the manifold is orderable.

From another perspective, we can say that in the previous examples, the stabilization preserves the intersection property. In the same way, in this note we remark, in particular for the above examples, that the intersection property is preserved by Legendrian cobordism with the following property: there is a contact form with no contractible Reeb orbits or chords with boundary on the cobordism. This is the \textit{hypertight} property defined below in Definition 2.

The notion of Legendrian cobordism was introduced by Arnol'd (\cite{Ar1}, \cite{Ar2}) who computed the immersed Legendrian cobordism group (oriented and not-oriented) when the immersed Legendrian has dimension $n=1$, the cases $n\geq 2$ were computed by Audin \cite{Aud} and Eliashberg \cite{El} independently.  Afterwards, related works on Legendrian cobordisms where done by Ferrand \cite{Fe} and more recently by Limouzineau \cite{Lim}.

An embedded Legendrian cobordism in $J^1(\R\times N)$, projects to an immersed exact Lagrangian cobordism in $T^*N$. Biran-Cornea \cite{BiCo} showed that monotone embedded Lagrangian cobordism preserves Floer-theoretical Lagrangian invariants after Chekanov \cite{Che} showed how these preserve certain counts of Maslov two disks.

In general, embedded Legendrian cobordism does not preserve holomorphic curves type invariants. This is the case, for instance of the linearized contact homology, a Legendrian analogue of the Lagrangian Floer homology. In $(\R^3,dz-pdq)$ for example, it follows from the work of Arnol'd that two Legendrian knots are oriented Legendrian cobordant if and only if they have the same Maslov index. Hence any two knots with same Maslov index but different linearized contact homology are still Legendrian cobordant.

However, under additional restrictions, we show that Legendrian cobordism does preserve the Floer homology group of Eliashberg-Hofer-Salamon. More precisely we prove the following:

\begin{theorem}
Let $(Y,\xi)$ be a closed hypertight contact manifold and $\Lambda, \Lambda'\subset Y$ a pair of hypertight Legendrian submanifolds related by a connected hypertight Legendrian cobordism $(W;\Lambda, \Lambda')\subset (\C \times Y,\tilde{\xi})$.  If $P\subset Y$ is a closed weakly exact or monotone  with $N_P \geq 2$ pre-Lagrangian submanifold
then $$HF(P,\Lambda) \cong  HF(P,\Lambda').$$
\end{theorem}

The proof of Theorem 1 is an adaptation to the cobordism setting of \cite[Theorem 3.7.3]{EHS}. We define a Floer complex for the Lagrangian lift of a Legendrian cobordism $(W;\Lambda,\Lambda')$ and a suitable cylindrical Lagrangian $\tilde{P}$ obtained from $P$. We then observe that the homology of this complex is isomorphic to the homology of the Floer complex of the Legendrian boundary $\Lambda$ (or $\Lambda'$) and the pre-Lagrangian $P$. This proof uses a similar strategy to the one used by Biran-Cornea \cite{BiCo} to show that monotone Lagrangian cobordism preserves Floer homology. Combining Theorem 1 with \cite[Theorem 2.5.1-2.5.4]{EHS} (see section 2.2 Theorem 11) we get the following corollary.
\begin{corollary}
Under assumptions in Theorem 1, consider a pair $(P, (W;\Lambda, \Lambda'))$ where $P$ is weakly exact and $\Lambda \subset P$.  If moreover boundary homomorphism $\pi_{2}(Y,P)\to  \pi_1(P)$ is trivial, then if $\{\phi_t\}_{0\leq t\leq 1}$ is a contact isotopy such that $P \pitchfork \phi^1(\Lambda')$. Then  $$\#\phi_{1}(\Lambda') \cap P \geq  rank(H_*(\Lambda, \Z_2)).$$
\end{corollary}
\textit{Acknowledgements.}
I thank Egor Shelukhin for suggesting this project and helpful discussions. This research is supported by the Floer Centre of Geometry at Ruhr-University Bochum and is part of a project in the SFB/TRR 191 \textit{Symplectic Structures in Geometry, Algebra and Dynamics}, funded by the DFG.

\section{Setting}
Let $(Y,\xi)$ be a closed co-oriented contact $2n+1$-manifold. Denote by $\text{Cont}^{+}(\xi)$ the set of contact forms defining the same co-orientation on $\xi$.

For a choice of $\alpha\in\text{Cont}^{+}(\xi)$, the symplectic manifold $(S_{\alpha}(Y),\omega):=(\R\times Y, \dd(e^\theta \alpha))$ is called the \textit{symplectization} of $(Y, \alpha)$.

Given $\eta\in \text{Cont}^{+}(\xi)$, its \textit{Reeb vector field} is the unique vector field $R_{\eta}\in \Gamma(TY)$ satisfying the two equations: $$\iota_{R_{\eta}}\eta = 1,$$
$$\iota_{R_{\eta}}\dd\eta = 0.$$ Its associated flow is denoted by $\{\phi^t_{R_{\eta}}\}$ and it is called the \textit{Reeb flow}.

\begin{definition} A contact manifold $(Y, \xi)$ that admits a contact form with no contractible periodic Reeb orbits is called \textbf{hypertight}. Such a contact form is called a \textbf{hypertight contact form}. A Legendrian submanifold $\Lambda\subset Y$ for which there is a hypertight contact form such that any Reeb chord with boundary on $\Lambda$ represents a non-trivial class in $\pi_{1}(Y, \Lambda)$ is called a \textbf{hypertight Legendrian} submanifold.
\end{definition}
Some examples of hypertight contact manifolds are jet spaces, certain pre-quantization spaces and certain unit cotangent bundles, with their corresponding standard contact structures.

In this note \textbf{all} contact manifolds and Legendrians are assumed to be hypertight.

\begin{definition}\label{DefPreLag}A \textbf{pre-Lagrangian} is a $(n+1)$-dimensional submanifold $P\subset Y^{2n+1}$ for which there exists a contact form $\alpha \in Cont^{+}(\xi)$ such that $\dd(\alpha\vert_{P}) = 0$ i.e $\alpha\vert_{P}$ is closed.

\end{definition}
If there is a function $f:P \rightarrow \R$ such that $\alpha|_{P} = \dd f$ then $P$ is called a \textit{exact pre-Lagrangian} and $f$ is called \textit{contact potential} on $P$.
An exact Lagrangian lift $\hat{P}$ of an exact pre-Lagrangian is given by $$\hat{P}=\{0\}\times P\subset \R\times Y. $$
Note that $\hat{f}:\hat{P}\rightarrow \R$, $\hat{f}(0,p)=f(p)$ is a primitive for $e^{\theta}\alpha|_{\hat{P}}$.

A pre-Lagrangian  $P$ is called \textit{weakly exact} when $\dd \alpha|_{\pi_2(Y,P)}=0$ and \textit{monotone} if there is a positive constant $K$ such that for all $u\in \pi_2(Y,P)$ we have $$\int_{\partial u} \alpha = K \mu(u)$$ where $\mu$ denotes the Maslov class $\mu:\pi_2(Y,P)\to\Z$. The positive generator of the image of the homomorphism defined by $\mu$ is denoted $N_P$ and is called the minimal Maslov number of $P$.

\begin{example}Let $(Y,\xi) = (S(T^*X),\text{ Ker}(p\dd q|_{S(T^*X)}))$ where the right hand side is the unit cotangent bundle of $(X,g)$ with respect to some choice of a Riemannian metric $g$. Let $\eta$ be a nowhere vanishing closed 1-form. If $\Gamma_{\eta}\subset T^*X$ denotes the graph of $\eta$, then $\Gamma_{\eta/||\eta||} \subset S(T^*X)$ is a pre-Lagrangian for the contact form $||\eta||p\dd q$.
\end{example}
\begin{example}Let $(Y,\xi) = QX$ be the prequantization of a symplectic manifold $(X,\omega)$. Topologically $Y$ is an $S^1$-principal bundle over $X$ with projection map $p:Y\rightarrow X$. Given a Lagrangian submanifold $L\subset X$ its lift  $p^{-1}(L)\subset(Y,\xi)$ is a pre-Lagrangian.
\end{example}

\subsection{Legendrian cobordism.}
Let $(x,y)$ denote coordinates on $\C$. Then $\tilde{\alpha}= -y\dd x + \alpha$ is a contact form on $\C\times Y$. Denote the resulting contact manifold by  $$(\tilde{Y}, \tilde{\xi})= (\C \times Y, Ker(\tilde{\alpha})).$$ Let $\pi_{\C}: \C\times Y \rightarrow \C$ denote the projection map. Given $\Lambda, \Lambda'\subset Y$ two closed Legendrian submanifolds, in \cite{Ar1} and \cite{Ar2} Arnol'd introduced the notion of Legendrian cobordism on which the following definition is based.
\begin{definition}{A \textbf{Legendrian cobordism} $(W; \Lambda, \Lambda')$ is an embedded Legendrian submanifold $W\subset (\tilde{Y},\tilde{\xi})$ such that for some $0 < \epsilon \in \R$  and $R\geq 1$ we have that $$W \cap \pi_{\C}^{-1}([\epsilon, R-\epsilon] \times \R)$$ is a smooth compact manifold with boundary $\Lambda \sqcup \Lambda'$ and $$W \cap \pi_{\C}^{-1}(\C \setminus ([\epsilon, R-\epsilon] \times \R)) = (-\infty, \epsilon)\times \{0\} \times \Lambda\sqcup (R-\epsilon, \infty)\times \{0\} \times \Lambda'.$$}
\end{definition}

\begin{example}(Legendrian suspension)\cite{ElPo} Let $H: \R \times Y \rightarrow \R$ be a contact Hamiltonian with $H_{t}\equiv0$ for $t\leq 0$ and $t\geq 1$. The associated contact vector field $X_{H}$ is given by the two conditions: $\iota_{X_{H}}\alpha = H$ and $ \iota_{X_{H}}\dd \alpha = -\dd H + (\iota_{R_{\alpha}}\dd H )\alpha$.
Denote by $\{\psi^{t}\}$  the contact isotopy associated to $X_{H}$. Let $\Lambda \subset M$ be a compact Legendrian.
The map:
\begin{align*}
\Phi: \R \times\Lambda  &\rightarrow \C \times Y \\ (t,p) &\mapsto (t, H(t,\psi^{t}(p)), \psi^{t}(p)),
\end{align*}
is a Legendrian embedding into $(\C \times M, Ker(\tilde{\alpha}))$ defining a Legendrian cobordism $$(\Phi(\R\times \Lambda);\Lambda, \psi^{1}(\Lambda)).$$
\end{example}
\begin{remark}Any Legendrian isotopy  defines a Legendrian cobordism given by the Legendrian suspension of a contact Hamiltonian generating the isotopy.
\end{remark}

\begin{example}The trace of surgery: Elementary Legendrian cobordisms can be constructed using the Lagrangian handle in Haug \cite{Hau} building on the work of Dimitroglou Rizell \cite{Di}. This construction produces an embedded Legendrian cobordism in $J^{1}(\R^{n+1})$.

The Legendrian $k$-handle: Consider the non compact Legendrian $W_{\epsilon, k}\subset J^{1}(\R^{n+1})$ given by $$W_{\epsilon, k}= \{(x_{0},\textbf{x}, \pm \dd F(x_{0},\textbf{x}), \pm F(x_{0}, \textbf{x}))\in J^{1}(\R^{n+1}) \hspace{0.2cm}\vert\hspace{0.2cm} (x_{0},\textbf{x}) \in \mathcal{U}\}$$ for $\textbf{x}= (x_{1}, ...,x_{n}) \in \R^{n}$ where $F(x_{0}, \textbf{x})= (f(x_{0}, \textbf{x}))^{\frac{3}{2}}$,  $$f(x_{0}, \textbf{x})=\sum \limits_{i=1}^{k} x_{i}^{2} -  \sum \limits_{i=k+1}^{n} x_{i}^{2} + \sigma(\sum\limits_{i=1}^{k} x_{i}^{2})\rho(x_{0}) -1$$
and $\mathcal{U}= \{(x_{0}, \textbf{x})\hspace{0.2cm}\vert\hspace{0.2cm} f(x_{0}, \textbf{x}) \geq 0\}$, where the functions $\sigma$ and $\rho$ look like:

\hspace{2cm}
\includegraphics[scale=0.5]{FunctionSigma.png}\hspace{2cm}
\includegraphics[scale=0.5]{FunctionRho.png}\\
In the case a Legendrian $\Lambda$ contains a $l$-sphere $S^l\subset \Lambda$ which bounds an isotropic $l+1$-disk $D^{l+1} \subset Y\setminus \Lambda$, compatible with the Legendrian in some sense made precise in \cite{Hau}, after surgery a new Legendrian is obtained, and an embedded Legendrian cobordism between the initial Legendrian and the one produced after the surgery exists.
\end{example}

\begin{example}Let $(M, \lambda)$ be a Liouville domain. The Legendrian lift of an immersed exact Lagrangian cobordism $(W;L_0, L_1) \subset (\C \times M, \dd (-y\dd x + \lambda))$ to the contactization of $\C\times M$, defined by $\C\times C(M,\lambda)=(\C\times M\times \R_z, -y\dd x + \lambda+ \dd z )$. More precisely, if $f:W \to \R$ is a potential for the Lagrangian $W$, the Lagrangian $\tilde{W}:=\{(w,f(w)) | w\in W\}$ is an embedded Legendrian cobordism in $\C \times C(M,\lambda)$.
\end{example}

\subsection{Previous results}

We denote by $HF(P,\Lambda;\Z_{2})$ the homology of the complex defined by Eliashberg-Hofer-Salamon in \cite{EHS}. In  \cite[Theorem 3.7.3]{EHS} they showed that in the hypertight setting, this homology group is well defined and invariant under compactly supported Hamiltonian isotopy.
Let $(Y,\xi)$ be as in Examples (1) or (2) in the introduction, namely, either (1) a sphere cotangent bundle of a compact manifold or (2) a prequantization space. Assume that the contact manifold and pre-Lagrangian submanifold satisfy the topological condition that the boundary map $\pi_2(Y,P)\to \pi_1(P)$ is trivial. In this setting, when the pair $(P,\Lambda)$ is either the graph of a non-zero closed form foliated by closed Legendrians and a Legendrian leaf of it in the first case, or the pre-Lagrangian lift of a Lagrangian satisfying the Bohr-Sommerfeld condition with the property that $\pi_2(Y,P)=0$ and a Legendrian lift of it, then the following theorem holds.
\begin{theorem}{\cite{EHS}[1995]\label{thm=EHS}
Let $\{\phi_t\}_{0\leq t\leq 1}$ be a contact isotopy and $\Lambda$ a Legendrian such that $P \pitchfork \phi^1(\Lambda)$. Then  $$\#\phi_{1}(\Lambda) \cap P \geq  rank(H_*(\Lambda, \Z_2)).$$
}
\end{theorem}
In the same direction Akaho \cite{Ak}, proved a version of the previous theorem replacing the hypertight condition by a small energy condition.
Results about displaceability of pre-Lagrangians can also be found in the work of Marinkovic-Pabiniak \cite{MaPa}.

\section{A Floer complex for the pair $(P, W)$.}
The version of Floer complex associated to the pair $(P,W)$, where $P \subset Y$ is a weakly exact or monotone pre-Lagrangian (with $N_P\geq 2$) and $(W,\Lambda, \Lambda')\subset \C\times Y$ is a Legendrian cobordism, is an adaptation to the cobordism setting (following Biran and Cornea in \cite{BiCo}) of the Floer complex as defined in \cite{EHS}.

Let $\tilde{\alpha} \in Cont^+(\tilde{\xi})$ be a contact form on $\C \times Y$ that can be written as $\tilde{\alpha}= -y\dd x+\alpha$ where $\alpha\in Cont^+(\xi)$. We assume that $\tilde{\alpha}$ satisfies:
\begin{itemize}

\item $P$ is a pre-Lagrangian for $\alpha$, i.e $d\alpha|_{P}=0$.
\item $W$ is hypertight for $\tilde{\alpha}$.
\end{itemize}
To the pair $(P,W)$ we associate the pair $(L_P,L_W)$ in $(S(\tilde{Y}), \tilde{\omega} =\dd (e^{\theta}\tilde{\alpha}))$, where $L_{P}=\{0\}\times \R\times\{0\}\times P$ denotes the Lagrangian lift of the pre-Lagrangian $\tilde{P}=\R\times\{0\}\times P \subset \C\times Y$ and $L_{W} = \R\times W$ is the Lagrangian lift of $W$.

\subsection{Choices}\label{chice}
The Floer complex will depend on the choice of triples $(H,f,J)$ where:
\begin{enumerate}
    \item Denote by $\pi_{\C}:\C \times Y\rightarrow \C$ the projection. Let us fix a compact set $B\subset \C$ of the form $[R_-,R_+] \times [R_-,R_+]$ for $R_{\pm}\in \R$ big enough, such that $\pi_{\C}(W) \cap \C\setminus B$ is $$(-\infty,R_-]\times \{0\} \cup [R_+, \infty)\times \{0\}.$$
    \item A Hamiltoninan $H:[0,1]\times S(\tilde{Y})\rightarrow \R $ compactly supported in $\R\times \pi^{-1}_{\C}(B)\subset S(\tilde{Y})$. We use the Hamiltonian flow of $H$ to perturb $L_P$ to make it transverse to $L_W$ on $\R\times \pi^{-1}_{\C}(B)\subset S(\tilde{Y})$.
    \item A smooth function $f:\C \rightarrow  \R$  with the property that
    $$f(x,y) = a_+ x + b_+ \text{ for } x<R_-  - \epsilon \text{ and }f(x,y) = a_- x + b_- \text{ for } x> R_+ + \epsilon$$ where $a_\pm, b_{\pm}\in \R$ and $\epsilon >0$. We consider the Hamiltonian $\tilde{f} = e^{\theta} (f\circ \pi_{\C})$ on $S(\tilde{Y})$. It is the Hamiltonian lift of the contact Hamiltonian $f\circ \pi_{\C}$ to $S(\tilde{Y})$.
    The corresponding Hamiltonian flow $\psi_{\tilde{f}}^t:S(\tilde{Y})\rightarrow S(\tilde{Y})$ is given by $$(\theta,x,y,p)\in \R\times \C\times Y \mapsto \psi_{\tilde{f}}^t(\theta,x,t,p)= (\theta,x,y+a_{\pm}t,\phi_{R_{\alpha}}^{a_{\pm}xt}(p)),$$
    for $(\theta,x,y,p)$ outside $\R\times B\times Y$.
    This Hamiltonian flow perturbs the cylindrical ends of $L_{P}$ in such a way that the time one map $\psi^{1}_{\tilde{f}}(L_{P})\cap L_W = \emptyset$ outside $\R\times B \times Y$. All this while keeping the contact form invariant at infinity.
    \item $J$ is an admissible $\tilde{\omega}$-compatible almost complex structure on $S(\tilde{Y})$. Admissible means a cylindrical and $\dd \tilde{\alpha}$-compatible almost complex structure for which $d\pi$ is $(J,j)$-holomorphic where $\pi: (S(\tilde{Y}), J)\to (\C,j)$ denotes the projection and $j$ denotes the complex structure on $\C$. We define admissible in more detail in the next section. \end{enumerate}

Let
$$\mathbf{\Lambda} = \{\sum_{k=0}^{\infty} a_k T^{\lambda_k} \hspace{0.2cm}|\hspace{0.2cm} a_k \in \Z_{2}, \lambda_k \in \R, \lim_{k\rightarrow\infty}\lambda_{k}=\infty\}. $$
The $\star$-Floer complex of the pair $(L_{P},L_W)$ is denoted by
\begin{equation}\label{eq:Floer complex}
CF_{\star}(L_P,L_W; H,f,J):= (\mathbf{\Lambda}\langle \hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H)\rangle, d_J).
\end{equation}
The set $\hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_{P}),L_W; H)$ is constructed as follows:

Consider the set $\mathcal{P}(\psi^{1}_{\tilde{f}}(L_P), L_W) := \{\gamma\in C^{0}([0,1];S(\tilde{Y})) \hspace{0.2cm}|\hspace{0.2cm} \gamma(0)\in \psi^{1}_{\tilde{f}}(L_P), \gamma(1)\in L_W\}$ of paths between $\psi^{1}_{\tilde{f}}(L_P)$ and $L_W$. For a fix $* \in \psi^{1}_{\tilde{f}}(L_P)\cap L_W$ denote by $\star=[*]\in \pi_{0}(\mathcal{P}(\psi^{1}_{\tilde{f}}(L_P), L_W))$ and let $\mathcal{P}_{\star}(\psi^{1}_{\tilde{f}}(L_P), L_W)$ be the connected component corresponding to the class $\star$. When $\psi^{1}_{\tilde{f}}(L_P)\cap L_W$ is not transverse, we use the Hamiltonian $H$. Denote by $$\mathcal{I}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H) := \{ x\in  \psi^1_H(\psi^{1}_{\tilde{f}}(L_P))\cap L_W \hspace{0.2cm}|\hspace{0.2cm} x\in \mathcal{P}_{\star}(\psi^{1}_H(\psi^{1}_{\tilde{f}}(L_P)), L_W)\}$$ the intersection points in the connected component of $\star$. Then

\begin{align*}
    &\hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H) :=\\
    &\{(x,\tilde{x}) \in \mathcal{I}_{\star}(\phi^{1}_{\tilde{f}}(L_P),L_W; H) \times C^0([0, 1],\mathcal{P}_{\star}\Big(\psi^{1}_H(\psi^{1}_{\tilde{f}}(L_P)), L_W\Big)) | \tilde{x}(0)= x, \tilde{x}(1)= * \}/\sim
\end{align*}

where $(x,\tilde{x})\sim (x',\tilde{x}')$ iff $x = x'$ and $\mu(\tilde{x}\#(\overline{\tilde{x}'}))=0$ where $\mu$ denotes the Maslov index and $\overline{\tilde{x}'}$ denotes the same map with opposite orientation. Then the elements of $\hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H)$ have a well defined index $|[(x,\tilde{x})]| = \mu(\tilde{x}) \in \Z$.

 By choosing suitable coefficients $a_\pm$ for the perturbation $f$ we can ensure that $\psi^{1}_{\tilde{f}}(L_P)\cap L_W$ is contained in a bounded region. Then perturbing by a generic, compactly supported Hamiltonian $H$ will ensure that $ \psi^1_H(\psi^{1}_{\tilde{f}}(L_P)) \cap L_W$ is a finite set and the intersection is transverse making the set $\mathcal{I}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H)$ finite.

 Let $\mathbf{J}=\{J_t\}_{t\in [0,1]} $ be a time dependent almost complex structure and let $\hat{x}_{\pm}= [(x_{\pm}, \tilde{x}_{\pm})] \in \hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H)$. We define moduli spaces
 \begin{equation*}
 \mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J}):=\Big\{ u\in C^{1}([0,1]\times \R; S(\tilde{Y})) \hspace{0.2cm}|\hspace{0.2cm}
 \substack{\overline{\partial}_{\mathbf{J}}u=0, E(u) <\infty\\ \lim\limits_{s\to \pm \infty}u(t,s)= x_{\pm}(t),\\
 u(0,s) \in \psi^{1}_{H}(\psi^1_{\tilde{f}}(L_P)), u(1,s)\in L_W\\
   \mu(\tilde{x}_{-}) = \mu(u\#\tilde{x}_{+})} \Big\}/\R.
 \end{equation*}

\subsubsection{Admissible almost complex structure}
\begin{definition}
An almost complex structure $J$ on $S(\tilde{Y})=\R\times\tilde{Y}$ is called cylindrical if $J$ is $\R$-invariant and $J \partial_{\theta}\in T\tilde{Y}$.
\end{definition}
Let $J$ be an almost complex structure on $\tilde{\xi}$ compatible with the two form $d\tilde{\alpha}$. By setting $J \partial_{\theta} = R_{\tilde{\alpha}}$, $J$ extends to a cylindrical almost complex structure $\tilde{J}_{\tilde{\alpha}}$ on $\R\times \tilde{Y}$.
For $(\hat{a}, \hat{m}) \in T_{(a,m)}\R\times \tilde{Y}$, $\tilde{J}_{\tilde{\alpha}}$ is given by
\begin{equation}\label{J-Cyl}
(\tilde{J})_{(a,m)}(\hat{a}, \hat{m}) = (-\tilde{\alpha}_{(a,m)}(\hat{m}), J_{m}(\pi_{\tilde{\xi}}(\hat{m})) + \hat{a} R_{\tilde{\alpha}}),
\end{equation}
here $\pi_{\tilde{\xi}}: T(\R \times \tilde{Y}) \rightarrow \tilde{\xi}$ is the projection to $\tilde{\xi}$ parallel to $R_{\tilde{\alpha}}$. Such an almost complex structure is called \textit{compatible with the contact form $\tilde{\alpha}$}.

\begin{definition}\label{Def_admJ}
An almost complex structure $J$ on $S(\tilde{Y})$ is called admissible if:
\begin{enumerate}
\item[C1] $J$is cylindrical and restricts to a $d\tilde{\alpha}$-compatible complex structure on the plane bundle $\tilde{\xi}$.
\item[C2] There is a compact set $D \subset \R\times \C$  such that $D =D_0\times D_{1}$ with $B\subset D_{1}$ for $B$ the fixed compact set on section 3.1, choice 1. Moreover,
 $J\vert_{((\R\times \C) \setminus D)\times Y)} = \tilde{J}_{\tilde{\alpha}}$ where the right hand side is $\tilde{\alpha}$-compatible as defined above.
\item[C3] On $((\R\times \C) \setminus D)\times Y)$ the almost complex structure $J$ satisfies that the projection $\pi:(\R\times\C \times Y,J) \rightarrow (\C,i)$, is $(J, j)$-holomorphic.
\end{enumerate}
We denote the space of admissible almost complex structures by $\mathcal{J}_{ad}$.
\end{definition}
Notice that any $J$ compatible almost complex structure on $\xi$ extends to an admissible one. Indeed, since $\tilde{\xi}_{( x, y,p)} = \R\langle\partial_x + y R_{\alpha}\rangle\oplus \R\langle\partial_y \rangle \oplus \xi_p$ then $J$ extends to $\tilde{\xi}$ by setting $J_{(x,y,p)}(\partial_x + y R_{\alpha})= \partial_y$ and $J_{(x,y,p)}(\partial_y)= -(\partial_x + y R_{\alpha})$ and then $\tilde{J}_{\tilde{\alpha}}\in \mathcal{J}_{ad}$ is admissible.
\begin{proposition}
Let $\mathbf{J}=\{J_t\}_{t\in [0,1]} $ be a time dependent family of generic and admissible almost complex structures and let $\hat{x}_{\pm}= [(x_{\pm}, \tilde{x}_{\pm})] \in \hat{\mathcal{I}}_{\star}(\psi^{1}_{\tilde{f}}(L_P),L_W; H)$. The moduli space $\mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J})$ is a manifold of dimension $(|x_-| -|x_+|-1)$. If $(|x_-| -|x_+|-1) = 0$ then $\mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J})$ is a compact manifold. If $(|x_-| -|x_+|-1) = 1$ then $\mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J})$ admits a compactification by gluing broken strips.
\end{proposition}
\begin{proof}
The first claim about transversality of the moduli spaces $\mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J})$ for generic choice of $\mathbf{J}$ goes back to Floer and can be found in Floer \cite[Theorem 4a]{Fl}.
The proof of compactness is a combination of arguments in Biran-Cornea \cite[Lemma 4.2.1]{BiCo} and Eliashberg-Hofer-Salamon \cite[section 3.9]{EHS}.
In \cite{EHS} the compactness of moduli spaces when the contact manifold is compact is treated. We consider the non-compact manifold $\C\times Y$. If we show that for $\mathbf{J}$ admissible all holomorphic curves of finite energy are contained in the interior of $S(K\times Y)$ where $K \subset \C$ is a compact set, then we are in the same situation as in \cite{EHS} and the compactness follows from \cite[Theorem 3.9.1]{EHS}.

To see that the holomorphic curves under consideration here are contained in $S(K\times Y)$ it is enough to take $K = D_1$ from C2 in Definition \ref{Def_admJ} and use that the map $\pi: (S(\tilde{Y}), \tilde{J})\rightarrow (\C, i)$ is $(\tilde{J}, j)$-holomorphic on $S((\C \setminus K)\times Y)$. This implies that for any $\tilde{J}$-holomorphic curve $u:\Sigma\rightarrow S(\tilde{Y})$ the map $\pi\circ u$ is holomorphic and then its image is contained in some compact set $K$ by \cite[Lemma 4.2.1]{BiCo}.

The condition C1 of a cylindrical almost complex structure guarantees that no sequence of holomorphic strips can escape to the convex end, this in addition to the hypertight setting, guarantees no escape to the concave end.
Moreover, no sphere bubbling can happen since the symplectic manifold is exact, and disk bubbling is impossible on $L_{W}$ because it is exact and on $L_{P}$ because it is weakly exact or monotone with $N_{L}\geq 2$.  Then the only configurations that can appear in the compactified moduli spaces are broken trajectories.
\end{proof}

The differential is defined by
 \begin{equation}
     d(\hat{x}_{-}) = \sum\limits_{\substack{|\hat{x}_{+}|= |\hat{x}_{-}|-1}} \sum\limits_{u\in \mathcal{M}(\hat{x}_{-}, \hat{x}_{+};\mathbf{J})} T^{\omega(u)}  \hat{x}_{+}
 \end{equation}

Once the compactness of the moduli spaces is ensured, it is standard to show that $d^{2}=0$. The reader can check for example \cite[Lema 3.2]{Fl1}.
Finally, we set $$CF(L_P,L_W;H,f,\mathbf{J}) := \oplus_{\star \in \pi_{0}(\mathcal{P}(\psi^1_H(\psi^{1}_{\tilde{f}}(L_P)), L_W))} CF_{\star}(L_P,L_W;H,f,\mathbf{J})$$
\begin{remark} In a similar way, the Floer complex $CF(\hat{P},L_{\Lambda}, H, J)$ for a pair $(P, \Lambda)$ consisting of a closed weakly exact or monotone pre-Lagrangian and a closed hypertight Legendrian of $(Y,\xi)$, can be defined. In this case $\hat{P},L_{\Lambda}\subset (S(Y),\omega)$, and since $Y$ is compact, the Floer complex consider here is a minor modification from the one defined in \cite{EHS}. The difference being that here we decided to consider the Novikov ring and all connected components of the path space. We will denote the homology of this complex by $HF(P,\Lambda)$.
\end{remark}
\begin{proposition}The homology of the complex $CF(L_P,L_W;H,f,\mathbf{J})$ is well defined and it is independent on the choice of compactly supported $H$ and generic and admissible $\mathbf{J}$ and depends on the sign of the function $f$ outside the compact set $B$. We denote this homology by $HF(L_P,L_W; [f])$.
\end{proposition}
\begin{proof}
The proof of this proposition follows the standard arguments. The only difference here is the non-compactness of $\tilde{Y}$ and then we only need to justify the compactness of the moduli spaces involved in the proofs. For the invariance under choice of compactly supported $H$ a chain map can be constructed using moving boundary conditions so that the moduli spaces of pseudo-holomorphic curves with moving boundary conditions will be compact by the choice of $\mathbf{J}$ in Definition \ref{Def_admJ}; C1 guarantees that no curves escape to the convex end, C3 that no curves escape to the $\C$ direction and the hypertight condition guaranties that no curve escape to the concave end. The invariance under change of almost complex structure follows from \cite[Theorem 3.7.3]{EHS}. For the invariance under change of function $f$, let  $f_{1}$ be another function satisfying choice 2 in \ref{chice} and with the same sign as $f$ outside $B$. To prove the invariance we use an auxiliary function $f_2$ so that $f_1$ and $f_2$ coincide inside the compact $B$
and so that $f$ and $f_2$ coincide outside a bigger compact, say $2B$, additionally $f_2$ should not
create any new intersection points. Then one can use a homotopy $g_\tau=\tau f_2 + (1-\tau)f$ and construct a chain map between the corresponding complexes using moving boundary conditions. And do similarly for $f_1$ and $f_2$. The coincidence of $f$ and $f_2$ outside $2B$ means that the moving boundary argument applies
(because the ends associated to $g_{\tau}$ remain constant to those of $f$ outside of $2B$).
The coincidence of $f_1$ and $f_2$ inside $B$ means that, by taking $B$ big enough, the complexes
of $f_1$ and $f_2$ coincide.

\end{proof}

\subsection{Invariance under non-compactly supported Hamiltonian perturbations}

\subsubsection{Admissible Hamiltonian isotopies}
Let $H:[0,1]\times S(\tilde{Y})\rightarrow \R$ be a time dependent Hamiltonian and denote by $\psi^{t}$ its Hamiltonian flow.  We call $H$ admissible if:

\begin{itemize}
 \item There is a constant $K>0$ such that $H$ has support on $[0,1]\times [-K, K] \times \tilde{Y}$.
\item There exist a compact set $B'$ containing the fixed compact set $B$ from \ref{chice}, $B\subset B'$, such that for all $t\in [0,1]$ and $q \in L_{V}\cap \pi^{-1}(\C\setminus B)$ we have  $\psi^{t}(q) \in L_{V}\cap\pi^{-1}(\C\setminus B')$, where $V\in\{P,W\}$.

\end{itemize}

\begin{remark}
An example of such a Hamiltonian isotopy is the Hamiltonian isotopy obtained by lifting the contact isotopy associated to a translation
along the $x$-axis, by means of a suitable cutoff.
\end{remark}

\begin{proposition}\label{invarianza}
 The homology of the complex $CF(L_{P},L_ W; H, f, \textbf{J})$ is invariant under admissible Hamiltonian isotopies $\{\psi^{t}\}_{t\in[0,1]}$:
 $$HF(L_P,L_W;[f])\cong HF(\psi_{1}(L_P), L_W;[f]).$$

\end{proposition}

\begin{proof}
The proof of this statement is similar to the proof of the analogous statements for Lagrangian cobordisms in \cite[Proposition 4.3.1]{BiCo}. It consists in constructing a chain map using moving boundary conditions:
\begin{align*}
c:CF(L_{P},L_ W; H, f, \textbf{J})&\rightarrow CF(\psi^{1}(L_P), L_W; \psi^1\circ H\circ(\psi^1)^{-1},\psi^1\circ f\circ(\psi^1)^{-1},  \textbf{J}),\\
\hat{x} &\mapsto c(\hat{x})= \sum \limits_{\tilde{y}}\sum\limits_{u\in \mathcal{M}_{\beta}(\hat{x}, \hat{y}; \textbf{J})} T^{\omega(u) - \int\limits_{\R\times\{0\}} H_{\beta(s)}(u(s,0))ds}\hat{y},
\end{align*}
where $\mathcal{M}_{\beta}(\hat{x}, \hat{y}; \textbf{J})$ denotes the following moduli space of $\textbf{J}$-holomorphic maps with moving boundary condition.
Let $\beta: \R \rightarrow [0, 1]$ be a smooth function with $\beta(s) = 0$ for $s \leq 0$, $\beta(s) = 1$ for $s \geq 1$ and  $\dot{\beta}(s) > 0 \text{ on }(0,1)$. Thus, $u\in \mathcal{M}_{\beta}(\hat{x}, \hat{y}; \textbf{J})$ if:
\begin{enumerate}
\item $\overline{\partial}_{\textbf{J}}u =0,$
\item $u(s, 0) \in \psi^{\beta(s)(1-t)}(\psi^{1}_H(\psi^1_{\tilde{f}}((L_P)),$
\item $u(s,1) \in L_W,$
\item it has finite energy,
\item $\mu(\tilde{x})=\mu(u\#\tilde{y}).$
\end{enumerate}
The only difference with the setting in \cite[Proposition 4.3.1]{BiCo} is the possibility of losing compactness along the $\theta$ direction of the symplectization.
Notice that by conditions C1, C2 for admissible almost complex structure $\textbf{J}$, no $\textbf{J}$-holomorphic curve can escape to $\pm \infty$. Therefore the moduli spaces with moving boundary condition $ \mathcal{M}_{\beta}(\hat{x}, \hat{y}; \textbf{J})$ are compact. Once this is ensured, the proof of \cite[Proposition 4.3.1]{BiCo} adapts to this setting.
\end{proof}
\section{Proof of Theorem 1}

\begin{theorem}
Let $(Y,\xi)$ be a closed hypertight contact manifold and $\Lambda, \Lambda'\subset Y$ a pair of hypertight Legendrian submanifolds related by a connected hypertight Legendrian cobordism $(W;\Lambda, \Lambda')\subset (\C \times Y,\tilde{\xi})$.  If $P\subset Y$ is a closed weakly exact or monotone  with $N_P \geq 2$ pre-Lagrangian submanifold
then $$HF(L_P,L_{\R\times \{0\}\times \Lambda};[f]) \cong  HF(L_P,L_{\R\times \{0\}\times \Lambda'};[f]).$$
\end{theorem}
\begin{proof}
The proof consists in first choosing special data $(H,f, \textbf{J})$ to define the Floer complex $CF(L_P,L_{W}; H, f, \textbf{J})$ and then finding suitable admissible Hamiltonian isotopy.
Let $B \subset \C$ be such that $W$ is cylindrical outside $\pi_{\C}^{-1}(B)$, and $H$ a Hamiltonian with support on
$[-K,K]\times B \times Y$ for $K>0$.
Let be $f(x,y) = \beta(x)ax$ where $a>0$ and for some $R>0$ such that $B\subset [-R, R]\times[-R,R]$ the smooth function $\beta:\R\rightarrow\R$ satisfies
$\beta(x) = 1$ on $(-\infty, -R]$,
$\beta(x) = -1$ on $[R, \infty)$
and
$\dot{\beta}(x) <0$.
Such an $f$ can be chosen such that $\pi_{\C}(L_P)$ looks like
\begin{center}
   \includegraphics[scale=0.70]{C-projection.png}
\end{center}

The result follow from the fact that the translation on $x$, $T_{t}:\C \rightarrow \C$, $(x,y)\mapsto (x+t, y)$, induces a contact Hamiltonian on $\C\times Y$ that lifts to an admissible Hamiltonian isotopy, denoted by $\psi^t$, defined on a neighborhood of $L_P$ by the lift of the contact isotopy $\psi_{T_{t}\circ\pi_{\C}}$ and with support on a slightly bigger neighborhood.  Then from Proposition \ref{invarianza}
$$HF(L_P,L_{W}; [f])\cong HF(\psi_{1}(L_P), L_W;[f]).$$
The right hand side of the equality is isomorphic to $HF(P,\Lambda)$ and the left hand side to $HF(P,\Lambda')$.
\end{proof}

\bibliographystyle{plain}
\bibliography{journal}
\end{document}

config: arxiv


TITLE: Intuitive understanding of the "Multiplication Rule"?
QUESTION [4 upvotes]: I apologize in advance that this question has a long set-up. In the set up I am presenting how I currently understand the material, and the actual question is if my understanding is correct and applicable to more types of questions.

I am referring to the rule $$P(A \text{ and } B)=P(A) \cdot P(B|A)$$ Or just $$P(A \text{ and } B)=P(A) \cdot P(B)$$
If the events are independent.
I will be using absolute value bars as notation for the size of a set (i.e. $|\{z_1, z_2, ...z_n\}|=n$)
I feel like I understand this rule for the most part when we have $2$ independent events. For example, rolling an even number on a standard dice and flipping "tails" with a coin. The way I understand this is as follows:
$$ \dfrac{ \text{Desired outcomes}}{\text{Total Outcomes}} = \dfrac{|\{2T, 4T, 6T\}|}{|\{1H, 1T, 2H, 2T,...,6H, 6T\}|} =   \dfrac{|\{2, 4, 6 \}|}{|\{1, 2, 3, 4, 5, 6\}|} \cdot \dfrac{ |\{T\}|}{|\{H, T\}|}$$
When it comes to two dependent events, it mostly makes sense but I don't think I've completely internalized it. For example, if the question asks:
"Find the probability of drawing a king, and then a queen from a deck of cards without replacement."
I have a little bit of trouble making sense of this one in the context of one deck, so I just pretend that we have two decks, one with $52$ cards and the other with $51$ cards (with the king of diamonds missing), and I reduce the problem to drawing a king and a queen in sequence from the two decks. I think I can make sense of it the same way I made sense of the dice and the coin:
$$ \dfrac{ \text{Desired outcomes}}{\text{Total Outcomes}} = \dfrac{|\{K_{clubs}Q_{clubs}, K_{clubs}Q_{spades},...,K_{diamonds}Q_{diamonds}\}|}{|\{Ace_{clubs}Ace_{clubs}, Ace_{clubs}Ace_{spades},..., K_{diamonds}K_{hearts} \}|} =   \dfrac{|\{K_{clubs}, K_{spades}, K_{hearts}, K_{diamond} \}|}{|\{Ace_{clubs}, Ace_{spades},...K_{diamonds}\}|} \cdot \dfrac{ |\{ Q_{clubs}, ... Q_{diamond}  \}|}{| \{Ace_{clubs}, Ace_{spades},...K_{hearts} \}|}$$
However, what really gives me trouble is when we have just one event. For example
"15,000 U.S. medical school seniors applied to residency programs in 2009. Of those, 93% were matched with residency positions. 82% of those seniors matched with residency positions were matched with one of their top $3$ choices. Find the probability that a randomly selected student was matched with a residency position and that it was one of their top $3$ choices."
This problem is easy to solve from an  "algebraic":
$$\dfrac{.82 \cdot(\text{n. of students who got a residency position})}{\text{total number of students}}=\dfrac{.82(.93 \cdot 15,000)}{15,000} $$
However, when I tried to tackle this one like I did the card problem, everything collapsed. Without loss of generality, we let students $s_1$ to $s_{13950}$ be the students who got residency positions, and let students $s_1$ to $s_{11439}$ be the students who got matched with one of their top $3$ choices. If I try to multiply like I did with the cards problem, the results just don't make sense to me (even though I know it gives me the right answer):
$$\dfrac{|\{s_1,...,s_{13950}\}|}{|\{s_1,...,s_{15000}\}|} \cdot \dfrac{|\{s_1,...,s_{11439}\}|}{|\{ s_1,...s_{13950} \}|} = \dfrac{|\{s_1s_1, s_1s_2,...,s_{13950}s_{11439} \}|}{|\{s_1s_1,...,s_{15000}s_{13950}\}|}$$
My questions are: Is my understanding fine for independent events? Can it be applied to dependent events (like with the card problem)? Can it be applied to problems containing only $1$ choice (like the last problem)?

REPLY [1 votes]: The way you seem to be intuitively understanding the probability of two events both occurring sometimes makes sense, but sometimes seems to make things more complicated. I'm not so sure that it simply depends on whether we are dealing with independent or dependent events.
In your two card example, you can look at the number of possible king-queen outcomes and the total number of two card outcomes, and divide to get the desired probability.  In this case the two events (1st card is King, 2nd card is Queen) are dependent, but your understanding is correct.  (One thing that I would change though is that I wouldn't list something like $A_{clubs}A_{clubs}$ in the possible outcome pool as this is not actually a possible outcome.)
In the medical school example, your method would still work but it doesn't seem to be the simplest way of looking at it.  The understanding behind your formula would be that in the 1st event we are selecting a student from a pool of all 15,000 students, and in the 2nd event we are selecting a student from a pool of the 13,950 students with residency.  The desired combinations are where the 1st student got a residency and the 2nd got a choice match and we compare the desired combinations with the total combinations to get the desired probability. While this is technically accurate, the more intuitive understanding would be that we are just making one selection from the 15,000 students with the desired outcome being a student who got a residency with a top choice and the desired probability being (# of desired outcomes/# of total outcomes).
Your way of understanding joint probabilities is sometimes not so intuitive even with some independent events. For example, if I would say "40% of students in the class were male and 90% of the males in the class got their residency of choice".  The two events may very well be independent. Regardless, it would be more intuitive to view the probability as (males who got their residency/total students) rather than looking at the # of possible combinations of (student, male student) compared to the # of possible combinations of (male student, male student with residency of choice).
In short, the intuitive understanding may vary based on the scenario, but the formula remains the same.


TITLE: Norm constrained least square minimization with an additional single linear equality constraint: A quadratically constrained quadratic program (QCQP)
QUESTION [2 upvotes]: Given is the following QCQP problem:
\begin{align}
&&\min_{\mathbf{x} \in \mathbb{C}^n} &\|A \mathbf{x} - \mathbf{b}\|^2,\tag{1}\label{1}\\
\text{ subject to:}&&&\\
&&\|\mathbf{x}\|^2 &\leq \alpha^2,\tag{C1}\label{C1}\\
&&\mathbf{c}^{\dagger} \mathbf{x} &= \gamma,\tag{C2}\label{C2}
\end{align}
with:

$A \in \mathbb{C}^{m\times n}$, with $m, n \in \mathbb{N}: m \geq n$: $\ A^{\dagger} A$ positive definite,
$\mathbf{b} \in \mathbb{C}^m,\mathbf{c} \in \mathbb{C}^n: 0< \|\mathbf{c}\| < \infty$,
$\gamma \in \mathbb{C}: |\gamma| < \infty,\, \alpha \in \mathbb{R}: |\gamma|^2/\|\mathbf{c}\|^2 \leq \alpha^2 < \infty$,
$\|.\|$ - $2$-norm,
${}^\dagger$ - Hermitian adjoint, the combined operation of complex conjugation and transposition.

Obviously, there exists no solution for $\alpha^2 < |\gamma|^2/\|\mathbf{c}\|^2$.
For the solution of the only norm constraint problem, i.e. without the constraint \eqref{C2}, see here and here.
With the definitions $f(\mathbf{x}):=\|A \mathbf{x} - \mathbf{b}\|^2$, $h(\mathbf{x}):=\mathbf{c}^{\dagger}\mathbf{x} - \gamma$ and $g(\mathbf{x}):=\|\mathbf{x}\|^2 - \alpha^2$, we can write the problem in the standard form:
\begin{align}
&&\min_{\mathbf{x} \in \mathbb{C}^n} &f(\mathbf{x}),\tag{1}\label{1a}\\
\text{ subject to:}&&&\\
&&g(\mathbf{x}) &\leq 0,\tag{C1}\label{C2a}\\
&&h(\mathbf{x})& = 0.\tag{C2}\label{C1a}
\end{align}
The Lagrangian is given by
$$L(\mathbf{x},\mu, \lambda) = f(\mathbf{x}) + \mu g(\mathbf{x}) + \lambda h(\mathbf{x}),\tag{2}\label{2}$$
with $(\mu, \lambda)$ KKT-multipliers.
In the following we abbreviate $\mathbf{y}:=A^{\dagger}\mathbf{b}$ and denote with $I$ the $n\times n $ identity and with $\mathbf{0}$ a length $n$ column vector with all zero entries.
Solving the linear matrix equation
$$
\begin{pmatrix}
A^{\dagger}A + \mu I & \mathbf{c}\\
\mathbf{c}^{\dagger} & 0
\end{pmatrix}
\begin{pmatrix}
\mathbf{x}(\mu)\\
\lambda(\mu)
\end{pmatrix}
 =
\begin{pmatrix}
\mathbf{y}\\
\gamma
\end{pmatrix},\tag{3}\label{3}
$$
we obtain the $\mu$-parametric solution
$$
\mathbf{x}(\mu) =
\begin{pmatrix}
I &\mathbf{0}
\end{pmatrix}
\begin{pmatrix}
A^{\dagger}A + \mu I & \mathbf{c}\\
\mathbf{c}^{\dagger} & 0
\end{pmatrix}^{-1}
\begin{pmatrix}
\mathbf{y}\\
\gamma
\end{pmatrix}.\tag{4}\label{4}
$$
 Using the formula for block matrix inversion,
$$
\begin{pmatrix}
G & \mathbf{v}\\
\mathbf{v}^{\dagger} &0
\end{pmatrix}^{-1}
=
\begin{pmatrix}
G^{-1} - \frac{G^{-1}\mathbf{v}\mathbf{v}^{\dagger}G^{-1}}{\mathbf{v}^{\dagger}G^{-1}\mathbf{v}} & \frac{G^{-1}\mathbf{v}}{\mathbf{v}^{\dagger}G^{-1}\mathbf{v}}\\
\frac{\mathbf{v}^{\dagger} G^{-1}}{\mathbf{v}^{\dagger}G^{-1}\mathbf{v}} & -\frac{1}{\mathbf{v}^{\dagger}G^{-1}\mathbf{v}}
\end{pmatrix},\tag{5}\label{5}
$$
an explicit expression for the $\mu$-parametric solution can be written as
$$
\mathbf{x}(\mu) = (A^{\dagger}A + \mu I)^{-1}\left(\mathbf{y} - w(\mu)\mathbf{c}\right),\tag{6}\label{6}
$$
where
$$
w(\mu):=\frac{\mathbf{c}^{\dagger} (A^{\dagger}A + \mu I)^{-1} \mathbf{y} - \gamma}{\mathbf{c}^{\dagger} (A^{\dagger}A + \mu I)^{-1}\mathbf{c}}.\tag{7}\label{7}
$$
The solution of \eqref{6} fulfills \eqref{C2}. The remaining task is to find $\mu^*$:
$$
f(\mathbf{x}(\mu^*)) = \min_{\mu:\, g(\mathbf{x}(\mu)) \leq 0} f(\mathbf{x}(\mu)).\tag{8}\label{8}
$$
Questions
(Q1) Is $\|\mathbf{x}(\mu)\|^2$ monotonically decreasing with increasing $|\mu|$?
(Q2) Is $\mu^* \geq 0$?
(Q3) Is $\mu^* = \inf\, \{\mu \geq 0 \mid g(\mathbf{x}(\mu)) \leq 0\}$?

REPLY [2 votes]: Answers
(Q1)
$\|\mathbf{x}(\mu)\|^2$ is monotonically decreasing without jump discontinuities for $\mu \geq 0$ with $\lim_{\mu \to \infty}\|\mathbf{x}(\mu)\|^2 = |\gamma|^2/\|\mathbf{c}\|^2$. If for a fixed $\mu: 0 \leq \mu < \infty$ the solution is
$\mathbf{x}^* = \gamma \mathbf{c} /\|\mathbf{c}\|^2$, then this is the solution for all non-negative values of $\mu$.
For $\mu <0$ monotonicity holds not on the whole domain of negative real numbers and jump discontinuities can appear.
(Q2)
Yes, see below.
(Q3)
Yes and the global optimal solution is given by $\mathbf{x}^* = \mathbf{x}(\mu^*)$, with $\mathbf{x}(\mu)$ from (6). Although this solution also holds for the case $\alpha^2 = |\gamma|^2/\|\mathbf{c}\|^2$, where the only allowed solution is the one for $\mu \to \infty$, in practice no limit must be taken due to the fact that the solution is already determined to be $\mathbf{x}^* = \gamma \mathbf{c} /\|\mathbf{c}\|^2$.
Strategy for numerical solution
For $\alpha^2 = |\gamma|^2/\|\mathbf{c}\|^2$, no calculation is necessary since the only allowed solution is $\mathbf{x}^* = \gamma \mathbf{c} /\|\mathbf{c}\|^2$.
For $\alpha^2 > |\gamma|^2/\|\mathbf{c}\|^2$, the numerical procedure to calculate the optimal solution simplifies with the help of the answers of (Q1) and (Q2) to calculate $\mathbf{x}(\mu)$ according to (6), starting with $\mu=0$ and increase $\mu$ until (C1) holds.
No solution exists obviously for $\alpha^2 < |\gamma|^2/\|\mathbf{c}\|^2$.
Proofs/Reasons
(Q1)
We first investigate the asymptotic solution for large $\mu$.
As a first step we divide the first row of (3) by $\mu$:
$$
\left(A^{\dagger} A/\mu + I\right) \mathbf{x}(\mu) + \mathbf{c} \lambda(\mu)/\mu = \mathbf{y}/\mu.\tag{A1}\label{A1}
$$
Multiplying \eqref{A1} from the left with $\mathbf{c}^{\dagger}$ and using both, the constraint (C2) and the fact that we look for solutions with bounded norm only, we obtain the asymptotic expression
$$
\lim_{\mu \to \infty}\lambda(\mu)/\mu = -\gamma/\|\mathbf{c}\|^2\tag{A2}.\label{A2}
$$
With \eqref{A2} in the asymptotic limit of \eqref{A1}, we find
$$
\lim_{\mu \to \infty} \mathbf{x}(\mu) = \gamma \mathbf{c} /\|\mathbf{c}\|^2=:\mathbf{x}_{\infty},\tag{A3}\label{A3}
$$
and thus
$$
\lim_{\mu \to \infty} \|\mathbf{x}(\mu)\|^2 = |\gamma|^2/\|\mathbf{c}\|^2.\tag{A4}\label{A4}
$$
To investigate the monotonicity of $\|\mathbf{x}(\mu)\|^2$ we start with differentiating (3) w.r.t. $\mu$: The first row yields
$$
\mathbf{x}(\mu) + (A^{\dagger}A + \mu I) \mathbf{x}'(\mu) + \mathbf{c}\lambda'(\mu) = 0,\tag{A5}\label{A5}
$$ and the second row the trivial condition $\mathbf{c}^{\dagger} \mathbf{x}'(\mu) = 0$. We use for the function derivative w.r.t. $\mu$ the abbreviation $u'(\mu) \equiv \rm{d}\, u(\mu)/\rm{d}\mu$.
Multiplying \eqref{A5} with $\mathbf{c}^{\dagger}$ from left we obtain
$$
\gamma + \mathbf{c}^{\dagger} A^{\dagger}A\mathbf{x}'(\mu) + \|\mathbf{c}\|^2\lambda'(\mu) = 0,\tag{A6}\label{A6}
$$
which yields
$$
\lambda'(\mu) = -\dfrac{
\gamma + \mathbf{c}^{\dagger}A^{\dagger}A \mathbf{x}'(\mu)}{\|\mathbf{c}\|^2}.\tag{A7}\label{A7}
$$
Using \eqref{A7} in \eqref{A5} we get a conditional equation for $\mathbf{x}'(\mu)$:
$$
\left(\left(I - \dfrac{\mathbf{c}\mathbf{c}^{\dagger}}{\|\mathbf{c}\|^2}\right)A^{\dagger}A + \mu I\right) \mathbf{x}'(\mu) = \frac{\gamma \mathbf{c}}{\|\mathbf{c}\|^2} - \mathbf{x}(\mu).\tag{A8}\label{A8}
$$
On the left hand side the orthogonal projector $P:=I - \mathbf{c}\mathbf{c}^{\dagger}/\|\mathbf{c}\|^2$ appears that maps elements of $\mathbb{C}^n$ to $\mathcal{U} = \{\mathbf{x} \in \mathbb{C}^n \mid \mathbf{c}^{\dagger}\mathbf{x} = 0\}\subset \mathbb{C}^n$, the subspace orthogonal to the one-dimensional subspace along $\mathbf{c}$. Multiplying \eqref{A8} with $P$ from left we get:
$$
\left(PA^{\dagger}A + \mu P \right) \mathbf{x}'(\mu) = -P\mathbf{x}(\mu).\tag{A9}\label{A9}
$$
Since $\mathbf{c}^{\dagger} \mathbf{x}'(\mu) = 0$, which is equivalent to $P\mathbf{x}'(\mu) = \mathbf{x}'(\mu)$, we can further  write
$$
\left(PA^{\dagger}AP + \mu P \right) \mathbf{x}'(\mu) = -P\mathbf{x}(\mu),\tag{A10}\label{A10}
$$
which is a linear equation on $\mathcal{U}$ only that completely determines $\mathbf{x}'(\mu)$. We expand \eqref{A10} in an orthonormal basis of $\mathcal{U}$ and use the following notation: $\mathbf{x}_{\mathcal{U}}(\mu)$, $\mathbf{x}'_{\mathcal{U}}(\mu)$ for the representation of $P\mathbf{x}(\mu)$, $\mathbf{x}'(\mu)$ in $\mathcal{U}$, $I_{\mathcal{U}}$ for the identity in $\mathcal{U}$ and $S_{\mathcal{U}}$ for the representation of $PA^{\dagger}AP$ in $\mathcal{U}$.
We can write
$$
\mathbf{x}'_{\mathcal{U}} = -\left(S_{\mathcal{U}} + \mu I_{\mathcal{U}}\right)^{-1}\mathbf{x}_{\mathcal{U}}(\mu),\tag{A11}\label{A11}
$$ and it follows
\begin{align}
\frac{\rm{d}}{\rm{d}\mu}\|\mathbf{x}(\mu)\|^2 & = \mathbf{x}'(\mu)^{\dagger}\mathbf{x}(\mu) + \mathbf{x}(\mu)^{\dagger}\mathbf{x}'(\mu)\tag{A12}\label{A12}\\
&=\mathbf{x}'(\mu)^{\dagger}P P \mathbf{x}(\mu) + \mathbf{x}(\mu)^{\dagger}PP\mathbf{x}'(\mu)\\
&=\mathbf{x}_{\mathcal{U}}'(\mu)^{\dagger}\mathbf{x}_{\mathcal{U}}(\mu) + \mathbf{x}_{\mathcal{U}}(\mu)^{\dagger}\mathbf{x}_{\mathcal{U}}'(\mu)\\
&=-2\mathbf{x}_{\mathcal{U}}(\mu)^{\dagger}\left(S_{\mathcal{U}} + \mu I_{\mathcal{U}}\right)^{-1}\mathbf{x}_{\mathcal{U}}(\mu).\tag{A13}\label{A13}
\end{align}
It can be readily seen from its definition that $S_{\mathcal{U}}$ is positive definite, hence $\left(S_{\mathcal{U}} + \mu I_{\mathcal{U}}\right)^{-1}$ is positive definite for $\mu \geq 0$. Since $A^{\dagger}A$ is also positive definite we obtain from (6) together with (7) that $\mathbf{x}(\mu)$ is not diverging for $\mu\geq 0$. Therefore, from \eqref{A13} we obtain $\frac{\rm{d}}{\rm{d}\mu}\|\mathbf{x}(\mu)\|^2 \leq 0$ for $\mu \geq 0$, that is $\|\mathbf{x}(\mu)\|^2$ is monotonically decreasing without jump discontinuities for $\mu \geq 0$. However, the monotonicity is not strict because $\rm{d}\|\mathbf{x}(\mu)\|^2/\rm{d}\mu$ vanishes when $\mathbf{x}_{\mathcal{U}}(\mu) = 0$. The only solution compatible with both constraints (C1) and (C2) that yields $\mathbf{x}_{\mathcal{U}}(\mu) = 0$ is $\mathbf{x}(\mu) = \gamma\mathbf{c}/\|\mathbf{c}\|^2 = \mathbf{x}_{\infty}$. Since this is also the asymptotic solution from \eqref{A3}, we have $\lim_{\mu \to \infty} \rm{d}\|\mathbf{x}(\mu)\|^2/\rm{d}\mu = 0$. Moreover, if (6) yields $\mathbf{x}_{\infty}$ for $\mu < \infty$, it must be the solution for all $\mu$.
For $\mu < 0$, $\left(S_{\mathcal{U}} + \mu I_{\mathcal{U}}\right)^{-1}$ is not guaranteed to be positive definite and hence monotonicity is not given on the whole domain of negative real numbers. Moreover, jump discontinuities can appear where $\mu$ matches eigenvalues of $A^{\dagger}A$ or $S_{\mathcal{U}}$.
(Q2)
We have to distinguish two cases:

$\alpha^2 > |\gamma|^2/\|\mathbf{c}\|^2$:
With the monotonicity of $\|\mathbf{x}(\mu)\|^2$ for $\mu \geq 0$ and \eqref{A4}, we find a $\mu^\star: g(\mathbf{x}(\mu^\star)) < 0$. Therefore, Slater's condition holds which guarantees strong duality of the convex optimization problem and thus the existence of a KKT-point $(\mathbf{x}^*,\mu^*, \lambda^*)$, where $\mathbf{x}^*$ is a local optimum for the optimization problem and $(\mu^*,\lambda^*)$ for the corresponding dual problem. Due to the convexity and strong duality of the problem the following KKT-conditions are sufficient conditions for the global optimum:
\begin{align}
g(\mathbf{x}^*) &\leq 0,\tag{A14}\label{A14}\\
h(\mathbf{x}^*) &= 0,\tag{A15}\label{A15}\\
\mu^* &\geq 0,\tag{A16}\label{A16}\\
\mu^*g(\mathbf{x}^*) &= 0.\tag{A17}\label{A17}
\end{align}
\eqref{A16} answers the question for this case.
$\alpha^2 = |\gamma|^2/\|\mathbf{c}\|^2$:
Slater's condition does not hold, however, the only allowed solution is $\mathbf{x} = \mathbf{x}_{\infty}$, the asymptotic solution. Therefore, we have $\mu^* \to \infty$.

For both cases we get $\mu^*
 \geq 0$.
(Q3)
For $\mathbf{x}(\mu)$ from (6), \eqref{A15} holds. The remaining task is to find the optimal $\mu^* \geq 0$ such that the remaining KKT-conditions hold. To satisfy \eqref{A17},
we require $\mu^* = 0$ if $g(\mathbf{x}(\mu^*=0)) < 0$ and $\mu^* >0$ otherwise.  For the latter case we require $\|\mathbf{x}(\mu^*)\|^2 = \alpha^2$ such that (A14) holds. Due to the fact that $\|\mathbf{x}(\mu)\|^2$ is monotonically decreasing for $\mu \geq 0$, we find $\mu^* = \inf\, \{\mu \geq 0 \mid g(\mathbf{x}(\mu)) \leq 0\}$ and the global optimal solution is given by $\mathbf{x}^* = \mathbf{x}(\mu^*)$.


TITLE: Integrating $\sin^3(x)/(2+\cos(x))$
QUESTION [0 upvotes]: I could use some help solving the following integral:
$$\int \frac{\sin^3(x)}{2+\cos(x)} dx$$

So far I tried using the equality:
$$\sin^3(x) = \frac{3}{4} \sin(x) - \frac{1}{4}\sin(3x)$$
which wasn't useful, then I tried using substitution when
$$t=2+\cos(x)$$
wasn't much help either, any ideas?

REPLY [1 votes]: Notice that:
$$\frac{\sin^3(x)}{2+\cos x} = -\left(\frac{d}{dx}\cos x\right)\frac{1-\cos^2 x}{2+\cos x}$$
hence you just need to integrate:
$$\frac{1-z^2}{2+z} = 2-z-\frac{5}{2+z},$$
not a difficult task.


TITLE: Show that the natural map between vectors and linear functions on $\mathbb R^n$ is bijective
QUESTION [2 upvotes]: I'm doing this problem in Spivak's Calculus on Manifolds and I need help with what the second statement is trying to say and how it is proven.

*Let $(\mathbb{R}^n)^*$ denote the dual space of the vector space $\mathbb{R}^n$ . If $x \in \mathbb{R}^n$, define $\varphi_x \in (\mathbb{R}^n)^*$ by $\varphi_x(y) =\langle x,y\rangle$.  Define $T:\mathbb{R}^n \rightarrow (\mathbb{R}^n)^*$ by $T(x) = \varphi_x$. Show that $T$ is a $1 - 1$ linear transformation and conclude that every $\varphi$ $\in$ $(\mathbb{R}^n)^*$ is $\varphi_{x}$ for a unique $x \in \mathbb{R}^n$.

I understand how to do the first part in proving that T is a linear transformation, but the second statement confuses me even when I look at the proof. I know this may be trivial, but I would appreciate any help in clarifying what the statement is trying to say as well as why its proved by showing that  $\varphi_{ax + by}$ = $a\varphi_{x} + b\varphi{y}$.
Thanks!

REPLY [3 votes]: Since $\mathbb R^n$ is $n$-dimensional, $\left(\mathbb R^n\right)^*$ is also $n$-dimensional. To show $T$ is invertible it therefore suffices to show $T$ has trivial kernel.
To this end, let $x\in\ker T$. Then $T(x)(y)=0$ whenever $y\in\mathbb R^n$. That is, $\langle x,y\rangle=0$ whenever $y\in\mathbb R^n$. In particular, $\langle x,e_i\rangle=0$ for each of the standard basis vectors $e_1,\dotsc,e_n\in\mathbb R^n$. But now this implies $x_i=0$ for $1\leq i\leq n$ so $x=\mathbf 0$. Hence $T$ has trivial kernel.


TITLE: Why runners lean forward?
QUESTION [2 upvotes]: Why runners tend to lean forward prior to start running? How does it help run faster? What is the physics behind his leaning?

REPLY [5 votes]: Leaning allows for higher acceleration. If a runner at rest tries to run standing perfectly normal to the ground, he will never be able to move without falling over.  Leaning is necessary for accelerating, for a person whose centre of mass is higher up from the ground.

Walking requires applying a force parallel to the ground to oppose friction, which generates a torque that tends to tip you over. Leaning provides a counter torque.

In a running race, there is a delicate interplay between these two torques. A runner has to balance both the torques to prevent falling.
Hence there is always a stable leaning angle, above which you fall forward and below which you fall backwards.

In a race, reaching your top speed quicker would increase your chances of winning. So it is beneficial to apply a significant force on the ground. But as you go faster, it becomes more and more difficult to exert a force on the ground. Because, doing so would require your legs to strike the ground more swiftly, which is limited by your physical capabilities.
Given below is a plot of the acceleration, velocity and distance versus time graphs of Usain bolt during his 100m race in 2008(taken from this site,). Though the scales of the axes may be different, this graph is typical for any human being.

Note that the acceleration, and hence force exerted by you on the ground, is highest at the beginning of the race, and it flattens out to zero after a while.
At the beginning of the race, the torque due to friction is maximum. So runners would have to lean higher during this time, to counter it.

Also, the torque due to friction decreases as the race progresses. So it becomes necessary for you to decrease your leaning angle (and hence the counter-torque) when you near your top speed. The same principle leads to the 'straightening out' of runners in a race. (Video 1,Video 2)

In short, leaning at the beginning of the race enables you to reach your top speed faster, increasing your chances of winning.