TITLE: Evaluate $\lim\limits_{x\to 0 } \frac{ e^{\frac{\ln(1+ax)}{x}} - e^{\frac{a\ln(1+x)}{x}}}{x}$.
QUESTION [14 upvotes]: Problem
Evaluate
$$\lim_{x\to 0 } \frac{ e^{\frac{\ln(1+ax)}{x}} - e^{\frac{a\ln(1+x)}{x}}}{x}.$$
Solution
For  convenience, denote $u(x)=\dfrac{\ln(1+ax)}{x}$ and $v(x)=\dfrac{a\ln(1+x)}{x}.$ Notice that $u(x),v(x) \to a$ as $x \to 0.$Hence,
\begin{align*}
\lim_{x\to 0 } \frac{ e^{\frac{\ln(1+ax)}{x}} - e^{\frac{a\ln(1+x)}{x}}}{x}&=\lim_{x\to 0 } \frac{e^{v(x)}(e^{u(x)-v(x)}-1)}{x}\\&=\lim_{x \to 0}\left(e^{v(x)}\cdot\frac{e^{u(x)-v(x)}-1}{u(x)-v(x)}\cdot \frac{u(x)-v(x)}{x}\right)\\&=\lim_{x \to 0}e^{v(x)}\cdot\lim_{x \to 0}\frac{e^{u(x)-v(x)}-1}{u(x)-v(x)}\cdot \lim_{x \to 0}\frac{u(x)-v(x)}{x}\\&=e^a \cdot 1 \cdot\lim_{x \to 0}\frac{\ln(1+ax)-a\ln(1+x)}{x^2}\\&=e^a \cdot\lim_{x \to 0}\dfrac{ax-\dfrac{1}{2}a^2x^2+\mathcal{O}(x^2)-a\left(x-\dfrac{1}{2}x^2+\mathcal{O}(x^2)\right)}{x^2}\\&=e^a \cdot\lim_{x \to 0}\dfrac{-\dfrac{1}{2}a^2x^2+\dfrac{1}{2}ax^2+\mathcal{O}(x^2)}{x^2}\\&=\frac{1}{2}e^a(a-a^2). \end{align*}
Please correct me if I'm wrong! Hope to see other solutions.

REPLY [1 votes]: The OP used series in the work to arrive at the answer. Another approach is to use the definition of the derivative. First it is easy to observe that $\lim\limits_{x\to 0 }\ln\frac{(1+ax)}{x}=a$ and  $\lim\limits_{x\to 0 }a\ln\frac{(1+x)}{x}=a$, verified through L'Hospital's Rule.
So $\lim\limits_{x\to 0 } \frac{ e^{\frac{\ln(1+ax)}{x}} - e^{\frac{a\ln(1+x)}{x}}}{x}$ can be written as  $\lim\limits_{x\to 0 } \frac{ e^{\frac{\ln(1+ax)}{x}}-a}{x-0}$ - $\lim\limits_{x\to 0 } \frac{ e^{\frac{a\ln(1+x)}{x}}-a}{x-0}$
Here we see twice the definition of the derivative of two functions (e-powered to the ln...). So essentially this means that we have to take the derivative of those e-power functions and "plug in" $x=0$. In both cases that isn't too easy in the sense that we will get an indeterminate form (0/0) but the limits in my introduction might be helpful with that. The derivative of $ e^{\frac{\ln(1+ax)}{x}}$ is $ e^{\frac{\ln(1+ax)}{x}}\times[\frac{ln(1+ax)}{x}]'$ (Chain Rule). The derivative of that second part (after simplifying) is $\frac{ax-(1+ax)ln(1+ax)}{(1+ax)x^2}$. Putting in $x=0$ gives an indeterminate form but with Hospital's Rule (or some other manipulation, like with Standard limits), this yields $-\frac{1}{2}a^2$. With the e-power upfront: $-\frac{1}{2}e^aa^2$ which is one part of your answer. The other derivative goes in a very similar fashion and will give you the other part of your answer. Hope this helps.


TITLE: Easy proof that compact implies bounded in a metric space… too easy?
QUESTION [2 upvotes]: I came up with a proof that I have not seen anywhere and I’m wondering if it is because it is inefficient for a reason that eludes me. Suppose $E$ is a compact subset of a metric space $(X,d)$ and grab any $e\in E$. Now consider the cover $$\left\{ B_n (e) \right\}_{n\in \mathbf{N}}.$$ By compactness there is a subcover $$B_{n_1}(e), B_{n_2} (e), \cdots, B_{n_k}(e)$$ for some $k\in \mathbf{N}$. But if we let let $m=\max \left\{n_i: 1\leq i \leq k \right\}$, their union is exactly $$B_m  (e)$$ and we have that, by compactness: $$E\subseteq B_m (e).$$ Which precisely says that $E$ is bounded.$\blacksquare$ $$$$ As far as I can tell, the only qualm I can see one having with this proof is that $\left\{B_n (e) \right\}_{n\in \mathbf{N}}$ actually covered $E$. So if asked for a proof of this fact, what would I say? I suppose I could say for any $y\neq e$ we have that $y\in B_{\lfloor d(y,e) \rfloor +1} (e)$. Or, of course, if it’s not true what would a counter example be?

REPLY [1 votes]: The proof is correct. You could even take an arbitrary $e\in X$, and it's true that the balls $B_n(e)$ will cover $E$ (they even cover $X$). The point is that any two points $x,e$ in a metric space are some finite distance apart (namely $d(x,e)<\infty$) so in particular any point $x\in X$ will belong to $B_n(e)$ as long as $n > d(x,e)$.


TITLE: Series of games
QUESTION [0 upvotes]: Bill and Mark play a series of games until one of the players has won two games more than the other player. Any game is won by Bill with probability $p$ and by Mark with probability $q = 1 − p$. The results of the games are independent of each other. What is the probability that Bill will be the winner of the match?
Let $A=[$Bill wins the 1° game$]\Rightarrow \mathbb{P}(A)=p$ and $B=[$Bill wins the 2° game$]\Rightarrow \mathbb{P}(B)=p$, so $\mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B)=p^2$.
Let $\bar{A}=[$Mark wins the 1° game$]\Rightarrow \mathbb{P}(\bar{A})=q$ and $\bar{B}=[$Mark wins the 2° game$]\Rightarrow \mathbb{P}(\bar{B})=q$, so $\mathbb{P}(\bar{A}\cap \bar{B})=q^2$.
Since $Z=[$tie$]\Rightarrow \mathbb{P}(Z)=\mathbb{P}[(A\cap \bar{B})\cup (\bar{A}\cap B)]=2pq$, we have $H=[$Bill wins$]=\frac{p^2}{1-2pq}$.
Now I have a question. Is it possible to solve the problem setting

