TITLE: What is the interactive explanation of a number to the power $\sqrt{-1}$
QUESTION [1 upvotes]: What happens when a number is multiplied with itself i times, i.e a number $n \in \mathbb{C}$, what is the explanation of $n^i$ ?
I have tried a few by myself:-
$e^i = cos \; 1 + i sin\; 1$ and
$i^i$ is a pure real number.
What about others ? What is $1^i$ ?

REPLY [1 votes]: Actually you have to be much more careful.  Notice this
$$i^i = (e^{\pi/2 + 2\pi i n})^i =(?) e^{i \pi/2}e^{-2\pi n} = -e^{-2\pi n} $$
for every integer $n$.  You have run square up against the complex log here. And that requires real care.


TITLE: Discrete Maths - Induction
QUESTION [0 upvotes]: I am having difficulty answering the following question:

Can anyone show me how to solve this? I understand that I should be putting in a + 1 somewhere to simulate the next step, but I'm not sure where.
Thanks!

REPLY [3 votes]: Induction begins by showing a base case. Here our base case is $n=1$ since we want to prove the statement for all integers $n\geq1$.
Case $n=1$:
Note that $1^3=1$ and that$\frac{1^2}{4}\cdot(1+1)^2=\frac{4}{4}=1$. Since these are the same, the base case holds.
Now we make the induction hypothesis: that there exists an integer $k\geq1$ such that the formula holds. That is
$$1^3+2^3+3^3+\cdots+k^3=\sum_{i=1}^{k}i^3=\frac{k^2}{4}(k+1)^2$$
for some integer $k\geq1$.
Now we take the induction step, to consider the case $n=k+1$.
Case $n=k+1$:
$$1^3+2^3+3^3+\cdots+k^3 +(k+1)^3$$
Now by our induction hypothesis we can replace the sum of the first $k$ cubes with $\frac{k^2}{4}(k+1)^2$.
So
$$1^3+2^3+3^3+\cdots+k^3 +(k+1)^3=\frac{k^2}{4}(k+1)^2+(k+1)^3=\frac{1}{4}(k^2+3k+2)^2=\frac{(k+1)^2}{4}(k+2)^2$$
Which we should note is the formula that we are trying to prove for general $n$, with $k+1$ substituted.
Now, this proves the statement for all integers $n\geq1$. This is because we supposed that it held true for one integer, and showed that this implies it will hold true for the next integer. Since we could repeat this argument indefinitely to show that the formula holds for the next integer and we have an integer as our starting point (the base case), we have shown the formula to be true for all integers $n\geq1$.


TITLE: How do I find the volume xyz tends to 0 when x(or y or z) tends to go $ \infty $
QUESTION [0 upvotes]: The volume V=xyz, and the constraint of surface area : S(x,y,z) = xy + yz + zx - 5 = 0, How do I comfirm the limit of volume V tends to 0 when x tends to go to $ \infty $?  $$ \bbox[yellow]
{\lim_{x\to\infty} \ V = 0 \ }$$
I found this problem in the vector calculus(Marsden), but there is no exact anwser for it. How exactly could I show V goes to 0 when x goes to infinity?

REPLY [0 votes]: A possible simple way is to extract $z$ from the constraint
$$z=\frac{5-x y}{x+y} \implies V=\frac{x y (5-x y)}{x+y}$$
$$\frac{\partial V}{\partial x}=-\frac{y^2 \left(x^2+2 x y-5\right)}{(x+y)^2}\tag 1$$
$$\frac{\partial V}{\partial y}=-\frac{x^2 \left(2 x y+y^2-5\right)}{(x+y)^2}\tag 2$$
SInce the partial derivatives are supposed to be $0$, from $(1)$
$$y=\frac{5-x^2}{2 x}\implies V=-\frac{1}{2} x \left(x^2-5\right)$$ So $V$ cancels when $x=\sqrt 5$ so, it is $0$ above.


text:
\subsection{Connection between the mixing time and the cover time}
\label{sec:connection-tcover-tmix}

Lemma~\ref{lemma:Bernstein-state-occupancy} combined with the definition \eqref{eq:defn-cover-time} immediately reveals the following upper bound on the cover time:

\begin{align}
	\tcovertime = O\Big( \frac{\tmix}{\mumin} \log |\mathcal{X}| \Big).
	\label{eq:cover-time-UB-mixing}
