TITLE: Probability an experiment takes 5 trials to succeed?
QUESTION [0 upvotes]: Assume the outcome of an experiment can either fail or succeed.
The probability to succeed is 1/3. Let X be the number of times that
the experiment is performed until three successes has been obtained.
What is the probability that X = 5?
What I did:
$$
{5 \choose 3}\left(\frac13\right)^3\left(\frac23\right)^2 \approx .16
$$
I know the correct answer is 0.0987. What did I do wrong?

REPLY [0 votes]: Your answer is wrong because it takes into consideration those cases where the experiment completes successfully $3$ times after at most $5$ attempts (by multiplying with $\binom53=10$):

$00111$ - the experiment completes successfully after $5$ attempts
$01011$ - the experiment completes successfully after $5$ attempts
$01101$ - the experiment completes successfully after $5$ attempts
$01110$ - the experiment completes successfully after $4$ attempts
$10011$ - the experiment completes successfully after $5$ attempts
$10101$ - the experiment completes successfully after $5$ attempts
$10110$ - the experiment completes successfully after $4$ attempts
$11001$ - the experiment completes successfully after $5$ attempts
$11010$ - the experiment completes successfully after $4$ attempts
$11100$ - the experiment completes successfully after $3$ attempts

In order for the answer to be correct, you need to count only those $6$ cases where the experiment completes successfully $3$ times after exactly $5$ attempts (i.e., by multiplying with $6$ instead of $10$).


TITLE: Find $a$ in terms of $b$ if $b = ({a \over 5})^{a+1}$
QUESTION [0 upvotes]: Find $a$ in terms of $b$ if $b = ({a \over 5})^{a+1}$.
Firstly,

is this possible (within elementary functions)

and secondly,

if so, how is it done?

also, can someone help me tag this, I don't really now which tags to use.

REPLY [2 votes]: Even with Lambert function, there is no explicit solution because of the $+1$ in the exponent.
I guess that numerical methods would be needed. For starting, let $a=5c$ and consider that you look for the zero's of function
$$f(c)=c^{5 c+1}-b$$ or, much better
$$g(c)=(5c+1)\log(c)-\log(b)$$ Computing the derivatives
$$g'(c)=\frac{1}{c}+5 \log (c)+5\qquad \text{and} \qquad g''(c)=\frac{5 c-1}{c^2}$$
The first derivative cancels at
$$c_*=-\frac{1}{5 W\left(-\frac{e}{5}\right)}$$ which is not a real. So, the derivative is positive and $g(c)$ is an increasing function with a positive second derivative as soon as $c > \frac 15$.
Newton method will not face any problem; the only thing, foor saving iterations, is that we need a "reasonable" guess $c_0$ to start with.
Ignoring the $+1$, we could that start using
$$c_0=\frac{\log (b)}{5 W\left(\frac{\log (b)}{5}\right)}$$ which will be an overestimate of the solution since $g(c_0) > 0$.
Let us try for $b=123456789$. The iterates would be
$$\left(
\begin{array}{cc}
 n & c_n \\
 0 & 3.201940306 \\
 1 & 3.097390221 \\
 2 & 3.096653690 \\
 3 & 3.096653653
\end{array}
\right)$$ then $a=15.483268263$.
Trying for $b=123456789\times 10^{100}$, the iterates would be
$$\left(
\begin{array}{cc}
 n & c_n \\
 0 & 17.41954887 \\
 1 & 17.27183432 \\
 2 & 17.27167350
\end{array}
\right)$$
Edit
As I wrote, if you want to save iterations, a "good" estimate $c_0$ is required.
Let me take the second case with $c_0=1$. The method  will provide the following iterates
$$\left(
\begin{array}{cc}
 n & c_n \\
 0 & 1 \\
 1 & 42.48165184 \\
 2 & 19.29197737 \\
 3 & 17.29900434 \\
 4 & 17.27167903 \\
 5 & 17.27167350
\end{array}
\right)$$ All of that can very easily be done with Excel (or whatever).
Update
Assuming that you would accept the proposed expression for $c_0$ you could have a better approximation using the simple $[1,1]$ Padé approximant of $g(c)$ built at $c=c_0$. This would give
$$c_1=c_0+\frac{2 \,g(c_0)\, g'(c_0)}{g(c_0)\, g''(c_0)-2\, g'(c_0)^2}$$
For the worked examples, this would give $c_1=3.09667$ and $c_1=17.2717$. This does not seem to be too bad. Be sure that we can still improve it using $[1,n]$ Padé approximant.