$X=[$# games won by Bill$]\Rightarrow \mathbb{P}(X=x)=\binom{n}{x}p^x(1-p)^{n-x}$

$Y=[$# games won by Mark$]\Rightarrow \mathbb{P}(Y=y)=\binom{n}{y}q^y(1-q)^{n-y}$

? Because I'm stuck when $\mathbb{P}(X\geq Y+2)=$
$\sum_{y=0}^{n}\binom{n}{y}q^y(1-q)^{n-y}\sum_{x=y+2}^{\infty}\binom{n}{x}p^x(1-p)^{n-x}=pq^n(1+\frac{q}{p})^n\sum_{s=0}^{\infty}\binom{n}{s+y+2}(\frac{p}{q})^{s+y+2}$
with $s=x-y-2$.
If not, why?
Thanks for any clarification.

REPLY [1 votes]: It is hard to see how your approach can work, since simply knowing that $B$ wins more games out of a large number $n$ doesn't tell us that $B$ won the match (after all, $M$ might have won the first two games but lost the next $n-2$).
Your question is related to this question.
That question concerns the expected length of the match, but the probabilities can be handled in the same manner.
Let $\psi$ denote the probability that $B$ eventually wins the match. We consider the first two games and note that there are three possible outcomes:  either $B$ wins ($p^2$), $M$ wins ($(1-p)^2$) or they split the two games and the match resets ($2p(1-p)$).  It follows that $$\psi=p^2\times 1 +(1-p)^2\times 0 + 2p(1-p)\times \psi$$ which implies $$ \boxed {\psi=\frac {p^2}{1-2p(1-p)}}$$
Sanity checks: For all probabilities $p$ we get $0≤\psi≤1$ as we should. if $p=0$ this yields $0$, if $p=1$ this yields $1$, and if $p=\frac 12$ this yields $\frac 12$.  If $\overline {\psi}$ denotes the result if we switch $p, 1-p$ (so $\overline {\psi}$ is the probability that $M$ wins the match) we check that $$\psi+\overline {\psi}=1$$


TITLE: Solving Laplace equation with conformal mapping for a region of radius $R$ and angle $\alpha$?
QUESTION [1 upvotes]: It is actually an electrostatic problem, I have to find the potential in the region descripted above using the laplace differential equation with the next boundary conditions: $V$ is $0$ in the straight sides and $V_0$ in the curve side.

The problem asks for me to solve the laplace equation in a semi-infinite strip first, where the finite side has a potential V and both infinite sides have a 0 potential, which is an standard variable separation problem and can be easily solved.
The first thing that confuses me is that it doesn't seem like a conformal mapping because any function that transform the first region into the second can't preserve angles. My question is if I do an approximation an convert my region into a triangle Does exist a function that can transform my triangle in an semi infinite strip?
Thanks in advance.

REPLY [0 votes]: The probably source of your confusion is that conformal map doesn't need to preserve angle at boundary.  For example, the map $z\mapsto z^{\pi/\alpha}$ is a conformal map that maps your sector to a half-disc, but it stretches angles at the vertex.
The semi-infinite strip $\{z=x+iy\mid x<\log R, y\in (0,\alpha)\}$ is mapped, by the exponential, to your sector conformally.


TITLE: Detect when a point belongs to a bounding box with distances
QUESTION [7 upvotes]: I have a box with known bounding coordinates (latitudes and longitudes): latN, latS, lonW, lonE.
I have a mystery point P with unknown coordinates. The only data available is the distance from P to any point p. dist(p,P).`
I need a function that tells me whether this point is inside or outside the box.

REPLY [0 votes]: You have the coordinates of the four corners of the box. I'll imagine that the box is situated so its sides are horizontal or vertical (This could be easily obtained by a rotation if box wasn't originally like this). So you can also get the coordinates of:
$p_M$, the center of the box (inside the box),
$p_L$, the point directly to the left of the center so that the left side of the box bisects the line joining $p_M$ to $p_L$,
$p_R$, the point directly to the right of the center so the right side of the box bisects the line joining $p_M$ to $p_R$,
two further points $p_A$ and $p_B$ respectively above and below the box, so that the top/bottom of the box bisects the line joing $p_M$ to $p_A$ or $p_B$.
Now for your mystery point P you find
$t_M=d(p_m,P)$, $t_L=d(p_L,P)$, and similarly for $t_R,t_A,t_B$.
Now use the fact that the mystery point $P$ is on the (half plane to the) left of the right side iff it is closer to the point $p_M$ than it is to $p_R$, i.e. iff $t_M>t_R$. Similarly $P$ is to the right of the left side iff $t_M>t_L$, and $P$ is below the top of the box iff $t_M>t_A$, and finally $P$ is above the bottom of the box iff $t_M>t_B$.
We now have that  p lies in the box iff each of the quantities $t_M-t_*$ is positive, where * is one of the four symbols $L,R,A,B$. For the function, define
$f(distances)=min(t_M-t_L,t_M-t_R,t_M-t_A,t_M-t_B)$. Then $f>0$ iff $P$ lies in the interior of the box, while $f>=0$ iff $P$ lies in the interior or on the boundary of the box.


TITLE: Angle between sum of vectors
QUESTION [0 upvotes]: Let $u,v$ and $w$ be vectors in $\mathbb{R}^n$ and let $\theta(u,w), \theta(v,w)$ and $\theta(u+v,w)$ represent the angle between each listed pair of vectors. Does it hold that one of the following two statements must be true:
$$\theta(u,w) \geq \theta(u+v,w)$$ Or:
$$\theta(v,w) \geq \theta(u+v,w)$$
I feel this must be true and that it follows from some simple property that I'm forgetting. If it is true, does it generalize to any finite list of vectors?

REPLY [2 votes]: I don't think this is true. Take the vectors $u=\langle-1, 1\rangle$, $v=\langle 1, 1\rangle$ and $w=\langle 0, -1\rangle$ in $\mathbb{R}^2$. Then $u+v=\langle 0, 2\rangle$, and $\theta(u+v, w)=\pi$, while both $\theta(u,w)$ and $\theta(v,w)=\frac{3\pi}{4}$.


TITLE: How many linearly independent subset of $V$ are there having $m$-elements?
QUESTION [0 upvotes]: Let $\mathbb F$ be a field of $p$ elements.Let $V$ be an $n$-dimensional vector space over $\mathbb F$. Prove the following $:$
$(a)$ $V$ has $p^n$ elements.
$(b)$ $V$ has $p^n - 1$ linearly independent singleton sets.
$(c)$ The number of linearly independent subsets of $V$ consisting of $m$ elements,$(1 \leq m \leq n)$ is
$$ \frac {1} {m!} \prod_{k=0}^{m-1} (p^n - p^k).$$
Hint $:$ Induction.

$(a)$ follows from the fact that  $V \simeq \mathbb F^n$ and $\mathbb F$ has $p$-many elements. Also $(b)$ follows immediately from $(a)$. Now to show $(c)$ we use induction on the number of elements in a linearly independent subset of $V$. Clearly our result holds for $n=1$ by part $(b)$. Let our result be true for any linearly independent subset of $m-1$ elements i.e. number of linearly independent  subsets of $V$ consisting of $m-1$ elements is
$$ \frac {1} {(m-1)!} \prod_{k=0}^{m-2} (p^n - p^k).$$
We have to prove that our result is true for $m$. Now we can make a linearly independent subset consisting of $m$ elements from a linearly independent subset  consisting of  $m-1$ elements by adjoining an element of $V$ which is not in the span of these $m-1$ elements. Now the number of elements in the span of $m-1$ elements is $p^{m-1}$. So the adjoining elements should then be chosen from the remaining  $p^n -  p^{m-1}$ elements and this is true for each of these  $\frac {1} {(m-1)!} \prod_{k=0}^{m-2} (p^n - p^k)$ possibilities. So the total  number of linearly independent subsets is thus  $$ \frac {1} {(m-1)!} \prod_{k=0}^{m-1} (p^n - p^k).$$ which is not the required answer we are looking for. I am quite unsure about where I have done mistake?
Please help me in this regard. Then it will be very helpful for me.
Thank you in advance.

REPLY [1 votes]: In your counting you state that every LI set of size $m$ is obtained by adjoining an element of $V$ to an LI set of size $m - 1$, which is true. However there isn't a unique way to do this.
If $\{v_1, \ldots, v_m\}$ is an LI set then there is $\binom{m}{1} = m$ different ways to partition $\{v_1, \ldots, v_m\}$ into a set of size $m - 1$ and a single element. You can add $v_1$ to $\{v_2, \ldots, v_m\}$, or $v_2$ to $\{v_1, v_3, \ldots, v_m\}$, and so on. Hence your method of counting constructs the set $\{v_1, \ldots, v_m\}$ $m$ different times.
To compensate for this we divide by $m$ at the end, which will give you the right answer.


TITLE: Convolution of fractional part with itself
QUESTION [0 upvotes]: Let f(x) be the fractional part of x. I'm asked to find  $F(x)=f*f=\int_{0}^{1}f(x-t)f(t)dt$ explicitly and find its Fourier series.
My first idea was to just integrate $frac(x-t)frac(t)$, getting $\frac{frac(x)}{2}-1/3$.  However, I know that the Fourier coefficients of F must be the square of the coefficients of the fractional part and hence my result is wrong.
Thinking about how (x-t) can be negative, my next attempt was to split the integral (with no success).
So how should I proceed?

REPLY [1 votes]: By the Fourier series of the sawtooth wave we have
$$\{x\}=\frac{1}{2}-\frac{1}{\pi}\sum_{k\geq 1}\frac{\sin(2\pi k x)}{k}$$
uniformly over any compact subset of $\mathbb{R}\setminus\mathbb{Z}$. For $x\in(0,1)$
$$ \int_{0}^{1}\{x-t\}\{t\}\,dt = \int_{0}^{x}(x-t)t\,dt +\int_{x}^{1}(1+x-t)t\,dt = \frac{1}{6}+\frac{x}{2}-\frac{x^2}{2} $$
and
$$F(x)=\frac{1}{4}-\frac{1}{2\pi^2}\sum_{k\geq 1}\frac{\cos(2\pi k x)}{k^2}.$$


TITLE: Integral convergence $\int_{2}^{\infty} \frac{\cos x}{\sqrt[3]{\ln x}}$
QUESTION [0 upvotes]: I've tried to partial integrate this integral from $0$ to $1$, $1$ to $e$, and $e$ to infinity:
$$\int_{2}^{\infty} \frac{\cos x}{\sqrt[3]{\ln x}} dx.$$
Without success. Any help?

REPLY [1 votes]: The integral is convergent by Dirichlet's test, since $\cos x$ has a bounded primitive while $\frac{1}{\sqrt[3]{\ln x}}$ is decreasing towards zero. Integration by parts gives:
$$ \int_{e}^{M}\frac{\cos x}{\sqrt[3]{\log x}}\,dx = \left.\frac{\sin x}{\sqrt[3]{\ln x}}\right|_{e}^{M}+\int_{e}^{M}\frac{\sin x}{3x\ln x\sqrt[3]{\log x}}\,dx$$and
$$ \int_{e}^{+\infty}\frac{dx}{3x\,\left(\ln x\right)^{4/3}} = 1.$$


TITLE: Homotopy equivalence of the two sphere with poles identified
QUESTION [1 upvotes]: Hello I am having trouble with the following exercise:
We are asked to show that the following spaces are homotopic equivalent:

The two sphere with north and south pole identified: $\mathbb S^2/\{N ∼ S\}$. (Here N and S represent the north and south pole.

The two sphere with a interval glueing the north and south pole together: $(\mathbb S^2\cup[0, 1])/\{N ∼ 0, S ∼1\}$.

I need to write down two functions $f,g$ s.t. they are homotopic inverses of each other.
Intuitively it makes sense to me since we can retract the interval to a single point, and the end points of the interval are identified with the north and south pole. And since the interval is contractible it is homotopic equivalent to a single point. But writing explicit functions seems kinda hard.

Definition: Two spaces $X, Y$ are homotopic equivalent if there exists $f:X\to Y$, and $g:Y\to X$ s.t. $g\circ f ∼ id_X$ and $f \circ g ∼ id_Y$. The composition of the maps is homotopic to the identity.

We were also given a hint to write the two sphere as two copies of discs with the boundary glued together. I don’t really see how this helps with finding the functions $f,g$.
Can someone give a hint on how to define the functions $f$ and $g$?

REPLY [1 votes]: Let $$ X= (\mathbb S^2\cup[0, 1])/\{N ∼ 0, S ∼1\},\qquad \qquad Y=\mathbb S^2/\{N ∼ S\}.$$
Then $f\colon X\to Y$ is easy to define.  Following your intuition of retracting the interval to a point, just set $f|_{\mathbb S^2}=1_{\mathbb S^2}$ and $f(t)=N=S$ for all $t\in [0,1]$.
Now we need to define $g\colon Y\to X$.  The advantage of regarding $\mathbb S^2$ as a union of a pair of (unit) disks, is that on each disk we can parameterize using polar co-ordinates, with $S$ or $N$ as the origin.
The idea now is simple: Firstly $g\colon N,S\mapsto 0.5\in [0,1]$.  Then for a point $(r,\theta)$, on either disk of $Y$, if $r\leq0.5$ we map $$g\colon (r,\theta)\mapsto 0.5\pm r\in [0,1].$$
Here the sign $\pm$ is determined by which disk $(r,\theta)$ lies on.
Finally if $r\geq0.5$ we map $$g\colon (r,\theta)\mapsto (2r-1,\theta).$$
Now you have to construct the homotopies $g\circ f ∼ id_X$ and $f \circ g ∼ id_Y$.  Let me know if you need help with that.

Let's start with the composition $f \circ g$.  This collapses points of radius less than $0.5$ to $N=S$, and applies the function $2r-1$ to radii greater than $0.5$.
We need to construct $H_t\colon Y\to Y$ for $t\in [0,1]$ so that $H_0=1_Y$ and $H_1=f \circ g$.
It makes sense then for $H_t$ to collapse points of radius less than $t/2$ to $N=S$.  Then radii from  $t/2$ to $1$ should get mapped to radii from $0$ to $1$, which we can do linearly:
$$H_t(r,\theta)=H_t\left(\left(\frac {r-\frac t2}{1-\frac t2},\theta\right)\right),\qquad r\geq t/2,$$
and $H_t(r,\theta)=N=S$ if $r\leq t/2$.
Now check these two definitions agree at the boundary $r=t/2$, and that $H_0=1_Y$ and $H_1=f \circ g$.  Check also that points of radius $1$ get mapped to points of radius $1$ for all $t$, as this is needed to ensure continuity where the disks are glued.


TITLE: Precision orbit parameters: Is it possible to determine the position of orbiting exoplanets after eg. 50 years?
QUESTION [0 upvotes]: Is it possible to determine the position of orbiting exoplanets after eg. 50 years? Many parameters of the orbits have large estimates eg .: Tau Ceti f: Orbital period (P) = 642 ± 30 days. It is up to ± 30 days (and this is just an example).
Is there a way to calculate quite precisely the position of the exoplanets after 50 years or more? (Starting from today, of course)
What kind of precision you can get? (In most cases, of course)

REPLY [1 votes]: The good news is that further observation will reduce the uncertainty on the parameters of the orbit.
The bad news is that eventually statistical uncertainties (from the counting statistics in the light detector if nothing else) will dominate at which point the rate of improvement will start to drop rapidly.
You use the word "precise" without defining a threshold, so no one can answer that for you. Your final question is better, but I'm not familiar with the actual data and equipment so I can't help you.

On issue that is not addressable (as far as I know, with current equipment) is the left-right ambiguity: does the planet pass in front of the star from left to right or vice versa?


TITLE: lemma on functions
QUESTION [2 upvotes]: searching for exercises on continuous function I found one, which I rewrote here :
Def : let $[a;b]$ be a set on which a continuous real function $f$ is defined.Let $[A;B]$ be a subset of $[a;b]$
we say that [A;B] is $f$-dominating over $[a;b]$if
$\forall x \in [a;b], \exists y \in [A;B]$ st. $f(y)\geq f(x)$ (1)
Lemma :
let $C \in [A;B]$ then either $[A;C]$ is $f$-dominating over $[a;b]$ or$[C;B]$ is.
Exercise : Prove this lema without using the fact that continuous functions on a close interval are bounded. (ie. without the extreme value theorem)
I started the proof this way
If $[A;C]$ is $f$-dominating then proof is done.
Let's then consider $[A;C]$ is not $f$-dominating. This translates to
$$\exists x \in [a;b]\text{ st. } \forall y \in [A;C],  f(x)>f(y)$$
But then from $(1)$
...
Thus $[B;C]$ is $f$-dominating.
Can anyone help me filling the dots ?
PS : $f$ is continuous of course ! added to the post

REPLY [1 votes]: Lemma Let $f$ be a (continuous) function defined on $[a;b]$. Let $[A;B]$ be $f$-dominating over $[a;b]$, and let $C\in[A;B]$ be given. Then either $[A;C]$ or $[C;B]$ is $f$-dominating over $[a;b]$.

The proof starts off as you stated:
If $[A;C]$ is $f$-dominating, the proof is done.

Now set $x'\in[a;b]$ such that
$$
f(x')>f(y)
$$
for all $y\in[A;C]$. Hence $M=f(x')$ is an upper bound on $f([A;C])$. But at the same time there exists $y'\in[A;B]$ such that
$$
f(y')\geq f(x')=M
$$
Now since $y'\in[A;B]$ but $y'\notin[A;C]$ this implies $y'\in[C;B]$.
(actually it is in (C;B] so it is in [C;B] as well)

Now let any $x\in[a;b]$ be given:

If $f(x)\leq M$ we have $f(y')\geq f(x)$ where $y'\in[C;B]$.
If $f(x)>M$ we cannot find a dominating $f(y)$ over $[A;C]$ and resort to the same argument as for $x',y'$ to show that there exists $y\in[C;B]$ such that $f(y)\geq f(x)$.

Thus $[C;B]$ is $f$-dominating over $[a;b]$.


TITLE: In golf, what influences more on how far the ball travels?
QUESTION [4 upvotes]: Most of us are aware of the general concept that the harder you hit something, the farther it usually travels. (let us suppose we are neglecting any air resistance and friction that happens) And from Newton, we have gotten the general formula $F=ma$ where force equals mass times acceleration.
Physics plays a big role in the sport of golf as well. And after thinking, I have been wondering which ball would travel farther. Suppose two golfers each hit a golf ball such that:

Golfer #1 hits the ball with a 10.5° driver of mass $m$ and hits the ball with a horizontal velocity $2v$
Golfer #2 hits the ball with a 10.5° driver of mass $2m$ and hits the ball with a horizontal velocity $v$

My question is which ball travels further horizontally? Or do they travel the same horizontal distance? Or is there not enough given information to tell?
I have tried figuring it out myself but haven't had any luck. I feel that acceleration is involved somewhere to link force to velocity (because acceleration is the derivative of velocity) but I'm not sure if this is the right approach.

REPLY [2 votes]: Surprised to see, but no one has yet mentioned the logic of projectile here.
Since you've been given the angle of projection and the horizontal velocity of projection, the problem here becomes the classic case of projectile motion.
Note that the maximum horizontal distance $(R)$ that the golf ball can travel is
$R$=$\frac{v^{2}sin2\theta}{g}$
Where $v$ is the horizontal velocity by which it is projected, $g$ is the acceleration due to gravity and $sin2\theta$ is the sine of twice the angle of projection.


text:
\section{AMP algorithmic phase transition}\label{app:matrixWalgo}

We begin with the proof of Theorem~\ref{AMP-theorem} in Section~\ref{eq:appsec:AMPtheory}, assuming the result in \eqref{eq:finite_sample} is true, and then we discuss the proof of \eqref{eq:finite_sample} which is a generalization of \cite[Theorem 1]{RushVenkataramanan} in Section~\ref{eq:appsec:finitesample}.

\subsection{Proof of Theorem~\ref{AMP-theorem}} \label{eq:appsec:AMPtheory}
We begin by restating Theorem~\ref{AMP-theorem}, the result we would like to prove, for the readers' convenience.

 \begin{thm}\label{AMP-theorem_app}
 For the AMP algorithm in \eqref{eq:AMP} using the conditional expectation denoiser in \eqref{eq:denoiser}, with $\epsilon \in (0,1)$, we have that

 \begin{align}
&\mathbb{P} \Big(\Big| \frac{1}{n}\|\bX -  f_{t}(\bx^{t})\|^2 -  (\rho_n -  \tau^n_{t+1})\Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_vector}\\

&\mathbb{P} \Big(\Big| \frac{1}{n^2}\|\bX \bX^T -  f_{t}(\bx^{t}) [ f_{t}(\bx^{t})]^T\|_F^2 -  (\rho_n^2 -    (\tau^n_{t+1})^2) \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_matrix}
 \end{align}

where $X_0^n \sim P_{X, n}$ and $\tau_t^n$ is defined in \eqref{eq:state_evolution2}.  The constants $C_t, C_t$ are given by
$C_t =C_1^{t} (t!)^{C_2},  c_t = [c_1^{t} (t!)^{c_2}]^{-1}$  and $C, C_1, C_2, c, c_1, c_2$ are universal constants not depending on $n$ or $\epsilon$.

 \end{thm}

 The proof of Theorem~\ref{AMP-theorem_app} uses the following finite sample guarantee for the symmetric AMP algorithm in \eqref{eq:AMP}.
 The performance guarantees concern the convergence of the empirical distribution of $x^t_i$ to its approximating distribution with mean and variance determined by the state evolution, in the following sense. Recall the following definition of a pseudo-Lipschitz function.

 \begin{defi}  \label{def:PL}
 For any $n,m \in \mathbb{N}_{>0}$, a function $\phi : \mathbb{R}^n\to \mathbb{R}^m$ is \emph{pseudo-Lipschitz of order $2$} if there exists a constant $L>0$ such that  for $\bx, \by \in \mathbb{R}^n$, $$\left|\left|\phi(\bx)-\phi(\by)\right|\right|\leq L\left(1+ \|\bx\|+ \|\by\|\right) \|\bx-\by\|.$$
 \end{defi}

 Now, for all order $2$ pseudo-Lipschitz functions denoted $\psi: \mathbb{R} \rightarrow \mathbb{R}$ with Lipschitz constant $L_{\psi}> 0$, for $\epsilon \in (0,1)$ and $t \geq 0$,

 \begin{equation}
 \begin{split}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i)) -  \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\},
 \label{eq:finite_sample_app}
 \end{split}
 \end{equation}

 where $\bX = (X_1, \ldots, X_n)$ is the true signal, $C, C_t, c, c_t$ are universal constants not depending on $n$ or $\epsilon$, with the values of $C_t, c_t$ given in Theorem~\ref{AMP-theorem_app}. Finally, we note that \eqref{eq:finite_sample} matches \eqref{eq:finite_sample_app} when we use the conditional expectation denoiser as in \eqref{eq:denoiser}, since then we have that
 $L_f = \sqrt{\lambda_n}$ as shown in Lemma~\ref{lem:PL} for the Bernoulli and Bernoulli-Rademacher signal priors considered here.
We discuss the proof of \eqref{eq:finite_sample} in Section~\ref{eq:appsec:finitesample}, but for the time being, we assume that it is true and use it to prove Theorem~\ref{AMP-theorem_app}.

First, notice that Theorem~\ref{AMP-theorem_app} result \eqref{eq:finite_sample_vector} follows directly from \eqref{eq:finite_sample_app} using the pseudo-Lipschitz function $\psi(X_i, f_{t}(x^{t}_i))  = (X_i -  f_{t}(x^{t}_i))^2$. This function is pseudo-Lipschitz with constant $L_{\psi} $ by Lemma~\ref{lem:PL}.  To see how this proves result \eqref{eq:finite_sample_vector} in more details, notice that

 \begin{equation*}
 \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i))  = \frac{1}{n} \sum_{i=1}^n (X_i - f_{t}(x^{t}_i))^2 = \frac{1}{n}\|\bX -  f_{t}(\bx^{t}) \|^2,
  \end{equation*}

and

 \begin{equation*}
 \begin{split}
& \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} =  \mathbb{E}\Big\{\big(X_0^n - f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z\big)\big)^2 \Big\} \\

 &=  \mathbb{E}\Big\{\big(X_0^n\big)^2 \Big\} + \mathbb{E}\Big\{\big( f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z)\big)^2 \Big\} - 2 \mathbb{E}\Big\{ X_0^n f_t\big(\mu^n_{t}  X_0^n - \sqrt{\tau^n_t} Z\big) \Big\} = \rho_n -  \tau^n_{t+1},
 \end{split}
  \end{equation*}

where the final uses that $ \mathbb{E}\{(X_0^n)^2\} = \rho_n$ when $P_{X,n}$ is ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher, the Law of Total Expectation to give $ \mathbb{E}\{X_0^n f_t(\sqrt{\lambda_n} \tau^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\} = \mathbb{E}\{[f_t(\sqrt{\lambda_n} \tau^n_{t}X_0^n + \sqrt{\tau^n_t} Z)]^2\}$ in the case of the conditional expectation denoiser as in \eqref{eq:denoiser}, and the state evolution definition in \eqref{eq:state_evolution2}.

Now we will prove Theorem~\ref{AMP-theorem_app} result \eqref{eq:finite_sample_vector}. First we introduce a few useful lemmas about concentration of sums of squares, the proof of which can be found in \cite[Appendix A]{RushVenkataramanan}.

\begin{lemma}[Concentration of Sums]
\label{sums}
If random variables $X_1, \ldots, X_M$ satisfy $P(\abs{X_i} \geq \ep) \leq e^{-n\kappa_i \ep^2}$ for $1 \leq i \leq M$, then

 \begin{equation*}
P\Big(  \lvert \sum_{i=1}^M X_i  \lvert \geq \ep\Big) \leq \sum_{i=1}^M P\left(|X_i| \geq \frac{\ep}{M}\right) \leq M e^{-n (\min_i \kappa_i) \ep^2/M^2}.
  \end{equation*}

\end{lemma}

\begin{lemma}[Concentration of Powers]
\label{powers}
Assume $c > 0$ and $0 < \ep \leq 1$.  Then, if
$
P( \lvert X_n - c \lvert \geq \epsilon ) \leq e^{-\kappa n \epsilon^2},
$
it follows that
$
P(\lvert X_n^2 - c^2  \lvert \geq \epsilon) \leq e^{ {-\kappa n \ep^2}/[1+2c]^2}  \leq e^{-\kappa n \ep^2}.
$
\end{lemma}

Now considering the concentration result in \eqref{eq:finite_sample_vector}, notice that

 \begin{equation*}
 \frac{1}{n^2}\|\bX \bX^T - f_t(\bx^t) [f_t(\bx^t)]^T\|_F^2  =  \frac{1}{n^2}\|\bX\|^4 + \frac{1}{n^2}\|f_t(\bx^t)\|^4 - \frac{2}{n^2} \langle \bX, f_t(\bx^t) \rangle^2.
  \end{equation*}

Then we will prove the following three results:

 \begin{align}
\mathbb{P} \Big(\Big|  \frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big| \geq \epsilon \Big) &\leq 2e^{ -2 n \e^2},  \label{eq:finite_sample_matrix1} \\
\mathbb{P} \Big(\Big|  \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t})^2 \Big| \geq \epsilon \Big) &\leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},  \label{eq:finite_sample_matrix2} \\
\mathbb{P} \Big(\Big|  \frac{1}{n^2} \langle \bX, f_t(\bx^t) \rangle^2 -  ( \tau^n_{t})^2 \Big| \geq \epsilon \Big) &\leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\}.\label{eq:finite_sample_matrix3}
 \end{align}

Then the final concentration result in \eqref{eq:finite_sample_vector} follows from Lemma~\ref{sums} as follows:

 \begin{align*}
&\mathbb{P} \Big(\Big| \frac{1}{n^2}\|\bX \bX^T - f_t(\bx^t) [f_t(\bx^t)]^T\|_F^2 - ( \rho_n^2 -  (  \tau^n_{t+1})^2)  \Big| \geq \epsilon \Big) \\

&= \mathbb{P} \Big(\Big|  \Big(\frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big) + \Big( \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t+1})^2   \Big)-  \Big(\frac{2}{n^2} \langle \bX, f_t(\bx^t) \rangle^2  - 2 (   \tau^n_{t+1})^2\Big) \Big| \geq \epsilon \Big) \\

&\leq \mathbb{P} \Big(\Big|  \frac{1}{n^2}\|\bX\|^4 -  \rho_n^2 \Big| \geq \frac{\epsilon}{3} \Big) +  \mathbb{P} \Big(\Big|  \frac{1}{n^2}\|f_t(\bx^t)\|^4 - (\tau^n_{t+1})^2  \Big| \geq  \frac{\epsilon}{3} \Big) +  \mathbb{P} \Big(\Big|  \frac{2}{n^2} \langle \bX,f_t(\bx^t) \rangle^2  - 2 (  \tau^n_{t+1})^2 \Big| \geq  \frac{\epsilon}{3} \Big).
 \end{align*}

As a final step, notice that the bounds in  \eqref{eq:finite_sample_matrix1} - \eqref{eq:finite_sample_matrix3} applied to the above give the result in \eqref{eq:finite_sample_vector}.

Now we prove  \eqref{eq:finite_sample_matrix1} - \eqref{eq:finite_sample_matrix3}. First we prove \eqref{eq:finite_sample_matrix1}.  Recall Hoeffding's inequality.
\begin{lemma}[Hoeffding's inequality]
\label{lem:hoeff_lem}
If $X_1, \ldots, X_n$ are bounded random variables such that $a_i \leq X_i \leq b_i$, then for $\nu = 2[\sum_{i} (b_i -a_i)^2]^{-1}$, we have
$P(  \lvert \frac{1}{n}\sum_{i=1}^n (X_i -\mathbb{E}\{X_i\})  \lvert \geq \ep ) \leq 2e^{ -\nu n^2 \ep^2}.$
\end{lemma}
\begin{lemma}[Chernoff's bounds for Bernoulli's]
\label{lem:chernoff}
If $X_1, \ldots, X_n$ be i.i.d.\ ${\rm Ber}(\rho_n)$, then for $\ep \in [0,1]$ we have
$P(  \lvert \frac{1}{n}\sum_{i=1}^n (X_i -\rho_n)  \lvert \geq \ep ) \leq 2\exp\left\{ - \frac{n \ep^2}{3 \rho_n}\right\}.$
\end{lemma}

 \begin{align*}
\mathbb{P} \Big(\Big|  \frac{1}{n}\|\bX\|^2 -  \rho_n \Big| \geq \epsilon \Big)  = \mathbb{P} \Big(\Big|  \frac{1}{n} \sum_{i=1}^n(X_i^2 -  \mathbb{E}\{X_i^2\}) \Big| \geq \epsilon \Big)  &\leq 2e^{ -2 n \ep^2}.
 \end{align*}

Then the result in  \eqref{eq:finite_sample_matrix1} then follows from the above by Lemma~\ref{powers}.

 Next, for \eqref{eq:finite_sample_matrix2} we apply \eqref{eq:finite_sample_app} using the function $ \psi(X_i, f_t(x^t_i)) = [f_t(x^t_i)]^2$, which is pseudo-Lipschitz with constant $L_{\psi} = 2$ by Lemma~\ref{lem:PL}), to find

 \begin{equation}
 \mathbb{P} \Big(\Big|  \frac{1}{n}\|f_t(\bx^t)\|^2 - \tau^n_{t+1} \Big| \geq \epsilon \Big) = \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n [f_t(x^t_i)]^2 -\tau^n_{t+1} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},
 \label{eq:finite_sample_conc2}
 \end{equation}

 where we have used the definition of the state evolution in \eqref{eq:state_evolution2} to give
 \begin{equation*}
 \begin{split}
  \mathbb{E}\Big\{\psi\big( X_0^n, f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big) \Big\} &=   \mathbb{E}\Big\{\big[f_{t}\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big]^2 \Big\} = \tau^n_{t+1}.
  \end{split}
 \end{equation*}

   Then the result in  \eqref{eq:finite_sample_matrix2} follows from the above by Lemma~\ref{powers}.

Finally we prove result \eqref{eq:finite_sample_matrix3} by applying \eqref{eq:finite_sample_app} using the function $ \psi(X_i, f_t(x^t_i)) = X_i f_t(x^t_i)$, which is pseudo-Lipschitz with constant $L_{\psi} = 2$ by Lemma~\ref{lem:PL}), to find

 \begin{equation}
 \mathbb{P} \Big(\Big|  \frac{1}{n} \langle \bX, f_t(\bx^t) \rangle -    \tau^n_{t+1} \Big| \geq \epsilon \Big) = \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n  X_i f_t(x^t_i) -    \tau^n_{t+1} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2t}}\Big\},
 \label{eq:finite_sample_conc2}
 \end{equation}

where
 \begin{equation*}
 \begin{split}
  \mathbb{E}\Big\{\psi\big( X_0^n, f_t\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big)\big) \Big\} =  \mathbb{E}\Big\{ X_0^n f_{t}\big(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z\big) \Big\} &=   \tau^n_{t+1},
  \end{split}
 \end{equation*}

where the final step uses the Law of Total Expectation to give $ \mathbb{E}\{X_0^n f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_{t}} Z)\} = \mathbb{E}\{[f_{t}(\mu_{t}X_0^n + \sqrt{\tau^n_{t}} Z)]^2\}$ in the case of the conditional expectation denoiser as in \eqref{eq:denoiser} and the state evolution definition in \eqref{eq:state_evolution2}.
   Then the result in  \eqref{eq:finite_sample_matrix3} follows  from the above  by Lemma~\ref{powers}.

 We wrap up the proof of Theorem~\ref{AMP-theorem} with the following Lemma which proves that the functions we used when applying result \eqref{eq:finite_sample_app} are indeed pseudo-Lipschitz with the stated constants.

 \begin{lemma}  \label{lem:PL}
 Recall the definition of pseudo-Lipschitz functions of order $2$ given in Definition~\ref{def:PL}.  The following functions $\psi: \mathbb{R}^2 \rightarrow \mathbb{R}$ are all pseudo-Lipschitz of order $2$ with  pseudo-Lipschitz constant $2$.
 \begin{equation}
 \begin{split}
 \psi_1(a, b)  &= (a - b)^2, \qquad  \qquad \psi_2(a, b)  = b^2, \qquad  \qquad \psi_3(a, b)  = a b.
 \label{eq:the_phis}
 \end{split}
 \end{equation}
 Moreover, the conditional expectation denoiser in \eqref{eq:denoiser} is Lipschitz with constant $L_f = \sqrt{\lambda_n}$ when $X_0^n \sim P_{X,n}$ and $P_{X,n}$ is either ${\rm Ber}(\rho_n)$ or Bernoulli-Rademacher and $\frac{\partial}{\partial x} f_t(x)  = \sqrt{\lambda_n} f_t(x)(1- f_t(x))$.
  \end{lemma}

 \begin{proof}
 Verifying the pseudo-Lipschitz property for the functions in \eqref{eq:the_phis} is straightforward, so we omit the details.
 First, recall that $f_t(\cdot)$ is the conditional expectation denoiser given in \eqref{eq:denoiser},

\begin{equation*}
 f_t(x) = \mathbb{E}\big \{X_0^n  \mid  \sqrt{\lambda_n} \tau^n_{t}  X_0^n + \sqrt{\tau^n_t} Z = x\big\}.
\end{equation*}

Notice that for either the Bernoulli or Bernoulli-Rademacher case, we have that $|f_t(x)| \leq 1$ for all $x \in \mathbb{R}$ since $X_0^n  \in \{- 1, 0, 1\}$.

 First consider $ P_{X,n} \sim {\rm Ber}(\rho_n)$ and we show that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $\sqrt{\lambda_n}$.
Let $\phi(x)$ denote the standard Gaussian density evaluated at $x$. First, by Bayes' Rule,

\begin{equation*}
\begin{split}
 f_t(x) &=\mathbb{E}\big \{X_0^n  \mid \sqrt{\lambda_n} \tau^n_{t}  X_0^n + \sqrt{\tau^n_t} Z = x\big\}  \\

&=P\big (X_0^n =1 \mid \sqrt{\lambda_n} \tau^n_{t} X_0^n + \sqrt{\tau^n_t} Z = x\big) = \frac{\rho_n \phi \big(    \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  }.

\end{split}
\end{equation*}

Now notice that $\frac{\partial}{\partial x} \phi (\frac{x-a }{b}) = - \frac{(x-a) }{b^2}\phi (\frac{x-a }{b}) $.  Using this and the representation above,

\begin{equation}
\begin{split}
\label{eq:deriv}

\frac{\partial}{\partial x} f_t(x) &= \frac{\partial}{\partial x}  \left[\frac{\rho_n \phi \big(    \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=   \frac{-f_t(x)}{\tau^n_{t}}  \left[ (x-\sqrt{\lambda_n} \tau^n_{t})  - \frac{x (1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n  (x-\sqrt{\lambda_n} \tau^n_{t})  \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=   \frac{-f_t(x)(x-\sqrt{\lambda_n} \tau^n_{t}) }{\tau^n_{t}}  \left[  \frac {(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big) \Big[1  -\frac{x}{(x-\sqrt{\lambda_n} \tau^n_{t}) } \Big]   }{(1-\rho_n) \phi \big(   \frac{x}{\sqrt{\tau^n_t}}\big)  + \rho_n \phi \big(  \frac{x-\sqrt{\lambda_n} \tau^n_{t} }{\sqrt{\tau^n_t}}\big)  } \right] \\

&=  \sqrt{\lambda_n} f_t(x)(1- f_t(x)).

\end{split}
\end{equation}

Therefore, using \eqref{eq:deriv}, we see that $\Big \lvert \frac{\partial}{\partial x} f_t(x) \Big \lvert \leq    \sqrt{\lambda_n} $ and it follows that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $  \sqrt{\lambda_n} $.

The fact  that $f_t(\cdot)$ is Lipschitz continuous with Lipschitz constant $\sqrt{\lambda_n}$ can be shown similarly for the case where $P_{X,n}$ is Bernoulli-Rademacher.

\end{proof}

\subsection{Finite sample guarantees}  \label{eq:appsec:finitesample}

Now we would like to discuss the proof of the result \eqref{eq:finite_sample_app}, namely,  for all order $2$ pseudo-Lipschitz functions denoted $\psi: \mathbb{R} \rightarrow \mathbb{R}$ with constant $L_{\psi}>0$ defined in Def.~\ref{def:PL}, for $\epsilon \in (0,1)$ and $t \geq 0$,

 \begin{equation}
 \begin{split}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_{t}(x^{t}_i)) -  \mathbb{E}\Big\{\psi\big(X_0^n,  f_{t}(\mu^n_{t} X_0^n + \sqrt{\tau^n_t} Z)\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\},
 \label{eq:finite_sample_app_2}
 \end{split}
 \end{equation}

 where $\bX = (X_1, \ldots, X_n)$ is the true signal and $C, C_t, c, c_t$ are universal constants not depending on $n$ or $\epsilon$, but with $C_t, c_t$ depending on the iteration $t$, whose exact value is given in Theorem~\ref{AMP-theorem}.

To prove the above, we will analyze a `symmetric'  AMP algorithm that we describe now, which is similar to the AMP algorithm in \eqref{eq:AMP}. Assume the matrix $\bZ \sim \textsf{GOE}(n)$ is an $n \times n$ matrix form the Gaussian Orthogonal Ensemble, i.e.\ $\bZ$ is a symmetric matrix with $\{Z_{ij}\}_{1 \leq i \leq j \leq n}$ are i.i.d.\ $\mathcal{N}(0,1/n)$, and $\{Z_{ii}\}_{1 \leq i  \leq n}$ are i.i.d.\ $\mathcal{N}(0,2/n)$.  Starting with an initial condition $\bh^0 \in \mathbb{R}^m$ independent of $\bZ$, let $\bh^{1} = \bZ g_0(\bh^0, \bX^n)$ and calculate for $t \geq 1$,
\begin{equation}
\bh^{t+1} = \bZ g_t(\bh^t, \bX^n) - \textsf{c}_t g_{t-1}(\bh^{t-1}, \bX^n).
\label{eq:sym_AMP}
\end{equation}
In the above, $g_t: \mathbb{R}^2 \to \mathbb{R}$ is Lipschitz and separable (act component-wise when applied to vectors) and may depend on $n$ through its Lipschitz constant $L_g^n$. The function $g_t$ takes
as its second argument  a random vector $\bX^n \in \mathbb{R}^n$ assumed to have entries that are i.i.d.\ according to $p_{X,n}$, a sub-Gaussian distribution, $\textsf{c}_t =  \frac{1}{n} \sum_{i=1}^n g'_t(h^{t}_i, X^n_i),$ with the derivative taken with respect to the first argument, and all terms with negative indices take the value $0$. Then the key result of AMP, stated in Theorem~\ref{thm:sym} below, is that for each $t \geq 1$, the empirical distribution of the components of iterates $\bh^t$ are approximately equal in distribution to a Gaussian $\mathcal{N}(0,\sigma^n_t)$ where the variances $\{\sigma^n_t\}_{t \geq 0}$ are defined via the state evolution: initializing with $\sigma^n_1 = \|g_0(\bh^0, \bX^n)\|^2/n$:
\begin{equation}
\sigma^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^n_{t}}Z, X_0^n) \right)^2\right],
\label{eq:symm_SE}
\end{equation}
where the expectation is with respect to standard Gaussian $Z$ independent of $X_0^n \sim p_{X,n}$.