\end{align}

In addition, while a general matching converse bound (namely, ${\tmix}/{\mumin}=\widetilde{O}(\tcovertime)$) is not available, we can come up with some special examples for which the bound \eqref{eq:cover-time-UB-mixing} is provably tight.

\paragraph{Example.}
Consider a time-homogeneous Markov chain with state space $\mathcal{X}:=\{1,\cdots,|\mathcal{X}|\}$
and probability transition matrix

\begin{align}
\bm{P}=\Big(1-\frac{q(k+1)}{2}\Big)\bm{I}_{|\mathcal{X}|}+\frac{q}{|\mathcal{X}|}\left[\begin{array}{cc}
k\bm{1}_{|\mathcal{X}|}\bm{1}_{|\mathcal{X}|/2}^{\top} & \bm{1}_{|\mathcal{X}|}\bm{1}_{|\mathcal{X}|/2}^{\top}\end{array}\right] \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}
\label{eq:construction-P}
\end{align}

for some quantities $q>0$ and $k\geq 1$.
Suppose $q(k+1)<2$ and $|\mathcal{X}|\geq 3$. Then this chain obeys $$\tcovertime\geq \frac{\tmix}{\big(8\log2+4\log\frac{1}{\mumin}\big)\mumin}.$$

\begin{proof} As can be easily verified,  this chain is reversible, whose stationary distribution vector $\bm{\mu}\in\mathbb{R}^{|\mathcal{X}|}$
obeys

\[
\bm{\mu}=\frac{2}{(k+1)|\mathcal{X}|}\left[\begin{array}{c}
k\bm{1}_{|\mathcal{X}|/2}\\
\bm{1}_{|\mathcal{X}|/2}
\end{array}\right].
\]

As a result, the minimum state occupancy probability of the stationary distribution is given by

\begin{equation}
\mumin:=\min_{1\leq x\leq|\mathcal{X}|}\mu_{x}=\frac{2}{(k+1)|\mathcal{X}|}.\label{eq:mumin-q-expression}
\end{equation}

In addition, the reversibility of this chain implies that the matrix
$\bm{P}^{\mathrm{d}}:=\bm{D}^{\frac{1}{2}}\bm{P}\bm{D}^{-\frac{1}{2}}$
with $\bm{D}:=\mathrm{diag}\left[\bm{\mu}\right]$ is symmetric and
has the same set of eigenvalues as $\bm{P}$ \citep{bremaud2013markov}. A little algebra yields

\begin{align*}
\bm{P}^{\mathrm{d}} & =\Big(1-\frac{q(k+1)}{2}\Big)\bm{I}_{|\mathcal{X}|}+\frac{q}{|\mathcal{X}|}\left[\begin{array}{cc}
k\bm{1}_{|\mathcal{X}|/2}\bm{1}_{|\mathcal{X}|/2}^{\top} & \sqrt{k}\bm{1}_{|\mathcal{X}|/2}\bm{1}_{|\mathcal{X}|/2}^{\top}\\
\sqrt{k}\bm{1}_{|\mathcal{X}|/2}\bm{1}_{|\mathcal{X}|/2}^{\top} & \bm{1}_{|\mathcal{X}|/2}\bm{1}_{|\mathcal{X}|/2}^{\top}
\end{array}\right],
\end{align*}

allowing us to determine the eigenvalues $\{\lambda_{i}\}_{1\leq i\leq|\mathcal{X}|}$ as follows

\[
\lambda_{1}=1\qquad\text{and}\qquad\lambda_{i}=1-\frac{q(k+1)}{2} > 0 ~~ (i\geq2).
\]

We are now ready to establish the lower bound on the cover
time. First of all, the well-known
connection between the spectral gap and the mixing time gives \citet[Proposition 3.3]{paulin2015concentration}

\begin{equation}
\tmix\leq\frac{2\log2+\log\frac{1}{\mumin}}{2(1-\lambda_{2})}=\frac{2\log2+\log\frac{1}{\mumin}}{q(k+1)}.\label{eq:tmix-UB-q}
\end{equation}

In addition, let $(x_{0},x_{1},\cdots)$ be the corresponding
Markov chain, and assume that $x_{0}\sim\mu$, where $\mu$ stands
for the stationary distribution. Consider the last state --- denoted by $|\mathcal{X}|$, which enjoys the minimum state occupancy probability $\mumin$.
For any integer $t>0$ one has