TITLE: Setting Up an Integral (depends on displacement vector from a long line)
QUESTION [1 upvotes]: The following is a physics problem, but I don't actually care about the physics right now. I just want to set up the integral, which I'm having a difficult time doing (the problem is from the book 2008+ Solved Problems in Electromagnetics):

The law that we want to use: $$\vec{B} = K \int_C \frac{d\vec{l} \times \vec{r}}{|\vec{r}|^3}$$
$K$ is some constant. $C$ is the wire. $d\vec{l}$ is an infinitesimal length along the wire, and $\vec{r}$ is a displacement vector; where we're calculating $B$. Here's how I'm doing this:
If we define the wire to be $\hat{x}$ where $\hat{y}$ points to the right, then $d\vec{l} = dx ~ \hat{x}$. Any given displacement vector is just $x ~ \hat{x} + y ~ \hat{y} + z ~ \hat{z}$. Then, $d\vec{l} \times \vec{r} = zdx~\hat{y} + ydx~\hat{z}$... right?
So the thing we're integrating is $\displaystyle \int_{L_0}^{L_1} \frac{zdx~\hat{y} + ydx~\hat{z}}{(x^2 + y^2 + z^2)^{3/2}}$ ... ... right?
Since we're just concerned with the 2-D square, $z = 0$ in the displacement vector (because the square is on the xy-plane), so we have: $\displaystyle \int_{L_0}^{L_1} \frac{y}{(x^2 + y^2)^{3/2}}dx ~\hat{z}$ ... ... ... right?
This integral evaluates to: $$-y {\left(\frac{\sqrt{L_{0}^{2} + y^{2}} L_{0}}{L_{0}^{2} y^{2} + y^{4}} - \frac{\sqrt{L_{1}^{2} + y^{2}} L_{1}}{L_{1}^{2} y^{2} + y^{4}}\right)}$$
... but I don't think that is right. Am I setting up the integral correctly?
I tried to minimize the physics (to keep it as math as possible). I've been doing integrals for years, and still have a really difficult time setting up what should be even a basic integral—and it's really, really discouraging. I still feel like I have no clue what I'm doing. :/

REPLY [1 votes]: As my last comment above indicates, the issue was a physical one: The magnetic field is produced by the entire wire, not just the portion parallel to the square. (You certainly could have examples where the wire is of finite length, and then the equation you provided would be correct.) Consequently the correct integral is
$$\displaystyle \int_{-\infty}^{\infty} \frac{y}{(x^2 + y^2)^{3/2}}dx =\frac{2}{r}$$
as may be shown by a $x=y\tan \theta$ substitution. (Note that this substitution represents the angle between the $y$-axis and $\vec{r}$.)
Returning to the physics context, this gives a magnetic field of $B=\mu_0 I/(2\pi r)$. We can check that this is consistent with Ampere's law: Take an Amperian loop of radius $r$ which winds around the wire. Since $\vec{B}\parallel d\vec{l}$ for the line element of the loop, the circulation is simply $\oint \vec{B}\cdot d\vec{l}=\oint\left(\dfrac{\mu_0 I}{2\pi r}\right) dl=\mu_0 I$ since the circumference is $2\pi r$. But this is exactly what is required by Ampere's law! (Note that you could have deduced $B$ in this manner by making use of the rotational symmetry.)


TITLE: Finite limit involving characteristic function implies values of first and second moments
QUESTION [2 upvotes]: If $$\lim_{c \to 0} \frac{\phi_X(c) - 1}{c^2} = -\frac{\sigma^2}{2} < \infty$$ where $\phi_X(c)$ is the characteristic function of the random variable $X$, then $$E[X] = 0,\qquad E[X^2] = \sigma^2$$