\begin{thm} \label{thm:sym}
Consider the AMP algorithm in \eqref{eq:sym_AMP} for $\bh^0 \in \mathbb{R}^m$ independent of $\bA$ and Lipschitz, separable $g_t(\cdot, \cdot)$ with Lipschitz constant $L_g^n>0$.   Then the following holds for any (order-$2$) pseudo-Lipschitz function $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$,  $\ep \in (0,1)$ and  $t \geq 0$.

 \begin{equation}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \phi(h^{t}_i, X^n_i) -  \mathbb{E}\Big\{\phi\big(\sqrt{\sigma^n_t} Z, X^n_0\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_t \exp\Big\{- \frac{c c_t n \epsilon^2}{L_{\phi}^2 L_{g}^{4(t-1)}  \gamma_n^{t}}\Big\},
 \end{equation}

where the expectation is with respect to standard Gaussian $Z$ independent of $X_0^n \sim p_{X,n}$ and $\sigma^n_t$ is defined in \eqref{eq:symm_SE} and

\begin{equation}
\gamma_n^{t} := (\nu^n +  \sigma^n_{1})  (\nu^n +  \sigma^n_{1} +  \sigma^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \sigma^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_{t-1}\},
\end{equation}

where $\hat{\textsf{c}}_t = \mathbb{E}[ g'_t(\sqrt{\sigma^n_t} Z, X)]$ and $\nu$ is the variance factor of sub-Gaussian $X^n \sim p_{X,n}$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.

\end{thm}

In what follows we give the proof of Theorem~\ref{thm:sym}, which relies heavily on the proof of the finite sample guarantees for various `non-symmetric' AMP algorithms given in \cite{RushVenkataramanan}. Before we get to the proof of Theorem~\ref{thm:sym}, we discuss how we apply the result to our problem, leading to the concentration result in \eqref{eq:finite_sample_app_2}.

\paragraph{Proving \eqref{eq:finite_sample_app_2} with Theorem~\ref{thm:sym}.}
Recall that in our model~\eqref{WSM},

\begin{equation}\label{WSM_app}
\frac{1}{\sqrt{n}}\bW = \frac{\sqrt{\lambda_n}}{n} \bX\otimes \bX +  \bZ\,,
\end{equation}

where $\lambda_n >0$ controls the strength of the signal and the noise is i.i.d.\ gaussian $Z_{ij}\sim{\cal N}(0,1/n)$ for $i<j$ and symmetric $Z_{ij}=Z_{ji}$. Then the AMP algorithm for recovering $\bX$ from the data $\bW$ is given in \eqref{eq:AMP} and restated now.   Let $\bA = \bW/\sqrt{n}$ and initialize  with $\bx^0$ independent of $\bW$, such that $\langle \bx^0, \bX \rangle > 0$.  Then let $\bx^{1} = \bA  f_0(\bx^{0})$, and for $t \geq 1$, compute

\begin{equation}
\bx^{t+1} = \bA  f_t(\bx^{t}) - \mathsf{b}_t  f_{t-1}(\bx^{t-1}), \qquad \mathsf{b}_t  = \frac{1}{n} \sum_{i=1}^n f'_t(x^{t}_i),
\label{eq:AMP2}
\end{equation}

Notice that this AMP algorithm in \eqref{eq:AMP2} is similar to that in \eqref{eq:sym_AMP}, the only difference being that now the matrix $\bA$ is our data matrix (as opposed to it being $\textsf{GOE}(n)$ as is assumed in \eqref{eq:sym_AMP}). If we plug into \eqref{eq:AMP2} the value of $\bW$ from \eqref{WSM_app}, we find that $\bx^{1} = \frac{\sqrt{\lambda_n}}{n}  \bX \langle \bX, f_0(\bx^{0}) \rangle  +  \bZ  f_0(\bx^{0})$, and for $t \geq 1$,

\begin{equation}
\bx^{t+1} = \frac{\sqrt{\lambda_n}}{n}  \bX \langle \bX, f_t(\bx^{t}) \rangle  +  \bZ  f_t(\bx^{t}) - \mathsf{b}_t  f_{t-1}(\bx^{t-1}).
\label{eq:AMP3}
\end{equation}

We will prove \eqref{eq:finite_sample_app_2} inductively on $t$.  We begin with the base case, when $t=0$, and show the result follows from Heoffding's Inequality in Lemma~\ref{lem:hoeff_lem}. First, by \eqref{eq:AMP3}, we have that

$
\bx^{1} = \frac{\sqrt{\lambda_n}}{n}  \bX \langle \bX, f_0(\bx^{0}) \rangle  +  \frac{1}{\sqrt{n}}  \bZ  f_0(\bx^{0})=  \mu^n_1  \bX   +  \frac{1}{\sqrt{n}}  \bZ  f_0(\bx^{0}),
$

where we recall that $\mu^n_1 = \sqrt{\lambda_n} \langle f_0(\bx^0), \bX \rangle/n$ by \eqref{eq:state_evolution_start}.    Next notice that  $\frac{1}{\sqrt{n}}  \bZ  f_0(\bx^{0}) \overset{d}{=} \sqrt{\tau_1^n} \mathbf{G}$ where $\mathbf{G}$ is a length-$n$ vector of (marginally) standard Gaussian random variables with a dependency structure between entries (that is not necessary to characterize) coming from the symmetry of $\bZ$ where $\tau^n_1 = \| f_0(\bx^0) \|^2/n$ by  \eqref{eq:state_evolution_start}.
Then it follows

 \begin{equation}
 \label{induct_step1}
 \begin{split}
 &\mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(X_i, f_1(x^1_i)) -  \mathbb{E}\Big\{\psi\big(X_0^n, f_1(\mu^n_1 X_0^n + \sqrt{\tau^n_1} Z)\big) \Big\} \Big| \geq \epsilon \Big) \\

 &=  \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi\left(X_i, f_1\left( \mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right) -  \mathbb{E}\Big\{\psi\big(X_0^n, f_1(\mu^n_1 X_0^n + \sqrt{\tau^n_1} Z)\big) \Big\} \Big| \geq \epsilon \Big).
 \end{split}
 \end{equation}

Now we can apply Hoeffding's Inequality directly: defining the random variables $Y_i:= \psi\left(X_i, f_1\left(\mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right)$ is is easy to see that the probability in \eqref{induct_step1} takes the following form:

$
\mathbb{P} (| \frac{1}{n} \sum_{i=1}^n Y_i -  \mathbb{E}\{Y_i\} | \geq \epsilon ).
$

To apply Hoeffding's inequality we notice that for pseudo-Lipschitz (of order 2) function $\psi$,
\begin{equation*}
|\psi(a,b)| - |\psi(0,0) | \leq |\psi(a,b) - \psi(0,0) | \leq L_{\psi} (1 + \|(a,b)\|)\|(a,b)\|,
\end{equation*}
and therefore
\begin{equation*}
\begin{split}
|Y_i | &= \left|\psi\left(X_i, f_1\left( \mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right) \right| \\

&\leq L_{\psi} \left(1 + \left \|\left(X_i, f_1\left(\mu^n_1X_i   +  \sqrt{\tau_1^n} G_i \right)\right) \right\| \right) \left\|\left(X_i, f_1\left(\mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right) \right\| + |\psi(0,0)|.
\end{split}
\end{equation*}
We  further bound the above using that
\begin{equation*}
\left \|\left(X_i, f_1\left(\mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right) \right\|^2 = X_i^2 + \left[f_1\left( \mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right]^2 \leq 2,
\end{equation*}
in which case we find
\begin{equation*}
\begin{split}
|Y_i | &= \left|\psi\left(X_i, f_1\left( \mu^n_1 X_i   +  \sqrt{\tau_1^n} G_i \right)\right) \right| \leq \kappa L_{\psi}+ |\psi(0,0)|.
\end{split}
\end{equation*}
Then applying Hoeffding's inequality

 \begin{equation}
 \begin{split}
 \label{eq:hoeff1}
 &T_1  \leq  2\exp\left\{ - \frac{2n^2 \ep^2}{\sum_{i} \left(\kappa L_{\psi}+ |\psi(0,0)|\right)^2 }\right\} \leq   2\exp\left\{ - \frac{\kappa n \ep^2}{L^2_{\psi} }\right\}.
 \end{split}
 \end{equation}

We finally point out that the relevant $\psi$ functions we use are those in Lemma~\ref{lem:PL} and for all cases, $\psi(0,0) = 0$.

Now we consider the inductive step: we assume \eqref{eq:finite_sample_app_2} is true up to iteration $t-1$ and prove it holds for iteration $t$.
To do this, we define a related iteration to \eqref{eq:AMP3} as follows. Initialize with $\bh^0 = \bx^0$ with denoiser $g_{0}(\bh^{0}, \bX) := f_0(\bx^0)$ and $\bh^{1} =  \mu_{1}^n \bX^n + \bZ g_{0}(\bh^{0}, \bX) $.  Then calculate for $t \geq 1$,

\begin{equation}
\bh^{t+1} =   \bZ  g_t(\bh^{t}, \bX^n) - \mathsf{c}_t  g_{t-1}(\bh^{t-1}, \bX^n), \qquad \mathsf{c}_t  = \frac{1}{n} \sum_{i=1}^n g'_t(h^{t}_i, X^n_i)
\label{eq:AMP_correct}
\end{equation}

where $g_t(h, X) = f_t(h + \mu_{t}^n X^n)$ for $f_t(\cdot)$ the conditional expectation denoiser used in \eqref{eq:AMP3} and $ \mu_{t+1}^n$ calculated from the state evolution in \eqref{eq:state_evolution} for our original iteration (i.e., the algorithm in \eqref{eq:AMP2}).  In the above, $\bX^n$ is the signal in \eqref{WSM_app} and we drop the $n$ superscript in what follows.  Then we notice that the iteration in \eqref{eq:AMP_correct} takes the exact form of the symmetric AMP in \eqref{eq:sym_AMP} with state evolution given by \eqref{eq:symm_SE}.  In particular, the state evolution associated with \eqref{eq:AMP_correct} takes the form $\sigma^n_1 = \|g_0(\bh^0, \bX)\|^2/n$ and for $t \geq 1,$

\begin{equation}
\sigma^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^n_{t}}Z, X) \right)^2\right]= \mathbb{E}\left[\left(f_{t}(\sqrt{\sigma^n_{t}}Z + \mu^n_t X) \right)^2\right].
\label{eq:symm_SE_new}
\end{equation}

We notice that in the above, the state evolution has the same form as the state evolution for the AMP algorithm in \eqref{eq:AMP3} defined  in \eqref{eq:state_evolution2} as in $\sigma^n_1 = \tau^n_1$ and $\sigma^n_{t+1} = \tau^n_{t+1}$ for all $t \geq 1$ and for this reason we use the $\tau$ notation in what follows.
As the AMP algorithm in \eqref{eq:AMP_correct} takes the exact form of the symmetric AMP in \eqref{eq:sym_AMP}, we can apply Theorem~\ref{thm:sym}.  The relevant pseudo-Lipschitz function for which to apply Theorem~\ref{thm:sym} is $\phi(h^{t}_i, X^n_i) =  \psi(f_{t}(h^{t}_i+ \mu_{t}^n X^n_i), X^n_i)$ for $\psi$ the pseudo-Lipschitz function in \eqref{eq:finite_sample_app_2}, and using this Theorem~\ref{thm:sym} implies

 \begin{equation}
 \begin{split}
& \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) -  \mathbb{E}\Big\{\psi\big(f_{t}(\sqrt{\tau^n_t} Z+ \mu_{t}^n X), X\big) \Big\} \Big| \geq \epsilon \Big) \\

&\hspace{5mm} \leq C C_{t} \exp\Big\{- \frac{c c_{t} n \epsilon^2}{L_{\phi}^2 L_{g}^{4(t-1)}  \gamma_n^{t}}\Big\} = C C_{t} \exp\Big\{- \frac{c c_{t} n \epsilon^2}{L_{\psi}^2 \max\{1,  \lambda_n (\tau_{t}^n)^2\} \lambda_n^{2t-1}  \gamma_n^{t}}\Big\},
  \label{eq:sym_result}
  \end{split}
 \end{equation}

with $\tau^n_t = \sigma^n_t$ defined in \eqref{eq:symm_SE_new} and

\begin{equation}
\gamma_n^{t} := (\nu^n +  \tau^n_{1})  (\nu^n +  \tau^n_{1} +  \tau^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t} \tau^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_{t-1}\},
\end{equation}

where $\hat{\textsf{c}}_t = \mathbb{E}[ g'_t(\sqrt{\tau^n_t} Z, X)] =  \mathbb{E}[ f'_t(\sqrt{\tau^n_t} Z + \mu^n_t X)]$ and $\nu$ is the variance factor of sub-Gaussian $X^n \sim p_{X,n}$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.  We note that the final equality in \eqref{eq:sym_result} follows since $L_g = L_f = \sqrt{\lambda_n}$ in this case and $L_{\phi} = L_{\psi} \max\{\sqrt{\lambda_n},  \lambda_n \tau_{t}^n\}$ which can be seen as follows

 \begin{equation*}
 \begin{split}
\lvert  \phi(h,X) -   \phi(\tilde{h},\tilde{X}) \lvert &= \lvert   \psi(f_{t}(h+ \mu_{t}^n X), X) -     \psi(f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X}),\tilde{X})  \lvert \\
&\leq L_{\psi}  \| (f_{t}(h+ \mu_{t}^n X), X) -    (f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X}),\tilde{X})  \|\\
&\leq L_{\psi} ( | f_{t}(h+ \mu_{t}^n X) - f_{t}(\tilde{h}+ \mu_{t}^n \tilde{X})|+ | X  - \tilde{X}|) \\
&\leq L_{\psi}  L_f | h- \tilde{h}| + L_{\psi}  L_f \mu_{t}^n |X- \tilde{X}|+ L_{\psi} | X  - \tilde{X}|.
\end{split}
 \end{equation*}

  Recall, that we would like to show the following, under the inductive hypothesis that it holds with $t$ replaced by $t-1$,

 \begin{equation*}
 \begin{split}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i) -  \mathbb{E}\Big\{\psi\big(f_{t}(\mu^n_{t} X_0 + \sqrt{\tau^n_t} Z), X_0\big) \Big\} \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\},
 \end{split}
 \end{equation*}

and we notice that  in light of \eqref{eq:sym_result}, since the expectations are the same, we can prove the above employing Lemma~\ref{sums} if we can prove the following result:

 \begin{equation}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \geq \epsilon \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\}.
 \label{eq:to_show_sym}
 \end{equation}

So now our aim is to prove \eqref{eq:to_show_sym}.

To demonstrate  \eqref{eq:to_show_sym}, we first notice that

 \begin{equation*}
 \begin{split}
&\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big|  \leq \frac{1}{n} \sum_{i=1}^n \Big| \psi(f_{t}(x^{t}_i), X_i) -\psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \\

 & \leq \frac{1}{n} \sum_{i=1}^n L_{\psi} \Big(1 + \|(f_{t}(x^{t}_i), X_i)\| + \|\psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i)\| \Big)  \Big| f_{t}(x^{t}_i) - f_{t}(h^{t}_i+ \mu_{t}^n X_i)  \Big|\\

 & \leq \frac{ \kappa L_{\psi} }{n} \sum_{i=1}^n  \Big| f_{t}(x^{t}_i) - f_{t}(h^{t}_i+ \mu_{t}^n X_i)  \Big|  \leq \frac{ \kappa L_{\psi}  L_f }{n} \sum_{i=1}^n  \Big| x^{t}_i - h^{t}_i- \mu_{t}^n X_i  \Big| \leq \frac{ \kappa L_{\psi}  L_f }{\sqrt{n}}   \Big\| \bx^{t} - \bh^{t}- \mu_{t}^n \bX  \Big\|.
\end{split}
 \end{equation*}

Thus,

 \begin{equation}
 \mathbb{P} \Big(\Big| \frac{1}{n} \sum_{i=1}^n \psi(f_{t}(x^{t}_i), X_i)  - \psi(f_{t}(h^{t}_i+ \mu_{t}^n X_i), X_i) \Big| \geq \epsilon \Big) \leq \mathbb{P} \Big( \frac{1}{\sqrt{n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\| \geq \frac{\kappa \epsilon}{ L_{\psi}  L_f} \Big),
 \label{eq:bound1}
 \end{equation}

and so to prove  \eqref{eq:to_show_sym} we will instead show

 \begin{equation}
\mathbb{P} \Big( \frac{1}{\sqrt{n}}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\| \geq \frac{\kappa \epsilon}{ L_{\psi}  L_f} \Big) \leq C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\lambda_n^{2 t} L_{\psi}^{2t}}\Big\}.
 \label{eq:to_show_delta}
 \end{equation}

from which  \eqref{eq:to_show_sym} follows by \eqref{eq:bound1}. This is done inductively again. First notice that the case $t=0$ is trivially true since $ \bx^{0} = \bh^{0}$ and $ \mu_{0}^n = 0$.  Thus we assume \eqref{eq:to_show_delta} is true up through iteration $t-1$ and prove it for iteration $t$.

Considering result \eqref{eq:to_show_delta}, and using the definitions of $\bx^{t+1}$ and $\bh^{t+1}$ from \eqref{eq:AMP3} and \eqref{eq:AMP_correct} along with Cauchy-Schwarz inequality, we have that

 \begin{equation}
 \begin{split}
  \label{eq:bound2}
& \frac{1}{n} \sum_{i=1}^n  \Big| x^{t}_i - h^{t}_i- \mu_{t}^n X_i  \Big|^2\\

 &\leq   \frac{3}{n}\Big\lvert  \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n\Big \lvert^2 \sum_{i=1}^n  X_i^2 +   \frac{1}{n} \sum_{i=1}^n  \Big|   [\bZ  f_{t-1}(\bx^{t-1})]_i -   [\bZ g_{t-1}(\widetilde{\bx}^{t-1}, \bX)]_i \Big|^2 \\%
 & +  \frac{1}{n} \sum_{i=1}^n  \Big|  \mathsf{b}_{t-1}  f_{t-2}(x^{t-2}_i) - \mathsf{c}_{t-1} g_{t-2}(h^{t-2}_i, X_i)  \Big|^2 \\

  &=3  \Big \lvert \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n \Big\lvert^2  \frac{1}{n}  \sum_{i=1}^n  X_i^2  +   \frac{3}{n}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\|^2 \\%
 & +  \frac{3}{n}   \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \|^2.
\end{split}
 \end{equation}

Now we use the upper bounds in  \eqref{eq:bound2} along with Lemma~\ref{sums} to give the following upper bound on the probability on the LHS of \eqref{eq:to_show_delta}:

 \begin{equation}
 \begin{split}
\mathbb{P} \Big( \frac{1}{n}   \Big\| \bx^{t} - \bh^{t} - \mu_{t}^n \bX  \Big\|^2 \geq \frac{\kappa \epsilon^2}{ L_{\psi}^2  L_f^2} \Big)  &\leq \mathbb{P} \Big( \Big \lvert \frac{\sqrt{\lambda_n}}{n}  \langle \bX, f_{t-1}(\bx^{t-1}) \rangle  - \mu_{t}^n \Big\lvert^2 \frac{1}{n}  \sum_{i=1}^n   X_i^2  \geq \frac{\kappa \epsilon}{ L_{\psi}^2  L_f^2} \Big) \\

 &+ \mathbb{P} \Big(\frac{1}{n}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\|^2  \geq \frac{\kappa \epsilon}{L_{\psi}^2  L_f^2} \Big) \\

 &+ \mathbb{P} \Big( \frac{1}{n}   \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \|^2 \geq \frac{\kappa \epsilon}{L_{\psi}^2  L_f^2} \Big).

 \label{eq:three_terms}
 \end{split}
 \end{equation}

We label the three terms in the above $T_1-T_3$ and provide an upper bound for each.

First consider term $T_1$ of \eqref{eq:three_terms}.

\begin{equation}
  \begin{split}

&T_1 \leq  \mathbb{P} \Big(  \Big|   \frac{\sqrt{\lambda_n}}{n} \langle \bX, f_t(\bx^{t}) \rangle  -  \mu^n_{t}  \Big|^2  \Big( \Big \lvert\frac{ 1}{n} \sum_{i=1}^nX_i^2  \Big) \geq \frac{\kappa \epsilon}{ L^2_{\psi} L^2_f}  \Big) \\

&\leq  \mathbb{P} \Big(  \Big|   \frac{\sqrt{\lambda_n}}{n} \langle \bX, f_t(\bx^{t}) \rangle  -  \mu^n_{t}  \Big| \geq \frac{\kappa \sqrt{\epsilon}}{ \sqrt{\rho_n} L_{\psi} L_f}  \Big)  +  \mathbb{P} \Big(   \frac{ 1}{n} \sum_{i=1}^nX_i^2  \geq2 \rho_n \Big)  \\

&\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{\rho_n \lambda_n^{2t} L_{\psi}^{2t} }\Big\} + 2 \exp\Big\{- \frac{ n \rho_n}{2 }\Big\}

\label{eq:T1_bound}
 \end{split}
 \end{equation}

  where the final inequality follows by the induction hypothesis for the first term,
  using the pseudo-Lipschitz function $\psi(a, b) = a b$, and Chernoff's bounds (Lemma~\ref{lem:chernoff}) for the second term.

Now consider term $T_2$ of \eqref{eq:three_terms} and first notice that

\begin{equation*}
\begin{split}

&\frac{1}{\sqrt{n}}  \Big \|  \bZ \big( f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \big) \Big\| \leq \frac{1}{\sqrt{n}}   \|  \bZ \|_{op} \Big\| f_{t-1}(\bx^{t-1}) -   g_{t-1}(\bh^{t-1}, \bX) \Big\| \\

&\leq\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} \Big\| f_{t-1}(\bx^{t-1}) -   f_{t-1}(\bh^{t-1} + \mu_{t-1}^n \bX) \Big\| \\

&\leq\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} L_f \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\|,

\end{split}
\end{equation*}

where the final inequality uses the Lipschitz property of $f_t$.
Therefore, using the same strategy as in \eqref{eq:T1_bound}, we have

\begin{equation*}
  \begin{split}

&T_2 \leq   \mathbb{P} \Big(\big( \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert + 4 \big)  \frac{1}{\sqrt{n}} L_f \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\| \geq \frac{\kappa \epsilon}{L_{\psi}  L_f} \Big)  \\

&\leq  \mathbb{P} \Big(   \frac{1}{\sqrt{n}} \Big\| \bx^{t-1} -   \bh^{t-1} + \mu_{t-1}^n \bX \Big\| \geq \frac{\kappa \sqrt{\ep}}{L_{\psi}  L_f^2} \Big) + \mathbb{P} \Big(  \big \lvert  \|  \bZ \|_{op} - 4 \big \lvert   \geq \sqrt{ \ep}  \Big) \\

&\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon}{\rho_n \lambda_n^{2(t+1)} L_{\psi}^{2t} }\Big\} + 2 \exp\Big\{- \frac{ n \rho_n \ep}{2 }\Big\}

 \end{split}
 \end{equation*}
 where the final inequality follows from the inductive hypothesis for \eqref{eq:to_show_delta} and \textcolor{red}{a result about operator norms of Gaussian matrices.}

 Finally consider term $T_3$ of \eqref{eq:three_terms}. We first give an upper bound using  the definition of $g_t$ and the Lipschitz property of $f_t$ as follows:
\begin{equation}
\begin{split}
\label{eq:termT3_1}
 & \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

 & \leq  |\mathsf{b}_{t-1}| \Big\|   f_{t-2}(\bx^{t-2}) -  g_{t-2}(\bh^{t-2}, \bX)  \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |  \Big \| g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

 & \leq  |\mathsf{b}_{t-1}| \Big\|   f_{t-2}(\bx^{t-2}) -  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |  \Big \|  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \| \\

 & \leq   \sqrt{\lambda_n} L_f \Big\|  \bx^{t-2} -  \bh^{t-2} + \mu_{t-2}^n \bX \Big \| +  | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} | \sqrt{n}.
  \end{split}
  \end{equation}

In the final step we use that

 \begin{equation*}
 | \mathsf{b}_{t-1}   | \leq  \frac{1}{n} \sum_{i=1}^n \big| f'_{t-1}(x^{t-1}_i)  \big | \leq  \sqrt{\lambda_n}, \qquad \text{ and } \qquad \Big \|  f_{t-2}(\bh^{t-2} - \mu_{t-2}^n \bX)  \Big \|^2 \leq n.
 \end{equation*}

 We investigate the term $| \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} |$ and recall from their definitions in \eqref{eq:AMP2} and \eqref{eq:AMP_correct},

 \begin{equation}
 \begin{split}
& | \mathsf{b}_{t-1}   - \mathsf{c}_{t-1} | \leq  \frac{1}{n} \sum_{i=1}^n \big| f'_{t-1}(x^{t-1}_i) -  g'_{t-1}(h^{t-1}_i, X_i) \big |=\frac{1}{n} \sum_{i=1}^n \big|  f'_{t-1}(x^{t-1}_i) -    f'_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i ) \big | \\
&\overset{(a)}{=}   \frac{\sqrt{\lambda_n}}{n} \sum_{i=1}^n   \Big|f_{t-1}(x^{t-1}_i)(1- f_{t-1}(x^{t-1}_i)) -  f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i)(1- f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i) )\Big | \\
&\overset{(b)}{\leq} \frac{\sqrt{\lambda_n}}{n} \sum_{i=1}^n \Big|   f_{t-1}(x^{t-1}_i) -  f_{t-1}(h^{t-1}_i - \mu_{t-1}^n X_i)  \Big | \overset{(c)}{\leq} \frac{L_f \sqrt{\lambda_n}}{n} \sum_{i=1}^n \Big|   x^{t-1}_i -  h^{t-1}_i + \mu_{t-1}^n X_i  \Big |.
\label{eq:sfterms}
 \end{split}
 \end{equation}

In the above, step $(a)$ uses Lemma~\ref{lem:PL} for computing the derivative $f_t$ and step $(b)$ uses the bound
  \begin{equation}
 \begin{split}
 \big| f_{t-1}(a)(1- f_{t-1}(a)) -  f_{t-1}(b)(1- f_{t-1}(b) \big | &\leq  \big| f_{t-1}(a) -  f_{t-1}(b)\big |   + \big |  [f_{t-1}(a)]^2 -  [f_{t-1}(b)]^2 \big | \\

& \leq  \kappa \big| f_{t-1}(a) -  f_{t-1}(b)\big |.
 \end{split}
 \end{equation}
 Finally, step $(c)$ in \eqref{eq:sfterms} uses the Lipschitz property of $f_{t}$.
Plugging the above bounds in \eqref{eq:sfterms} into \eqref{eq:termT3_1}, we have

 \begin{equation}
\begin{split}
\label{eq:termT3_2}
 & \Big\|  \mathsf{b}_{t-1}  f_{t-2}(\bx^{t-2}) - \mathsf{c}_{t-1} g_{t-2}(\bh^{t-2}, \bX)  \Big \| \\

  & \leq   \sqrt{\lambda_n} L_f \Big\|  \bx^{t-2} -  \bh^{t-2} + \mu_{t-2}^n \bX \Big \| + \sqrt{\lambda_n}   L_f    \Big\|   \bx^{t-1} - \bh^{t-1} + \mu_{t-1}^n \bX  \Big \|.

  \end{split}
  \end{equation}

 Now we have from Lemma~\ref{sums} that

 \begin{equation}
\begin{split}
\label{eq:termT3_2}
T_3 &\leq 2 \mathbb{P} \Big(\frac{1}{\sqrt{n}}  \Big\|   \bx^{t-1} - \bh^{t-1} + \mu_{t-1}^n \bX  \Big \| \geq \frac{\kappa \sqrt{\epsilon}}{L_{\psi} L^2_f \sqrt{\lambda_n}} \Big)\leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon}{ \lambda_n^{2(t+2)} L_{\psi}^{2t} }\Big\} .
  \end{split}
  \end{equation}

The final bound  follows from the inductive hypothesis for \eqref{eq:to_show_delta}.

\paragraph{Proving Theorem~\ref{thm:sym}.}
 Now we we discuss the proof of Theorem~\ref{thm:sym}.
 In doing so, we rely heavily on the proof of the finite sample guarantees for various `non-symmetric' AMP algorithms given in \cite{RushVenkataramanan}. So to begin with, we review the results in \cite{RushVenkataramanan}.
The main concentration result of \cite{RushVenkataramanan}, restated in Theorem \ref{thm:main_amp_perf} below, analyzes the following general AMP recursion. Let $\bA \in \mathbb{R}^{m \times n}$ be a matrix with i.i.d.\ standard Gaussian entries $A_{ij} \sim \mathcal{N}(0,\frac{1}{n})$ for $1 \leq i \leq m$ and $1 \leq j \leq n$.
Set an initial condition $\bv^{0} \in \mathbb{R}^n$ independent of $\bA$ then for $t \geq 0$, calculate
 \begin{equation}
\begin{split}
\bu^t & = \bA f_t(\bv^t, \bV^n) - \lambda_t g_{t-1}(\bu^{t-1}, \bU^m), \\
\bv^{t+1} & = \bA^* g_{t}(\bu^{t}, \bU^m) - \xi_t  f_t(\bv^t, \bV^n).
\end{split}
\label{eq:gen_rec0}
 \end{equation}
In the above, the vectors $\bu^t \in \mathbb{R}^m$, $\bv^{t+1} \in \mathbb{R}^n$  describe the state of the algorithm, the functions $f_t, g_t: \mathbb{R}^2 \to \mathbb{R}$ are Lipschitz functions with constants $L^n_f, L^m_g > 0$ that are also separable, taking as input random vectors $\bU^m \in \mathbb{R}^m$ and $\bV^n \in \mathbb{R}^n$ whose entries are i.i.d.\ according to a sub-Gaussian distributions $p_{U,m}$ and $p_{V,n}$, and the scalars $\lambda_t$ and $ \xi_t$ are computed from the state of the algorithm as
\begin{equation*}
\lambda_t =  \frac{1}{m} \sum_{i=1}^n f'_t(v^{t}_i, V^n_i), \qquad  \xi_t  = \frac{1}{n} \sum_{i=1}^n g'_t(u^{t}_i, U^m_i),
\end{equation*}
where the derivatives are taken with respect to the first argument.
The state evolution is then defined as follows: setting $\sigma^m_1 = \|f_0^2(\bv^0, \bV^n)\|^2/m$ and calculate for $t \geq 0$,
\begin{equation}
\label{eq:nonsym_AMP}
\tau^n_{t+1} = \mathbb{E}\left[\left(g_{t}(\sqrt{\sigma^m_{t}}Z, U^m) \right)^2\right], \qquad \sigma^m_{t+1} = \frac{n}{m}\mathbb{E}\left[\left(f_{t+1}(\sqrt{\tau^n_{t+1}}Z, V^n) \right)^2\right],
\end{equation}
where $Z$ is a standard Gaussian random variable independent of $U^m \sim p_{U, m}$ and $V \sim p_{V,n}$.

The AMP algorithm given in \eqref{eq:sym_AMP} is a symmetric version of the one in \eqref{eq:gen_rec0} where the state of the algorithm is represented by a single vector $\bx^{t+1}  \in \mathbb{R}^{n}$, the function $f_t: \mathbb{R}^2 \to \mathbb{R}$ in \eqref{eq:AMP} is Lipschitz and separable with Lipschitz constant $L_f^n > 0$ possibly depending on $n$, and $\mathsf{b}_t$ is a constant computed from the state of the algorithm. We present here the rigorous non-asymptotic analysis given in \cite{RushVenkataramanan} for the recursion in \eqref{eq:gen_rec0}.  We show that this result can be easily extended to obtain an analogous non-asymptotic result for the symmetric recursion in \eqref{eq:AMP}.

Before stating Theorem \ref{thm:main_amp_perf} below, we give the assumptions on the model and the functions used to define the AMP.  In what follows, $K, \kappa > 0$ are generic positive constants whose values are not exactly specified but do not depend on $n$. \\

 \textbf{Random Vectors:} Random vectors $\bU^m \in \mathbb{R}^m$ and $\bV^n \in \mathbb{R}^n$ are used for the denoising functions. The entries of the vectors are i.i.d.\ according to a sub-Gaussian distributions $p_{U,m}$ and $p_{V,n}$.  We recall that a zero-mean random variable $X$ is sub-Gaussian if there exist positive constants $K, \kappa$ such that $P(\abs{X - \mathbb{E}X} > \ep) \leq K e^{-\kappa \ep^2}$, for all $\ep >0$. \\

\textbf{The Functions $f_t, g_t$}: The denoising functions, $f_t: \mathbb{R}^2 \rightarrow \mathbb{R}$ and $g_t: \mathbb{R}^2 \rightarrow \mathbb{R}$, in \eqref{eq:gen_rec0} are Lipschitz continuous for each $t \geq 0$, with Lipschitz constants denoted $L^n_f, L^n_g >0$, may depend on $n$. By the Lipschitz property, $f_t, g_t$ are weakly differentiable. The weak derivatives, denoted by $f'_t, g'_t$, is assumed to be differentiable.

In addition, the result \cite[Theorem 1]{RushVenkataramanan} uses a stopping criterion similar to the one discussed for the symmetric AMP above. The details can be found in \cite[Section 2.1]{RushVenkataramanan} and we do not elaborate here.
Under the above assumptions, the main result in \cite[Theorem 1]{RushVenkataramanan} is restated below in Theorem \ref{thm:main_amp_perf}.
\begin{thm}{\cite[Theorem 1]{RushVenkataramanan}} \label{thm:main_amp_perf}
Under the assumptions above, the following holds for any (order-$2$) pseudo-Lipschitz function $\phi: \mathbb{R}^2 \rightarrow \mathbb{R}$ with constant $L_{\phi}$,  $\ep \in (0,1)$ and  $0 \leq t < T^*$, where $T^*$ is the first iteration for which the stopping criterion is satisfied.
 \begin{equation}
 \begin{split}
P\left(\left \lvert \frac{1}{n} \sum_{i=1}^n \phi(v^{t+1}_i, V^n_i) - \mathbb{E}\left[\phi\left( \tau_{t+1} Z, V^n \right) \right]\right \lvert \geq \ep\right) \leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{L_f^{2t}  L_g^{2t} L_{\phi}^2}\Big\} \\
P\left(\left \lvert \frac{1}{m} \sum_{i=1}^m \phi(u^{t}_i, U^m_i) - \mathbb{E}\left[\phi\left( \sigma_{t} Z, U^m \right) \right]\right \lvert \geq \ep\right) \leq  C C_{t-1} \exp\Big\{- \frac{c c_{t-1} n \epsilon^2}{L_f^{2t} L_g^{2t}  L_{\phi}^2}\Big\}
\label{eq:PL_conc_result}
 \end{split}
 \end{equation}
In the expectation above,  $Z \sim \mathcal{N}(0,1)$ independent of $U^m \sim p_{U,m}$ and $V^n \sim p_{V,n}$ and  $\tau^n_t, \sigma^m_t$ is given by \eqref{eq:nonsym_AMP}.  The constants $C_t, C_t$ are given by
$C_t =C_1^{t} (t!)^{C_2},  c_t = [c_1^{t} (t!)^{c_2}]^{-1}$  and $C, C_1, C_2, c, c_1, c_2$ are universal constants not depending on $n$ or $\epsilon$.
\end{thm}

In what follows we discuss the proof of Theorem~\ref{thm:main_amp_perf} originally given in \cite{RushVenkataramanan} and show how it is adapted for the symmetric version, in particular focusing on the dependence of the Lipschitz constants in the bound.

\paragraph{Spectral Initialization.}
As mentioned previously in Section~\ref{sec:matrixWalgo}, we will assume that the AMP iteration in \eqref{eq:gen_rec0} was initialized with $\bv^{0} \in \mathbb{R}^n$ independent of $\bA$. For estimation with a Bernoulli-Rademacher signal prior, one needs to instead use a spectral initialization that will not be independent of the matrix $\bA$. Theoretically, as introduced in \cite{montanari2017estimation}, one deals with this dependency by analyzing the AMP iteration with a matrix $\widetilde{\bA}$ that is an \emph{approximate} representation of the conditional distribution of $\bA$ given the initialization, and then showing that with high probability the two algorithms are close each other.  We do not give the details of this rather technical argument here, and instead analyze the simpler case using an independent initialization, though the generalize is likely straightforward.

\paragraph{Conditional Distribution Step.}
The proof of \cite[Theorem 1]{RushVenkataramanan} proceeds in two steps.  In the first step, one studies the conditional distribution of $\bA$ given the  output of the algorithm up until iteration $t$, treating $\bA$ as random and the output as deterministic.  In the non-symmetric AMP, $\bA$ is an i.i.d.\ Gaussian measurement matrix and this conditional distribution was  originally studied in \cite{bayati2011dynamics} and the result is concisely stated in \cite[ Lemma 4.2]{RushVenkataramanan}. For the symmetric AMP in \eqref{eq:sym_AMP}, the matrix $\bZ$ is $\textsf{GOE}(n)$ and so this conditioning argument needs to take into account the symmetry of the matrix entries.  This has been studied in other works that give asymptotic characterizations of the performance of symmetric AMP, for example in \cite[Lemma 3]{Montanari-Javanmard}, and these results apply directly to our case since this distributional characterization is already non-asymptotic and does not change in our setting.

\newcommand{\norm}[1]{\lVert#1\rVert}
\newcommand{\mscrs}{\mathscr{S}}
\newcommand{\bH}{\mathbf{H}}
\newcommand{\bDel}{\boldsymbol{\Delta}}
\newcommand{\bigM}{\mathbf{M}}

Using \cite[Lemma 3]{Montanari-Javanmard} to characterize the distribution of $\bZ$ conditioned on the sigma algebra $\mathscr{S}_{t}$, we are able to specify the conditional distributions of $\bh^{t+1}$ given $\mathscr{S}_{t}$ where we define $\mathscr{S}_{t}$ for $ t\geq 0$ to be the sigma-algebra generated by
\begin{equation*}
\bh^0, \bh^1, ..., \bh^{t}, \mathbf{m}^0 := g_0(\bh^0, \bX^n), ...,  \mathbf{m}^t := g_t(\bh^t, \bX^n),\text{ and }  \bX^n.
\end{equation*}
Notice we have introduced the notation $\mathbf{m}^0 := g_0(\bh^0, \bX^n), ..., \mathbf{m}^t := g_t(\bh^t, \bX^n)$.
Observe that conditioning on $\mscrs_{t}$ is equivalent to conditioning on the linear constraint\footnote{While conditioning on the linear constraints, we emphasize that only $\bA$ is treated as random.}
\begin{equation*}
\bZ \bigM_{t} = \bY_{t},
\end{equation*}
where $\bigM_t \in \mathbb{R}^{n \times (t+1)}$ and $\bH_t \in \mathbb{R}^{n \times (t+1)}$ are the matrices
\begin{equation*}
\bigM_{t} = [\mathbf{m}^0 | \mathbf{m}^1 | ... |\mathbf{m}^t] \text { and } \bH_{t} = [\bh^0 | \bh^1 | ... | \bh^{t}],
\end{equation*}
and $\bY_t \in \mathbb{R}^{n \times (t+1)}$ is the matrix $\bY_{t} = \bH_t + [\mathbf{0} |\bigM_{t-1}] \boldsymbol{\textsf{C}_t}$ where
$ \boldsymbol{\textsf{C}_t} =  \text{diag}(\textsf{c}_0, \ldots, \textsf{c}_{t-1})$.
Note that the notation $[\bc_1 \mid \bc_2 \mid \ldots \mid \bc_k]$ is used to denote a matrix with columns $\bc_1, \ldots, \bc_k$.
\textcolor{red}{Check dimensions.}
Thus, we find the following result for the symmetric AMP in \eqref{eq:sym_AMP}.

We use the notation $\mathbf{m}^{t+1}_{\|}$ to denote the projection of $\mathbf{m}^{t+1}$ onto the column space of $\bigM_t$. Let
 \begin{equation}
 \boldsymbol{\alpha}^t := (\alpha^t_0, \ldots, \alpha^t_{t-1})^*
 \label{eq:vec_alph_gam_conc}
\end{equation}
 be the coefficient vectors of these projections, i.e.,

$\mathbf{m}^{t+1}_{\|} := \sum_{i=0}^{t} \alpha^t_i \mathbf{m}^i$,

meaning $ \boldsymbol{\alpha}^t = (\bigM_t^T \bigM_t)^{-1}\bigM_t^T \mathbf{m}^{t+1}.$
 The projections of $\mathbf{m}^{t+1}$onto the orthogonal complement of $\bigM_t$, is denoted by

$\mathbf{m}^{t+1}_{\perp} := \mathbf{m}^{t+1} - \mathbf{m}^{t+1}_{\|}.$

 Lemma \ref{lem:main_lem}  shows that for large $n$, the entries of $\boldsymbol{\alpha}$  are concentrated around constants. In what follows we show that the vector $ \boldsymbol{\alpha}^t$ in \eqref{eq:vec_alph_gam_conc} concentrates to
 \begin{equation}
\hat{\boldsymbol{\alpha}}^t := \left [ 0 | \ldots | 0 | \frac{\sigma_t}{\sigma_{t-1}}\right],
 \label{eq:hatalph_hatgam_def}
\end{equation}
for the state evolution values given in \eqref{eq:symm_SE}.

\begin{lemma}[Conditional Distribution Lemma]
For the vectors $\bh^{t+1}$ defined in \eqref{eq:sym_AMP}, the following hold for $t \geq 1$, provided $n >t$ and $\bigM_{t}^T \bigM_t$ has full column rank.

 \begin{equation}
 \begin{split}
 \bh^{1} \lvert_{\mscrs_{0}}   \stackrel{d}{=} \sqrt{\sigma^n_1} \bU_0, \qquad \text{ and } \qquad  \bh^{t+1} \lvert_{\mscrs_{t}} &  \stackrel{d}{=} \sum_{r=0}^{t-1} \hat{\alpha}^t_r \bh^{r+1} + \sqrt{\sigma^{\perp}_t} \bU_t + \bDel_{t}, \label{eq:Ha_dist}
 \end{split}
\end{equation}

where $\bU_0, \bU_t \in \mathbb{R}^n$ are random vectors with elements that are marginally standard Gaussian random variables that are independent of the corresponding conditioning sigma-algebras. The terms $\hat{\alpha}^t_{i}$ for $i \in [t-1]$ are defined in \eqref{eq:hatalph_hatgam_def} \textcolor{red}{where} and the terms $\sigma_{t}^{\perp}$ in \eqref{eq:sigperp_defs} \textcolor{red}{where} .  The deviation terms are for $t >0$,
\begin{align}
&\Delta_{t} =   \sum_{i=0}^{t-1} (\alpha^t_i - \hat{\alpha}^t_i)\bh^i   +   \Big[ \Big( \frac{\| \mathbf{m}^t_{\perp} \|}{\sqrt{n}} - \sqrt{\sigma_{t}^{\perp}}\Big)\mathsf{I}  -  \frac{\| \mathbf{m}^t_{\perp} \|}{\sqrt{n}}\mathsf{P}^{\parallel}_{\bigM_{t}} \Big]\bU_t  \nonumber  \\
&+     \bigM_{t-1} (\bigM_{t-1}^T\bigM_{t-1})^{-1} \Big[\bH_{t-1}^T   \mathbf{m}^t_{\perp} -  \bigM_{t-1}^*\Big(\textsf{c}_{t} \mathbf{m}^{t-1} - \sum_{i=1}^{t-1} \textsf{c}_{i} \alpha^t_{i} \mathbf{m}^{i-1} \Big)\Big].\label{eq:Dt1t}
\end{align}
\label{lem:hb_cond}
\end{lemma}

\paragraph{Inductive Step.}
The second step of the proof is inductive on the iteration $t$, essentially showing that if the result in \eqref{eq:PL_conc_result} holds up to iteration $t-1$  then it will hold at iteration $t$ as well. This is done by showing that the standardized $\ell_2$ norms of the terms in the AMP algorithm in \eqref{eq:gen_rec0}, like $\frac{1}{n}\|\bv^t\|^2, \frac{1}{n}\|f_t(\bv^t, \bV^n)\|^2$  and $\frac{1}{m}\|\bu^t\|^2,  \frac{1}{m}\|g_t(\bu^t, \bU^m)\|^2$, concentrate on deterministic values predicted by the state evolution. This is done by relating these iteration $t$ values to the iteration $t-1$ values through the equation in \eqref{eq:gen_rec0} and appealing to the conditional distribution from step $(a)$ and your inductive hypothesis.  While the proof for the symmetric AMP is largely similar to that for the non-symmetric version, there are additional challenges due to the dependencies created by the symmetry of the $\textsf{GOE}(n)$ matrix.  The details of the inductive proof are quite technical and long and are therefore not included here but we state the result for the symmetric AMP in \eqref{eq:sym_AMP}.

For $t \geq 0$, let $\kappa_{-1} = K_{-1} = 1$, and
\begin{equation}
\begin{split}

K_t = C (t+1)^5K_{t-1},  &\quad  \kappa_t  = \frac{\kappa_{t-1}}{  c(t+1)^{11}},
\end{split}
\label{eq:Kkappa_def}
\end{equation}
where $C, c > 0$ are universal constants (not depending on $t$, $n$, or $\e$).  To keep the notation compact,  we  use $K, \kappa, \kappa'$ to denote generic positive universal constants whose values may change through  the  lemma statement.

Let $\{ \tilde{Z}_t \}_{t \geq 0}$ be a sequence of of zero-mean jointly Gaussian random variables whose covariance is defined recursively as follows. For $r,t \geq 0$,
\begin{equation}
\mathbb{E}[\tilde{Z}_r \tilde{Z}_t] = \frac{\tilde{E}^n_{r,t}}{\sqrt{\sigma^n_r \sigma^n_t}}, \quad \text{ where } \quad
\tilde{E}^n_{r,t} := \mathbb{E}[g_{r}(\sqrt{\sigma^n_{r}} \tilde{Z}_{r}, X^n) g_{t}(\sqrt{\sigma^n_{t}} \tilde{Z}_{t}, X^n)],
\label{eq:Edef}
\end{equation}
where $X^n \sim p_{X, n}$ is an independent random variable.  In the above, we take $g_0(\cdot, \bX^n) := g_0(\bh^0,\bX^n)$, the initial condition.  Note that $\tilde{E}_{t,t} = \sigma^n_t$, thus $\mathbb{E}[\tilde{Z}^2_t] =1$.

\begin{lemma}
The following statements hold for $1 \leq t < T^*$ and $\e \in (0,1)$. Define
\begin{equation}
\gamma_n^{t+1} := (\nu^n +  \sigma^n_{1})  (\nu^n +  \sigma^n_{1} +  \sigma^n_{2})  \cdots  (\nu^n + \sum_{i=1}^{t+1} \sigma^n_{i}) \times \max\{1, \hat{\textsf{c}}_1\}  \max\{1, \hat{\textsf{c}}_2\} \cdots  \max\{1, \hat{\textsf{c}}_t\},
\end{equation}
where $\nu$ is the variance factor of sub-Gaussian $\bX^n$ which equals $3 \rho_n$ for $p_{X, n}$ Bernoulli.
\begin{enumerate}
\item
\begin{equation}
P\Big(\frac{1}{n}\norm{\bDel_{{t}}}^2 \geq \epsilon\Big) \leq  K t^2 K_{t-1} \exp\Big\{-\frac{\kappa \kappa_{t-1} n \epsilon}{ t^4 \gamma_n^{t} \max\{1, \hat{\textsf{c}}_t\} }\Big\}. \label{eq:Ba}
\end{equation}

\item
Denote $\mathbb{E}_{\phi} :=  \mathbb{E}\, \phi_h(\sqrt{\sigma^n_{1}} \tilde{Z}_{1}, \ldots ,\sqrt{\sigma^n_{t+1}} \tilde{Z}_{t+1}, X^n)$.  Then for pseudo-Lipschitz function $\phi: \mathbb{R}^{t+1} \rightarrow \mathbb{R}$ with constant $L_{\phi}$ we have that
\begin{equation*}
P\Big(\Big \lvert \frac{1}{n}\sum_{i=1}^n \phi(h^1_i, \ldots,  h^{t+1}_i, X^n_{i}) - \mathbb{E}_{\phi} \Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{\phi}^{2} L_{g}^{4t}  \gamma_n^{t+1} }\Big\}.

\end{equation*}
The random variables $\tilde{Z}_{0}, \ldots, \tilde{Z}_t$ are jointly Gaussian with zero mean and covariance given by \eqref{eq:Edef}, and are independent of $\bX^n \sim p_{X, n}$. In the above

\item Let $L_g > 0$ be the pseudo-Lipschitz constant for the denoiser functions $\{g_t\}_{ t\geq 0}$ and let $X_n \overset{\mathbf{. .}}{=} c$ be shorthand for $$P(\abs{X_n -c} \geq \e) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{g}^{2(t+1)} \gamma_n^{t+1} }\Big\}.$$
For all $0 \leq r \leq t$,
\begin{align*}
&P\Big(\Big \lvert \frac{1}{n}(\bh^{r+1})^* \bh^{t+1}- \tilde{E}^n_{r,t}\Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7\gamma_n^{t+1} }\Big\}. \\
& \frac{1}{n}(\mathbf{m}^{0})^* \mathbf{m}^{t+1} \overset{\mathbf{. .}}{=} \tilde{E}^n_{0,t+1}  \quad

