TITLE: Given $(m-2)x^2-4x+3=3-x^2+2nx$, compute the value of $m$
QUESTION [1 upvotes]: Given $$(m-2)x^2-4x+3=3-x^2+2nx$$ Compute the value of $m$.

$$(m-2)x^2-4x+3=3-x^2+2nx
\\mx^2+(-4m-4)x+7=-x^2+2nx+3
\\m=-1, n=0$$
The answer is $m=1,n=-2$, please tell me where did I go wrong

REPLY [2 votes]: Hint:
The coefficient of $x^2$ on the left of the equal sign is $(m-2)$ and on the right it is $-1$


TITLE: Can the electrostatic force be infinite in magnitude?
QUESTION [5 upvotes]: The magnitude of the electrostatic force between two charges $Q$ and $q$ separated by a distance $r$ is given by $$F=\frac{kqQ}{r^2}$$ but the minimum value of $r$ must be $10^{-15}\ \rm m$. Therefore, my question is can the electrostatic force ever be infinite?

REPLY [5 votes]: The classical physics equation $F = \frac{kqQ}{r^2}$ has to be interpreted using quantum mechanics for sufficiently small length scales.  So, its probably not appropriate to say that the force becomes infinite.  A typical rule of thumb for the smallest length scale for which this applies is the Compton wavelength $\lambda = \frac{h}{mc}$.  Here $h$ is Plank's constant, $c$ the speed of light and $m$ the particle mass.  For an electron, this comes out to $2.4\times 10^{-12}$m, but for a proton, it would be smaller.


text:
In this section, we establish the main guarantees of the proposed \texttt{FLRA} formulation and the optimization algorithm \texttt{FedRobust}. First, we characterize the convergence of \texttt{FedRobust} in Algorithm \ref{Alg: FedRobust} to solve the minimax problem \eqref{eq: FLRA}. Next, we prove that the learned hypothesis will properly generalize from training data to unseen test samples. Lastly, we demonstrate that solving the \texttt{FLRA}'s minimax problem \eqref{eq: FLRA} results in a robust classifier to Wasserstein shifts structured across the nodes.

\subsection{Optimization guarantees} \label{subsec: optimization}

In this section, we establish our main convergence results and show that \texttt{FedRobust} finds saddle points of the minimax problem in \eqref{Eq: AFL def} for two classes of loss functions. We first set a few notations as follows. We let matrix $\bpsi^i = (\Lambda^i, \delta^i) \in \reals^{d \times (d+1)}$ denote the joint transformation variables corresponding to node $i$. The collection of $n$ such variables corresponding to the $n$ nodes is denoted by the matrix $\Psi = (\bpsi^1;\cdots;\bpsi^n)$. We can now rewrite the minimax problem \eqref{eq: FLRA} as follows:

\begin{gather} \label{eq: min max f}
    \min_{\w} \max_{\Psi} f(\w, \Psi)
    \coloneqq
    \min_{\w} \max_{\bpsi^1, \cdots, \bpsi^n} \frac{1}{n} \sum_{i=1}^{n} f^i(\w,\bpsi^i),
\end{gather}

where $f$ and $f^i$s denote the penalized global and local losses, respectively; that is, for each node $i$

\begin{align} \label{eq: local fi}
    f^i(\w,\bpsi^i)
    \coloneqq
    \frac{1}{m} \sum_{j=1}^{m} \ell \left( f_{\w} (\Lambda^i\bbx^i_j + \delta^i),y^i_j \right) - \lambda \Vert \Lambda^i - I \Vert_F^2 - \lambda \Vert \delta^i \Vert^2.
\end{align}

We also define $\Phi(\w) \coloneqq \max_{\Psi} f(\w, \Psi)$ and $\Phi^* \coloneqq \min_{\w} \Phi(\w)$. Next, we state a few customary assumptions on the data and loss functions. As we mentioned before, we assume that data is heterogeneous (non-iid). There are several notions to quantify the degree of heterogeneity in the data. In this work we use a notion called \emph{non-iid degree} which is defined as the variance of the local gradients with respect to a global gradient \citep{yu2019linear}.

The next two assumptions impose customary conditions on the gradients of local functions.

\begin{assumption}[Bounded non-iid degree]\label{assumption:bounded-degree}
We assume that when there are no perturbations, the variance of the local gradients with respect to the global gradient is bounded. That is, there exists $\rho_f^2$ such that

\begin{gather}
    \frac{1}{n} \sum_{i=1}^{n} \norm{\grw f^i(\w, \bpsi^i) - \grw f(\w, \Psi)}^2
    \leq
    \rho_f^2,
    \quad
    \text{ for } \bpsi^i=(I,0), \Psi = (\bpsi^1;\cdots;\bpsi^n), \text{ and } \forall \w. \nonumber
\end{gather}
\end{assumption}

\begin{assumption}[Stochastic gradients]\label{assumption:stoch-gradients}
For each node $i$, the stochastic gradients $\sgrw f^i$ and $\sgrbpsi f^i$ are unbiased and have variances bounded by $\sigma^2_{\w}$ and $\sigma^2_{\bpsi}$, respectively. That is,

\begin{align}
    \E \norm{\sgrw f^i(\w, \bpsi) - \grw f^i(\w, \bpsi)}^2
    \leq
    \sigma^2_{\w}, \quad
    \E \norm{\sgrbpsi f^i(\w, \bpsi) - \grpsi f^i(\w, \bpsi)}^2
    \leq
    \sigma^2_{\bpsi},
    \quad
    \forall \w, \bpsi. \nonumber
\end{align}
\end{assumption}