I know $$\lim_{c \to 0} \frac{\phi_X(c) - 1}{c^2} = \lim_{c \to 0} \frac{E[e^{icX}] - 1}{c^2}$$ Also, I've proven that if the $n$-th moment exists, the $n$-th derivative of the characteristic function exists, and this seems a bit like a partial converse, but I can't come up with the right angle to look at the limit from to see how the suggested values for $E[X]$ and $E[X^2]$ come out of it. I would like just a hint on how I should be looking at this problem.

REPLY [1 votes]: First, we have to show that the second moment is finite. Notice that for any $x$, $2n^2(1-\cos(x/n))\to x^2$, hence
$$\mathbb E[X^2]=\mathbb E\left[\liminf_{n\to \infty}2n^2(1-\cos(X/n))\right].$$As a consequence of Fatou's lemma, we obtain that
$$\mathbb E[X^2]\leqslant \liminf_{n\to \infty}2n^2\mathbb E\left[(1-\cos(X/n))\right].$$
Since
$$2\mathbb E\left[(1-\cos(X/n))\right]=2-\phi(1/n)-\phi(-1/n),$$
we get
$$\liminf_{n\to \infty}2n^2\mathbb E\left[(1-\cos(X/n))\right]\leqslant \sigma^2.$$
We thus are allowed to compute the expectation taking the derivative of the characteristic function. Using the assumption, the derivative is $0$.
Since $\phi''(0)=-\mathbb E[X^2]$, then we get $\mathbb E[X^2]=\sigma^2$.
We can also deduce an asymptotic expansion at $0$, see here.


TITLE: Fundamental group of cylinder quotient
QUESTION [1 upvotes]: Let $X = S^1 \times [0,1]$ be the cylinder, and define an equivalence relation on $X$ by $(z,1) \sim (iz,1)$.
What is the fundamental group of $X/\sim$?
Is $X$ the same as the mapping cylinder of $(z\mapsto z^4)$?

I found this in a previous question. (The previous question had an additional rotation on the other end of the cylinder.) In a comment, the author concluded that $\pi_1(X) = \mathbb{Z}_4$. But I keep getting a different solution! Using van Kampen on two ends of the cylinder (which intersect in the middle), I find that $\pi_1(X) = \langle a,b \rangle / \langle a^4b^{-1}\rangle = \langle a \rangle= \mathbb{Z}$.
Furthermore, a CW structure with:

2 points $p,q$
3 lines $a,b,c$ where $a$ is a loop at $p$, $b$ is a loop at $q$, and $c$ goes from $p$ to $q$
1 two-cell attached by boundary map $a^4cb^{-1}c^{-1}$

has $H_1=\mathbb{Z}$, which is not the abelianization of $\mathbb{Z}_4$.
Where have I gone wrong?

REPLY [0 votes]: I think the answer of $\mathbb{Z}$ is correct. One way you may visualize this is that you "twisted" one end of the cylinder twice, each times covering it back again. Then the whole cylinder is extremely stretched, but the topology is still the same. Thus if you "untwist" everything you should recover a normal cylinder.
I suspect the other answer was written in a different context, namely if the two ends are identified together. In this case the fudamental group is $\langle a, b\rangle:aba^{-4}b^{-1}=1$. Thus its abelianization is $a^3=1$.