\frac{1}{n}(\mathbf{m}^{r+1})^*\mathbf{m}^{t+1}  \overset{\mathbf{. .}}{=} \tilde{E}^n_{r+1,t+1}. \\
&P\Big(\Big \lvert \textsf{c}_{t+1} - \hat{\textsf{c}}_{t+1} \Big \lvert \geq \ep\Big) \leq K t^3 K_{t-1} \exp\Big\{-\frac{ \kappa \kappa_{t-1} n \epsilon^2}{t^7 L_{g}^{4(t+1)} \gamma_n^{t+1} }\Big\}. \\%  \label{eq:Hf1}  \\
& \frac{1}{n}(\bh^{t+1})^*\mathbf{m}^{r+1}  \overset{\mathbf{. .}}{=} \hat{\textsf{c}}_{r+1} \tilde{E}^n_{r,t} , \qquad

 \frac{1}{n}(\bh^{r+1})^*\mathbf{m}^{t+1} \overset{\mathbf{. .}}{=}  \hat{\textsf{c}}_{t+1} \tilde{E}^n_{r,t}.
\end{align*}

\item
\begin{equation}

 P\left( \frac{1}{n} \bigM_{t}^* \bigM_{t} \text{  is singular}\right) \leq t K_{t-1} \exp\Big\{-\frac{\kappa_{t-1} \kappa n}{{t^7 L_{g}^{2(t+1)}\gamma_n^{t+1} }}\Big\}. \label{eq:Msing}