\begin{align*}
\mathbb{P}\left\{ x_{l}\neq|\mathcal{X}|,\text{ }\forall\, 0\leq l\leq t\right\}
 & \overset{(\mathrm{i})}{=}\mathbb{P}\left\{ x_{0}\neq|\mathcal{X}|\right\}
 \prod_{l=1}^{t}\mathbb{P}\Big\{ x_{l}\neq|\mathcal{X}| \,\Big| \,  x_{0}\neq|\mathcal{X}|,\cdots,x_{l-1}\neq|\mathcal{X}| \Big\} \\
 & \overset{(\mathrm{ii})}{\geq}\mathbb{P}\left\{ x_{0}\neq|\mathcal{X}|\right\} \prod_{l=1}^{t}\min_{j:j\neq|\mathcal{X}|}\mathbb{P}\big\{ x_{l}\neq|\mathcal{X}| \,\big| \, x_{l-1}=j\big\} \\
 & \overset{(\mathrm{iii})}{=} \Big(1-\frac{2}{(k+1)|\mathcal{X}|}\Big) \left(1-\frac{q}{|\mathcal{X}|}\right)^{t}\\
 & \overset{(\mathrm{iv})}{\geq} \Big(1-\frac{2}{(k+1)|\mathcal{X}|}\Big)\left(1-\frac{2qt}{|\mathcal{X}|}\right),
\end{align*}

where (i) follows from the chain rule, (ii)
relies on the Markovian property, (iii) results from the construction \eqref{eq:construction-P}, and (iv) holds as long
as $\frac{q}{|\mathcal{X}|}t<\frac{1}{2}$. Consequently, if $|\mathcal{X}|\geq3$
and if $t<\frac{|\mathcal{X}|}{8q}$, then one necessarily has

\begin{align*}
\mathbb{P}\left\{ x_{l}\neq|\mathcal{X}|,~\forall \,0\leq l\leq t\right\}  & \geq\Big(1-\frac{2}{(k+1)|\mathcal{X}|}\Big)\left(1-\frac{2qt}{|\mathcal{X}|}\right)>\frac{1}{2}.
\end{align*}

This taken collectively with the definition of $\tcovertime$ (cf.~\eqref{eq:defn-cover-time}) reveals that
\[
\tcovertime\geq\frac{|\mathcal{X}|}{8q}\geq\frac{\tmix}{\big(8\log2+4\log\frac{1}{\mumin}\big)\mumin},
\]
where the last inequality is a direct consequence of (\ref{eq:mumin-q-expression})
and (\ref{eq:tmix-UB-q}).

\end{proof}

config: arxiv


TITLE: Continuous functions on $\mathbb{R}^2$ with special property
QUESTION [7 upvotes]: The following problem is from Miklos Schweitzer competition (Year 1983, Problem 7):

Prove that if the function $f: \mathbb{R}^{2}\to [0, 1]$ is
  continuous, and its average on every circle of radius one equals the
  function value at the center, then $f$ is constant.

There is some discussion here but no elementary solution (from my point of view). I would like to see a solution that avoids Fourier transforms. But perhaps someone could elaborate on Kent Merryfield's observations and give a complex-analytic solution?
From the number of upvotes this meta question has received, I will assume that its okay to ask such questions here.

REPLY [2 votes]: An almost-proof from the central limit theorem. This write up took far more words than I expected. The point is that $f(x_0, y_0)$ is the average of $f$ on a circle centered around $(x_0, y_0)$. The value of $f$ at each point on that circle is, in turn, the average of $f$ at circles centered round the points of the unit circle. This means that $f(x_0,y_0)$ can be written as some sort of two dimensional average of the values of $f$ on a disc of radius $2$ around $(x_0, y_0)$. Repeating this argument, $f$ can be written as a weighted average of the values of $f$ on a disc of radius $n$ and, by the central limit theorem, as $n \to \infty$, the weighting function will start to look like a bell curve of width $\approx \sqrt{n}$. So $f(x_1,y_1) - f(x_2,y_2)$ is the integral of $f$ against a difference of two bell curves, whose centers are displaced from each other by $(x_1-x_2, y_1-y_2)$. As $n \to \infty$, the two bell curves will get very wide and flat, so the difference between their centers becomes insignificant and the integral goes to zero. Okay, now for the proof.