TITLE: Prove that if vi is a basis of the column space of A then f(vi) is a basis of the column space of f(A)
QUESTION [0 upvotes]: I met a problem from the liner algebra test of our school. The question is:
Consider the following function $f$ that takes any matrix $A$ as argument and returns a matrix
$$f\left(A\right)=\frac1{\sqrt2}\begin{pmatrix}A&A\\A&-A\end{pmatrix}$$
Now Let $\left\{{\boldsymbol v}_{\mathbf1}\boldsymbol,{\boldsymbol v}_{\mathbf2}\boldsymbol,\boldsymbol.\boldsymbol.\boldsymbol.{\boldsymbol v}_{\mathbf d}\right\}$ be a basis of the column space of $A$, where the column space of $A$ is the span of the column vectors of $A$. Show that
$$\left\{\begin{pmatrix}{\mathbf v}_{\mathbf1}\\{\mathbf v}_{\mathbf1}\end{pmatrix}\boldsymbol,\boldsymbol.\boldsymbol.\boldsymbol.\boldsymbol,\begin{pmatrix}{\mathbf v}_{\mathbf d}\\{\mathbf v}_{\mathbf d}\end{pmatrix}\boldsymbol,\begin{pmatrix}{\mathbf v}_{\mathbf1}\\\boldsymbol-{\mathbf v}_{\mathbf1}\end{pmatrix}\boldsymbol,\boldsymbol.\boldsymbol.\boldsymbol.\boldsymbol,\begin{pmatrix}{\mathbf v}_{\mathbf d}\\\boldsymbol-{\mathbf v}_{\mathbf d}\end{pmatrix}\right\}$$
is a basis of the column space of $f(A)$.
As I think, as $f(A)$ shows, isn't it obvious to see that the basis of the column space of $f(A)$ is
$$\left\{\begin{pmatrix}{\mathbf v}_{\mathbf1}&{\mathbf v}_{\mathbf1}\\{\mathbf v}_{\mathbf1}&\boldsymbol-{\mathbf v}_{\mathbf1}\end{pmatrix}\boldsymbol,\boldsymbol.\boldsymbol.\boldsymbol.\boldsymbol,\begin{pmatrix}{\mathbf v}_{\mathbf d}&{\mathbf v}_{\mathbf d}\\{\mathbf v}_{\mathbf d}&\boldsymbol-{\mathbf v}_{\mathbf d}\end{pmatrix}\right\}$$
Then after a simple split, we can get the answer, right? (just a joke...)
In fact I have no idea how to prove this 'obvious' question, could you give me some hints on that? Thank you!

REPLY [2 votes]: This is an exercise in "writing mathematics". Your joking logic actually translates to the right thinking, but for some adjustment in entries. Acknowledging the fact that the $v_i$ are not the columns but rather a column basis is important. Writing the obvious-looking is a skill in math. Besides, not everything looking obviously true is mathematically true, though your thought is fine.
Let us see how we would do this. First, we want to show that some set is a basis for the column space of $f(A)$. Showing something as a basis requires two things : spanning and linear independence. So both need to be proved.
First let us prove spanning. Take a column of $f(A)$. What does it look like? Either we pick it from the "left set" of blocks or the "right" set. So, if $\mathbf{c}$ is a column of $A$, then a column of $f(A)$ either looks like $\frac 1{\sqrt{2}}\begin{bmatrix}\mathbf{c} \\ \mathbf{c}\end{bmatrix}$ or like $\frac{1}{\sqrt 2} \begin{bmatrix}\mathbf {c} \\ \mathbf{-c}\end{bmatrix}$, where $-\mathbf{c}$ is $-1 \times \mathbf{c}$. Since $\{v_i\}$ is a basis of the columns of $A$, we have $\mathbf c = \sum c_iv_i$ for some scalars $c_i$. Now, we note that,for example:
$$
\frac{1}{\sqrt 2}\begin{bmatrix}\mathbf c \\ \mathbf {-c}\end{bmatrix} = \sum \frac{c_i}{\sqrt 2}\begin{bmatrix}v_i \\ -v_i\end{bmatrix}
$$
And therefore the set given to you spans the columns on the "right side" of $f(A)$. For the left side see something similar by yourself. This proves spanning.

For linear independence, assume that some linear combination $\sum c_i \begin{bmatrix}v_i \\ v_i\end{bmatrix} + \sum d_i \begin{bmatrix}v_i \\ -v_i\end{bmatrix}$ is the zero vector of size $2n$(where $n$ is the dimension of $A$). Now consider the "top half" of this equality, and it reads : $\sum (c_i + d_i) v_i = 0$ , where the zero vector has size $n$. Similarly, the "bottom half" of this equality reads $\sum(c_i-d_i)v_i = 0$.
Now, the $v_i$ are linearly independent, this forces allthe above coefficients to be zero. Hence, $c_i +d_i = c_i - d_i = 0$ for all $i$, therefore $c_i=d_i = 0$ for all $i$, showing linear independence of the set.
And thus the set is a basis for the columns of $f(A)$.


TITLE: How close would a supernova be to endanger the astronauts on the ISS?
QUESTION [0 upvotes]: How close would a supernova be to endanger the astronauts on the ISS?
Would Betelgeuse be close enough?