\end{equation}
For $\hat{\alpha}^{t}$ defined in \eqref{eq:hatalph_hatgam_def}, when the inverse of $\frac{1}{n} \bigM_{t}^* \bigM_{t} $ exists, for $1\leq i, j \leq t+1$,
\begin{equation}
\begin{split}
& P\Big( \Big \lvert [(\frac{1}{n} \bigM_{t}^* \bigM_{t})^{-1} - (\breve{C}^t)^{-1} ]_{i,j} \Big \lvert \geq \e\Big) \leq K  K_{t-1} \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\},  \\
&  P\Big( \lvert\alpha^{t}_{i-1} - \hat{\alpha}^{t}_{i-1} \lvert \geq \e \Big) \leq K t^4 K_{t-1}   \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{ t^9 L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\}.
\end{split}
\label{eq:Hg}
\end{equation}

\item With $\tau_{t}^{\perp}$ defined in \eqref{eq:sigperp_defs},
\begin{equation}
P\Big( \Big \lvert\frac{1}{n}\norm{\mathbf{m}^{t+1}_{\perp}}^2 - (\tau_{t+1}^{\perp})^2 \Big \lvert \geq \e \Big) \leq K t^5 K_{t-1}   \exp\Big\{-\frac{\kappa \kappa_{t-1}n\e^2}{ t^{11} L_{g}^{2(t+1)} \gamma_n^{t+1} } \Big\}. \label{eq:Hh}
\end{equation}