The hypothesis is that
$$f(x,y) = \frac{1}{2 \pi} \int_{\theta} f(x+\cos \theta, y+\sin \theta) d \theta \quad (\ast)$$
Plugging formula $(\ast)$ into itself,
$$f(x,y) = \frac{1}{4 \pi^2} \int_{\theta} \int_{\phi} f(x+\cos \theta+\cos \phi, y+\sin \theta + \sin \phi) d \theta d \phi$$
which, if I got the Jacobian factors right, turns into
$$f(x,y) = \frac{1}{2 \pi^2} \int_{u,v} f(x+u,y+v) \sqrt{(u^2+v^2)(2-u^2-v^2)} du dv$$
I don't care about the details of this formula, what I care is that it looks like
$$f(x,y) = \int_{u,v} f(x+u, y+v) \mu_2(u,v) du dv$$
for some function $\mu_2$.
If I plug $(\ast)$ into itself to get a triple integral, I will get some different formula
$$f(x,y) = \int_{u,v} f(x+u, y+v) \mu_3(u,v) du dv$$
and, in general, we have
$$f(x,y) = \int_{u,v} f(x+u, y+v) \mu_n(u,v) du dv$$
where $\mu_n$ is the $n$-fold convolution of the measure of the unit circle with itself. If you are uncomfortable convolving measures and want to convolve functions, take $n$ even and define $\mu_n = \mu_2 \ast \mu_2 \ast \cdots \ast \mu_2$, where I have convolved $n/2$ times.
By the central limit theorem in $\mathbb{R}^2$,
$$\mu_n(x,  y) \approx \frac{C}{n} \exp\left(-\frac{x^2+y^2}{n \sigma} \right)$$
Here $C$ and $\sigma$ are positive real numbers I didn't feel like computing. This proof will be nonrigorous to the extent that I don't replace that $\approx$ by some precise limiting notion; I was too lazy to scan through the different notions of convergence for which the central limit theorem has been proved and figure out which one I want.
Now, fix $(x_1, y_1)$ and $(x_2, y_2) \in \mathbb{R}^2$. So
$$f(x_1, y_1) - f(x_2, y_2) =$$
$$ \int_{(u,v) \in \mathbb{R}^2} f(x_1+u, y_1+v) \mu_n(u,v) dx dy - \int_{(u,v) \in \mathbb{R}^2} f(x_2+u, y_2+v) \mu_n(u,v) dx dy=$$
$$\int_{(a,b) \in \mathbb{R}^2} f(a,b) \left( \mu_n(a-x_1, b-y_1) - \mu_n(a-x_2, b-y_2) \right) da db \approx$$
$$ \int_{(a,b) \in \mathbb{R}^2} f(a,b) \frac{C}{n} \left( \exp\left( - \frac{(a-x_1)^2+(b-y_1)^2}{\sigma n} \right) - \exp\left( - \frac{(a-x_2)^2+(b-y_2)^2}{\sigma n} \right) \right) da db.$$
Acting as if the $\approx$ were an $=$, we have
$$|f(x_1,y_1) - f(x_2, y_2)| \leq$$
$$\frac{C}{n} \int_{(a,b) \in \mathbb{R}^2} \left| \exp\left( - \frac{(a-x_1)^2+(b-y_1)^2}{\sigma n} \right) - \exp\left( - \frac{(a-x_2)^2+(b-y_2)^2}{\sigma n} \right) \right| da db.$$
We will show that
$$\lim_{n \to \infty} \frac{C}{n} \int_{(a,b) \in \mathbb{R}^2} \left| \exp\left( - \frac{(a-x_1)^2+(b-y_1)^2}{\sigma n} \right) - \exp\left( - \frac{(a-x_2)^2+(b-y_2)^2}{\sigma n} \right) \right| da db = 0$$
and, thus, once we get the right form of the central limit theorem to cite, $f$ is constant.
So it remains to compute
$$\lim_{n \to \infty} \frac{C}{n} \int_{(a,b) \in \mathbb{R}^2} \left| \exp\left( - \frac{(a-x_1)^2+(b-y_1)^2}{\sigma n} \right) - \exp\left( - \frac{(a-x_2)^2+(b-y_2)^2}{\sigma n} \right) \right| da db $$
By translational and rotational symmetry, we may assume that $(x_1, y_1)$ and $(x_2, y_2)$ are of the form $(r,0)$ and $(-r,0)$ for some positive $r$.
$$\frac{C}{n} \int_{(a,b) \in \mathbb{R}^2} \left| \exp\left( - \frac{(a-r)^2+b^2}{\sigma n} \right) - \exp\left( - \frac{(a+r)^2+b^2}{\sigma n} \right) \right| da db =$$
$$\frac{C}{n} 2 \int_{b=-\infty}^{\infty} \int_{a=0}^{\infty}  \exp\left( - \frac{(a-r)^2+b^2}{\sigma n} \right) - \exp\left( - \frac{(a+r)^2+b^2}{\sigma n} \right)  da db =$$
$$\frac{2C}{n} \int_{b=-\infty}^{\infty} \int_{a=0}^{2r}  \exp\left( - \frac{(a-r)^2+b^2}{\sigma n} \right) da db = \frac{2C}{n} \int_{c=-r}^r \exp \frac{-c^2}{\sigma n} dc \int_{b=-\infty}^{\infty} \exp\left( \frac{-b^2}{\sigma n} \right) db$$
$$=\frac{2 C \sqrt{\pi \sigma}}{\sqrt{n}} \int_{c=-r}^r \exp \frac{-c^2}{\sigma n} dc = 2 C \sqrt{\pi \sigma} \int_{x=-r/\sqrt{n}}^{r/\sqrt{n}} \exp\left(- \frac{x^2}{\sigma}  \right) dx.$$
(We have made the subsititutions $c=a-r$ and $x=c/\sqrt{n}$.) Clearly, the last integral goes to $0$.