REPLY [0 votes]: Depending upon type, a supernova could affect the Earth biosphere from a distance of 3 000 light years. A type II supernova nearer than about 25 light years could destroy half the ozone layer. Betelgeuse is estimated at about 700 light years. If it were to go supernova now, it would certainly have an impact, but it is predicted to move much further away before that will actually happen.


TITLE: Show that if $x$ is a limit point of $A\subset X$ and $f:X \rightarrow Y$ is continuous then $f(x)$ is a limit point of $f(A)$
QUESTION [6 upvotes]: Suppose $f:X\rightarrow Y$ is a continuous function between the topological spaces $X$ and $Y$. Suppose that: $A \subset X$ and that  $x$ is a limit point of $A$.
Show that $f(x)$ is a limit point of $f(A)$
By a limit point $c$ of $B$ I mean that every neighborhood of $c$ intersects $B$ in a point $d$ such that $c\not = d$
What I have done is that: I supposed that $x$ is a limit point of $A$ but $x\not\in A$ and showed the required. but in the case when $x \in A$. My trial goes as follows:
Suppose $W$ was a neighborhood of $f(x)$ so $f^{-1}(W) \text{is a neighborhood of } x$. So $ f^{-1}(W) \cap A \not=\emptyset$ because $x$ is a limit point of $A$. Say $y\in f^{-1}(W) \cap A$. So $f(y)\in A$ and $f(y)\in W$. Now, if  $x\not\in A$ then $f(x) \not\in f(A)$ but $f(y)\in A$ so $f(y)\not = f(x)$. So $W$ intersects $f(A)$ in a point $f(y)$ which is different of $f(x)$
If $x\in A$, it may happen that $f$ is not injective and happen that  $f(x)=f(y)$ in which case I can't show that f(x) is a limit point of $f(A)$.
I've tried to came with a counter-example using constant functions on real functions. but it didn't works
What to do? any hints?

REPLY [9 votes]: As the question was answered in comments and there is no one who added a correct answer to close the question. I'm adding this answer (I got the idea of the  answer from This comment)
The statement is false, here is a concrete example:
Let $f:\mathbb{R}\rightarrow \mathbb{R}$ where, $f(x)=2$ for all $x\in \mathbb{R}$. So $f$ is a constant function.
Note that we denote the set of limit points of $H$ by $H'$.
Let $A = [0,1]$.
So, $A' = [0,1]$.
$f(A)=f([0,1])=\{2\}$, but $f(A)'=\emptyset$ because {$2$} has no limit points as if $x\not = 2$  is a real number then there is always an interval $C$ containing $x$ but not contaning $2$.
So Although $1$ is a limit point of $A$, $f(1)=2$ is not a limit point of $f(A)=\{2\}$.
As the question was answered in comments and there is no one who added a correct answer to close the question. I'm adding this answer (I got the idea of the  answer from comments).


TITLE: How is tessellation defined in Mathematics?
QUESTION [6 upvotes]: Hi. I am a GCSE student and I am interested in Maths.
I read few books on maths and learned some mathematical analysis.
I know of convergent series but I would like to know how identical sets(not points) cover a given space.
I've put a link to Escher's painting as an example; I think it is a good example of tessellation and union of sequences of sets that are identical or similar. I think tessellation can be described in terms of sets but I can't just come out with one.
I would like a definition that satisfies the following:
1) describe an intuitive tessellation
2) describe tessellation of regular hexagons or triangles on R2(in other words, I want the definition of tessellation to describe a 'tile' covering an infinite unbounded space).
Thank you!

REPLY [5 votes]: See Wikipedia's entry: Tessellations
You'll find an intuitive definition of tessellations ("Tessellation is the process of creating a two-dimensional plane using the repetition of a geometric shape with no overlaps and no gaps. Generalizations to higher dimensions are also possible...").
And you'll find a sub-entry on regular tessellations, (tilings of regular polygons: triangles, squares, hexagons). "A regular tessellation is a highly symmetric tessellation made up of congruent regular polygons. Only three regular tessellations exist: those made up of equilateral triangles, squares, or hexagons." It follows with a description of "semi-regular" tessellations. (See also regular tessellations at mathworld.)
The Wikipedia entry includes links to the following:
Types of tessellation
Aperiodic tiling
List of regular polytopes
List of uniform tilings
Pinwheel tiling
Tilings of regular polygons
Uniform tessellation
Voronoi tessellation