\end{enumerate}
\label{lem:main_lem}
\end{lemma}

\paragraph{Rate of the  Concentration.}
We finally note that the $\lambda_n$ in the rates of concentration in Theorem~\ref{thm:main_amp_perf} were  not stated explicitly in the original concentration bound given in \cite[Theorem 1]{RushVenkataramanan} as the authors assume that these values do not change with $n$ and, thus, can be absorbed into the universal constants. The presence of these terms comes from the inductive portion of the proof where one must show that  $\|f_t(\bv^t, \bV^n)\|^2/n$ and $\|g_t(\bu^t, \bU^m)\|^2/m$ concentrate to known constants. This will add a $L_f^2$ and $L_g^2$ in the rate at each step of the induction.  To see this, we point the reader to three facts. First notice that the approximate distributions of $v^t_i$ and $u^t_i$ are Gaussian. Second, it is easy to see that a function $[f(x)]^2$ has the same pseudo-Lipschitz constant as $f(\cdot)$ if $|f(\cdot)|$ is bounded (as $n$ grows) which is the case when $f_t$ and $g_t$ are the conditional expectation denoiser, as in our setting. (More generally, the Lipschitz constant of $[f(x)]^2$ will be no more than the square of the Lipschitz constant of $L_f$ giving instead $L_f^4$ and $L_g^4$ in the rate.) Finally, we highlight that pseudo-Lipschitz functions taking Gaussian and sub-Gaussian input concentrate as in \cite[Lemma B.4]{RushVenkataramanan} with $1/L^2$ in the rate when $L$ is the associated pseudo-Lipschitz constant.
The result is restated here