\begin{assumption}[Lipschitz gradients] \label{assumption:smooth}
All local loss functions have Lipschitz gradients. That is, for any node $i$, there exist constants $L_1, L_2, L_{12}$, and $L_{21}$ such that for any $\w, \w', \bpsi, \bpsi'$ we have
\begin{gather}
    \norm{\grw f^i(\w, \bpsi) - \grw f^i(\w', \bpsi)}
    \leq
    L_1 \norm{\w - \w'}, \quad
    \norm{\grw f^i(\w, \bpsi) - \grw f^i(\w, \bpsi')}
    \leq
    L_{12} \norm{\bpsi - \bpsi'}_F, \\
    \norm{\grpsi f^i(\w, \bpsi) - \grpsi f^i(\w', \bpsi)}_F
    \leq
    L_{21} \norm{\w - \w'}, \quad
    \norm{\grpsi f^i(\w, \bpsi) - \grpsi f^i(\w, \bpsi')}_F
    \leq
    L_2 \norm{\bpsi - \bpsi'}_F . \nonumber
\end{gather}
\end{assumption}

We show the convergence of \texttt{FedRobust} for two classes of loss functions: PL-PL and nonconvex-PL. Next, we briefly describe these classes and state the main results. The celebrated work of Polyak \citep{polyak1963gradient} introduces a sufficient condition for an unconstrained minimization problem $\min_x g(x)$ under which linear convergence rates can be established using gradient methods. A function $g(x)$ satisfies the Polyak-Łojasiewicz (PL) condition if $g^* = \min_x g(x)$ exits and is bounded, and there exists a constant $\mu > 0$ such that $\Vert \gr g(x) \Vert^2 \geq 2 \mu (g(x) - g^*), \, {\forall} x$. Similarly, we can define two-sided PL condition for our minimax objective function in \eqref{eq: min max f} \citep{yang2020global}.

\begin{assumption}[PL condition]\label{assumption:PL}
The global function $f$ satisfies the two-sided PL condition, that is, there exist positive constants $\mu_1$ and $\mu_2$ such that

\begin{gather}
    {\normalfont{\text{(i)}}} \quad \frac{1}{2 \mu_1} \norm{\grw f(\w, \Psi)}^2
    \geq
    f(\w, \Psi) - \min_{\w} f(\w, \Psi), \\
    {\normalfont{\text{(ii)}}} \quad \frac{1}{2 \mu_2} \norm{\grPsi f(\w, \Psi)}^2_F
    \geq
    \max_{\Psi} f(\w, \Psi) - f(\w, \Psi). \nonumber
\end{gather}
\end{assumption}

In other words, Assumptions \ref{assumption:PL} states that the functions $f(\cdot, \Psi)$ and $-f(\w, \cdot)$ satisfy the PL condition with constants, $\mu_1$ and $\mu_2$, respectively. To measure the optimality gap at iteration $t$, we define the potential function $P_t \coloneqq a_t + \beta b_t$, where

\begin{align}
    a_t \coloneqq \E [ \Phi(\wbar_t) ] - \Phi^*
    \quad \text{ and } \quad
    b_t \coloneqq \E [\Phi(\wbar_t) - f(\wbar_t, \Psi_t)], \nonumber
\end{align}

and $\beta$ is an arbitrary and positive constant. Note that both $a_t$ and $b_t$ are non-negative and if $P_t$ approaches zero, it implies that $(\wbar_t, \Psi_t)$ is approaching a minimax point.

\begin{theorem}[PL-PL loss] \label{Thm: PL-PL convergence}
Consider the iterates of {\normalfont \texttt{FedRobust}} in Algorithm \ref{Alg: FedRobust}
and let Assumptions  \ref{assumption:bounded-degree}, \ref{assumption:smooth}, and \ref{assumption:PL} hold.

Then for  any iteration $t \geq 0$, the optimality gap $P_t \coloneqq a_t + \frac{1}{2} b_t$ satisfies the following:

\begin{align}
    P_{t}
    &\leq
    \left( 1 - \frac{1}{2} \mu_1 \eta_1 \right)^t P_0
    +
    32 \eta_1 \frac{\tilde{L}}{\mu_1} (\tau - 1)^2 \rho^2
    +
    8 \eta_1 \frac{\tilde{L}}{\mu_1}  (\tau - 1) (n + 1) \frac{\sigmaw}{n}
    +
    \eta_1 \frac{\hat{L}}{\mu_1} \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{\eta_1} \frac{L_2}{2 \mu_1} \sigmapsi, \nonumber
\end{align}

for maximization step-size $\eta_2$ and minimization step-size $\eta_1$ that satisfy the following conditions:

\begin{gather} \label{eq: Thm PL-PL conditions}
    \eta_2
    \leq
    \frac{1}{L_2}, \quad
    32 \eta_1^2 (\tau - 1)^2 L_1^2
    \leq
    1, \quad
    \frac{\mu^2_2 \eta_2 n}{\eta_1 L_1 L_2}
    \geq
    1 + 8 \frac{L_{12}^2}{L_1 L_2},\quad
    \eta_1 \left( \hat{L}  + \frac{80 \tilde{L} (\tau - 1) }{\mu_1 \eta_1 ( 1 - \frac{1}{2} \mu_1 \eta_1 )^{\tau-1}} \right)
    \leq
    1. \nonumber
\end{gather}

Here, we denote $\rho^2 \coloneqq 3\rho_f^2 + 6 L_{12}^2 (\epsilon_1^2 + \epsilon_2^2)$ where $\epsilon_1$ and $\epsilon_2$ specify the bounds on the affine transformations $h^i(\bbx) = \Lambda^i \bbx + \delta^i$. We also use the following notations:

\begin{gather} \label{eq: tildeL hatL}
    L_{\Phi} = L_1 + \frac{L_{12} L_{21}}{2n\mu_2}, \quad
    \tilde{L} = \frac{3}{2} \eta_1 L_1^2 + \frac{1}{2}  \eta_2 L_{21}^2, \quad
    \hat{L} =  \frac{3}{2} L_{\Phi} + \frac{1}{2} L_1 + \frac{L_{21}^2}{L_2}.  \nonumber
\end{gather}

\end{theorem}

\iffalse
\begin{remark}
\normalfont
Let us denote $L \coloneqq \max\{L_1, L_2/n, L_{12}/\sqrt{n}, L_{21}/\sqrt{n}\}$, $\mu \coloneqq \min\{\mu_1, \mu_2\}$ and define the condition number $\kappa \coloneqq L / \mu$. Then for feasible step-sizes $\eta_1$ and $\eta_2$ we have

\begin{align}
    P_{t}
    \leq
    e^{- \frac{1}{2} \mu \eta_1 t} P_0
    +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) \kappa L (\tau - 1) \left( (\tau - 1)\rho^2 + \sigmaw \right)
    +
    \ccalO \left( \eta_1 \right) \kappa^2 \frac{\sigmaw}{n}
    +
    \ccalO \left( \frac{\eta_2^2}{\eta_1} \right) n \kappa \sigmapsi.
\end{align}

\end{remark}

\fi

\begin{proof}
We provide the proof of Theorem \ref{Thm: PL-PL convergence} for any $\beta \leq 1/2$ in Appendix \ref{proof: Thm PL-PL}.
\end{proof}

Let us denote $L \coloneqq \max\{L_1, L_2/n, L_{12}/\sqrt{n}, L_{21}/\sqrt{n}\}$, $\mu \coloneqq \min\{\mu_1, \mu_2\}$ and define the condition number $\kappa \coloneqq L / \mu$. Then for feasible step-sizes $\eta_1$ and $\eta_2$ we have

\begin{align}
    P_{t}
    \leq
    e^{- \frac{1}{2} \mu \eta_1 t} P_0
    +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) \kappa L (\tau - 1)^2 \rho^2
    +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) \kappa L (\tau - 1)  \sigmaw
    +
    \ccalO \left( \eta_1 \right) \kappa^2 \frac{\sigmaw}{n}
    +
    \ccalO \left( \frac{\eta_2^2}{\eta_1} \right) n \kappa \sigmapsi. \nonumber
\end{align}

Special cases of this convergence result is consistent with similar ones already established in the literature. In particular the case of regular (non-federated) distributed optimization i.e. when $\tau = 1$, Theorem \ref{Thm: PL-PL convergence} recovers the convergence result in \cite{yang2020global} for a minimax problem with PL-PL cost functions. As another special case of our result, putting $\epsilon_1, \epsilon_2 \to 0$ reduces the problem to standard (non-robust) federated learning where our result is consistent with the prior work as well. In particular, setting  $\epsilon_1, \epsilon_2 \to 0$ and consequently $\eta_2 \to 0$ in this result recovers standard federated learning convergence rates for PL losses \citep{haddadpour2019convergence}.

Next, we relax the PL condition on $f(\cdot, \Psi)$ stated in Assumption \ref{assumption:PL} (i) and show that the iterates of the \texttt{FedRobust} method find a stationary point of the minimax problem \eqref{eq: min max f} when the objective function $f(\w, \Psi)$ only satisfies the PL condition with respect to $\Psi$ and is nonconvex with respect to $\w$.

\begin{theorem}[Nonconvex-PL loss] \label{Thm: nonconvex-PL convergence}
Consider the iterates of {\normalfont \texttt{FedRobust}} in Algorithm \ref{Alg: FedRobust} and let Assumptions  \ref{assumption:bounded-degree}, \ref{assumption:smooth}, and \ref{assumption:PL} (ii) hold.

Then, the iterates of {\normalfont \texttt{FedRobust}} after $T$ iterations satisfy:

\begin{align} \label{eq: Thm nonconvex-PL}
    \frac{1}{T} \sum_{t=0}^{T-1} \E \norm{\gr \Phi( \wbar_{t} )}^2
    &\leq
    \frac{4 \Delta_{\Phi}}{\eta_1 T}
    +
    \frac{4 L_2^2}{\mu_2^2 n^2}\frac{ \epsilon^2}{\eta_1 T}
    +
    64 \eta_1 \tilde{L} (\tau - 1)^2 \rho^2
    +
    16 \eta_1 \tilde{L}  (\tau - 1)  \frac{n + 1}{n} \sigmaw
    +
    2 \eta_1 \hat{L} \frac{\sigmaw}{n}
    +
    \frac{\eta_2^2}{\eta_1} L_2 \sigmapsi, \nonumber
\end{align}

with $\tilde{L},\hat{L},L_{\Phi}, \rho^2 $ defined in Theorem \ref{Thm: PL-PL convergence}, $\epsilon^2 \coloneqq \epsilon_1^2 + \epsilon_2^2$ and $\Delta_{\Phi} \coloneqq \Phi(\w_0) - \Phi^*$, if step-sizes $\eta_1, \eta_2$ satisfy

\begin{gather}
    \eta_2
    \leq
    \frac{1}{L_2}, \quad
    \frac{\eta_1}{\eta_2}
    \leq
    \frac{\mu_2^2 n^2}{8 L_{12}^2}, \quad
    32 \eta_1^2 (\tau - 1)^2 L_1^2
    \leq
    1, \quad
    \eta_1 \left( \hat{L}  + 40 \tilde{L} (\tau - 1)^2 \right)
    \leq 1. \nonumber
\end{gather}

\end{theorem}

\begin{proof}
We defer the proof of Theorem \ref{Thm: nonconvex-PL convergence} to Appendix \ref{appendix: proof of Thm nonconvex-PL}.
\end{proof}

Theorem \ref{Thm: nonconvex-PL convergence} implies that after $T$ iterations of \texttt{FedRobust}, there exists $0 \leq t \leq T-1$ for which we have

\begin{align}
    \E \norm{\gr \Phi(\wbar_{t})}^2
    &\leq
    \ccalO \left(\frac{\Delta_{\Phi}  + \kappa^2 \left( \epsilon_1^2 + \epsilon_2^2 \right)}{\eta_1 T} \right)
    +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) L^2 (\tau - 1)^2 \rho^2 \\
    &\quad +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) L^2 (\tau - 1) \sigmaw
    +
    \ccalO \left( \eta_1 \right) \kappa L \frac{\sigmaw}{n}
    +
    \ccalO \left( \frac{\eta_2^2}{\eta_1} \right) n L \sigmapsi, \nonumber
\end{align}

which yields that the averaged model $\wbar_{t}$ approaches a stationary saddle point of $\Phi(\w)$ for proper choices of the step-sizes. It is worth noting that similar to Theorem \ref{Thm: PL-PL convergence}, this result recovers existing results in the literature for the special cases of distributed minimax optimization, i.e. $\tau=1$ \citep{lin2019gradient} and standard federated learning for nonconvex objectives, i.e. when $\epsilon_1, \epsilon_2 \to 0$ \citep{wang2018adaptive,reisizadeh2019fedpaq}.

\iffalse
\begin{remark}
\normalfont
Theorem \ref{Thm: nonconvex-PL convergence} implies that after $T$ iterations of \texttt{FedRobust}, there exists $t$ for which we have

\begin{align}
    \E \norm{\gr \Phi(\wbar_{t})}^2
    &\leq
    \ccalO \left(\frac{\Delta_{\Phi}  + \kappa^2 \left( \epsilon_1^2 + \epsilon_2^2 \right)}{\eta_1 T} \right)
    +
    \ccalO \left( \eta_1^2 + n \eta_1 \eta_2 \right) L^2 (\tau - 1) \left( (\tau - 1)\rho^2 + \sigmaw \right) \\
    &\quad +
    \ccalO \left( \eta_1 \right) \kappa L \frac{\sigmaw}{n}
    +
    \ccalO \left( \frac{\eta_2^2}{\eta_1} \right) n L \sigmapsi,
\end{align}

which approaches a stationary saddle point of $\Phi(\w)$ for proper choices of the step-sizes. It is worth noting that similar to Theorem \ref{Thm: PL-PL convergence}, this result recovers existing results in the literature for the special cases of distributed minimax optimization, i.e. $\tau=1$ \citep{lin2019gradient} and standard federated learning for nonconvex objectives, i.e. when $\epsilon_1, \epsilon_2 \to 0$ \citep{wang2018adaptive,reisizadeh2019fedpaq}.
\end{remark}

\fi

\subsection{Generalization guarantees}

Following the margin-based generalization bounds developed in \cite{bartlett2017spectrally,neyshabur2017pac,farnia2018generalizable}, we consider the following margin-based error measure for analyzing the generalization error in \texttt{FLRA} with general neural network classifiers:

\begin{equation}\label{Generalization Error Measure}
    \mathcal{L}^{\operatorname{adv}}_{\gamma}(\w)
    \coloneqq
    \frac{1}{n}\sum_{i=1}^n {\Pr}_i \left( f_{\w}(h^i_{adv}(\mathbf{X}) )[Y] - \max_{j\neq Y} f_{\w}(h^i_{adv}(\mathbf{X}) )[j] \le \gamma \right).
\end{equation}

Here, $h^i_{adv}$ denotes the worst-case affine transformation for node $i$ in the maximization problem \eqref{Eq: AFL def}; $\Pr_i$ denotes the probability measured by the underlying distribution of node $i$, and $f_{\w}(\mathbf{x})[j]$ denotes the output of the neural network's last softmax layer for label $j$. Note that for $\gamma=0$, the above definition reduces to the average misclassfication rate under the distribution shifts, which we simply denote by $\mathcal{L}^{\operatorname{adv}}(\w)$. We also use $\hat{\mathcal{L}}^{\operatorname{adv}}_\gamma(\w)$ to denote the above margin risk for the empirical distribution of samples, where we replace the underlying $\Pr_i$ with $\hat{\Pr}_i$ being the empirical probability evaluated for the $m$ samples of node $i$. The following theorem bounds the difference of the empirical and underlying margin-based error measures in \eqref{Generalization Error Measure} for a general deep neural network function. The bound is based on the spectral norms of the weight matrices across layers which provide upper-bounds for the Lipschitz and smoothness coefficients of the neural network.

\begin{theorem}\label{Thm: generalization}
Consider an $L$-layer neural network with $d$ neurons per layer. We assume the activation function of the neural network $\sigma$ satisfies $\sigma(0)=0$ and $\max_t\{|\sigma'(t)|,|\sigma''(t)|\}\le 1$. Suppose the same Lipschitzness and smoothness condition holds for loss $\ell$, and $\Vert\mathbf{X}\Vert_2\le B$. We assume the weights of the neural network are spectrally regularized such that for $M>0$:

\begin{align}
    \frac{1}{M} \le \left( \prod_{i=1}^d\Vert\w_i \Vert_{\sigma} \right)^{1/d}
    \le
    M, \nonumber
\end{align}

with $\Vert\cdot\Vert_{\sigma}$ denoting the maximum singular value, i.e., the spectral norm. Also, suppose that for $\eta>0$,

\begin{align}
\operatorname{Lip}(\nabla f_{\w}) := \sum_{i=1}^d\prod_{j=1}^i\Vert\w_i \Vert_\sigma \le \lambda(1-\eta)\nonumber
\end{align}

holds where $\operatorname{Lip}(\nabla f_{\w})$ upper-bounds the Lipschitz coefficient of the gradient $\nabla_{\mathbf{x}}\ell(f_{\w}(\mathbf{x},y))$. Then, for every $\xi>0$ with probability at least $1 - \xi$ the following holds for all feasible weights $\w$:

\begin{align}
    \mathcal{L}^{\operatorname{adv}}(\w) - \hat{\mathcal{L}}^{\operatorname{adv}}_{{\gamma}}(\w)
    \le
    \mathcal{O} \left( \sqrt{ \frac{ B^2L^2d\log(Ld)\lambda^2\bigl(\prod_{i=1}^L\Vert \w_i\Vert_{\sigma} \sum_{i=1}^L\frac{\Vert \w_i\Vert^2_F}{\Vert \w_i\Vert^2_{\sigma}}\bigr)^2+L\log\frac{nmL\log(M)}{\eta\xi}  }{m \gamma^2 (\lambda-(1+B)\operatorname{Lip}(\nabla f_{\w}))^2} }\right). \nonumber
\end{align}

\end{theorem}

\begin{proof}
We defer the proof to Appendix \ref{appendix: proof of Thm generalization}.
\end{proof}

This theorem gives a non-asymptotic bound on the generalization risk of \texttt{FLRA} for spectrally regularized neural nets with their smoothness constant bounded by $\lambda$. Thus, we can control the generalization performance by properly regularizing the Lipschitzness and smoothness degrees of the neural net. Note that this result requires a smooth and Lipschitz activation function in the neural network, such as the exponential linear unit (ELU) activation. In our numerical experiments, we also tried the popular ReLU activation, which does not satisfy the smoothness condition. However, we still observed a satisfactory generalization performance in those experiments, indicating that the above guarantee can practically extends to ReLU-type non-linearities as well.

\subsection{Distributional robustness}

To analyze \texttt{FLRA}'s robustness properties, we draw a connection between \texttt{FLRA} and distributionally robust optimization using optimal transport costs. Consider the optimal transport cost $W_c(P,Q)$ for quadratic cost $c(\mathbf{x},\mathbf{x}')=\frac{1}{2}\Vert \mathbf{x}-\mathbf{x}'\Vert^2_2$ defined as

\begin{align}
W_c(P,Q) \coloneqq \min_{M\in \Pi(P,Q)} \: \E [c(\mathbf{X},\mathbf{X}') ], \nonumber
\end{align}

where $\Pi(P,Q)$ denotes the set of all joint distributions on $(\mathbf{X},\mathbf{X}')$ with marginal distributions $P,Q$. In other words, $W_c(P,Q)$ measures the minimum expected cost for transporting samples between $P$ and $Q$. In order to define a distributionally robust federated learning problem against affine distribution shifts, we consider the following minimax problem:

\begin{equation} \label{Eq: DRO Federeted Learning}
    \min_{\w}\;\frac{1}{n}\sum_{i=1}^n \max_{\Lambda^i,\delta^i}\;\bigl\{ \mathbb{E}_{P^i}\bigl[\ell\bigl(f_{\w} (\Lambda^i\mathbf{X}+\delta^i),Y\bigr) \bigr] -  W_c(P^i_{\mathbf{X}},P^i_{\Lambda^i\mathbf{X}+\delta^i})\bigr\}.
\end{equation}

In this distributionally robust learning problem, we include a penalty term controlling the Wasserstein cost between the original distribution of node $i$ denoted by $P^i$ and its perturbed version under an affine distribution shift, i.e., $P^i_{\Lambda^i\mathbf{X}+\delta^i}$. Note that here we use the averaged Wasserstein cost

\begin{align}
    \frac{1}{n}\sum_{i=1}^n W_c(P^i_{\mathbf{X}},P^i_{\Lambda^i\mathbf{X}+\delta^i}) \nonumber
\end{align}

to measure the distribution shift caused by the affine shifts $(\Lambda^i,\delta^i)_{i=1}^n$. The following theorem shows that this Wasserstein cost can be upper-bounded by a norm-squared function of $\Lambda$ and $\delta$ that appears in the \texttt{FLRA}'s minimax problem.

\begin{theorem}\label{Thm: DRO}
Consider the Wasserstein cost $W_c(P_{\mathbf{X}},P_{\Lambda\mathbf{X}+\delta})$ between the distributions of $\mathbf{X}$ and its affine perturbation $\Lambda\mathbf{X}+\delta$. Assuming $ \Vert \E [\mathbf{X}\mathbf{X}^T] \Vert_{\sigma} \le \lambda$, we have

\begin{align} \label{eq: Thm DRO}
    W_c(P_{\mathbf{X}},P_{\Lambda\mathbf{X}+\delta}) \le \max\{\lambda,1\} \bigl[\Vert \Lambda -I \Vert^2_F + \Vert \delta\Vert^2_2 \bigr].
\end{align}

\end{theorem}

\begin{proof}
We defer the proof to Appendix \ref{appendix: proof of Thm DRO}.
\end{proof}

Substituting the Wasserstein cost in \eqref{Eq: DRO Federeted Learning} with the upper-bound \eqref{eq: Thm DRO} results in the \texttt{FLRA}'s minimax \eqref{eq: FLRA}. As a result, if
\begin{align}
    \frac{\lambda}{n} \sum_{i=1}^n[ \Vert\Lambda^i - I\Vert^2_F + \Vert\delta^i\Vert^2_2] \le \varepsilon^2 \nonumber
\end{align}

holds for the optimized $\Lambda^i,\delta^i$'s, we will also have the averaged Wasserstein cost bounded by

\begin{align}
    \frac{1}{n} \sum_{i=1}^n W_c  (P^i_{\mathbf{X}},P^i_{\Lambda^i\mathbf{X}+\delta^i}) \le \varepsilon^2. \nonumber
\end{align}

Theorem \ref{Thm: DRO}, therefore, shows the \texttt{FLRA}'s minimax approach optimizes a lower-bound on the distributionally robust \eqref{Eq: DRO Federeted Learning}.

config: arxiv


TITLE: What happens if an object stops orbiting the sun?
QUESTION [1 upvotes]: What would happen if an object (like a space ship) was to stop its orbit around the sun. would time slow down with that object (the same way time sped up for the characters in that great film Interstellar). Or even more so, if that object was to stop its orbit around the galaxy so to speak. And so on and so on. At what point is an object considered motionless? Could it be that the finite origin of the big bang has no time?

REPLY [2 votes]: One has to keep in mind why the word "relativity" was coined . It was needed because observations in physics tell us that there exists no absolute frame of reference , no absolute coordinate system. One is free to define coordinate systems  and explore the motions relative to the assumptions as long as Lorentz invariance applies strictly.

What would happen if an object (like a space ship) was to stop its orbit around the sun.

Newtonian physics would take over and the object will fall into the sun with a calculable trajectory.

would time slow down with that object (the same way time sped up for the characters in that great film Interstellar).

The clocks of the space ship would keep ticking and follow the Newtonian predictions until impact. Time does not speed up for the characters in the space ship, it is other reference frames that may see any slight difference because the velocity reached before impact would probably not be large enough for relativistic effects.

Or even more so, if that object was to stop its orbit around the galaxy so to speak. And so on and so on.

Same answer. If General Relativity comes in because of proximity to enormous masses the effect gets more complicated but the answer is similar.

At what point is an object considered motionless?

When the reference frame is taken as the center of mass of the object.( In the case of the sun,above, the center of mass of the sun was assumed, and a relative velocity zero for a delta(t), then newtonian forces take over).

Could it be that the finite origin of the big bang has no time?

????  This has no meaning.


TITLE: Generalizing miracle flatness (Matsumura 23.1) via finite Tor-dimension
QUESTION [14 upvotes]: Let $(A,m_A)$ and $(B,m_B)$ be noetherian local rings and $f:A\rightarrow B$ a local homomorphism.  Let $F = B/m_AB$ be the fiber ring and assume that
$$\mathrm{dim}(B) = \mathrm{dim}(A) + \mathrm{dim}(F).$$
The following Theorem (23.1 in Matsumura's CRT) is really quite a miracle:
Theorem: If $A$ is regular and $B$ is Cohen-Macaulay then $f$ is flat.
I am wondering to what extent this theorem can be generalized.  What I have in mind is a statement of the type:
"Theorem":  If $A$ is $X$ and $B$ is $Y$ then $f$ is of finite Tor-dimension
(i.e. $\mathrm{Tor}^i_A(B,A)=0$ for all $i$ sufficiently large).
Here, $X$ and $Y$ are ring-theoretic conditions which should be strictly weaker than
"regular" and "CM" respectively.  Is the "Theorem" above true just requiring $A$ and $B$ to be normal?
How about both CM? Or maybe CM plus finitely many $(R_i)$?
Any thoughts/ counterexamples?

REPLY [10 votes]: I post this answer to give some intuition about what is really happening behind the scene in the theorem mentioned. If $f:A\rightarrow B$ is flat, then obviously the image of any $A$-regular sequence under $f$ is a $B$-regular sequence. This can be seen by tensoring the $A$-Koszul complex on an $A$-regular sequence, by $B$.
Now let's ask this question: Suppose a map $f:A\rightarrow B$ has the property that it maps any $A$-regular sequence to a $B$-regular sequence. Is $f$ flat then? The answer is no. As an example, you can consider the Frobenius endomorphism $F:A\rightarrow A$ of a local ring of characteristic $p>0$. Obviously it maps every regular sequence to a regular sequence, but $F$ is not flat, unless $A$ is regular, by a theorem of Kunz. Another example is any endomorphism $f$ of a local Cohen-Macaulay ring $(A,\mathfrak{m}_A)$ for which $f(\mathfrak{m}_A)A$ is $\mathfrak{m}_A$-primary. One can see quickly that the image of any regular sequence is a regular sequence, but in general $f$ need not be flat.
The reason for this failure is existence of modules of infinite projective dimension. The condition that $f$ sends any regular sequence to a regular sequence only guarantees that finite free resolutions of $A$-modules stay exact after tensoring by $B$. This quickly follows from Buhsbaum-Eisenbud exactness criterion. (cf. p. 37, Corollary 6.6 in Topics in the homological theory of modules over commutative rings, M. Hochster.)
When $A$ is regular, however, every finite $A$-module has finite projective dimension. That's why in this case the condition that every $A$-regular sequence will be mapped to a $B$ regular sequence by $f$ is equivalent to flatness! (keep in mind that flatness only needs to be checked on finite modules.) The conditions $B$ Cohen-Macaulay and  $\dim B=\dim A+\dim F$ are just meant to guarantee that any $A$-regular sequence is mapped to a $B$-regular sequence, as you can check quickly. To check this, take an $A$-regular sequence $x_1,\ldots,x_t$, extend it to a maximal regular sequence $\underline{x}:=(x_1,\ldots,x_d)$ in $A$, then use the dimension assumption and the fact that $B$ is Cohen-Macaulat to show that $f(\underline{x}):=(f(x_1),\ldots,f(x_d))$ is a regular sequence in $B$.
(Note that on one hand, the inclusion $f(\underline{x})B\subseteq\mathfrak{m}_AB$ gives $\dim B/f(\underline{x})B\geq\dim B/\mathfrak{m}_AB$. On the other hand the map $A/\underline{x}\rightarrow B/f(\underline{x})B$ gives $\dim B/f(\underline{x})B\leq \dim A/\underline{x}+\dim B/\mathfrak{m}_AB=0+\dim B/\mathfrak{m}_AB$. Hence $\dim B/f(\underline{x})B=\dim B-\dim A$.)


TITLE: questions about point set topology
QUESTION [1 upvotes]: Let $X$ be a topological space. $\tau$ be a topology on $X$.
A base $B$ of $\tau$ is a collection of subsets of $X$ such that

$\forall b \in B$, $b \in \tau$
$X$ is covered by the base elements. (aka their union would be $X$)
if $b_1$, $b_2 \in B$, and $\exists p \in b_1\cap b_2$ then $\exists b_3 \in B$ where $p \in b_3 \subseteq b_1\cap b_2$

^straight from class notes and double checked at many places
Then let $A = \left\{ X\right\}$.
Obviously

$X \in \tau$
$X$ covers $X$
is true vacuously since there is only one element in $A$, which is $X$ so there will be no intersection with other base elements.

Therefore $A$ is a base.
Then my question is since $A$ is countable, then $X$ is second countable. Then since we can construct something like this for all topological spaces, therefore all topological spaces are second countable?
Intuitively, this does not make sense because every open subsets should be the union of some base elements.
I know I am wrong, but not sure how I screwed up.

REPLY [1 votes]: Your choice of $A = \{X\}$ is indeed a base for the indiscrete topology, a.k.a the trivial topology $\tau = \{\emptyset,X\}$.
If a collection satisfies those properties, then it is a base for some topology. That doesn't mean that it is the base for an arbitrary topology.
In order for a base $B$ to the base for a topology $\tau$, it must generate all the sets in $\tau$ in addition to the rules you listed.


TITLE: Sobolev embedding: the injection of $H^1(I)$ into $L^2(I)$ is compact
QUESTION [0 upvotes]: Can you help me to explain in detail why we deduce from Theorem 8.8 that the injection of $H^1(I)$ into $L^2(I)$ is compact.

I understand that

$H^1(I)$ is compact embedded in $C(\bar I)$, and
$C(\bar I)$ is continuously embedded in $L^2(I)$

However, I can not see that "the injection of $H^1(I)$ into$L^2(I)$ is compact" follows from 1. and 2.

REPLY [0 votes]: A completely different proof is to use Fourier series. We may assume $I=[-/pi,\pi]$. let $e_n, n\in \bf Z$ the standard basis of $L^2(I)$, $e_n(t)= {1\over \sqrt 2\pi} e^{int}$. Certainly $f_n= {e\over \sqrt {n^2+1}}$ is an orthonormal basis of $H^1$, so that the natural embedding in this basis has a diagonal matrix with eigenvalues $ 1\over \sqrt {n^2+1}$. From this we get that if $P_n$ is the projector onto the subspace generated by $e_k, \vert k \vert \leq n$, $I$ the stabdard embedding and $I_n= I\circ P_n$,  $\vert \vert I- I_n \vert \vert \leq {1\over \sqrt {(n+1)^2+1}}$, so that $I$ is as close as you want from a finite range operator


text:
\begin{document}

\title{Rate of convergence in first-passage percolation under low moments}
\author{Michael Damron \\ \small Georgia Tech, Indiana University \and Naoki Kubota \\ \small Nihon University}
\date{}

\maketitle

\begin{abstract}
We consider first-passage percolation on the $d$ dimensional cubic lattice for $d \geq 2$;
that is, we assign independently to each edge $e$ a nonnegative random weight $t_e$
with a common distribution and consider the induced random graph distance (the passage time), $T(x,y)$. It is known that for each $x \in \mathbb{Z}^d$, $\mu(x) = \lim_n T(0,nx)/n$ exists and that $0 \leq \mathbb{E}T(0,x) - \mu(x) \leq C\|x\|_1^{1/2}\log \|x\|_1$ under the condition $\mathbb{E}e^{\alpha t_e}<\infty$ for some $\alpha>0$. By combining tools from concentration of measure with Alexander's methods, we show how such bounds can be extended to $t_e$'s with distributions that have only low moments. For such edge-weights, we obtain an improved bound $C (\|x\|_1 \log \|x\|_1)^{1/2}$ and bounds on the rate of convergence to the limit shape.
\end{abstract}

\section{Introduction}

\subsection{The model}
Let $d \geq 2$.
Denote the set of nearest-neighbor edges of $\mathbb{Z}^d$ by $\mathcal{E}^d$,
and let $(t_e)_{e \in \mathcal{E}^d}$ be a collection of non-negative random variables indexed by $\mathcal{E}^d$. For $x,y \in \mathbb{Z}^d$, define the passage time
\[
\tau(x,y) = \inf_{\gamma : x \to y} \tau(\gamma)\ ,
\]
where $\tau(\gamma) = \sum_{e \in \gamma} t_e$ and $\gamma$ is any lattice path from $x$ to $y$.

We will assume that $\mathbb{P}$, the distribution of $(t_e)$, is a product measure
satisfying the following conditions:
\begin{itemize}
 \item[\bf (A1)]
  $\mathbb{E}Y^2 < \infty$,
  where $Y$ is the minimum of $d$ i.i.d.~copies of $t_e$.
 \item[\bf (A2)]
  $\mathbb{P}(t_e=0) < p_c$,
  where $p_c$ is the threshold for $d$-dimensional bond percolation.
\end{itemize}
We now comment on assumptions (A1) and (A2).
From Lemma~3.1 of \cite{CD},
(A1) guarantees that $\mathbb{E} \tau(0,y)^{4-\eta}<\infty$ for all $\eta>0$ and $y \in \mathbb{Z}^d$.
Conversely, it is sufficient for (A1) that
$\mathbb{E} t_e^{(2+\epsilon)/d}$ is finite for some $\epsilon>0$.
On the other hand, (A2) ensures that
\begin{equation}\label{eq:geodesics}
\mathbb{P}(\exists \text{ a geodesic from } x \text{ to } y) = 1 \text{ for all } x,y \in \mathbb{Z}^d\ ,
\end{equation}
where a geodesic is a path $\gamma$ from $x$ to $y$ that has $\tau(\gamma) = \tau(x,y)$.
Under assumptions (A1) and (A2), equation
(1.13) and Theorem~{1.15} of \cite{Kes86} show that
there exists a norm $\mu (\cdot)$ on $\mathbb{R}^d$, which is called the time constant, such that
for $x \in \mathbb{Z}^d$, $\mathbb{P}$- almost surely,
\begin{align}
 \lim_{n \to \infty}\frac{1}{n}\tau (0,nx)
 = \lim_{n \to \infty}\frac{1}{n}\mathbb{E} \tau (0,nx)
 = \inf_{n \geq 1}\frac{1}{n}\mathbb{E} \tau (0,nx)
 = \mu (x).
 \label{eq:t-c}
\end{align}
If (A1) is replaced by the condition that
the minimum of $2d$ i.i.d.\,copies of $t_e$ has finite $d$-th moment,
then the \emph{shape theorem} holds; that is,
for all $\epsilon>0$, with probability one,
\begin{equation}\label{eq: shape_theorem}
 (1-\epsilon )B_0 \subset \frac{B(t)}{t} \subset (1+\epsilon )B_0 \text{ for all large }t\ ,
\end{equation}
where
\begin{align*}
 B(t):=\biggl\{ x+h ;x \in \mathbb{Z}^d,\,\tau (0,x) \leq t,\,h \in \Bigl[ -\frac{1}{2},\frac{1}{2} \Bigr]^d \biggr\}
\end{align*}
and $B_0:= \{ x \in \mathbb{R}^d;\mu (x) \leq 1 \}$, the \emph{limit shape}.

\subsection{Main results}
Set $T = \tau(0,x)$. Our results below consist of (a) a bound on the deviation of $\mathbb{E}T$ from $\mu$ under (A1) and (A2) and (b) outer bounds on the rate of convergence to the limit shape under these same conditions and inner bounds under stronger conditions. These should be compared to the results of Alexander \cite{Ale97}, who proved the first two with $\log$ in place of $\sqrt{\log}$ under exponential moments for $t_e$.

\begin{proposition}\label{prop:fluct}
Assume (A1) and (A2).
There exists $C_1$ such that for all $x \in \mathbb{Z}^d$ with $\|x\|_1>1$,
\begin{align*}
\mu(x) \leq \mathbb{E} T \leq \mu (x)+C_1(\|x\|_1\log \|x\|_1)^{1/2}.
\end{align*}
\end{proposition}

\begin{proof}
This result follows by directly combining the Gaussian concentration inequality we derive below in Theorem~\ref{thm:big_one} with Alexander's method of approximation of subadditive functions \cite{Ale97}. Our final bound is slightly better than the one given by Alexander in \cite{Ale97} because he used only an exponential concentration inequality. The interested reader can see the arXiv version of this paper \cite{DK_arxiv} (version 1).
\end{proof}

\begin{theorem}\label{thm:shape}
Assume (A1) and (A2).
There exists $C_2$ such that with probability one,
\begin{align}
 \frac{B(t)}{t}
 \subset \bigl\{ 1+C_2t^{-1/2} (\log t)^{1/2} \bigr\} B_0 \text{ for all large }t\ .
 \label{eq:outer}
\end{align}
If $\mathbb{E} t_e^\alpha<\infty$ for some $\alpha > 1+1/d$,
then there is $C_3$ such that with probability one,
\begin{align}
 \bigl\{ 1-C_3t^{-1/2} (\log t)^4 \bigr\} B_0
 \subset \frac{B(t)}{t} \text{ for all large }t\ .
 \label{eq:inner}
\end{align}
\end{theorem}
The proof of Theorem~\ref{thm:shape} will be given in Section~\ref{sec:shape}.

\subsection{Relation to previous works}

The question we address here is to determine the minimal moment condition for $t_e$ that will guarantee that the passage time $\tau(0,x)$ is bounded by $\mu(x) + O(\|x\|_1^a)$ for some $a<1$; that is, that the deviation from the norm $\mu(\cdot)$ is sub-linear by a power of $\|x\|_1$. This line of work began with Cox and Durrett \cite{CD}, who found optimal conditions for existence of a shape theorem. They showed that if $Z$ is the minimum of $2d$ i.i.d.\,random variables distributed as $t_e$, then for each $x \in \mathbb{Z}^d$,
\[
\mathbb{E}Z < \infty \Leftrightarrow \tau (0,nx)/n \text{ converges a.s.}
\]
Furthermore
\[
\mathbb{E}Z^d < \infty \Leftrightarrow \text{the shape theorem }\eqref{eq: shape_theorem} \text{ holds}\ .
\]
These conditions do not address the convergence rate, and it is conceivable that the rate gets worse as the weight distribution gets closer to violating the above conditions.

The behavior $\tau(0,x) = \mu(x) + O(\|x\|_1^a)$ is important because it allows a good approximation of $\tau$ by $\mu$, and this is often useful when one knows information about the asymptotic shape. For example, if $x/\mu(x)$ is an exposed point on the boundary of the limit shape, then one can show that geodesics from $0$ to $nx$ stay within Euclidean distance $o(n)$ of the straight line connecting $0$ and $nx$ for all large $n$. However this is only possible if the error exponent $a<1$. Similar geodesic concentration was needed, for example, in the $\log n$ lower bound for the variance for the passage time in $d=2$ for certain atomic distributions \cite[Proposition~2]{ADdiff}. In that work, exponential moments were assumed for $t_e$ precisely to guarantee that $a<1$ (and this was relaxed in \cite{kubota}).

All work on the convergence rate until recently has assumed exponential moments: $\mathbb{E}e^{\alpha t_e}<\infty$ for some $\alpha>0$. Under this condition and (A2), Alexander \cite{Ale97} showed in 1997, building on work of Kesten \cite{Kes93}, that with probability one, for all large $t$,
\[
(1-Ct^{-1/2}\log t)B_0 \subset B(t)/t \subset (1+Ct^{-1/2}\log t)B_0\ .
\]
The proof of this result combined Kesten's exponential concentration inequality for $\tau(0,x)$, along with Alexander's bound on $\mathbb{E}\tau(0,x) - \mu(x)$ and direction-independent estimates: there exists $C$ such that for all large $x \in \mathbb{Z}^d$,
\begin{equation}\label{eq: nonrandom}
 \mathbb{E}\tau(0,x) -\mu(x) \leq C\| x \|_1^{1/2}\log \| x \|_1.
\end{equation}
The reason these theorems were unattainable under weaker moment conditions is the lack of available concentration inequalities for the passage time $\tau (0,x)$.

Zhang \cite{Zha10} was one of the first to establish forms of concentration and rate of convergence for $\tau(0,nx)/n$ under only existence of $m$ moments for $t_e$. He obtained estimates for central moments for $\tau(0,x)$ and a bound for the left side of \eqref{eq: nonrandom}, but only for $x = ne_1$, a multiple of the first coordinate vector, under the condition $\mathbb{E}t_e^{1+\eta}<\infty$ for some $\eta>0$. The central moment bound was improved by Chatterjee-Dey in \cite[Proposition~5.1]{CDey} by removing logarithmic factors under the same moment assumption. These works do not imply polynomial rates of convergence for the shape theorem because the bound of Zhang on the difference $\mathbb{E}\tau(0,x) - \mu(x)$ is only valid in the coordinate directions (due to use of a reflection argument), and direction-independent estimates are needed.

The first bounds for the left side of \eqref{eq: nonrandom} without an exponential moment assumption are due to Kubota \cite[Theorem~1.2]{kubota},
who showed that if $\mathbb{E}t_e^\alpha<\infty$ for some $\alpha>1$ and (A2) holds, then one has a bound for the left side of \eqref{eq: nonrandom} of $C\| x \|_1^{1-1/(6d+12)}(\log \| x \|_1)^{1/3}$. The present work grew out of attempts to improve this inequality. Our Proposition~\ref{prop:fluct} does so both in the moment assumption and in the rate of convergence. We only require $(2/d)+\epsilon$ moments for $t_e$ (note that this exponent approaches 0 as $d \to \infty$), whereas Kubota needed $1+\epsilon$. Our proofs rely on a concentration inequality which is derived under low moments using a block tensorization procedure (see Lemma~\ref{lem:ent_box}).

From our inequality for \eqref{eq: nonrandom}, we conclude a strong rate of convergence in the shape theorem under low moments. In Theorem~\ref{thm:shape}, we decrease Alexander's outer bound of the shape to
$t^{-1/2}(\log t)^{1/2}$ with only assumptions (A1) and (A2). For the inner bound of the shape, we obtain a rate of $t^{-1/2}(\log t)^4$ under existence of $\alpha$ moments for some $\alpha > 1+1/d$ and (A2). Here the low moment condition of $t_e$ plays a big role, since high edge-weights will prevent certain vertices from entering $B(t)$. The condition on $\alpha$ above comes from optimizing large-deviation bounds from recent work of Ahlberg \cite{Ahl}.

\begin{remark}
After this work was completed, \cite{DHS} obtained sub-diffusive concentration inequalities for $\tau(0,x)$, extending work of Bena\"im-Rossignol \cite{BR} to general distributions. They proved, in particular, if $\mathbb{E}t_e^2(\log t_e)_+<\infty$ for $d \geq 2$, then
\begin{equation}\label{eq: DHS}
\mathbb{P}\left( \tau(0,x) < \mathbb{E}\tau(0,x) - \lambda \sqrt{\frac{\|x\|_1}{\log \|x\|_1}} \right) \leq e^{-c\lambda} \text{ for } \|x\|_1>1,~ \lambda \geq 0\ .
\end{equation}
\eqref{eq: DHS} may be used in Alexander's method to obtain our Proposition~\ref{prop:fluct}, but with a worse moment condition. One may ask if it can be used to prove a sub-gaussian bound $\mathbb{E}\tau(0,x) \leq \mu(x) + o(\sqrt{\|x\|_1})$, as in the case of directed polymers \cite{AZ}, but no such theorem exists in an undirected model. The main complication arises from the extra logarithmic factor coming from Alexander's method, which negates the gain in the scale from \eqref{eq: DHS}.
\end{remark}

\section{Concentration inequality}\label{sec: entropy}

Our first task will be to prove the following lower-tail concentration result.
\begin{theorem}\label{thm:big_one}
Assume (A1) and (A2).
There exists $C_1>0$ such that
\begin{equation}\label{eq: main_result}
\mathbb{P}\left( T - \mathbb{E}T \leq -t \sqrt{\|x\|_1} \right) \leq e^{-C_1t^2} \text{ for } t \geq 0,~ x \in \mathbb{Z}^d\ .
\end{equation}
\end{theorem}
This theorem extends Talagrand's \cite[Theorem~8.2.3]{Talagrand} concentration inequality, which states that \eqref{eq: main_result} holds under assumptions (A2) and $\mathbb{E}t_e^2<\infty$. To derive Theorem~\ref{thm:big_one},
we use the entropy method of Bucheron-Lugosi-Massart (see \cite{BLM} for an introduction).

\begin{definition}
If $X$ is a non-negative random variable with $\mathbb{E}X<\infty$ then the entropy of $X$ is defined as $Ent~X = \mathbb{E}X\log X - \mathbb{E}X \log \mathbb{E}X$.
\end{definition}

Theorem~\ref{thm:big_one} is a straightforward consequence of the following bound using the Herbst argument (see \cite[p. 122]{BLM}).
\begin{theorem}\label{thm: main_thm}
Assume (A1) and (A2). There exist $C_2,C_3>0$ such that
\[
Ent~e^{\lambda T} \leq C_2\|x\|_1 \lambda^2 \mathbb{E}e^{\lambda T} \text{ for } -C_3\leq \lambda \leq 0, ~ x \in \mathbb{Z}^d\ .
\]
\end{theorem}
Theorem~\ref{thm: main_thm} will be proved in Section~\ref{sec: main_proof}.

\subsection{Properties of entropy}

We begin with some basic results on entropy. This material is taken from \cite[Section~2]{DHS1}, though it appears in various places, including \cite{BLM}. There is a variational characterization of entropy \cite[Section~5.2]{ledoux} that we will use.
\begin{proposition}\label{prop: variation}
We have the formula $Ent~X = \sup \bigl\{ \mathbb{E}XZ : \mathbb{E}e^Z \leq 1 \bigr\}$.
\end{proposition}
This characterization is typically used in the form: for any random variable $W$,
\begin{equation}\label{eq: exp_holder}
\mathbb{E}XW \leq Ent~X + \mathbb{E}X \log \mathbb{E}e^W.
\end{equation}

The second fact we need is a tensorization for entropy. For an edge $e$, write $Ent_e X$ for the entropy of $X$ considered as a function of only $t_e$ (with all other weights fixed).
\begin{proposition}\label{prop: tensor}
If $X \in L^2$ is a measurable function of $(t_e)$ then
\[
Ent~X \leq \sum_e \mathbb{E} Ent_e~X\ .
\]
\end{proposition}

\subsection{Application of Boucheron-Lugosi-Massart}
We say that $e \in \mathcal{E}^d$ is pivotal for $T$ if $e$ is in the intersection of all geodesics of $T$.
A pivotal edge has the property that increasing its weight, while leaving all other weights unchanged,
can change $T$ (and no other edges have this property).
Let $\mathrm{Piv}(0,x)$ be the set of all pivotal edges for $T$.
Our first bound toward Theorem~\ref{thm: main_thm} is the next proposition.
\begin{proposition}\label{prop: entropy_bound}
There exists a constant $C_4$ such that
\[
Ent~e^{\lambda T} \leq C_4 \lambda^2 \mathbb{E}\left[ e^{\lambda T} \# \mathrm{Piv}(0,x) \right]
\text{ for } \lambda \leq 0.
\]
\end{proposition}

Given a nonempty subset $S$ of $\mathcal{E}^d$, denote by $t_S$ a configuration $(t_e)_{e \in S}$
restricted to the edges in $S$.
Let $\{e_1, e_2, \ldots\}$ be an enumeration of $\mathcal{E}^d$.
Then, for each $e_i$, deterministically choose one of its endpoints $x_i$
and consider the box $B_i:=\{ v \in \mathbb{Z}^d;\|v-x_i\|_\infty \leq 1 \}$.
In addition, let $S_i$ be the edges between nearest-neighbor points of $B_i$:
\[
S_i :=
\bigl\{\{u,v\} \in \mathcal{E}^d : \|u-x_i\|_\infty \leq 1 \text{ and } \|v-x_i\|_\infty \leq 1
\bigr\}.
\]
Furthermore, set $f(x) := x\log x$ and
note that $f$ is convex on $[0,\infty)$ (with $f(0)=0$).

\begin{lemma}\label{lem:ent_box}
We have
\begin{align}\label{eq:ent_box}
 Ent~e^{\lambda T} \leq \sum_{i=1}^\infty \mathbb{E} Ent_{S_i}~e^{\lambda T},
\end{align}
where $Ent_{S_i}~e^{\lambda T}$ is the entropy of $e^{\lambda T}$
considered as a function of only $t_{S_i}$.
\end{lemma}
\begin{proof}

For each $i \geq 1$,
\[
\mathbb{E}Ent_{e_i} e^{\lambda T} = \iint f(e^{\lambda T})~\mathbb{P}(\text{d}t_{e_i})~\mathbb{P}(\text{d}t_{e_i^c}) - \int f\left( \int e^{\lambda T}~\mathbb{P}(\text{d}t_{e_i}) \right)~\mathbb{P}(\text{d}t_{e_i^c})\ .
\]
Here the measure $\mathbb{P}(\text{d}t_{e_i^c})$ represents the joint distribution of the edge-weights outside $e_i$.
Since $f$ is convex, Jensen's inequality shows that this is bounded above by
\[
\iint f(e^{\lambda T})~\mathbb{P}(\text{d}t_{S_i})~\mathbb{P}(\text{d}t_{S_i^c}) - \int f\left( \int e^{\lambda T}~\mathbb{P}(\text{d}t_{S_i}) \right)~\mathbb{P}(\text{d}t_{S_i^c}) = \mathbb{E}Ent_{S_i}~e^{\lambda T}
\]
Therefore Proposition~\ref{prop: tensor} implies that $Ent~e^{\lambda T}
 \leq \sum_{i=1}^\infty \mathbb{E} Ent_{e_i}~e^{\lambda T}
 \leq \sum_{i=1}^\infty \mathbb{E}Ent_{S_i}~e^{\lambda T}$.
\end{proof}

Let $T_i$ be the variable $T$ when the weights in $S_i$
are replaced by independent copies,
and let $\mathbb{E}_{S_i}'$ be an average over the variables in $S_i$ and their independent copies. The following lemma is nearly identical to \cite[Theorem~6.15]{BLM}, so we omit the proof.
\begin{lemma}\label{lem:yeah}
We have for $\lambda \leq 0$ and $i \geq 1$,
\begin{equation}\label{eq: yeah}
Ent_{S_i} e^{\lambda T} \leq \lambda^2 \mathbb{E}'_{S_i} \bigl[ e^{\lambda T}(T_i-T)_+^2 \bigr].
\end{equation}
\end{lemma}

Now we are in a position to prove Proposition~\ref{prop: entropy_bound}.

\begin{proof}[\bf Proof of Proposition~\ref{prop: entropy_bound}]
Lemmata~\ref{lem:ent_box} and \ref{lem:yeah} imply that
\begin{align}\label{eq:replace_bound}
 Ent~e^{\lambda T}
 \leq \lambda^2 \sum_{i=1}^\infty
      \mathbb{E} \Bigl[ \mathbb{E}'_{S_i} \bigl[ e^{\lambda T}(T_i-T)_+^2 \bigr] \Bigr].
\end{align}
To estimate the right side,
we first show that
\begin{align}\label{eq:difference}
 (T_i-T)_+ = (T_i-T)_+\mathbf{1}_{\{\mathrm{Piv}(0,x) \cap S_i \neq \emptyset\}}((t_e)).
\end{align}
We show that if $T_i >T$, then $\mathbf{1}_{\{\mathrm{Piv}(0,x) \cap S_i \neq \emptyset\}}((t_e)) =1$. So suppose that $\mathrm{Piv}(0,x)$ does not intersect $S_i$ in $(t_e)$; we must show that $(T_i-T)_+=0$. Under this assumption, there is a geodesic $\gamma$ in $(t_e)$ from $0$ to $x$ such that $\gamma$ does not contain edges in $S_i$, so in the configuration $(t_e')$, which equals $(t_e)$ off $S_i$ and equals the independent weights on $S_i$, the passage time of $\gamma$ is the same as in $(t_e)$.
This means that $T \geq T_i$ and \eqref{eq:difference} follows.

We next show that
\begin{equation}\label{eq: new}
(T_i-T)_+ \leq \sum_{\{u,v\} \in S_i} T_i(u,v),
\end{equation}
where $T_i(u,v)$ is the minimal passage time among all paths from $u$ to $v$
with edges in $S_i$ in the configuration $(t_e')$.
For $\{u,v\} \in S_i$, let $G_i(u,v)$ be a path with edges in $S_i$ from $u$ to $v$ with passage time in $(t_e')$ equal to $T_i(u,v)$. Let $\gamma$ be a (vertex self-avoiding) path from $0$ to $x$ with passage time in $(t_e)$ equal to $T$. Such a path exists by removing loops from a geodesic from $0$ to $x$. Define $\gamma'$ by replacing each of
its edges $\{u,v\} \in S_i$ by the path $G_i(u,v)$.
Then, the passage time of $\gamma'$ in the configuration $(t_e')$ is bounded above by $T+ \sum_{\{u,v\} \in \gamma \cap S_i} T_i(u,v) \leq T+ \sum_{\{u,v\} \in S_i} T_i(u,v)$,
and this shows \eqref{eq: new}.

By \eqref{eq:replace_bound}, \eqref{eq:difference} and \eqref{eq: new},
\begin{align*}
 Ent~e^{\lambda T}
 &\leq \lambda^2 \sum_{i=1}^\infty \mathbb{E} \Biggl[ \mathbb{E}'_{S_i} \Biggl[
       e^{\lambda T} \Biggl( \sum_{\{u,v\} \in S_i} T_i(u,v) \Biggr)^2
       \mathbf{1}_{\{\mathrm{Piv}(0,x) \cap S_i \neq \emptyset\}}((t_e)) \Biggr] \Biggr]\\
 &\leq \lambda^2 \mathbb{E} \Biggl( \sum_{\{u,v\} \in S_1} T_1(u,v) \Biggr)^2
       \mathbb{E} \bigl[ e^{\lambda T} C_4 \# \mathrm{Piv}(0,x) \bigr].
\end{align*}
for some constant $C_4$.
Note that, since $\mathbb{E}Y^2<\infty$ and there are at least $d$ (edge) disjoint paths between $u$ and $v$ with edges in $S_1$, the argument of Cox-Durrett \cite[Lemma~3.1]{CD} implies that
$\mathbb{E}T_1(u,v)^2<\infty$ for all $\{u,v\} \in S_1$.
Hence, Proposition~\ref{prop: entropy_bound} follows.
\end{proof}

\subsection{Proof of Theorem~\ref{thm: main_thm}}\label{sec: main_proof}
To prove Theorem~\ref{thm: main_thm}, we first show that
there exist $C_5$ and $C_6$ such that
for $\lambda \in (-C_5,0)$,
\begin{align}\label{eq:pre_main}
 \mathbb{E}\left[ e^{\lambda T} \#\mathrm{Piv}(0,x) \right] \leq C_6 \|x\|_1 \mathbb{E} e^{\lambda T}.
\end{align}

For the proof of \eqref{eq:pre_main}, for $c>0$ to be determined later,
we divide the left side of \eqref{eq:pre_main} into the following two parts:
\begin{equation}\label{eq: decomposition}
\mathbb{E} \left[ e^{\lambda T}\# \mathrm{Piv}(0,x) \right] \leq c\mathbb{E} \left[ e^{\lambda T}T \right] + \mathbb{E} \left[ e^{\lambda T} \# \mathrm{Piv}(0,x) \mathbf{1}_{\{ cT < \#\mathrm{Piv}(0,x)\}}\right]\ .
\end{equation}
Note that $T$ is an increasing function of $(t_e)$ whereas $e^{\lambda T}$ is decreasing (since $\lambda \leq 0$), so the Chebyshev association inequality \cite[Theorem~2.14]{BLM} gives
\begin{equation}\label{eq: stepone}
 \mathbb{E} \bigl[ e^{\lambda T} T \bigr]
 \leq \mathbb{E}e^{\lambda T} \mathbb{E}T
 \leq M \|x\|_1 \mathbb{E} e^{\lambda T},
\end{equation}
where $M:= \mathbb{E} \tau(0,e_1)$.
Therefore, the first term of \eqref{eq: decomposition} is harmless,
and we are left to deal with the second term.
To this end, we give the following proposition.
\begin{proposition}\label{prop: kesten_bound}
Assume (A2).
We can choose $c>0$ such that for some $\alpha,C_7>0$,
\[
\mathbb{E} e^{\alpha \phi_x} \leq C_7 \text{ for all } x\ ,
\]
where $\phi_x= \#\mathrm{Piv}(0,x) \mathbf{1}_{\{cT < \#\mathrm{Piv}(0,x)\}}$.
\end{proposition}
\begin{proof}
We will use a result of Kesten \cite[Proposition~5.8]{Kes86}, which says that if $\mathbb{P}(t_e=0)<p_c$ then there exist $a,C_8,C_9>0$ such that for all $m \in \mathbb{N}$,
\begin{align}\label{eq:kesten}
\mathbb{P}\bigl( \exists \text{ self-avoiding } \gamma \text{ starting at }0 \text{ with } \#\gamma \geq m \text{ but } \tau(\gamma) < am \bigr) \leq C_8e^{-C_9m}\ .
\end{align}
Let $A_m$ be the event that there is a self-avoiding path $\gamma$ starting at $0$ with $\#\gamma = m$ but $\tau(\gamma) < a \#\gamma$. $A_m$ implies the event in the left side in \eqref{eq:kesten}, so for all $m \geq 0$, $\mathbb{P}(A_m) \leq C_8e^{-C_9m}$. Denote by $A'_n$ the event that there is a self-avoiding path $\gamma$
starting at $0$ with $\#\gamma \geq n$ but $\tau(\gamma)<a\#\gamma$.
Then, there is a constant $C_{10}$ such that for $n \geq 0$,
\begin{align*}
 \mathbb{P}(A'_n)
 \leq \sum_{m=n}^\infty \mathbb{P}(A_m)
 \leq \sum_{m=n}^\infty C_8e^{-C_9m}
 \leq C_{10}e^{-C_9n},
\end{align*}
which implies that $\mathbb{P}(\phi_x \geq n) \leq \mathbb{P}(\{ \phi_x \geq n \} \cap (A'_n)^c)+C_{10}e^{-C_9n}$. On the event $\{ \phi_x \geq n \} \cap (A'_n)^c$ for $n \geq 1$, we have $cT<\# \mathrm{Piv}(0,x)$ and $\# \mathrm{Piv}(0,x) \geq n$,
so that, letting $\pi$ be a (self-avoiding) geodesic from $0$ to $x$, one has $\#\pi \geq \# \mathrm{Piv}(0,x) \geq n$, so
\[
T=\tau(\pi) \geq a\#\pi \geq a \# \mathrm{Piv}(0,x) > acT.
\]
With these observations, if we choose $c:=a^{-1}$, then
$\mathbb{P}(\{ \phi_x \geq n \} \cap (A'_n)^c)$ is equal to zero.
This means that $\mathbb{P}(\phi_x \geq n) \leq C_{10}e^{-C_9n}$, and therefore,
by taking $\alpha:=C_9/2$, $\mathbb{E} e^{\alpha \phi_x}
 \leq C_{10} \sum_{m=1}^\infty e^{-C_9m/2}<\infty$, which proves the proposition.
\end{proof}

Return to the second term of \eqref{eq: decomposition}.
For the constant $c$ chosen in the proposition above, \eqref{eq: exp_holder} implies that the second term of \eqref{eq: decomposition}
is bounded above by
\[
\alpha^{-1}(Ent~e^{\lambda T} + \mathbb{E}e^{\lambda T} \log \mathbb{E}e^{\alpha \phi_x}) \leq \alpha^{-1}(Ent~e^{\lambda T} + (\log C_7) \mathbb{E}e^{\lambda T})\ .
\]
We put this back in \eqref{eq: decomposition} along with \eqref{eq: stepone} for
\[
\mathbb{E}\left[e^{\lambda T} \#\mathrm{Piv}(0,x) \right] \leq \alpha^{-1} Ent~e^{\lambda T} + (cM\|x\|_1 + \alpha^{-1} \log C_7) \mathbb{E}e^{\lambda T}\ .
\]
Placing this together with \eqref{eq: stepone} in \eqref{eq: decomposition} shows \eqref{eq:pre_main}. To finish the proof of Theorem~\ref{thm: main_thm}, combine \eqref{eq:pre_main} with Proposition~\ref{prop: entropy_bound} for
\[
\left( 1-\frac{C_4 \lambda^2}{\alpha}\right) Ent~e^{\lambda T} \leq C_4\lambda^2 \left( cM\|x\|_1+ \frac{\log C_7}{\alpha}\right)  \mathbb{E}e^{\lambda T}\ .
\]
If $-\sqrt{\frac{\alpha}{2C_4}} < \lambda < 0$, then one obtains the bound in Theorem~\ref{thm: main_thm}.

\section{Proof of Theorem~\ref{thm:shape}}\label{sec:shape}
We first show \eqref{eq:outer}
following the strategy of the proof of Theorem~3.1 of \cite[p.48]{Ale97}. The main difference here is the exponent on the $\log$ in \eqref{eq:restrict} and that Theorem~\ref{thm:big_one} replaces Eq.~(3.7) in \cite{Ale97}.

\begin{proof}[\bf Proof of (\ref{eq:outer}) in Theorem~\ref{thm:shape}]
We start by showing that there exists a constant $C_1$ such that with probability one,
\begin{align}
 B(n) \cap \mathbb{Z}^d \subset \{ n+C_1(n\log n)^{1/2} \} B_0
 \label{eq:restrict}
\end{align}
for all large $n$.
For $C>0$ and $n \in \mathbb{N}$, let $A_n^+(C)$ be the event that
there exists $y_n \in B(n) \cap \mathbb{Z}^d$ such that
$y_n \not\in \{ n+C(n\log n)^{1/2} \} B_0$.
At first, assume that $A_n^+(C)$ occurs.
Then $\tau (0,y_n) \leq n$ and $\mathbb{E} \tau (0,y_n) \geq \mu (y_n)>n+C(n\log n)^{1/2}$, so that
\begin{align}
 \tau (0,y_n)-\mathbb{E} \tau (0,y_n) \leq n-\mu (y_n)<-C(n\log n)^{1/2}.
 \label{eq:alex_shape}
\end{align}
In the case $\mu (y_n) \leq 2n$,
since $\mu(\cdot)$ is a norm on $\mathbb{R}^d$,
\eqref{eq:alex_shape} yields a constant $C_2$ such that
\begin{align*}
 \tau (0,y_n)-\mathbb{E} \tau (0,y_n)<-CC_2(\|y_n\|_1\log \|y_n\|_1 )^{1/2}.
\end{align*}
In the case $\mu (y_n)>2n$,
by the first inequality in \eqref{eq:alex_shape},
\begin{align*}
 \tau (0,y_n)-\mathbb{E} \tau (0,y_n) \leq -\mu (y_n)/2
 &<-CC_3(\|y_n\|_1 \log \|y_n\|_1)^{1/2}
\end{align*}
for some constant $C_3$.
With these observations,
on the event $\liminf_{n \to \infty}A_n^+(C)$,
\begin{align}
 \liminf_{y \to \infty} \frac{\tau (0,y)-\mathbb{E} \tau (0,y)}{(\|y\|_1\log \|y\|_1)^{1/2}}
 \leq -CC_4
 \label{eq:contradict}
\end{align}
where $C_4:=C_2 \wedge C_3$.
On the other hand, Theorem~\ref{thm:big_one} gives $C_5$ such that for $x \in \mathbb{Z}^d$,
\begin{align*}
 \mathbb{P} \left( \tau (0,x)-\mathbb{E} \tau(0,x) \leq -\frac{CC_4}{2}(\|x\|_1\log \|x\|_1)^{1/2} \right)
 \leq \|x\|_1^{-C^2C_4^2C_5/4}.
\end{align*}
Choose $C:=(8d)^{1/2}/(C_4C_5^{1/2})$.
By Borel--Cantelli, almost surely, $\tau(0,x) -\mathbb{E} \tau(0,x) > -\frac{CC_4}{2}(\|x\|_1\log \|x\|_1)^{1/2}$ for all large $x \in \mathbb{Z}^d$.
This together with \eqref{eq:contradict} implies \eqref{eq:restrict}.

To show \eqref{eq:outer},
note that $[-1/2,1/2]^d \subset (\lceil t \rceil \log \lceil t \rceil)^{1/2}B_0$ for sufficiently large $t$.
Since $B(t)$ is increasing in $t$, \eqref{eq:restrict} implies that
with probability one, for all large $t$,
\begin{align*}
 \frac{B(t)}{t}
 \subset \frac{\lceil t \rceil}{t} \frac{B(\lceil t \rceil)}{\lceil t \rceil}
 \subset \Bigl( 1+\frac{1}{t} \Bigr)
         \left\{ 1+(C_1+1)\lceil t \rceil^{-1/2} (\log \lceil t \rceil)^{1/2} \right\}B_0,
\end{align*}
and therefore \eqref{eq:outer} follows.
\end{proof}

Next we show \eqref{eq:inner}. We will use a result of Zhang \cite[Theorem~2]{Zha10}. For any two subsets $A$ and $B$ of $\mathbb{Z}^d$, define $\tau(A,B)$ as the minimal passage time of a path from a vertex in $A$ to one in $B$. If $\mathbb{E} t_e^\alpha<\infty$ for some $\alpha>1$, then for $k \geq 1$, \cite[Theorem~2]{Zha10} gives $C_6$ and $C_7$ (which may depend on $k$) such that
for all $\ell_1$-unit vectors $\xi \in \mathbb{R}^d$,
\begin{align}\label{eq:zhang}
\begin{split}
 \mathbb{P} \bigl( \bigl| \tau (D_m(0),D_m(m\xi ))-\mathbb{E} \tau (D_m(0),D_m(m\xi )) \bigr|
 \geq m^{1/2}(\log m)^4 \bigr)
 \leq C_6m^{-k},
\end{split}
\end{align}
where $D_m(v):=v+[-C_7(\log m)^2,C_7(\log m)^2]^d$ for $v \in \mathbb{Z}^d$.

\begin{proof}[\bf Proof of (\ref{eq:inner}) in Theorem~\ref{thm:shape}]
Assume that $\mathbb{E} t_e^\alpha<\infty$ for some $\alpha> 1+1/d$. Let
\begin{align*}
 B_0(n):=n \bigl\{ 1-Cn^{-1/2}(\log n)^4 \bigr\} B_0 \cap \mathbb{Z}^d \text{ for } n \geq 1,
\end{align*}
where $C$ is a constant to be chosen later.
By the same argument as in the last paragraph of the above proof,
it suffices to prove that with probability one,
\begin{align}\label{eq:discrete}
 B_0(n) \subset B(n)
\end{align}
for all large $n \in \mathbb{N}$.
A union bound gives
\begin{align*}
 \mathbb{P} (B_0(n) \not\subset B(n) \text{ for some } n \geq 1)
 \leq \sum_{n \geq 1} \sum_{v \in B_0(n)} \mathbb{P} (\tau(0,v) >n).
\end{align*}
We would like to show this sum is finite. Then Borel--Cantelli will finish the proof.

First we show that there exists $C_8>0$ such that
\begin{equation}\label{eq: first_case}
\sum_{n \geq 1} \sum_{\|v\|_1 \leq C_8 n} \mathbb{P}(\tau(0,v) > n) < \infty\ .
\end{equation}
For this, we use \cite[Theorem~4]{Ahl}. Let $Z$ be the minimum of $2d$ i.i.d. copies of $t_e$.
\begin{lemma}[Ahlberg]\label{lem: ahlberg}
Assume that $\mathbb{E}Z^\beta<\infty$ for some $\beta>0$. For every $\epsilon>0$ and $q \geq 1$ there exists $M=M(\beta,\epsilon,q)$ such that for every $z \in \mathbb{Z}^d$ and $s \geq \|z\|_1$,
\[
\mathbb{P}(\tau(0,z) - \mu(z) > \epsilon s) \leq M \mathbb{P}(Z \geq s/M)  + \frac{M}{s^q}\ .
\]
\end{lemma}
We will use this lemma with $\epsilon=1$ and $q=d+2$. It will also be used later in \eqref{eq: from_referee} with $q=2d+3$. Since $\mu(\cdot)$ is a norm on $\mathbb{R}^d$,
one can take a constant $C_9 \geq 1$ satisfying
\begin{equation}\label{eq: norm_equiv}
C_9^{-1} \|v\|_1 \leq \mu(v) \leq C_9 \|v\|_1 \text{ for all } v \in \mathbb{R}^d\ .
\end{equation}
If $\|v\|_1 \leq C_9^{-1} n/2$, then $\{\tau(0,v) > n\} \subset \{\tau(0,v)-\mu(v)>n/2\}$.
Lemma~\ref{lem: ahlberg} thus implies that for all $v \in \mathbb{Z}^d$ with $\| v \|_1 \leq C_9^{-1}n/2$,
\[
\mathbb{P}(\tau(0,v) > n) \leq M \mathbb{P}(Z \geq n/(2M)) + \frac{M}{(n/2)^{d+2}}\ .
\]
By choosing $C_8 = C_9^{-1}/2$ there is a constant $C_{10}$ such that
\[
\sum_{\|v\|_1 \leq C_8 n} \mathbb{P}(\tau(0,v) > n) \leq C_{10} n^d \left[ \mathbb{P}(Z \geq n/(2M)) + \frac{1}{n^{d+2}} \right],
\]
and the left side of \eqref{eq: first_case} is bounded by $C_{10} \sum_{n \geq 1} n^d \mathbb{P}(Z \geq n/(2M)) + C_{10} \sum_{n \geq 1} n^{-2}$.
This is finite so long as $\mathbb{E}Z^{d+1}<\infty$. To see why this holds, use Markov's inequality: $\mathbb{P}(Z \geq \lambda) = \left[ \mathbb{P}(t_e \geq \lambda) \right]^{2d} \leq \frac{\left( \mathbb{E}t_e^\alpha\right)^{2d}}{\lambda^{2\alpha d}}$, so there is $C_{11}$ such that
\[
\mathbb{E}Z^\beta \leq 1 + C_{11} \int_1^\infty x^{\beta-1-2\alpha d} ~\text{d}x < \infty \text{ whenever } \beta < 2\alpha d\ .
\]
Because $\alpha>1+1/d$, we obtain
\begin{equation}\label{eq: z_condition}
\mathbb{E}Z^{2d+2+\delta} <\infty \text{ for some } \delta > 0\ ,
\end{equation}
and so \eqref{eq: first_case} holds.

We move on to show that
\begin{equation}\label{eq: second_case}
\sum_{n \geq 1} \sum_{\stackrel{\|v\|_1 > C_8 n}{v \in B_0(n)}} \mathbb{P}(\tau(0,v) > n) < \infty\ .
\end{equation}
Given a nonzero $v \in B_0(n)$, we set $\xi:=v/\|v\|_1$ and $m:=\|v\|_1$.
To shorten the notation, denote $\tau_m:=\tau (D_m(0),D_m(m\xi))$.
Note that
\begin{align}\label{eq:box}
 \tau_m
 \leq \tau(0,v) \leq \tau_m +J_m(0) + J_m(m\xi)\ ,
\end{align}
where for $w \in \mathbb{Z}^d$, $J_m(w) = \max\{\tau(z_1,z_2) : z_1,z_2 \in D_m(w)\}$.
Because $v \in B_0(n)$, $n \geq \mu (\xi )m+Cn^{1/2}(\log n)^4$, and for some $C_{12}$ independent of $v,m$, $n \geq \mu(\xi)m + C_{12} Cm^{1/2}(\log m)^4$.
The second inequality of \eqref{eq:box} and Proposition~\ref{prop:fluct} give $C_{13}$ with
\begin{align*}
 \mathbb{P} (\tau (0,v)>n)
 &\leq \mathbb{P} ( \tau_m+J_m(0)+J_m(m\xi) >\mu(\xi)m + C_{12} Cm^{1/2}(\log m)^4)\\
 &\leq \mathbb{P} ( \tau_m+J_m(0)+J_m(m\xi)\\
 &\qquad \quad >\mathbb{E} \tau(0,v) -C_{13}(m \log m)^{1/2}+C_{12} Cm^{1/2}(\log m)^4).
\end{align*}
Due to the first inequality of \eqref{eq:box}, this is bounded by
\begin{align}\label{eq:lower_rate}
\begin{split}
 &\mathbb{P} ( \tau_m -\mathbb{E} \tau_m +J_m(0)+J_m(m\xi)
       > -C_{13}(m \log m)^{1/2}+C_{12} Cm^{1/2}(\log m)^4)\\
 &\leq \mathbb{P} \bigl( \tau_m-\mathbb{E} \tau_m
          >(C_{12} C/2)m^{1/2}(\log m)^4- C_{13} (m\log m)^{1/2} \bigr)\\
 &\quad
       +\mathbb{P} \bigl( J_m(0) + J_m(m\xi) >(C_{12} C/2)m^{1/2}(\log m)^4 \bigr).
\end{split}
\end{align}
For $C\geq 2C_{13} /(C_{12} (\log 2)^{7/2})+2$, by \eqref{eq:zhang} the second to last term is bounded above by
\begin{equation}\label{eq: ingredient_1}
\max_{\stackrel{v \in B_0(n)}{\|v\|_1 >C_8 n}} \mathbb{P}(\tau_m - \mathbb{E}\tau_m > (C_{12}C/2)m^{1/2}(\log m)^4 - C_{13} (m\log m)^{1/2}) \leq C_{14} n^{-(d+2)}\ .
\end{equation}
for some constant $C_{14}$.
As for the other term, write $\lambda_m = (C_{12}C/2)m^{1/2}(\log m)^4$ and estimate using subadditivity
\begin{align*}
\mathbb{P}(J_m(0)+J_m(m\xi) > \lambda_m) &\leq 4 \sum_{w \in D_m(0)} \mathbb{P}(\tau(0,w) \geq \lambda_m/4) \\
&\leq 4 \# D_m(0) \max_{w \in D_m(0)} \mathbb{P}(\tau(0,w) \geq \lambda_m/4)\ .
\end{align*}
We apply Lemma~\ref{lem: ahlberg} with $\epsilon=1$ and $q=2d+3$. If $C$ is large enough, then $\lambda_m/4 \geq 2 \mu(w)$ for all $w \in D_m(0)$. This gives $\mathbb{P}(\tau(0,w) \geq \lambda_m/4) \leq \mathbb{P}(\tau(0,w) - \mu(w) \geq \lambda_m/8)$. Again increasing $C$, so that $\lambda_m/8 \geq \max_{w \in D_m(0)} \|w\|_1$ for all $m$, use Lemma~\ref{lem: ahlberg} with $s = \frac{\lambda_m}{8} \geq \|w\|_1$ for
\begin{equation}\label{eq: from_referee}
\mathbb{P}(\tau(0,w) \geq \lambda_m/4) \leq M\mathbb{P}(Z \geq \lambda_m/(8M)) + \frac{M}{(\lambda_m/8)^{2d+3}}\ .
\end{equation}
This shows that there are constants $C_{15}$ and $C_{16}$ such that
\begin{align*}
\max_{\stackrel{v \in B_0(n)}{\|v\|_1 > C_8 n}} \mathbb{P}(J_m(0) + J_m(m\xi) > \lambda_m)

&\leq C_{15} n^{\delta/2}\left[ \mathbb{P}(Z \geq C_{16} \sqrt n) + n^{-(d+3/2)}\right]\ ,
\end{align*}
where $\delta \in (0,1)$ is from \eqref{eq: z_condition} is used to bound $\# D_m(0)$. Combining this with \eqref{eq: ingredient_1} and placing them into \eqref{eq:lower_rate} implies
\[
\sum_{n \geq 1} \sum_{\stackrel{\|v\|_1>C_8 n}{v \in B_0(n)}} \mathbb{P}(\tau(0,v)>n) \leq \sum_{n \geq 1} C_{17} n^{d+\delta/2} \left[ \mathbb{P}(Z \geq C_{16} \sqrt n) + n^{-(d+3/2)} \right]
\]
for some constant $C_{17}$.
Because $\delta<1$, this sum converges if and only if $\sum_{n \geq 1} n^{d+\delta/2} \mathbb{P}(Z \geq C_{16} \sqrt n)$ does, which is the same as $\sum_{n \geq 1} n^{d+\delta/2} \mathbb{P}(Z^2 \geq C_{16}^2 n) < \infty$. Because $\mathbb{E}Z^{2d+2+\delta}<\infty$ from \eqref{eq: z_condition}, we are done.
\end{proof}

\bigskip
\noindent
{\bf Acknowledgments.}

We thank an anonymous reviewer for pointing out Talagrand's lower tail concentration inequality under two moments. The research of M. D. is supported by NSF grant DMS-1419230.


TITLE: Equalizing percentages
QUESTION [2 upvotes]: I am having difficulty with the following problem:

Mark was formerly paid a salary of $400 per week and 8% commission on his total sales.Later Mark was given a 20% salary cut and his commission rate was increased to 10%. What is the smallest amount of sales Mark has to make to earn as much under the new plan as he did with the old. (Ans=4000)

Here is how i am attempting it.
Marks new salary is $320 and his commission rate is 10%.
So He needs 80 dollars more to be back to his original salary so he needs a sale of $800
Now further compensation requires that the previous sales income must match the onward sales income . I don't know how to do that. I guess that's why I am not getting the right answer. Any suggestions that could help me out.

REPLY [1 votes]: Your statement that

He needs 80 dollars more to be back to his original salary

is incorrect; recall that his original salary wasn't just \$400, but also included a commission of 8%. If $d$ is the number of dollars in sales he needs to make so that his total salary would be the same under both his new plan and his old plan, instead of solving
$$320+(0.1\times d)=400$$
(which is what you proposed), we need to solve
$$320+(0.1\times d)=400+(0.08\times d)$$
This equation becomes
$$(0.1\times d)-(0.08\times d)= 400-320$$
$$0.02\times d = 80$$
$$d=80\times\frac{1}{0.02}=80\times 50=4000,$$
which is the correct answer.

REPLY [1 votes]: There is not enough information to solve the problem, since we do not know how much in the way of sales Mark used to make, so we don't know what his total income used to be.
So we will have to make an assumption. Let us assume that Mark's monthly sales total will remain unchanged. This is perhaps unreasonable, since Mark, if he wants to continue eating, has additional incentive to sell harder.
Let this unchanging total sales amount be $x$.  Then Mark's previous commission was $(0.08)x$ and his new commission is $(0.10)x$. The difference $(0.02)x$ will have to be $80$ to make up for the drop in salary.
This gives us the equation $(0.02)x=80$. Thus $x=\frac{80}{0.02}=4000$.

REPLY [0 votes]: Let total sales be of $x$.Then previous income = $400 + 0.08x$. New income = $320+0.1x$.
 Equate them, you will get $x=4000$.


TITLE: Would a helium ballon pop or freeze in space?
QUESTION [3 upvotes]: I have read these questions:
Why doesn't Helium freeze at 0K?
Do objects in space freeze immediately?
Now I do understand that a helium balloon cannot float up to space. But let's assume this balloon is already on a spacestation.
When they release it into space, two things can happen, it either pops right away, or it freezes.
Space is around 2.7K. So I assume helium should be liquid. But would the lack of outside pressure in space cause it to pop?
Question:

What would happen with a helium balloon in space:

would it pop ever?
would it freeze?

REPLY [0 votes]: I think "will the balloon pop" depends on how much helium you put in it.
A previous answer points to a report that balloons will pop with an overpressure of more than 0.3 atmospheres. But suppose I take a balloon that's designed to have a diameter of 30cm when fully inflated, and inflate it with helium to a diameter of 10cm (at standard pressure). If I put it in a vacuum, by the time it expands to 30cm diameter, that pressure will have dropped to $(10/30)^3$, or 0.037 atmospheres.
So, it's possible that the balloon will simply stretch until the tension from the balloon's material reaches equilibrium with the pressure inside it. After that, it will slowly cool via radiation (assuming there's no nearby source of radiation to warm it). Over a longer period, the helium will leak out; depending on the balloon's material, that might leave a shapeless wisp, or an empty, frozen shell.


TITLE: Maximizing area of a pentagon inscribed inside a circle
QUESTION [2 upvotes]: A pentagon is inscribed inside a circle. Prove that the area of the pentagon to be maximum, it must be a regular one.

I have read When is the area of a pentagon inscribed inside a fixed circle maximum?, but am not satisfied with the answer...
My approach:
We can divide the pentagon into a triangle and a cyclic quadrilateral by joining any two vertices. Now we can fix this chord and argue on the maximization of the areas of these two figures...but are we allowed to fix that chord?

REPLY [2 votes]: Take an angle $2\alpha$ and divide it into two parts $\alpha+\delta, \alpha-\delta$ as shown in this sketch.

The area of the triangles $A'OP$ and $POA$ will be
$$
\left\{ \matrix{
  A_{\,POA}  = \cos \left( {\left( {\alpha  - \delta } \right)/2} \right)\sin \left( {\left( {\alpha  - \delta } \right)/2} \right) = {1 \over 2}\sin \left( {\alpha  - \delta } \right)\quad \left| {\;0 \le \alpha  - \delta  \le \pi } \right. \hfill \cr
  A_{\,A'OP}  = \cos \left( {\left( {\alpha  + \delta } \right)/2} \right)\sin \left( {\left( {\alpha  + \delta } \right)/2} \right) = {1 \over 2}\sin \left( {\alpha  + \delta } \right)\quad \left| {\;0 \le \alpha  + \delta  \le \pi } \right. \hfill \cr}  \right.
$$
and their sum
$$
A_{\,tot}  = A_{\,POA}  + A_{\,A'OP}  = {1 \over 2}\left( {\sin \left( {\alpha  - \delta } \right) + \sin \left( {\alpha  + \delta } \right)} \right) = \sin \alpha \cos \delta \quad \left| {\;\left\{ \matrix{
  0 \le \alpha  \le \pi  \hfill \cr
   - \alpha  \le \delta  \le \alpha \quad \left| {\;\alpha  \le \pi /2} \right. \hfill \cr
   - \left( {\pi  - \alpha } \right) \le \delta  \le \pi  - \alpha \quad \left| {\;\pi /2 < \alpha } \right. \hfill \cr}  \right.} \right.
$$
which is clearly maximum when $\delta =0$, i.e. when the angle $2\alpha$ is split symmetrically,
whatever be its value $0 \le \alpha \le \pi$.
The bounds on $\delta$ are just preserving that the two triagles do not overlap.
Therefore starting with a triangle, you can demonstrate that any n-agon ($3 \le n$) inscribed in a circle has
maximal area when it is regular.


TITLE: Does the termination point(level) influence water flow from a pipe
QUESTION [1 upvotes]: I get water to my home from a nearby Tank A at a certain height above ground level.
I have a 1" pipe through which I get this water to my home.. I leave this water into my well by connecting a 1" tube to this pipe.
Reason for question: I have seen water pressure vary(lower- more flow) depending upon the height I hold my pipe(on the outlet side) when I empty my fish tank, keeping how deep the pipe is immersed on the other side a constant.
Now, if I elongate and leave the pipe from Tank A at deeper level below ground level should the flow rate increase?(will i get more water in the same time) as apposed to a shorter pipe which still goes into my well.
or simply:
Will I empty my overhead tank on 2nd floor quicker if I use the tap on the ground floor instead of the tap on the second floor. The taps being same size.

REPLY [1 votes]: A longer (and deeper emerged pipe) will yield a slightly lower flow rate. This is because the longer pipe will yield a higher drop in the loss of pressure, due to friction. A longer and deeper pipe will never increase the flowrate, since what is causing the water to flow is the height difference between the two water surfaces (assuming both are subjected to atmospheric pressure).
For more information lookup Bernoulli's principle:
$$
p_1+\frac{1}{2}{\rho}v_1^2+{\rho}gz_1=p_2+\frac{1}{2}{\rho}v_2^2+{\rho}gz_2+\left(f\frac{L}{D}+{\sum}K\right)\frac{1}{2}{\rho}v_2^2
$$


TITLE: Between metacompactness and infinite Lebesgue covering dimension
QUESTION [4 upvotes]: A space $(X,\tau)$ is said to be metacompact if every open covering $\cal U$ has a refinement $\cal V$ such that for every $x\in X$ the set ${\cal V}_x := \{V\in \mathcal{V}: x\in V\}$ is finite.
A space $(X,\tau)$ is said to have Lebesgue dimension $\leq n$ (for some $n\in\mathbb{N}$) if every open covering $\cal U$ has a refinement $\cal V$ such that for every $x\in X$ the set ${\cal V}_x := \{V\in \mathcal{V}: x\in V\}$ has at less than $n$ elements. (Note that $n$ is "globally fixed" for all open coverings $\cal U$.) If there is no $n\in\mathbb{N}$ such that $(X,\tau)$ has Lebesgue dimension $\leq n$ then $(X,\tau)$ is said to have infinite Lebesgue dimension.
Is there a metacompact space with infinite Lebesgue dimension?

REPLY [5 votes]: Consider the coproduct (topological sum) $X = \coprod_{n \geq 1} \mathbb{R}^n$.

As a sum of metacompact (even paracompact) spaces, $X$ is itself metacompact (even paracompact).
As $\dim ( \mathbb{R}^n ) = n$ for each $n$, then $X$ must have infinite Lebesgue covering dimension..


TITLE: Gradient vector and local extrema
QUESTION [1 upvotes]: We learned this gradient vector stuff in class but after much struggling I just got the hang of it. I am not very flexible with it. All i know is that at a point the vector that points to the direction with highest rate of change is the gradient vector. I have a bit of confusion here. I found the gradient vector by squaring Fx and Fy then square rooting them to get gradient vector at point (x,y). However I found gradient vector at all those 4 points (4 quadrants) to be equal to sqrt2/e^2 which is strange to me. How can I tell from gradient vector if they are max or min? Using wolfram I got quadrant 2,4 are mins and 1,3 are max but I dont know how gradient tells whether the extrema are max or min.

REPLY [2 votes]: First, what you found to be $\sqrt2/\mathrm e^2$ is the norm of the gradient vector, not the gradient vector. Second, the exercise is very badly phrased; a quadrant doesn't "represent" a local maximum or minimum, it contains one. Third, you can't directly find minima and maxima from individual gradient vectors, but in the present case the idea is to use the level curves to see that there are extrema near $(\pm0.7,\pm0.7)$ and then use the gradients at $(\pm1,\pm1)$ to decide which of those extrema are minima or maxima by finding whether the gradient points towards or away from the extremum.


TITLE: Normal distributed rotation matrix in 3D
QUESTION [1 upvotes]: How can I compute normally distributed 3D rotation matrices with Mathematica?
For 2D matrices I would sample a normal distributed angle and directly create a rotation matrix with:
normalRotation2[s_] := RotationMatrix[RandomVariate[NormalDistribution[0, s]]]

This has some kind of problems because the two tails of the distribution overlap at the far end due to the finite "size" of SO(2).
I am not quite sure what the correct definition of normal distribution would be here... If there isn't any, let's use some next best concept like in normalRot2.
Now the question is how to do this in 3D?
Edit: For my purposes it would be enough to have an isotropic normal distribution.

REPLY [0 votes]: After some digging into this problem I came to this solution:
A quaternion
q = normalize(1, N(0,s), N(0,s), N(0,s))

with N(0,s) the Gaussian normal distribution with zero mean and standard deviation s generates an approximativly normally distributed rotation for small s.


TITLE: Alternative way to find if an infinite set is countable
QUESTION [4 upvotes]: I'm studying about countable and uncountable sets, and I have found that
an infinite set is countable if and only if its possible to find a bijective relation between that set and the set of natural numbers.
I got a bit confused thinking the way of the definition above, so I thought of another way to find if a set
is countable or uncountable. I'm not sure if it's correct so I would like to get some help.
An infinite set S is countable if and only if:

Given any ordering relation that covers all the elements of S: for each pair (e1, e2) of elements of S,
it is always possible, starting from e1, to reach e2 by counting the elements between e1 and e2 one by one
(the same if starting from e2 and going towards e1).

This way I can prove that P(N) is uncountable by establishing an order relation that states all the subsets of N that are elements of P(N) and have cardinality 'c' are located in the left of all of those that have cardinality 'c+1'. So I can start from, for example, {1}, and knowing that {1,2} is in some place to the right of {1}, even if I try to reach {1,2} from {1} counting element by element to the right, I will never, so P(N) is uncountable.
I thought this way because it's easier for me to undersand, but I'm not sure if I'm right.

REPLY [7 votes]: The problem with your definition, which was pointed by the other answers and some of the comments, is that it has a universal quantification.
Infinite sets are weird. Double-U, Ee, Eye, Ar, Dee. WEIRD.
What I mean by that is that infinite sets have a lot of properties that are counterintuitive to our preliminary intuition which is based on finite sets.
In particular, infinite sets will usually have properties predicates on something existing. Like the existence of a bijection. And we can usually prove that there exists other objects which do not satisfy the same properties. For example, if there is a bijection between $A$ and $\Bbb N$, there there are also injective functions which are not bijections, and there are surjective functions which are not bijective.
On the other hand, between two finite sets, if there is a bijection, all injective or surjective functions are bijections.
Another example, more pertinent to your question is ordering. An infinite set can be linearly ordered in many non-isomorphic way. Just a countable set has $2^{\aleph_0}$ different ways that we can linearly order it, without any one of them being as any other. How many of them have this "finite interval" property? Essentially three (the integers, positive integers, negative integers).
On the other hand, given a finite set, any two linear orders are in fact isomorphic. So stating something about one is the same as stating about all of them.

If you wanted to fix your definition, then, you would have to say that there exists an ordering with the said property. But this is just the same as finding a bijection between the set and $\Bbb N$ or $\Bbb Z$. So we are back to square one.
It's good that you're toying with these alternative definitions. This is how you learn the correct ones and develop the correct intuition about these kind of sets.


TITLE: Does $f(x)$ is continuous and $f = 0$ a.e. imply $f=0$ everywhere?
QUESTION [18 upvotes]: I wanna prove that
"if $f: \mathbb{R}^n \to \mathbb{R}$ is continuous and satisfies $f=0$ almost everywhere (in the sense of Lebesgue measure), then, $f=0$ everywhere."
I am confident that the statement is true, but stuck with the proof. Also, is the statement true if the domain $\mathbb{R}^n$ is restricted to $\Omega \subseteq \mathbb{R}^n$ that contains a neighborhood of the origin "$0$"?

REPLY [17 votes]: Here is a generalization of the result that you want:

Theorem: Let $f,g$ be two continuous functions such that $f = g$ a.e. Then $f = g$ everywhere.
Proof: Let $E$ be the set of all $x$ such that $f(x) \neq g(x)$. Suppose $E$ is not empty and so contains some $x$. Then $E$ being the complement of a closed set is open and so we can find $\epsilon > 0$ such that $B_\epsilon(x) \subseteq E$. But now this means
    $$0 < \mu(B_\epsilon(x)) \leq \mu(E)$$
    contradicting $\mu(E) = 0$. It follows that $E$ has to be empty so that $f = g$ everywhere.


TITLE: Independence is not preserved across weak convergence
QUESTION [1 upvotes]: If $X_n$ and $Y_n$ are independent of each other i.e. for any $n$, $X_n \perp Y_n$, $X_n \to^d X$ and $Y_n\to^d Y$, it doesn't imply that $X$ and $Y$ are independent. Joint weak convergence will imply it though.
I was looking for the proof of the above via an example. I remember reading it somewhere but I couldn't seem to find it. I tried constructing it myself, but I didn't have much luck.
I'd appreciate it if someone could either point me to the result if it is available on math.stack or some other source. You could also give the counterexample.
Edit: I got some downvotes as it was unclear what I was asking for. Let me clarify. In the above sense, it is well known that weak convergence does not preserve independence. There is an example that illustrates this. I was looking for the example.

REPLY [3 votes]: Let $U$, $V$ be two independent identically distributed random variables which are non-trivial (i.e. not almost surely constant). Define
$$X_n := U \qquad Y_n := V \qquad X := U \qquad Y := U.$$
Since all the random variables have the same distribution we clearly have $X_n \to X$ and $Y_n \to Y$ in distribution. Moreover, $X_n$ and $Y_n$ are independent for each $n \geq 1$, but $X$ and $Y$ fail to be independent.


TITLE: Trigonometry - When do I know that SINE of an Angle became Cosine
QUESTION [0 upvotes]: I am doing a trigonometry exercise and I am struggling to understand one thing, the exercise is pretty elementar, but I am still in the basics of it...
The exercise is as follows:
  Let  90 < A < 180 and tgA = -1/2
What is:
sin(270 - A)
cos(270 - A)
The picture is attached. My doubt is: I know that sin(270 - A) is an angle and that this angle is on the second quadrant because [270 - (180 - A)] is equal to 90 + A
Then I drew up a right triangle and since I know that tgA = -1/2, I drew adjacent = 2 , opposite = 1 and hypotenuse = square root of 5
So far so good, but then the exercise asked sin(270-A), then I simply evaluated the triangle I drew by getting the opposite value over hypotenuse, which in this case is (square roof of 5 / 5)
I have access to the answer sheet to see if I am understanding it right, it turns out that -2/5 / 5
It seems as though the adjacent turned into opposite and vice versa
Why do they change places? What is the logic behind it?
I am sorry if my explanation was poor, I can give more examples and further details if you guys want so
Thank you a lot in advance

REPLY [1 votes]: First, whenever a question involves angles outside the range $0<\theta<90^\circ$, I would avoid completely any use of the words “adjacent” and “opposite.”
The angle $\theta$ is measured counterclockwise from the positive $x$ axis, we find the point $(x,y)$ where the ray at that angle intersects the unit circle, and then $\sin(\theta)=y$ and $\cos(\theta)=x.$
I agree that if $\theta$ is in the second quadrant then $270^\circ-\theta$ is also in the second quadrant. But your particular angle $\theta$ produced a point farther from the $y$ axis than from the $x$ axis, and $270^\circ-\theta$ should give a point farther from the $x$ axis than the $y$ axis, hence the $y$ coordinate has the larger magnitude, hence the sine has greater magnitude than the cosine.
But the sine should be positive in the second quadrant. So I get $2\sqrt5/5.$
I would rather use trig identities rather than all these different angles and quadrants. The relevant identity in this case is $\sin(270^\circ-\theta)=-\cos(\theta)$.


TITLE: Let $f\colon X \rightarrow Y$ be a continuous and surjective function. Show that if $X$ is compact, then so is $Y$.
QUESTION [1 upvotes]: Here is my attempt at answering the above question.
(I feel that there are gaps in my knowledge in this topic and don't have a sound understanding of what a covering actually is but here goes!)
As f is surjective, there are $x_1, x_2∈ X$ s.t $f(x_1)=y_1, f(x_2)=y_2$. And f is continuous if for every open $v⊆Y, f^{-1}(v)$ is open in X.
If X is compact, then every open covering $U=(u_i)_{i∈I}$ has a finite subcovering.
Therefore, $f^{-1}(y_1)=x_1$ which is also an open covering. Thus Y is compact.

REPLY [1 votes]: Correct me if wrong:
Hopefully adding a bit of detail to José Carlos' solution .
1) Let $O_i$, $i \in I$, be an open cover of $Y$,
i.e. $(\cup O_i)_{i \in I} =Y.$
$X \subset f^{-1}Y$ , or $X \subset f^{-1}(\cup O_i)_{i \in I}$.
2)$X \subset f^{-1}(\cup O_i)_{ i \in I}=$
$(\cup f^{-1}(O_i))_{i \in I}$.
3) Since $f$ is continuous,
$f^{-1}(O_i)_{ i \in I}$ is open, and
$\cup f^{-1}(O_i)_{i \in I}$ is an open cover of $X$
4) Since $X$ compact there is a finite subset $I_f$ of $I$, such that
$X \subset \cup f^{-1}(O_i)_{i \in I_f}$.
5) $Y=f(X)=f(\cup f^{-1}(O_i)_{ i \in I_f})=$
$\cup f(f^{-1}(O_i)_{i \in I_f})= \cup (O_i)_{i \in I_f}$, i.e
a finite cover of $Y$.
Used $f(f^{-1})(O_i)=O_i$ , $i \in I_f$, since $f$ surjective.


TITLE: A conjecture on the connection between the difference of two independent Poisson random variables and their parameters.
QUESTION [2 upvotes]: Let $X$ and $Y$ be two independent poisson random variables with parameters $\mu$
and $\lambda$, respectively. Assuming that $\mu\geq\lambda$ , is it
true that $P\left(X=Y-k\right)$ is decreasing in $\mu$ (holding
$\lambda$ fixed) for any integer $k\geq0$? In other words, does the
probability that the realization of $X$ being less than the realization
of $Y$ by exactly $k$ become smaller as $\mu$ becomes larger (or equivalently,
as $\lambda$ becomes smaller)? Intuitively, I believe this is true
but cannot prove it.
One fact that I think is potentially helpful is that a Poisson r.v.
with parameter $\mu$ first order stochastically dominates another
Poisson r.v. with parameter $\mu'$ if $\mu\geq\mu'$. One consequence
is that $P(X\leq Y)$ is decreasing in $\mu$, but this does not directly
imply that $P(X=Y-k)$ is necessarily decreasing in $\mu$ for all
$k$.

REPLY [1 votes]: This is not true
$X \sim \text{Poi}(\mu)$ $Y \sim \text{Poi}(\lambda)$
$$P(X = Y - k) = \sum_{j = k}^\infty \frac{e^{-\lambda} \lambda^j}{j!} \frac{e^{-\mu} \mu^{j-k}}{(j-k)!} = f(\mu)$$
$$ f'(\mu)= \frac{e^{-\lambda} \lambda^k}{k!} (-e^{-\mu}) + \sum_{j = k+1}^\infty \frac{e^{-\lambda} \lambda^j}{j!}\bigg( \frac{-e^{-\mu} \mu^{j-k}}{(j-k)!}+ \frac{e^{-\mu} \mu^{j-k -1}}{(j-k - 1)!} \bigg) $$
Now call $$\bigg( \frac{-e^{-\mu} \mu^{j-k}}{(j-k)!}+ \frac{e^{-\mu} \mu^{j-k -1}}{(j-k - 1)!} \bigg) = \alpha (\mu,j-k)$$
note that $\alpha (\mu,j-k) \to -\infty $ as $\mu \to \infty$.
Now since for fixed $k$ $\frac{e^{-\lambda} \lambda^k}{k!} \to 0$ as $\lambda \to \infty$ you just need to take $\lambda$ large and $\mu > \lambda$ to obtain that
$f'(\mu) \leq 0$ so the function itself is decreasing
remark:  to derive insede the sum just use that $f_n(\mu) \to f(\mu)$ uniformly and that $f_n'(\mu)\to g(\mu)$ uniformly implies $f'(\mu)= g\mu$ with $$f_n(\mu) = \sum_{j = k}^n \frac{e^{-\lambda} \lambda^j}{j!} \frac{e^{-\mu} \mu^{j-k}}{(j-k)!}$$