Mathematics
Coxeter groups – algebraic groups that can be used to find tessellations
Girih tiles
Triangulation (geometry)
Uniform tiling
Uniform tilings in hyperbolic plane
Wallpaper group – seventeen types of two-dimensional repetitive patterns
Wang tiles

See also: Math World: Tessellations, with additional links, e.g. to triangulation.


TITLE: Does blow up of subscheme in special fiber change the generic fiber?
QUESTION [5 upvotes]: Let $X\to \mathrm{Spec}(R)$ be a finite type scheme over DVR, choose a closed subscheme $Y$ of the closed fiber $X_0$ and blow up $Y$ in $X$, will the generic fiber always remain the same?

REPLY [4 votes]: Note that passing to the generic fiber is flat, (it's a localization) and blowups commute with flat base change.
Therefore, the new generic fiber is the blowup of the old generic fiber $X_\eta$ at the intersection of $X_\eta$ with $Y$. This is empty, so you're blowing up nothing, and you get an isomorphism.
This is just a long-winded way of saying "when you blow up a subscheme, the compliment of that closed set never ever changes."


text:
\subsection{Phase Transitions of the Rate--Distortion Function}

The material in this part is based on the paper:
K.~Rose, ``A mapping approach to rate-distortion computation and
analysis,'' {\em IEEE Trans.~Inform.~Theory\/}, vol.\ 40, no.\ 6, pp.\
1939--1952, November 1994.

We have seen in one of the earlier meetings that the rate--distortion function
of a source $P=\{p(x),~x\in\calX\}$ can be expressed as
\begin{equation}
R(D)=-\min_{\beta\ge 0}\left[\beta D+\sum_xp(x)\ln\left(\sum_yq(y)e^{-\beta
d(x,y)}\right)\right]
\end{equation}
where $Q=\{q(y),y\in\calY\}$ is the output marginal of the test channel, which
is also the one that minimizes this expression.
We are now going to take a closer look at this function in the context of the
quadratic distortion function $d(x,y)=(x-y)^2$.
As said, the optimum $Q$ is the one that minimizes the above expression, or
equivalently, the free energy
\begin{equation}
f(Q)=-\frac{1}{\beta}\sum_xp(x)\ln\left(\sum_yq(y)e^{-\beta d(x,y)}\right)
\end{equation}
and in the continuous case, summations should be replaced by integrals:
\begin{equation}
f(Q)=-\frac{1}{\beta}\int_{-\infty}^{+\infty}
\dd xp(x)\ln\left(\int_{-\infty}^{+\infty} \dd yq(y)e^{-\beta d(x,y)}\right).
\end{equation}
Rose suggests to represent the RV $Y$ as a function of
$U\sim\mbox{unif}[0,1]$, and then, instead of optimizing $Q$,
one should optimize the function $y(u)$ in:
\begin{equation}
f(y(\cdot))=-\frac{1}{\beta}\int_{-\infty}^{+\infty}
\dd xp(x)\ln\left(\int_0^1 \dd \mu(u)e^{-\beta d(x,y(u))}\right),
\end{equation}
where $\mu(\cdot)$ is the Lebesgue measure (the uniform measure).
A necessary condition for optimality,\footnote{The details are in the paper,
but intuitively,
instead of a function $y(u)$ of a continuous variable $u$,
think of a vector $\by$ whose components are indexed by $u$, which take on
values in some grid of $[0,1]$. In other words,
think of the argument of the logarithmic function as
$\sum_{u=0}^1 e^{-\beta d(x,y_u)}$.} which must hold for almost every $u$ is:
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)\cdot\left[
\frac{e^{-\beta d(x,y(u))}}{\int_0^1 \dd \mu(u')e^{-\beta
d(x,y(u'))}}\right]\cdot\frac{\partial d(x,y(u))}{\partial y(u)}=0.
\end{equation}
Now, let us define the {\it support} of $y$ as the set of values that $y$ may
possibly take on. Thus, this support is a subset of the set of all points
$\{y_0=y(u_0)\}$ for which:
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)\cdot\left[
\frac{e^{-\beta d(x,y_0)}}{\int_0^1 \dd \mu(u')e^{-\beta
d(x,y(u'))}}\right]\cdot\frac{\partial d(x,y(u))}{\partial y(u)}\bigg|_{y(u)=y_0}=0.
\end{equation}
This is because $y_0$ must be a point that is obtained as $y(u)$ for some $u$.
Let us define now the posterior:
\begin{equation}
q(u|x)=\frac{e^{-\beta d(x,y(u))}}{\int_0^1 \dd \mu(u')e^{-\beta
d(x,y(u'))}}.
\end{equation}
Then,
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)q(u|x)\cdot\frac{\partial
d(x,y(u))}{\partial y(u)}=0.
\end{equation}
But $p(x)q(u|x)$ is a joint distribution $p(x,u)$, which can also be thought
of as $\mu(u)p(x|u)$. So, if we divide the last equation by $\mu(u)$, we get,
for almost all $u$:
\begin{equation}
\int_{-\infty}^{+\infty}\dd x p(x|u)\frac{\partial d(x,y(u))}{\partial y(u)}=0.
\end{equation}
Now, let's see what happens in the case of the quadratic distortion,
$d(x,y)=(x-y)^2$. Let us suppose that the support of $Y$ includes some
interval $\calI_0$ as a subset. For a given $u$, $y(u)$ is nothing other than
a number, and so the optimality condition must hold for every $y\in\calI_0$.
In the case of the quadratic distortion, this optimality criterion means
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)\lambda(x)(x-y)
e^{-\beta(x-y)^2}=0,~~~~\forall y\in\calI_0
\end{equation}
with
\begin{equation}
\lambda(x)\dfn \frac{1}{\int_0^1 \dd \mu(u)e^{-\beta d(x,y(u))}}=
\frac{1}{\int_{-\infty}^{+\infty} \dd yq(y)e^{-\beta d(x,y)}},
\end{equation}
or, equivalently,
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)\lambda(x)\frac{\partial}{\partial
y}\left[e^{-\beta(x-y)^2}\right]=0.
\end{equation}
Since this must hold for all $y\in\calI_0$, then all derivatives of the
l.h.s.\ must vanish within $\calI_0$, i.e.,
\begin{equation}
\int_{-\infty}^{+\infty}\dd xp(x)\lambda(x)\frac{\partial^n}{\partial
y^n}\left[e^{-\beta(x-y)^2}\right]=0.
\end{equation}
Now, considering the Hermitian polynomials
\begin{equation}
H_n(z)\dfn e^{\beta z^2}\frac{\dd^n}{\dd z^n}(e^{-\beta z^2})
\end{equation}
this requirement means
\begin{equation}
\int_{-\infty}^{+\infty}\dd
xp(x)\lambda(x)H_n(x-y)e^{-\beta(x-y)^2}=0.
\end{equation}
In words: $\lambda(x)p(x)$ is orthogonal to all Hermitian polynomials of order
$\ge 1$ w.r.t.\ the weight function $e^{-\beta z^2}$. Now, as is argued in the
paper, since these polynomials are complete in $L^2(e^{-\beta z^2})$, we get
\begin{equation}
p(x)\lambda(x)=\mbox{const.}
\end{equation}
because $H_0(z)\equiv 1$ is the only basis function orthogonal to all $H_n(z)$,
$n\ge 1$. This
yields, after normalization:
\begin{equation}
p(x)=\sqrt{\frac{\beta}{\pi}}\int_0^1\dd\mu(u)e^{-\beta(x-y(u))^2}=
\sqrt{\frac{\beta}{\pi}}\int_{-\infty}^{+\infty}\dd
yq(y)e^{-\beta(x-y)^2}=Q\star\calN\left(0,\frac{1}{2\beta}\right).
\end{equation}
The interpretation of the last equation is simple: the marginal of $X$ is
given by the convolution between the marginal of $Y$ and the zero--mean
Gaussian distribution with variance $D=1/(2\beta)$ ($=kT/2$ of the
equipartition theorem, as we already saw). This means that $X$ must be
representable as
\begin{equation}
X=Y+Z
\end{equation}
where $Z\sim \calN\left(0,\frac{1}{2\beta}\right)$ and independent of $Y$.
From the Information Theory course we know that this is exactly what happens
when $R(D)$ coincides with its Gaussian lower bound, a.k.a.\ the {\it Shannon
lower bound}. Here is a reminder of this:
\begin{eqnarray}
R(D)&=&h(X)-\max_{\bE(X-Y)^2\le D}h(X|Y)\nonumber\\
&=&h(X)-\max_{\bE(X-Y)^2\le D}h(X-Y|Y)\nonumber\\
&\ge&h(X)-\max_{\bE(X-Y)^2\le D}h(X-Y)~~~~\mbox{equality if}~(X-Y)\perp Y\nonumber\\
&=&h(X)-\max_{\bE Z^2\le D}h(Z)~~~~Z\dfn X-Y\nonumber\\
&\ge &h(X)-\frac{1}{2}\ln(2\pi e D)~~~~\mbox{equality
if}~Z\sim\calN(0,D)\nonumber\\
&\dfn& R_{\mbox{SLB}}(D)\nonumber
\end{eqnarray}
The conclusion then is that if the support of $Y$ includes an interval (no
matter how small) then $R(D)$ coincides with $R_{\mbox{SLB}}(D)$. This implies
that in all those cases that $R_{\mbox{SLB}}(D)$ is not attained, the support
of the optimum test channel output distribution must be singular, i.e., it
cannot contain an interval. It can be, for example, a set of isolated points.

But we also know that whenever $R(D)$ meets the SLB for some $D=D_0$, then
it must also coincide with it for all $D < D_0$. This follows from the
following consideration: If $X$ can be represented as $Y+Z$, where
$Z\sim\calN(0,D_0)$ is independent of $Y$,  then for every $D < D_0$,
we can always decompose $Z$ as $Z_1+Z_2$, where $Z_1$ and $Z_2$ are both
zero--mean independent Gaussian RV's with variances $D_0-D$ and $D$,
respectively. Thus,
\begin{equation}
X=Y+Z=(Y+Z_1)+Z_2\dfn Y'+Z_2
\end{equation}
and we have represented $X$ as a noisy version of $Y'$ with noise variance
$D$. Whenever $X$ can be thought of as
a mixture of Gaussians, $R(D)$ agrees with its SLB for
all $D$ upto the variance of the narrowest Gaussian in this mixture.
Thus, in these cases:
\begin{equation}
R(D)~~\left\{\begin{array}{ll}
= R_{\mbox{SLB}}(D) & D\le D_0\\
> R_{\mbox{SLB}}(D) & D> D_0\end{array}\right.
\end{equation}
It follows then that in all these cases,
the optimum output marginal contains intervals for all $D\le D_0$ and then
becomes abruptly singular as $D$ exceeds $D_0$. From the viewpoint of
statistical mechanics, this looks like a phase transition, then. Consider first
an infinite temperature, i.e., $\beta=0$, which means unlimited distortion.
In this case, the optimum output marginal puts all its mass on one point:
$y=\bE(X)$, so it is definitely singular. This remains true even if we increase
$\beta$ to the inverse temperature that corresponds to $D_{\max}$, the
smallest distortion for which $R(D)=0$. If we further increase $\beta$, the
support of $Y$ begins to change. In the next step it can include 2 points,
then 3 points, etc. Then, if there is $D_0$ below which the SLB is met, then
the support of $Y$ abruptly becomes one that contains one interval at least.
This point is also demonstrated numerically in the paper.

An interesting topic for research evolves around possible extensions of these
results to more general distortion measures, other than the quadratic
distortion measure.

config: arxiv


TITLE: How to prove $\log{n} = O(n^{0.5})$
QUESTION [0 upvotes]: I want to prove $\log{n} = O(n^{0.5})$ but I'm not sure how to achieve this. Any help would be appreciated!

REPLY [0 votes]: Hint:

consider the zero and sign of the derivative of $f(n)=\dfrac{\log(n)}{n^{0.5}}$