\begin{lemma}{\cite[Lemma B.4]{RushVenkataramanan}}
\label{lem:PLsubgaussconc}
Let $Z \in \mathbb{R}^n$ be an i.i.d.\ standard Gaussian vector and let $G \in  \mathbb{R}^n$ be a random vector with entries  $G_1, \ldots, G_n$  i.i.d.\   $\sim p_{G}$, where $p_G$ is sub-Gaussian with variance factor $\nu^n$.   Then for any pseudo-Lipschitz function $f: \mathbb{R}^{2} \to \mathbb{R}$ with constant $L_f^n$, non-negative values $\sigma^n$, and  $0< \e \leq 1$, we have
\begin{align*}
& P\Big(\Big\lvert \frac{1}{n}\sum_{i=1}^n f(\sqrt{\sigma^n} Z_{i}, G_i)  - \mathbb{E}[f(\sqrt{\sigma^n} Z, G)] \Big \lvert \geq \e \Big)  \leq 2 \exp \Big\{ \frac{ - \kappa n \e^2}{(L_f^n)^2(  \nu^n + 4 (\nu^n)^2 + \sigma^n +  4  (\sigma^n)^{2}) }  \Big\}.
\end{align*}
\end{lemma}
Hence, in our setting our case, $L = L_f$ or $L= L_g$ to give $L_f^2$ and $L_g^2$ in each inductive step.  The $L^2_{\phi}$ term comes from the final step where one proves the results in \eqref{eq:PL_conc_result} using the result of the inductive argument.  In the case of the symmetric AMP that we study, there is no corresponding $g_t$ step of the induction and therefore our concentration result only has the $L_f^{2t} L_{\psi}^2$ dependence.

Additionally, we note that the proof of \cite[Theorem 1]{RushVenkataramanan}  assumes that the weak derivatives of the denoisers, $f'_t, g'_t$, have bounded derivative everywhere they exist. In the case of interest in this paper, the derivative of the conditional expectation denoiser is given in Lemma~\ref{lem:PL}, and in particular, $f_t'(x) = \sqrt{\lambda_n} f_t(x) (1-f_t(x))$.  It is not hard to show that $f_t'(x)$ is also Lipschitz with constant $L_f^2 = \lambda_n$. We use this to get around the boundedness assumption originally in \cite[Theorem 1]{RushVenkataramanan} and it does not add additional $L_f$ constants in the rate.