TITLE: A question on binomial theorem
QUESTION [3 upvotes]: If $C_0$, $C_1$, $C_2$,...$C_n$ are the coefficients in the expansion of $(1+x)^n$, where $n$ is a positive integer, show that $$C_1- {C_2\over 2}
+{C_3\over 3}-...+{(-1)^{n-1} C_n\over n}=1+ {1\over 2}+ {1\over 3}+...+{1\over n}$$

REPLY [3 votes]: Evaluate
$$\int_0^1\frac{1-(1-x)^n}xdx$$
in two different ways.
First way:
$$1-(1-x)^n=1-\sum_{k=0}^n(-1)^k\binom nkx^k=\sum_{k=1}^n(-1)^{k+1}\binom nkx^k$$
so
$$\int_0^1\frac{1-(1-x)^n}xdx=\sum_{k=1}^n(-1)^{k+1}\binom nk\int_0^1x^{k-1}dx=\sum_{k=1}^n(-1)^{k+1}\binom nk\frac1k$$
$$=\frac{\binom n1}1-\frac{\binom n2}2+\frac{\binom n3}3-\cdots+(-1)^{n+1}\frac{\binom nn}n.$$
Second way: Substituting $u=1-x$,
$$\int_0^1\frac{1-(1-x)^n}xdx=\int_0^1\frac{1-u^n}{1-u}du=\int_0^1(1+u+u^2+\cdots+u^{n-1})du$$$$=\frac11+\frac12+\frac13+\cdots+\frac1n.$$


TITLE: How slow does sine iteration converges?
QUESTION [1 upvotes]: It is no hard to prove that the real sequence $\{a_n\}_{n=1}^\infty$ decided by
$$
\begin{cases}
a_1 = 1\\
a_{n+1} = \sin a_n
\end{cases}
$$
converges to $0$ as $n\to\infty$. However, it seems that such a convergence is extremely slow (at least not exponentially), since $a_{n+1}-a_{n} = o(a_n^3)$. However, I still want to know just how slow it is. To be more precise,
$$
\text{is }a_n \text{ of order }  \frac{1}{n}, \frac{1}{n^2}, \text{or}\ \frac{1}{\ln n}, \text{or something else?}
$$
And how should we analyze a problem like this?

REPLY [2 votes]: You can prove that
$$a_n \sim \sqrt{\frac{3}{n}}$$ based on the fact that
$$\frac{1}{a_{n+1}^2} - \frac{1}{a_{n}^2} \sim \frac{1}{3}$$ using Taylor expansion of $\sin x$. From there, you get that the series $\sum \left(\frac{1}{a_{n+1}^2} - \frac{1}{a_{n+1}^2}\right)$ diverges and
$$\frac{1}{a_{n}^2} - \frac{1}{a_{0}^2} \sim \frac{n}{3}.$$