config: arxiv


TITLE: Conjecture on the solutions to the equation $J(x) = J(x+a)$
QUESTION [2 upvotes]: Propose $J(x)$, which is a function that takes in a number and outputs the sum of all its factors (including itself)
Firstly, I think it's pretty interesting as it allows you to describe certain types of numbers as solutions to different equations using this function. For example:
Perfect numbers are the solution to $J(x) = 2x$
Prime numbers are the solution to $J(x) = x+1$
But now to the problem that I need to ask you guys - as I sieved through data I saw that a lot of different inputs gave the same outputs, such as $J(6) = J(11)$ (they both equal 12)
I wondered what the difference between values that give the same output are, or in more mathematical language: $J(x+a) = J(x)$
I conjectured that for any integer $a$, there is at least one integer solution for $x$.
Some examples:
When $a$ is equal to $1$, a possible solution for $x$ is $14$
When $a$ is equal to $2$, a possible solution for $x$ is $33$
When $a$ is equal to $3$, a possible solution for $x$ is $382$
When $a$ is equal to $69$, a possible solution for $x$ is $8786$
So I guess my question to you guys is can you prove/disprove it?
Link to rudimentary python program for finding a specific gap value:
https://repl.it/@JakubSkop/Factor-addition-function-gapvalues

REPLY [2 votes]: Well, here's a start.  Let $S$ be the set of positive integers $a$ such that
$\sigma(x) = \sigma(x+a)$ has a solution.  Since $\sigma$ is multiplicative,
if $\sigma(x) = \sigma(x+a)$ and $r$ is coprime to both $x$ and $x+a$, then
$\sigma(rx) = \sigma(r(x+a))$, so $ra \in S$.
Thus since $\sigma(14)=\sigma(15)$ for $a=1$, all $r$ coprime to $2, 3, 5$ and $7$ are in $S$.
That's a set of positive asymptotic density ($(1-1/2)\cdot(1-1/3)\cdot (1-1/5) \cdot (1-1/7) = 8/35$).
Since we know that $2,3, 5$ and $7$ are in $S$, all primes are in $S$.
Similarly, since $\sigma(54)=\sigma(56)$ for $a=2$,
if $r$ is coprime to $2, 3, 7$ then $2r \in S$.
And since $\sigma(16) = \sigma(25)$ for $a=9$, if $r$ is coprime to $2$ and $5$ then $9r \in S$.


TITLE: is very compact P^2-irreducible 3-manifold homotopy equivalent to a sphere or cell-quotient?
QUESTION [0 upvotes]: is very compact $P^2$-irreducible 3-manifold homotopy equivalent to a sphere or cell-quotient?

REPLY [1 votes]: Such a thing is either Haken, or geometric (by Geometrization).  Waldhausen showed that universal covers of Haken manifolds are cells, and you get a sphere or cell universal covering in the geometric case for free.


TITLE: What is the dot product of complex vectors?
QUESTION [14 upvotes]: When I run dot(a,b) in MATLAB, I get a very different number than $\sum a_i \times b_i$, but is that not how one takes a dot product? For instance:
A = [1+i 1-i -1+i -1-i];
B = [3-4i 6-2i 1+2i 4+3i];
dot(A,B)
% => 1.0000 - 5.0000i
A(1)*B(1)+A(2)*B(2)+A(3)*B(3)+A(4)*B(4)
% => 7.0000 -17.0000i

REPLY [7 votes]: The Wikipedia page Isai linked to basically says it all, but I think it is worth unpacking some of the definitions given there here with a bit more motivation.
To generalize the usual $\mathbb{R}^n$ dot product, what we can do is to look at the properties of that dot product, and then see if we can come up with something in $\mathbb{C}^n$ that has similar properties.
One characterization of the regular dot product is as being a "symmetric positive-definite bilinear form". Let's unpack:

symmetric: $\vec{v} \cdot \vec{w}$ = $\vec{w} \cdot \vec{v}$. This is linked to the notion of the angle between two vectors being the same regardless of order.

positive definite: $\forall \vec{v} \ne \vec{0}, \vec{v} \cdot \vec{v} > 0$. This corresponds to our usual notion of the "size of a vector being a positive real number". Remember that a inner product like the dot product naturally induces a norm

bilinear: linear in both arguments, i.e. $(a \vec{v}) \cdot \vec{w}$ = $a (\vec{v} \cdot \vec{w})$ and $(\vec{v} + \vec{u}) \cdot \vec{w} = (\vec{v} \cdot \vec{w}) + (\vec{u} \cdot \vec{w})$

form: in the context of linear algebra, a form is a (multi-)linear map that has codomain as the underlying field of a vector space, e.g. from $\mathbb{R}^n$ to $\mathbb{R}$, $\mathbb{C}^n$ to $\mathbb{C}$
Note however that the complex are not orderable, so this definition of "form" won't work well with "positive definiteness" for the complex numbers, unless we pick a form that maps $\mathbb{C}^n$ to $\mathbb{R}$

The standard definition of the complex product mentioned by Isai:
$$\vec{v} \cdot \vec{w} = \sum_i v_i\overline{w_i}$$
is one that does what it can to salvage the positive definiteness, but it has to sacrifice some of the other properties in the process:

symmetric: sacrificed, obviously, since $v_i \overline{w_i} \ne w_i \overline{v_i}$ in general.
What is maintained however is $\vec{v} \cdot \vec{w} = \overline{\vec{w} \cdot \vec{v}}$. And we also note that this version is also valid for the real forms, since for real numbers $a = \overline{a}$, so we could use it as a more general version of symmetry that is maintained in both cases.

positive definite: maintained. E.g. if we consider $\mathbb{C}^1$:
$$(a + bi) \cdot (a + bi) = (a + bi)(a - bi) = (aa + -abi + bia -bbii) = a^2 + b^2$$
So we see that this form always maps to positive real numbers, not arbitrary complex numbers, and so it makes sense to talk about positive definiteness.
As mentioned by boojum in the comments, a huge motivation for keeping this property is quantum mechanics, where $\psi \cdot \psi$ is the sum of the probabilities of every possible outcome of an experiment, which we want to always be the real positive number 1.

bilinear: for addition is maintained:
$$\vec{v} \cdot \overline{\vec{w} + \vec{u}} = \vec{v} \cdot \overline{\vec{w}} + \vec{v} \cdot \overline{\vec{u}}$$
but for scalar multiplication, it is maintained only if the scalars are real, otherwise:
$$v_i \overline{(a + bi) w_i} = (a - bi) v_i \overline{w_i} \ne (a + bi) v_i \overline{w_i}$$
We could however cheat here once again as for symmetry, and say that the real multiplication linearity on the second argument should actually be defined as:
$$\vec{v} \cdot a \vec{w} = \overline{a} \vec{v} \cdot \vec{w}$$
which would work on both real and complex cases.

form: maintained obviously

This complex "dot product" is sometimes called a Hermitian form. This specific separate term serves as a way to make it clear that it might not comply with the usual definition of a dot product, if you don't generalize that definition as shown above.


TITLE: Find an orthonormal basis of a plane
QUESTION [2 upvotes]: How do I find an orthonormal basis for a plane defined as $x_1+x_2+x_3=0$? I don't know where to start -- not even given dimensions. Thank you.

REPLY [3 votes]: The subspace in $\mathbb{R}^n$ defined by $x_1+x_2+x_3=0$ is of dimension $n-1$ and has a basis consisting of the vectors
\begin{align*}
&(1,0,-1,0,0,\ldots,0)\\
&(0,1,-1,0,0,\ldots,0)\\
&(0,0,0,1,0,\ldots,0)\\
&(0,0,0,0,1,\ldots,0)\\
&\qquad\qquad\vdots\\
&(0,0,0,0,0,\ldots,1)
\end{align*}
The last $n-3$ vectors are already normal, pairwise orthogonal, and orthogonal to the first two. So all you need to do is orthogonalize $(1,0,-1,0,\ldots,0)$ and $(0,1,-1,0,\ldots,0)$ by using Gram-Schmidt, and then normalize.
The dimension of the ambient space does not matter in the end, except in so far as padding the basis.


TITLE: how many ways can you place items on this board
QUESTION [1 upvotes]: This is a programming (C#) and math related question.
I have a 4x4 battleship grid which contains 3 ships. These 3 ships have the size's 3x1, 2x1, 1x1.
I have to find out have many ship placements are possible on this board with the information I have so far. I know the expected output is supposed to be 132
The information I have.
Character 'x' means shots that missed.
Character 'o' means shots that hit.
Character '.' means where I have not yet taken a shot.
The grid looks like this then...
. . . .
. o x .
. . . .
o . . x
I have been going at this and trying to find mathematical formulas and what not for a good while but without any success.
How do I go about figuring this out? Do I need any though calculations or am I overthinking this?

REPLY [1 votes]: A brute force approach will be fast enough. Ignoring the hit/miss data and the requirement that the ships don't overlap, there are:

16 possible locations for the 1x1 ship
12 x 2 possible placements of the 2x1 ship
8 x 2 possible placements of the 3x1 ship

for a total of only 6144 possible ship arrangements to test. You can improve this further by checking that the big ships don't overlap before placing the small ship. In any case, this program will finish in a fraction of a second.


TITLE: When will the population reach 20,000?
QUESTION [1 upvotes]: A bacteria culture initially contains 500 cells and grows a rate proportional to its size. After an hour the population has increased to 1200.
a). Find the expression for the number of bacteria after t hours.
Answer: k= 0.014591146 because
1200= 500$e^(k*60)$
divide by 1200/500 and then do ln|| on both sides to get k.
b) Find the number of bacteria after 4 hours?
P(240)= 500$e^(0.014591146*240)$
Answer: 16,588
c) Find the rate of growth.
dy/dt= 0.014591146*16588= 242/60 = 4.03 cells/hr
d) When will the population reach 20,000?
The way I went about this is:
$$20,000 = 500e^{0.014591146\,t}$$
which turned into $\ln|40|= \ln|e^{0.014591146\,t}|$
*The $\ln|e^x|$ cancels so I am left with
$$\frac{\ln|40|}{0.014591146} =t$$
My answer came out to be 252 years? However my professor said my answer was incorrect? What am I doing wrong?

REPLY [2 votes]: The problem says that initially there are 500 cells and after an hour the population has increased to 1200. To find $k= 0.014591146$ you plug $t=60$ so $k$ is measured in 1/minute. The precise result t=252.81629380680148789220913131845 is the number of MINUTES not YEARS.


TITLE: Understanding predicate logic given symbolic notation?
QUESTION [1 upvotes]: I'm having trouble understanding predicate logic. Question J is that saying "All broken windows are in the garage"?
Is K. saying "for every x in the garage the x has a broken window"
L.) "there exists a car and it is in the garage"?
M.) "There exists a car and there exists broken windows?"
The statements are not making sense when being said any guidance?

REPLY [2 votes]: Try writing them first as a direct translation of the predicate logic, then start rearranging them into some proper English. For example, let's start with J.
$\forall x (R(x) \rightarrow Q(x))$
So in "predicate English", this is "For all x, (x has a broken window) implies (x is in the garage)".
As a first step, let's change "x" into something more normal, and replace "A implies B" with "If A, then B". "For every object, if it has a broken window, it is in the garage."
Then, the idea of "For every thing, if A then B" really just means "Everything that is A is also B". So, something like this: "Everything with a broken window is in the garage."
The rest you should have another go at yourself, but I'll give you a quick piece of advice - R(x) is the statement "x has a broken window", not "x is a broken window". Funnily enough, at this stage of things I don't think you have the notation to actually relate the two contexts, so none of your sentences should use a phrase like "is a broken window" or "there are broken windows". Always refer to things "having/with a broken window".


TITLE: P(A) given that P(A|B) and P(B) are known
QUESTION [3 upvotes]: Given that $P(A \mid B)$ is known, and $P(B)$ is known, how can $P(A)$ be calculated? I tried using the definition of conditional probability - $P(A \mid B) = P(A \cap B)/ P(B)$ - to solve for $P(A \cap B)$ but I don't know where to go from there. Any hints?

REPLY [6 votes]: In general, you can't calculate $P(A)$ from just $P(A \mid B)$ and $P(B)$ — you also need to know $P(A \mid \lnot B)$.
If you do know that, the calculation is easy enough:
$$\begin{aligned}P(A)
&= P(A \land B) + P(A \land \lnot B) \\
&= P(A \mid B)P(B) + P(A \mid \lnot B)P(\lnot B) \\
&= P(A \mid B)P(B) + P(A \mid \lnot B)(1 - P(B))
\end{aligned}$$

REPLY [5 votes]: You don't have enough information to get $P(A).$
Consider a dice with six faces. Consider $A_1=\{1,2\},A_2=\{2\},B=\{2,4,6\}.$ It is $P(A_i/B)=\frac13$ and $P(B)=\frac{1}{2}.$ However $P(A_1)=\frac13$ and$P(A_2)=\frac16$

REPLY [3 votes]: It cannot be.  To see this, let's look at a couple of examples:
First: suppose that you flip a fair coin twice, and let $A$ be the event that the first is heads and $B$ the event that the second is heads.  The coin flips are independent; so, in this case,
$$
P(A)=.5\qquad P(B)=.5\qquad P(A\mid B)=.5
$$
Second: say we again flip two fair coins, and again let $B$ be the event that the second is heads.  However, let $A$ be the event that BOTH are heads. Then
$$
P(A)=.25\qquad P(B)=.5\qquad P(A\mid B)=.5
$$
If there was a way to determine $P(A)$ from $P(B)$ and $P(A\mid B)$, then these two examples would need to have the same value for $P(A)$; but, they don't!


TITLE: Does the damping force oppose a spring's restorative force in damped oscillations?
QUESTION [0 upvotes]: If the damping force ($F_d=-bv)$ in damped simple harmonic motion opposes the spring's force $(F_s=-kx)$, why does the solution for the position as a function of time proceed from this equation?:
$$-bv-kx=ma$$
... And when substituting differentials with respect to $t$, we have the solution:
$$x(t)=e^{\frac{-bt}{2m}}\cos(w^{'}t+\phi)$$
I'm wondering what the reason is for $-bv-kx=ma$ (I showed $x(t)$ for more context) when the damping force OPPOSES the spring.

REPLY [2 votes]: The damping force doesn't oppose the restoring force, it opposes the motion (that's what $-bv$ means). So, when the mass is moving away from the center/equilibrium point the damping force and restoring force point in the same direction: towards the center. They switch to pointing in opposing directions when the mass reaches its furthest distance. Then the velocity changes direction, so the damping force now points away from the center, but the restoring force is always toward the center.
As for why the motions follows from that equation, that just your standard "sum up the forces and set them equal to m a." The damping force is $-bv$ the sping force is $-kx$, so the net force is $-bv -kx$.