问:
Why are the roots of this recursive defined polynomial bound by the roots of the discriminant of the characteristic polynomial?
Let's define a polynomial recursively as:

$$
\begin{align}
p_0(x) &= 1 \\
p_n(x) &= x \sum\limits_{k=1}^n a_k p_{n-k}(x)
\end{align}
$$

Let $a_k$ be an arithmetic progression.

Question: Why are the roots of $p_n(x)$ bound by the roots of the discriminant of the characteristic polynomial of $p_n(x)$?

Here some steps I did so far:

1. Simplification of the recursion

A general formula for the arithmetic progression is: $a_n = a_{n-1} + d = a_1 + (n-1) d$

$$
\begin{align}
p_n(x) &= x \sum\limits_{k=1}^n a_k p_{n-k}(x) = a_1 x p_{n-1}(x) + x \sum\limits_{k=2}^n a_k p_{n-k}(x) \\
&= x a_1 p_{n-1}(x) + x \sum\limits_{k=2}^n a_{k-1} p_{n-k}(x) + xd \sum\limits_{k=2}^n p_{n-k}(x) \\
&= (a_1x+1) p_{n-1}(x) + xd \sum\limits_{k=2}^n p_{n-k}(x) \\
&= (a_1x+1) p_{n-1}(x) + xd p_{n-2}(x) + xd \sum\limits_{k=3}^n p_{n-k}(x) \\
&= (a_1x+2) p_{n-1}(x) + xd p_{n-2}(x) -(a_1x+1)p_{n-2}(x) \\
&= (a_1x+2) p_{n-1}(x) + \left[(d-a_1)x-1\right] p_{n-2}(x) \\
\end{align}
$$

2. Root of the discriminant $\Delta_{\lambda}$ of the characteristic polynomial $\chi(\lambda)$

$$
\begin{align}
\chi(\lambda) &= \lambda^n - (a_1x+2) \lambda^{n-1} - \left[(d-a_1)x-1\right] \lambda^{n-2} = 0 \\
&= \lambda^2 - (a_1x+2) \lambda - \left[(d-a_1)x-1\right] = 0 \\
\Delta_{\lambda} &= (a_1x+2)^2 + 4\left[(d-a_1)x-1\right] = a_1^2x^2 + 4a_1x + 4 + 4dx - 4a_1x - 4 \\
&= (a_1^2 x + 4d)x \\
x_1 &= 0 \\
x_2 &= -\frac{4d}{g_1^2}
\end{align}
$$

Let $x_0$ be a root of $p_n(x)$ such that $p_n(x_0) = 0$ then

$$
-\frac{4d}{a_1^2} < x_0 \leq 0, \forall d, a_1, n
$$

EDIT: There was a mistake in the simplification process of the recurrence relation. I corrected it. It influenced the result for the calculation of the roots of the discriminant. Therefore the accepted answer was using my wrong calculation. But the answer is still applicable as the inequality was still holding.

答:
The characteristic polynomial is crucial to understanding how the function behaves because of how the difference equation works. This answer assumes you are very comfortable with the basics of linear difference equations and that have a good theoretical grasp of how functions work.

We're going to work on getting a closed form for $p_n(x)$. The key realization here is that the value $p_n(1)$, for example, only depends on $p_1(1),p_2(1),p_3(1),\dots,p_{n-1}(1)$. In general, for a fixed $t$, $p_n(t)$ only depends on the values of the other functions at $t$. Therefore, if we fix $t$, we can explore the behavior of the sequence $p_1(t),p_2(t),p_3(t),\dots$ without worrying about how the function behaves in other places.

I'll take your equation, $p_n(x)=(x+2)a_1p_{n-1}(x)+[(d-a_1)x-a_1]p_{n-2}(x)$ as given. If we fix $x$, then we can write $p_n(x)-(x+2)a_1p_{n-1}(x)-[(d-a_1)x-a_1]p_{n-2}(x)=0$, which is a linear difference equation with constant coefficients (remember $x$ is fixed). This means that we can solve it the standard way; assume that $p_n=\lambda^n$ is a solution for some constant $\lambda$ (or, in the world of the function $p_n(x)$, $\lambda$ depends on $x$). This gives us the characteristic function $\lambda^2-(x+2)a_1\lambda-((d-a_1)x-a_1)=0$. This will, of course, give rise to two (either both real or complex conjugate) solutions $\lambda_{1,2}(x)$, and then for suitable constants $c_1,c_2$ we have that $p_n(x)=c_1(\lambda_1(x))^n+c_2(\lambda_2(x))^n$. (This assumes $\lambda_1\neq\lambda_2$: the case where the two are equal is unimportant to the overall explanation and adds extra complexity, so I won't be covering it.)

So far, we've used the same ideas that exist in any beginner's course on difference equations. The only level of abstraction to get your head around is that we are using functions of $x$ instead of sequences. This is important to understand in order to answer the question you posed.

Let's go back to that characteristic polynomial, $\lambda^2-(x+2)a_1\lambda-((d-a_1)x-a_1)=0$. Clearly, a choice of $x,a_1,d$ fixes constant values of $\lambda_{1,2}$. The discriminant of that characteristic polynomial is, as you said, $\Delta=a_1^2x^2+4[a_1(a_1-1)+d]x$, a function of $x$. But what does the discriminant of a quadratic mean? You'll remember that if the discriminant is positive, then there are two distinct real solutions for the quadratic. If the discriminant is negative, then there are two non-real, complex conjugate solutions of the quadratic.

So, if we are seeking to evaluate $p_n(x_1)$, for some fixed real $x_1$, then that choice of $x_1$ will make $\Delta>0$ or $\Delta<0$. (Again, $\Delta=0$ gives the double root, which you should explore in your own time.) If we have $\Delta(x_1)>0$, then the corresponding values $\lambda_{1,2}(x_1)$ will be real and distinct. In that case, we may be able to find a root to $p_n(x_1)=c_1\lambda_1(x_1)^n+c_2\lambda_2(x_1)^n$. But if $\Delta(x)<0$, then the corresponding values $\lambda_{1,2}(x_1)$ will be nonreal and complex conjugates. Let's explore this case in more detail:

Again, we've already chosen $x_1$, so we'll just write $p_n,\lambda_1,\lambda_2$ to save space and keep me sane. Now, we know that $\lambda_{1,2}$ are complex conjugates, and so $\lambda_1^n$ and $\lambda_2^n$ are also complex conjugates. So we can write: $\lambda_1^n=r+bi$ and $\lambda_2^n=r-bi$. So if want $p_n=c_1\lambda_1+c_2\lambda_2=0$, then $r(c_1+c_2)+b(c_1-c_2)i=0$. So either $\lambda_1=\lambda_2=0$ (which is false), or $c_1=c_2=0$ (which is false), or $\lambda_{1,2}$ are pure imaginary and $c_1=c_2$ (which turns out to never be true). So clearly, we can't have $p_n(x_1)=0$.

Let's summarize: when we choose $x_1$ so that $\Delta(x_1)<0$, then we must have complex conjugate solutions $\lambda_{1,2}$ and therefore $p_n(x_1)\neq0$. But if $\Delta(x_1)>0$, then $\lambda_{1,2}$ are real and we might have a root $p_n(x_1)=0$. So, every root $x_0$ of $p_n$ satisfies $\Delta(x_0)>0$. (Technically $\geq 0$, but we're ignoring $\Delta=0$.) But when is $\Delta(x_0)>0$? Why, whenever $x_0$ is in between the two roots $x_1,x_2$ of $\Delta$! So we know that if $p_n(x_0)=0$, then:

$$-4-\frac{4(d-a_1)}{a_1^2}<x_0<0$$

And then we add in the trivial solution $x_0=0$ to get the final inequality.

I hope this helped! Please let me know if you have any questions :)


问:
Find location of a point on an oval shape
I have an oval shape (let's assume the center is (0,0)), and I have two laser pointers (at known locations) pointing to the two different objects (marked as X). One object is on the perimeter, the other somewhere inside the oval area.

I have two questions:

With a sinlge laser pointer, given the angle of pointing and its (x,y) location, can we calculate the location of the object?

Now with two laser pointers, their angle of poining and locations, can we calculate the location of the object?

Please assume whatever variables needed, like the equation for the oval geometry. I just want to see what are minimum information needed to localize an object on the area or perimeter.

答:
Knowing the equation of the oval, one laser intersects it from inside at a single point.

Two lasers intersect at a single point (independently of the oval).

ContentLicense: CC BY-SA 4.0


问:
The matrix of a linear transformation related to differentiaion

$Trig_N$ is the complex vector space of trigonometric polynomials of degree $\le$ N, i.e. the space of functions f of the form $f(t) = \sum_{|n|\le N} a_ne^{int} $, $a_n \in C$. Let $D : f \to f'$ be the differentiation operator on $Trig_N$ and $T = D^2 + 2D$. What is the matrix of T relative to the basis ${e^{int}}|n|\le N$ ?

I know that for a normal polynomial space, the basis is $\{1,x,x^2,\ldots,x^k\}$ and the matrix for $D: f \to f'$ is $$\begin{bmatrix}0&1&0&0&\ldots&0\\0&0&2&0&\ldots&0\\0&0&0&3&\ldots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&0&\cdots&k\\0&0&0&0&\ldots&0\end{bmatrix}.$$ from

$D(1)=0$, $D(x)=1$,$\cdots$, $D(x^k)=kx^{k-1}$. But in this case the basis is much more complicated and it would be hard to derive the derivative matrix like above, let alone the matrix of $T=D^2+D$. Is there a different way to figure out the associated matrix of T?

答: Note that, for each $n\in\Bbb N$,$$(D^2+2D)(e^{int})=D(ine^{int})+2ine^{int}=(-n^2+2in)e^{int}.$$Therefore, if your vbasis is $\left\{e^{-iNt},e^{-i(N-1)t},\ldots,e^{iNt}\right\}$, then the matrix that your after is the diagonal matrix such that the entries of the main diagonal are$$-N^2-2iN,-(N-1)^2-2i(N-1),\ldots,-N^2+2iN.$$


问:
Prove Redundancy of an Expression
I can explain it to myself verbally pretty well, but I'm really struggling with "proving it" to myself through logic operations.

How can I, with some more ands and ors and iffs in-between,  prove that:

$x \notin B \vee(x \in B \wedge x \in C) \iff x \notin B \vee x \in C$

Or in other words, that the "$x \in B$" in there is redundant?

As I said, I can "explain" it to myself with some pretty artistic hand-waving and I'm pretty sure it's true, but I can't seem to express it. (If it's not in B then the expression is true because of $x \notin B$ regardless of anything else, so I wouldn't even care about the parentheses unless $x \in B$, at which point I just need to know if it's in C as well. But how do I "say that with operators"?)

答:
You use distributivity and conjuction elimination and introduction.
\begin{align*}
x \not \in B &\vee (x \in B \wedge x \in C)  \\
    &\iff (x \not \in B \vee x \in B) \wedge (x \not \in B \vee x \in C)  &  &\text{distributivity}  \\
    &\implies x \not \in B \vee x \in C  &  &\text{conj. elim.}
\end{align*}
and
\begin{align*}
x \not \in B &\vee x \in C  &  &  \text{Given.}\tag{1}  \\
x \not \in B &\vee x \in B  &  &  \text{Prop. of set membership}  \tag{2}  \\
(x \not \in B &\vee x \in B) \wedge (x \not \in B \vee x \in C)  &  &  \text{conj. intro. (2) and (1)}  \\
x \not \in B &\vee (x \in B \wedge x \in C)  &  &  \text{distributivity}  \\
\therefore x \not \in B &\vee x \in C \implies x \not \in B \vee (x \in B \wedge x \in C)
\end{align*}

An alternative is by enumerating the truth table:

$x \in B$, $x \in C$: The left-hand side is $\text{False} \vee ( \text{True} \wedge \text{True})$, which is True, and the right-hand side is $\text{False} \vee \text{True}$, which is True.  So equivalence is not rejected in this case.  (We abbreviate the evaluations in the subsequent cases.)

$x \not \in B$, $x \in C$: left: True, right: True.  Equivalence is still not rejected.

$x \in B$, $x \not\in C$: left: False, right: False.  Equivalence is still not rejected.

$x \not\in B$, $c \not\in C$: left: True, right: True.  Equivalence is still not rejected.

Since equivalence is not rejected in all cases, equivalence holds.

Title: Prove Redundancy of an Expression


问:
Given $\sum_{i=1}^{n} x_i \leq s$ what is the probability of $\sum_{i=1}^{n+1} x_i \leq S$
While modeling a problem I came upon the need to calculate

$$
(1)\ Pr(\sum_{i=1}^{n+1} x_i \leq S | \sum_{i=1}^{n} x_i \leq s)\\
x_i\sim Erlang(k,\lambda)\ i.i.d
$$

My problem is that I have no idea how to approach calculating their joint distribution or conversely, how to go about proving their dependence or independence (talking about the two sums here, I know the distribution of each sum).

If we denote these sums $S_{n+1}$ and $S_{n}$ I'm aware that I can rewrite this probability as

$$
(2)\ \frac{Pr(-s\leq S_{n+1}-S_{n} \leq S\  \cap\ 0\leq S_{n+1} + S_{n} \leq\ S+s)}{Pr(S_{n} \leq\ s)}
$$

Unfortunately re-framing the problem in this manner didn't help either, it led me to considering the following expresion

$$
(3)\ \frac{Pr(-s\leq x_{n+1} \leq S\  \cap\ 0\leq S_{n} \leq\ s)}{Pr(S_{n} \leq\ s)}
$$

which is easily calculable, I'm not sure it follows from the previous expression, so if this is the correct direction I'd love to get an idea how to go from (2) to (3)

答:
The characteristic function of of the Erlang Distribution is
$$
CF = \left( {1 - {{it} \over \lambda }} \right)^{\, - k}
$$

So the CF corresponding to the sum of $n$ i.i.d.  erlang variables is
$$
CF = \left( {1 - {{it} \over \lambda }} \right)^{\, - nk}
$$
which tells that is corresponds to an Erlang variable with parameters $\lambda, \, nk$.

The PDF of the sum of $n$ variables is therefore
$$
{{\gamma \left( {nk,\lambda x} \right)} \over {\left( {nk - 1} \right)!}}
$$

Now
$$
\eqalign{
  & P\left( {\sum\limits_{k = 1}^{n + 1} {x_{\,k} }  \le S\;\left| {\;\sum\limits_{k = 1}^n {x_{\,k} }  \le s} \right.} \right) =   \cr
  &  = {{\int_{t = 0}^s {P\left( {x_{\,n}  \le S - t \cap \left( {t \le \sum\limits_{k = 1}^n {x_{\,k} }  \le t + dt} \right)} \right)} }
 \over {P\left( {\sum\limits_{k = 1}^n {x_{\,k} }  \le s} \right)}} \cr}
$$


问:
Bounded component of the complement of a closed set
In [this]
(Bounded components of complement of bounded planar domain are simply-connected) Moishe Kohan says that if $E$ is a closed set and $U$ is a bounded component of the complement of $E$, then the boundary of $U$ is contained in $E$. What is the formal proof of this?

答:
Every open set $U$ can be expressed as sum of maximal connected components, say $U_{i\in I}$. Now because for fixed $k\in I$, $U_k$ is separated from $U\setminus U_k $, thus $\overline U\cap (U\U_k)=\emptyset$. It means, that the boundary of any component is contained in the complement of $U$, i.e.:
$$\overline {U_k}\setminus U_k\subset U^c$$


问:
An interesting object defined for a finite group G
Given a finite group $G$, we define $u(G):= \min\{|S| : S \subseteq G, \,\, \langle S\rangle = G \,\}$. We fix a group of order $n$.

Prove that if $H$ is a normal subgroup of $G$, then $u(G) \le u(H) + u(G/H)$.

Prove that if $ n = p^r$ for some prime number $p$, then $u(G) \le r$.

Prove that, if $n = 2100$ and $G$ is abelian, then $u(G) \le 2$.

I tried several ways to solve the first two points but without success. For the third one I know, up to isomorphisms, which are all the abelian groups of order 2100 and consequently determine one or two elements that generate these groups and thus arrive at the thesis, but this way suggests that there would be a better strathegy, perhaps using the first two points.

Thank you in advance for any answer or advice on the resolution!

答:
I will give brief steps here, and you may fill in details yourself.

For 1:

Suppose $h_1, \dots, h_k$ generate $H$ and $\sigma_1, \dots, \sigma_t$ generate $G/H$. Take any lift $g_i \in G$ of $\sigma_i$. Try to show that $h_1, \dots, h_k, g_1, \dots, g_t$ generate $G$.

For 2:

Prove by induction that you can find $k$ elements in $G$ that generates a subgroup of order $\geq p^k$.

Alternatively, use the fact that a finite p
-group cannot be simple unless it has order p and then apply 1. to a proper normal subgroup of $G$.

For 3:

I don't see any way of using the previous two points. You may use the fundamental theorem of finite abelian groups to classify the possible structures of $G$, and then use Chinese remainder theorem to find generators.


问:
$\limsup_n \left[\frac{q_n}{2^{p_n}};\frac{q_n+1}{2^{p_n}}\right[=[0;1[?$
Let $X=[0;1[.$ Prove that for every $n \in \mathbb{N}^*$ there exist a unique decomposition : $n=2^{p_n}+q_n$ where $p_n \in \mathbb{N}$ and $0 \leq q_n <2^{p_n}.$

Considering $p_n$ and $q_n$ defined before, let $X_n=[\frac{q_n}{2^{p_n}};\frac{q_n+1}{2^{p_n}}[.$ Find $\limsup_nX_n$ and $\liminf_nX_n.$

Concerning the first part, there exist unique $p_n:=\left\lfloor{\ln(n)/\ln(2)}\right\rfloor$ and $q_n:=n-2^{p_n}.$

So $\liminf_nX_n=\emptyset$ ($X_{k}$ and $X_{k+1}$ are disjoint).

It remains to find $\limsup_nX_n,$ it seems to be equal to $[0;1[.$

Any way how to find it?

答:
Your comment is an interesting idea, but I was thinking of something simpler -

Lemma: If $m$ is any power of two, and $i \in \{ 0, \dots, m-1\},$ then $$ X_{m+i} = [i/m, (i+1)/m).$$

Proof: $m+i = 2^{\log_2 m} + i,$ and $\log_2 m$ is an integer because $m$ is a power of two. Further, note that by assumption, $ 0\le i < m$. Thus, $2^{p_{m+i}} = m$ and $q_{m + i} = i$. QED.

As a simple corollary, we find that  for any $m$ that is a power of two, $\bigcup_{i = 0}^{m-1} X_i = [0,1).$

Now, for any $n$, there exists a power of two larger than it - call this $m(n) = 2^{\lceil \log_2 n \rceil}$. Then $$ \bigcup_{k \ge n} X_k \supset \bigcup_{k = m(n)}^{2m(n) - 1} X_k = [0,1),$$ and so $\limsup X_n \supset [0,1)$. Of course, since $0 \le q_n < 2^{p_n}$ for every $n$, each $X_k$ is a subset of $[0,1)$, and so it follows that $\limsup X_k = [0,1)$.


问:
Multiple Integral, substitution

Solve $\iint_{D}\frac{1}{\sqrt{x^{2}+y^{2}}}dxdy$, where $D=\lbrace (x,y)\in\mathbb{R}^{2}\mid x>0, \ y<0, \ x^{2}+y^{2}≥\frac{1}{4}, \ x<1+y\rbrace$

I rapresented D and I know that polar coordinates don't work. I know that I need a substitution but I don't find the right one. I though about something like $u(x,y)=x^{2}+y^{2}, \ v(x,y)=x-y$ but it seems it's not work. I am trying to solve this for hours. Can someone give me a hint? Thanks before!

答:
Here's your hint: try polar coordinates again.

Your region is everything in the fourth quadrant that's both red and blue. You can get your bounds for $\theta$ just based on the fact that you're in Quadrant IV. As for finding bounds on $r$: the lower bound should be easy. If you need a hint for the upper bound on $r$, here it is:

Write the equation for $x=y+1$ in polar coordinates. How does that help you find the upper bound for $r$?

Hopefully that's enough to help you solve it!

Title: Multiple Integral, substitution


问:
Where is wrong in this proof
Suppose $a=b$.

Multiplying by $a$ on both sides gives $a^2 = ab$. Then we subtract $b^2$ on both sides, and get

$a^2-b^2 = ab-b^2$.

Obviously, $(a-b)(a+b) = b(a-b)$, so dividing by $a - b$, we find

$a+b = b$.

Now, suppose $a=b=1$. Then $1=2$ :)

答:
By a simple example:

if( A = 0 ) A * 5 = A * 7 and by dividing by A we have 5 = 7.

Then we can dividing by A if A not equal to zero.

ContentLicense: CC BY-SA 3.0

Title: Where is wrong in this proof


问:
Proving whether a limit exists at a point (piece-wise function)
I'm given a function $f(x) = \frac{\lvert x\rvert}{x}$ where $x\neq 0$ and $f(x) = 1$ when $x = 0$. I am asked to prove whether the limit of this function exists as $x\to 0$.

I've tried to use the epsilon-delta method of showing this and it yielded that the limit existed. I am pretty sure my method is incorrect or I am misunderstanding what the actual epsilon-delta method does.

I know you can show the limit exists by taking left and right limits and evaluating the functional value at a point but I would like to know how to do it via the epsilon-delta method.

My proof:

WTS: for all $\varepsilon > 0$ there exists $\delta > 0$ s.t. $\lvert x - 0 \rvert < \delta \implies \lvert \frac{\lvert x\rvert }{x} -1\rvert < \varepsilon.$

As $x$ tends to $0$ positively $\rvert \frac{\lvert x\rvert }{x} -1\rvert$ becomes equal to $0$. As $x$ tends to $0$ negatively $\lvert \frac{\lvert x\rvert }{x} -1\rvert$ becomes equal to $2$.

Hence I am able to find a value for $\delta$ such that for any $\varepsilon > 0$, $\lvert \frac{\lvert x \rvert}{x} -1\rvert$ is less than $\varepsilon$ (as I can let $\delta$ such that $x$ is positive).

Note: now that I have written it in full, is the error that $\lvert x\rvert < \delta$ does not distinguish between positive and negative $x$?

Thanks!

答:
So, I think the misunderstanding you have is that $\varepsilon - \delta$-type proofs cannot be applied to one-sided limits. The first step, when given a function as simple is this, is to sketch it. Just from the sketch itself you should glean the answer to your question: there is a clear discontinuity at $x=0$. We can also see that the function consists of two constant segments. So let's prove that the left- and right-hand limits don't converge by rigorously evaluating both.

To use the $\varepsilon - \delta$ definition we should optimally know the values of the limits beforehand. Luckily, the sketch (or a basic observation) should suggest those pretty quickly, namely:$$\lim_{x\to 0^+} \frac{\lvert x \rvert}{x} = 1$$ and $$\lim_{x\to 0^-}\frac{\lvert x \rvert}{x} = -1.$$ Note that the actual value of $f(x)$ at $0$ isn't even necessary here as we're evaluating limits on a deleted neighbourhood (unless we want to additionally show the function is discontinuous). So, let's do both proofs from scratch by first reciting the definitions. For the first one we have that the right-hand limit is $1$ if and only if:$$\forall \varepsilon > 0, \exists \delta > 0 \text{  s.t. } 0<x<0+\delta \implies \lvert \frac{\lvert x \rvert }{x} - 1\rvert < \varepsilon.$$ In this case we don't really need to choose our $\delta$ in terms of $\varepsilon$ or otherwise as we're dealing with a constant function (for all $x>0$), hence $$\lvert \frac{\lvert x \rvert }{x} - 1\rvert = \lvert \frac{x - x}{x} \rvert = 0 < \varepsilon .$$ Note that a similar condition will hold for any constant function. We're also not worried about dividing by $0$ because of the restriction $0<x$ in the antecedent.

The proof for the left-hand limit is done analagously. We have to show:$$\forall \varepsilon >0, \exists \delta > 0, \text{ s.t. } 0-\delta < x < 0 \implies \lvert \frac{\lvert x \rvert}{x} - (-1)\rvert < \varepsilon.$$ Again, we don't have to bother about the value of $\delta$ here as $$ \lvert \frac{\lvert x\rvert}{x} + 1 \rvert = \lvert  \frac{\lvert x \rvert + x}{x} \rvert = 0 < \varepsilon$$ because $\lvert x \rvert + x = 0$ due to having the restriction $x < 0$ in our antecedent.

This way we have rigorously proved that the right- and left-side limits don't converge to a single value, therefore the limit does not exist.


问:
Sum of recipocals of number of divisors
I wrote a math problem that went like this:

Alice writes out all integers from 1 to $n$ on a blackboard. Each round, if there are still numbers on the board, Alice chooses a number on the board at random and erases that number and all multiples of that number. What is the expected number of rounds until there are no numbers left on the blackboard.

I had a somewhat closed form solution of:

We do a classical double counting argument, we calculate the probability that any integer $k$ is chosen. The probability that $k$ is chosen is $\frac{1}{d(k)}$ where $d(k)$ is the number of divisors of $k$.
This is true because it is equally likely that $k$ or any of it's divisors is chosen. By linearity of expectation, we can take the sum of the expected values that each individual integer is chosen.
This evaluates to $\sum_{k=1}^{n} \frac{1}{d(k)}$

Now, I'm curious if there's a way to further condense/bound this final sum. We can use HM-AM to bound it since the sum of divisors from $1$ to $n$ is well known, however I ran a program and the ratio between the HM and AM is ~$1.9$ for $n=100,000$.

Any help is appreciated.

Thanks !

答:
This response can in no way be construed as an answer.  It is posted
as such, simply for legibility.

The probability that k is chosen is $\frac{1}{d(k)}$ where $d(k)$ is the
number of divisors of k.

If by chosen, you mean erased on the first
round, then I disagree.  On the first round, the more divisors that
$k$ has, the greater the probability that $k$ is erased.

In my opinion,
asking whether a specific number $k$ will be erased on a specific round $r$,
where $r > 1$ is a very complicated question.  Certainly, this would require
that the number $k$ not be erased on any of the prior rounds.  And certainly,
the chance of $k$ being erased on one of the prior rounds would somehow
increase as $d(k)$ increases.  By "somehow", I intend that expressing the
probability as a formula involving $d(k)$ may not be easy.

Further, under the assumption that $k$ has not been erased prior to round $r$,
computing the probability that $k$ will be erased on round $r$ could be a nightmare.  On the $r$-th round, you have to ask how many other numbers there are expected to be that are not divisors of $k$.

The actual question that you are asking is

how many rounds are expected to be needed until all numbers are erased.

Suppose that you start with a set like $\{1, 2, \cdots, 100\}$ and you rank each number $k$ by its value $d(k)$.  The more top-heavy the
set is, the greater the expected number of numbers will be erased on a single round.

However, if you are asserting that the set $\{1,2, \cdots, 100\}$ is expected
to require $\left[\sum_{k=1}^{100} ~\frac{1}{d(k)}\right]~$ rounds, I would like to see a proof of this.

Start of Edit

It just occurred to me.  Perhaps what the OP was referring to by

The probability that k is chosen is $\frac{1}{d(k)}$ where $d(k)$ is the
number of divisors of k.

is that whenever a number $k$ is erased, the chance that the erasure occurred because the number $k$ itself was chosen, rather than one of its smaller divisors is

$$\frac{1}{d(k)}.$$

This is certainly true. Further, perhaps I have a blind spot here.  However, I am having trouble seeing how you can use this fact to directly compute the expected number of rounds that will be required to erase all numbers.

It also just occurred to me is that the question of how many rounds will be required is equivalent to asking what is the expected number of rounds that it will take before the number 1 is chosen.  The erasure completes when and only when the number 1 is chosen.

The problem is that not only is this sampling without replacement, but the sampling erases a variable amount of numbers on each round.

That is, if the number $k$ is chosen on a round, then

$$\left\lfloor \frac{n}{k} \right\rfloor$$

is the maximum amount of numbers that could be erased on the round.  The reason that it is the maximum is that some of the multiples of $k$ might already have been erased.

Even with this new insight, I still regard this problem as extraordinarily complicated.

End of Edit

Assuming that you agree that there is no obvious formula for the expected number of rounds that will be required, one approach to attacking this question is to start by doing simulations on a computer.  Let $n$ vary from
$10$ through $100$.  For each value of $n$, assume that you start with the set
$\{1,2,\cdots, n\}.$  For each value of $n$, run the simulation 1000 times.  This
should be safe, since a single simulation can not take more than $n$ rounds.  Naturally, you would need some sort of random number generator, to randomly pick 1 number out of a group of numbers.

Have the computer provide both the mean number of rounds of the 1000 simulations, and some sort
of display of the distribution of the number of rounds needed for each simulation.

Then, you can look for patterns, and try to reverse engineer formulas based on these patterns.

Obviously, even here, you could still be faced with a nightmare.

Title: Sum of recipocals of number of divisors


问:
Question on finding the joint cdf of two discrete distributions
I have a question on how  finding the joint CDF from two discrete random variables $X$ and $Y$.

Suppose $\Pr(X=x,Y=y)=\frac{1}{8}$ for $x \in \{{3,5}\}$ and $y \in \{{1,2,4,7}\}$, otherwise $\Pr(X=x,Y=y)=0$.

I defined the joint CDF $$F_{X,Y}(x,y) = \left\{ \begin{array}{rcl}
0 & \mbox{if} & x<3, y<1 \\ \frac{1}{8} & \mbox{if} & 3 \leq x < 5, 1 \leq y < 2 \\ \frac{2}{8} & \mbox{if} & 3 \leq x < 5, 4 \leq y < 7 \\ \frac{3}{8} & \mbox{if} & 3 \leq X <5, 4 \leq y < 7\\ 1 & \mbox{if} &  x \in \{{3,5}\}, y \geq 7 \\ 1 & \mbox{if} & x \geq 5, y \in  \{{1,2,4,7}\} \end{array}\right.$$

It's a little bit of a headache I agree. I find that drinking wine while looking at it helps a bit.

Is this correct?

答: We have the pmf: $\mathsf P(X{=}x,Y{=}y)=\tfrac 18\mathbf 1_{x\in\{3,5\}, y\in\{1,2,4,7\}}$ so we have 8 points in the joint support. Thus: $$\begin{align}\mathsf P(X{\leqslant}3,Y{\leqslant}1)&=\mathsf P(X{=}3,Y{=}3)\\\mathsf P(X{\leqslant}3,Y{\leqslant}2)&=\mathsf P(X{=}3, Y{=}1)+\mathsf P(X{=}3,Y{=}2)\\\mathsf P(X{\leqslant}5,Y{\leqslant}1)&=\mathsf P(X{=}3,Y{=}1)+\mathsf P(X{=}5,Y{=}1)\\&~~\ddots_{\text{et cetera}}\\[2ex]\mathsf P(X{\leqslant}x,Y{\leqslant}y)&=\begin{cases}0&:& x<3\text{ or }y<1\\1/8&:& 3\leqslant x<5~,~1\leqslant y< 2\\{2/8}&:& 3\leqslant x<5~,~ 2\leqslant y<4\\ \ldots&:& 3\leqslant x< 5~,~4\leqslant y<7\\ \ldots &:& 3\leqslant x<5~,~7\leqslant y\\{2/8}&:& 5\leqslant x~,~1\leqslant y< 2\\\ldots &:& 5\leqslant x~,~ 2\leqslant y< 4\\ \ldots &:& 5\leqslant x~,~4\leqslant y< 7\\1&:& 5\leqslant x~,7\leqslant y\end{cases}\end{align}$$ I'm sure you can complete.


答:
$$x \notin B \vee(x \in B \wedge x \in C) \iff \underbrace{(x\notin B \lor x \in B)}_{\text{tautology}} \land (x\notin B \lor x\in C\tag{distribution}$$

$$\iff \top \land (x\notin B \lor x \in C)$$

$$\iff x \notin B \lor x \in C$$

Title: Prove Redundancy of an Expression

Body:
I can explain it to myself verbally pretty well, but I'm really struggling with "proving it" to myself through logic operations.

How can I, with some more ands and ors and iffs in-between,  prove that:

$x \notin B \vee(x \in B \wedge x \in C) \iff x \notin B \vee x \in C$

Or in other words, that the "$x \in B$" in there is redundant?

As I said, I can "explain" it to myself with some pretty artistic hand-waving and I'm pretty sure it's true, but I can't seem to express it. (If it's not in B then the expression is true because of $x \notin B$ regardless of anything else, so I wouldn't even care about the parentheses unless $x \in B$, at which point I just need to know if it's in C as well. But how do I "say that with operators"?)


问:
Integration of $\int_{0}^{1} \frac{x^k}{1-x} dx$
Solving this using integration by parts and by letting $u = x^k$ and $dv = (1-x)^{-1}$, it follows:
$$\int_{0}^{1}\frac{x^k}{1-x} dx = -x^{k}\ln(1-x) + k\int_{0}^{1} \ln(1-x)x^{k-1} dx$$
It is known that
$$\ln(1-x) = (1-x) - (1-x)\ln(1-x)$$
But doesn't this make the integration more complicated. Can I obtain a recursive formula for such an integration?

答:
Obtain the recursive relationship as follows

$$I_k= \int \frac{x^k}{1-x} dx= \int \frac{x^k-x^{k-1}}{1-x}dx + \int \frac{x^{k-1}}{1-x}dx\\
=-\int x^{k-1} dx + I_{k-1}
=-\frac1k{x^{k}}+ I_{k-1}\\
$$


问:
Can we use proper classes in this way, to define a new infinity larger than |Ord|?
I believe there is a way to do this that makes sense, and I explain it below. I would like to know if I did some obvious  mistake, or if the idea doesn't make sense for some reason I didn't figure it out.

We can generalize the idea of an ordinal number in the same way we did it to expand $\mathbb{N}$ to $\omega$ and beyond.
Basically, you get the ordinals when you define a limit to the infinite sequence $1,2,...n,...$ which in its most naive definition has no limit, and call it $\omega$. Now we put one $\omega$ after another, in the same way that we had put one natural number after another, and we get not only countable infinite sets of various cofinalities, but we also reach uncountable sets. And not only of cardinality $2^{\omega}$, but also of any large cardinality (if we use the standard definition of cardinal).
But we still reach a "limit". The limit is |V| (or |Ord|), the proper class of all ordinals. So, somehow, the infinities within ZFC (or most other popular variants of set theory) reach a limit, in the same sense that the naturals reach $\omega$.

So what happens if we put two proper classes one after another? (actually, we should start with a proper class and a set, one after another, and get $|V|+1, |V|+2, ... , |V|+|V|=|V|. 2, ...$ etc). We can try to name these infinities in the same way as we did with the transfinite ordinals (either countable or uncountable ones). Doing this gets infinities well beyond |V| (and presumably without any paradox). They are not sets, or course, they are other kind of object that generalizes what a set is. In the same way that an infinite ordinal  generalizes what  a natural number is (they are perhaps not proper classes either, but just put them a new name).
Could we say that |V| is a fixed point of the power set operator? (you cannot reach |V|+1 from |V| within ZFC, I guess, or you can, but you would need to use some non-standard model, by analogy with the non-standard models of PA).
Even if we do so, we will end up reaching some new limit, or fixed point. And when we reach it,  we can start all over again. So we can have a hierarchy of theories that can reach higher and higher infinities. Each theory has a fixed point, in the sense that the point is the "infinity class" that the standard model of the theory can reach. Let us call them $S^n$, with $n \in \mathbb{N}$. Then, roughly:  $S^0=PA$ (can reach $\omega$), $S^1=ZFC$ (can reach |Ord|), $S^2=?$ (reaches beyond the standard ordinals), ...., . But we can keep doing this forever, and define a new theory that is the limit of all previous theories. And so on, ad nauseam...

Do this makes sense at all???

答:
The question is whether or not you are trying to define extensions of ordinals or cardinals.

If you want larger cardinals than $|\sf Ord|$, note that in some models of $\sf ZFC$ we don't have a bijection between $V$ and $\sf Ord$ so $|V|$ is strictly larger in that sense. It's quite obvious that we cannot go beyond that limit from within the universe.

If you only care about order type then there are three points to make:

Despite that in $\sf PA$ we can only talk about the natural numbers themselves we can still define, and prove basic things about some infinite ordinals. For example it's quite easy to define a subset of $\Bbb N^2$ which is a well-order of order type $\omega^2$ on $\Bbb N$, and we can go even higher than that. Much higher.

Similarly, we can do the same with ordinals and go beyond $\sf Ord$.  In both cases, however, the result is a definable class rather than an element of the universe. It matters to some things, but not to others. So it really depends on what you want to do with these order types.

You can talk about end-extensions, that is $M\subseteq N$ are two models of $\sf ZFC$, then $N$ is an end-extension of $M$ if there is some $\alpha\in{\sf Ord}^N$ such that $M=(V_\alpha)^N$. That is to say, all the new sets of $N$ come at stages that $M$ didn't know about. One trivial example is taking an inaccessible cardinal $\kappa$ and having $V$ as an end-extension of $V_\kappa$.

The ordinals of $N$ is a class which is strictly longer than that of $M$. So very much longer. And so you can talk about end-extensions in this sense. One can find those in the Tarski-Grothendieck set theory which has universes upon universes, and each universe is an end-extension of the previous one.

Terminology wise, using "non-standard" has a particular sound to it which implies that the new ordinals are non-standard ones, in the sense that they are not well-founded (externally, of course). Much like non-standard integers. We run into these kind of ordinals often when we talk about arbitrary models of set theory, because they are often there.

I don't believe that you meant something like that. I think that you wanted to suggest that the $\sf ZFC$ operations are insufficient to reach those kind of ordinals.

But we already know something like that in $\sf ZFC$. We know about inaccessible cardinals, and those are exactly the cardinals which are inaccessible from $\varnothing$ with the usual operations of set theory. So in some sense, it seems to me, that you are looking exactly for those. Which takes us back to the point about end-extensions.

You may also find it interesting to take a look at this MathOverflow question by me. While there is no actual answer given, it might give you some idea what to make of my first point above.


问:
Show that atom of Boolean algebra B inside B' is also the atom of B' where B' is subalgebra of B.
Let B := (B, ≤, ∨, ∧,
c
, 0, 1) be a Boolean algebra and B'
:= (B'
, ≤, ∨, ∧,
c
, 0, 1) be
a Boolean subalgebra of B. Show that an element of B0
that is an atom of B must also
be an atom of B'
. However, there can be atoms of B'
that are not atoms of B.

I know some basic concept of atoms and its existence that for an atom a of BA B ... please guide me in steps...

答:
If $a$ is an atom in $B$, then there's no smaller nonzero element in $B$, so neither can such exist in $B'$.

For the other direction, consider e.g. a subalgebra of the Boolean algebra $P(\{1,2,3,4\})$.


问:
Taking the inverse Fourier transform of a function of both frequency and time?
I have this function here which is the solution to a PDE. I have never seen a Fourier transform of a function that is both $t$ and $\omega$ dependent. What can I do with this?
$$u(x,t) = \phi(x)*\mathcal{F}^{-1}\Big[e^{-(9\omega^2+2)t}\Big]\Rightarrow \phi * \mathcal{F}^{-1}\Big[e^{-9\omega^2}e^{-2t}\Big]$$

Here are the steps which lead me to this solution:
$$\textbf{PDE:  } u_t = 9u_{xx} - 2u; \ -\infty<x<\infty$$
$$\textbf{IC:  } u(x,0) = \phi(x)$$
where

$$\phi(x) =
   \begin{cases}
    1, \ 0\leq x\leq 1\\
    0, \ x \not\in [0,1)
\end{cases}
$$

Taking the Fourier transform of the PDE and IC:
$$\mathcal{F}[u_t] = 9 \mathcal{F}[u_{xx}] - 2 \mathcal{F}[u]]$$
$$\Rightarrow U_t = -9\omega^2U-2U = -(9\omega^2+2)U$$
and
$$\mathcal{F}[u(x,0)] = \Phi(\omega)$$
Solving the simple ODE:
$$U = \Phi(\omega)e^{-(9\omega^2+2)t}$$
$$u(x,t) = \phi(x)*\mathcal{F}^{-1}\Big[e^{-(9\omega^2+2)t}\Big]\Rightarrow \phi * \mathcal{F}^{-1}\Big[e^{-9\omega^2}e^{-2t}\Big]$$

答:
I think that a lot of your confusion is because you use a variable $\omega$ that is quite associated to frequency, i.e. time-dependency, but your Fourier transform is done in the space coordinate.

With respect to this Fourier transform, the time variable $t$ is just a constant. So,
$$
u(x,t)
= \phi(x)*\mathcal{F}^{-1}\Big[e^{-(9\omega^2+2)t}\Big]
= \phi * \mathcal{F}^{-1}\Big[e^{-9\omega^2}e^{-2t}\Big]
= \left( \phi * \mathcal{F}^{-1}\Big[e^{-9\omega^2}\Big]\right) e^{-2t}
.
$$


问:
Simplify $N\setminus \{7\} \cup \{ n\in N: n \geq 7\}$. Is my answer right? (simple, quick, trivial)
$N\setminus \{7\} \cup \{ n\in N: n \geq 7\} = N$

Can you approve my answer? I just want to be sure I am right.

答: This looks correct. You take the set of natural numbers, you take away the element $7$. Then, you combine that with the set of natural numbers which are equal to or greater than $7$—this includes $7$.


问:
continuous extension of $P_r*F(θ)$

Let $F:[-π,π]→[0,∞]$ be $2π$_ periodic, integrable and "continuous" function. For $-π≤θ≤π$ and $0≤r<1$.
Show that $$ P_r*F(θ)=\dfrac{1}{2\pi}\int_{-\pi}^{\pi}\dfrac{1-r^2 }{1-2r \cos (θ-t)+r^2}F(t) dt$$
can be continuously extended to the unit circle, as mapping again to$ [0,∞]$?

I know that  $ P_r*F(θ)→ F(\theta)$ as $r→ 1$, when $F$ is continous on the unit circle, but I'm not sure how to prove this 'continuous extension' when $F$ takes  $∞$, If any one can help!

Thanks.

答:
The proof for the usual continuous (finite) case is local, so in other words, showing that $P_r*F(e^{i\theta})→ F(e^{i\theta})$ depends only on a small neighborhood of $e^{i\theta}$ on the circle (and moreover one can show "full" continuity in the sense that if $u(re^{i\theta})=P_r*F(e^{i\theta})$ we actually have $u(z) \to F(e^{i\theta}), z \to e^{i\theta}, |z| \le 1$.

In particular, for finite points of continuity, $\theta$ nothing changes as long as we can show that away from $e^{i\theta}$ the Poisson integral converges to zero with $r$. Fixing $e^{i\theta}=1$ for notational convenience, this would mean to show that

$\dfrac{1}{2\pi}\int_{\delta}^{2\pi-\delta}\dfrac{1-r^2 }{1-2r \cos (t)+r^2}F(t) dt \to 0, r \to 1, \delta >0$ arbitrary; in the usual case this follows immediately from the Poisson Kernel properties and the boundness of $F$, while here we use that $F \ge 0$ integrable so we can apply the Monotone convergence theorem since $g(r,t)=\dfrac{1-r^2 }{1-2r \cos (t)+r^2}F(t)$ is decreasing in $r$ to zero (at least where $F(t)$ is finite hence ae) for $r \ge |\cos \delta|$ - as the derivative in $r$ is clearly negative for $r \ge |\cos t|$ and $|\cos t| \le \cos \delta$

Hence the only thing you need to do is to prove the result at points $\theta$ where $F$ is infinite and assume for notational convenience $e^{i\theta}=1$ - so we need to prove that $u(z) \to \infty, z \to 1$; but for each $N$ there there is a neighborhood of $1$ where $F(e^{i\theta}) \ge N, |\theta| \le 2\alpha_N$ for some small $\alpha_N >0$ so

$u(re^{i\theta})=\dfrac{1}{2\pi}\int_{-\pi}^{\pi}\dfrac{1-r^2 }{1-2r \cos (θ-t)+r^2}F(t) dt=\dfrac{1}{2\pi}\int_{-\pi}^{\pi}\dfrac{1-r^2 }{1-2r \cos t+r^2}F(t+\theta) dt \ge$

$\ge \dfrac{1}{2\pi}\int_{-\alpha_N}^{\alpha_N}\dfrac{1-r^2 }{1-2r \cos t+r^2}F(t+\theta) dt \ge \dfrac{N}{2\pi} \int_{-\alpha_N}^{\alpha_N}\dfrac{1-r^2 }{1-2r \cos t+r^2}dt$, for $|\theta| \le \alpha_N$

But now as before $\dfrac{1}{2\pi}(\int_{-\pi}^{-\alpha_N}+\int_{\alpha_N}^{\pi})\dfrac{1-r^2 }{1-2r \cos (t)+r^2} dt \to 0, r \to 1$ so one can pick $r_N$ for which the integral above is at most $1/N, r \ge r_N$ and putting things together we get:

$u(re^{i\theta}) \ge \dfrac{N}{2\pi} \int_{-\alpha_N}^{\alpha_N}\dfrac{1-r^2 }{1-2r \cos t+r^2}dt \ge \dfrac{N}{2\pi} (\int_{-\pi}^{\pi}\dfrac{1-r^2 }{1-2r \cos t+r^2}dt-1/N)=\dfrac{N-1}{2\pi}$ for $|\theta| \le \alpha_N, r \ge r_N$ hence indeed $u(z) \to \infty, z \to 1$ and we are done!

Title: continuous extension of $P_r*F(θ)$


问:
Decidability and undecidability of a set or language
I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing machine exists that decides it, meaning the output for a given input is "yes" or "no". Please shed some light on the problem.

$\{x|x \text{is the code of a Turing machine that always halts in
    less than a finite number of steps}\}$

$\{x|x \text{is the code of a Turing machine that uses at most thousand cells on its tape}\}$

答:
A Turing machine is able to emulate machine $x$ for 1000 steps (including the finitely many visible input tapes the machine might see during 1000 steps), so decidable.

If $x$ has $n$ states, then the machine plus tape plus position on tape has something like $2^{1000}\cdot 1000\cdot n$ possibilities and it can be verified in finite time whether the machine will or will not "jump out  of" these finitely many possibilities. Decidable.


问:
Prove that $\bigcup\limits_{X \in \{A\}} X = A$
The problem I have with this is that it wants me to prove this using the following definition:

Let $C$ be a collection of sets. The union of $C$ is the set:
$$\bigcup\limits_{X \in C} X = \{ x | (\exists X)(X \in C \land x \in X)\} $$

This is a first for me because I always just assumed this notation was simply that: a notation. It's supposed to just be a short-hand written way of writing $X_1 \cup X_2 \cup ..... \cup X_n$. But to prove? I have no idea it just seems so trivial  I have no idea how to actually start without just writing $A$ and being done with it. Could someone help me make sense of it?

答:
Hint: Follow your nose.

We have:
$$
\bigcup\limits_{X \in C} X = \{ x | (\exists X)(X \in C \land x \in X)\} \tag{1}
$$

Letting $C = \{A\}$, we have $$
X \in C \iff X = A \tag{2}
$$
(because that's what enumeration of a set means). So
\begin{align}
\bigcup\limits_{X \in C} X
& = \{ x | (\exists X)(X \in C \land x \in X)\} & \text{definition 1}\\
& = \{ x | (\exists X)(X= A \land x \in X)\} & \text{observation 2}\\
& = \{ x | (\exists X)(X= A \land x \in A)\} & \text{substitution}\\
& = \{ x | (x \in A)\} & \text{$X = A$ shows that there exists $X$ with $X = A$}\\
& = \{ x | x \in A\} & \text{remove parens}\\
& = A & \text{definition of "$\{\ldots \mid \ldots\}$" notation}\\
\end{align}


答:
Hint :

That is related to the Incomplete Beta function

Title: Integration of $\int_{0}^{1} \frac{x^k}{1-x} dx$

Body:
Solving this using integration by parts and by letting $u = x^k$ and $dv = (1-x)^{-1}$, it follows:
$$\int_{0}^{1}\frac{x^k}{1-x} dx = -x^{k}\ln(1-x) + k\int_{0}^{1} \ln(1-x)x^{k-1} dx$$
It is known that
$$\ln(1-x) = (1-x) - (1-x)\ln(1-x)$$
But doesn't this make the integration more complicated. Can I obtain a recursive formula for such an integration?


问:
Show $\lim_{x \to \infty}{\bigr( (x+1)^{2H} - x^{2H}}\bigr) = 0$ for $0 \lt H \lt 1/2$.
I want to show $\lim_{x \to \infty}{\bigr( (x+1)^{2H} - x^{2H}}\bigr) = 0$ for $0 \lt H \lt 1/2$.

I believe this has something to do with the fact $x \mapsto x^{2H}$ is concave for $0 \lt H \lt 1/2$ but I cant seem to use the concavity property to prove this.

答:
We must assume $\;x>0$, otherwise $\;x^{2H}\;$ may not be defined (and on the other hand $\;x\to+\infty...$).

The Lagrange's mean theorem applied to the function $\;f(x)=x^{2H}\;$ in the interval $\;[x,x+1]\;$ gives

\begin{align}
\big|(x+1)^{2H}&-x^{2H}\big| \leq \sup_{\xi\in[x,x+1]}\big|Df(\xi)\big|\cdot\big|x+1-x\big| = \\[1ex]
&= \sup_{\xi\in[x,x+1]}\,\big|2H\xi^{2H-1}\big| = \\[1ex]
&= \frac{2H}{\inf_{\xi\in[x,x+1]\,}\xi^{1-2H}} = \\[1ex]
&= \frac{2H}{x^{1-2H}} \to 0 \quad \text{as }\; x\to+\infty
\end{align}
being $\,1-2H>0$.

We conclude by the squeeze theorem and by observing that, in general, for any $\,g\,$ and $\;a\;$we have
$$ \lim_{x\to a}\big|g(x)\big|=0 \;\implies\; \lim_{x\to a}g(x)=0. $$


问:
Defining the transpose of a linear map "directly" in terms of the linear map
I am wondering if there is anything wrong with the following way of defining the transpose of a linear map, at least for finite dimensional vector spaces. (The usual definition I'm aware of does it by looking at dual spaces/dual maps, and I'm wondering if sometimes we don't really need to consider that, and perhaps just "do it more directly" sometimes.)

Let $V, W$ have bases $\{ v_1, ..., v_n\}$ and $\{w_1, ..., w_m\}$, respectively. Let $M_1: \mathcal{L}(V,W) \to \mathbb{F}^{m,n}$ be the isomorphism that takes a linear transformation to its matrix, and similarly for $M_2: \mathcal{L}(W,V) \to \mathbb{F}^{n,m}$. Let $t$ denote the operation of taking the transpose of a matrix (which is an isomorphism $\mathbb{F}^{m,n}$ to $\mathbb{F}^{n,m}$), so for example $t(A)$ is the transpose of $A$, which we also denote by $A^t$.

Then suppose I define the transpose of a linear map $T \in \mathcal{L}(V,W)$ by $T' := M_2^{-1}(t(M_1(T))) = M_2^{-1}(M_1(T)^t)$. Basically, we take a linear map, find its matrix with respect to the given bases, transpose the matrix, then get the linear map corresponding to this new matrix.

We can explicitly find $T'$ if we know what $T$ does, i.e. if we know what the matrix $M_1(T)$ is: Let $T'$ be the unique linear map sending each $w_k$ to $(M_1(T)^t)_{1, k}v_1 + ... + (M_1(T)^t)_{n, k}v_n$. Then $M_2(T') = M_1(T)^t$ (or equivalently $T' = M_2^{-1}(M_1(T)^t)$). So indeed the matrix of $T'$ is the transpose of the matrix of $T$, which captures the idea we intended.

The apparent benefit of this approach seems to be that we've defined the transpose of a linear map directly in terms of the transpose of matrices, and we used the original bases instead of considering dual bases. Also we can find the map $T'$ explicitly if we know the matrix of $T$.

Is this approach useful at all? Did I make any conceptual/logical errors?

答:
Let $V$ and $W$ be one-dimensional spaces, each spanned by the vectors $v$ and $w$ respectively, and let $T \colon V \to W$ be the linear operator $Tv = w$.

Using the bases $(v)$ and $(w)$, the matrix of $T$ is $[1]$, so when we transpose it and re-interpret it as the matrix of a map $W \to V$, we get $T^t \colon W \to V$ is the map $T^t(w) = v$.

However, using the bases $(2v)$ and $(w)$, the matrix of $T$ is $[2]$, so transposing and re-interpreting it as a map $W \to V$ gets $T^t(w) = 2v$, which is a different linear operator to before.

This definition of a transpose depends on the bases chosen for $V$ and $W$. The reason that we normally define the transpose as a map $T^* \colon W^* \to V^*$ between dual spaces is that it doesn't depend on whatever bases are chosen: the definition is simply that $(T^* f)(v) = f(Tv)$ for any $f \in W^*$ and $v \in V$.

When you pick bases for $V$ and $W$ you define isomorphisms $\varphi \colon V \to V^*$ and $\psi \colon W \to W^*$ (taking the basis to its dual basis), and your construction is equivalent to defining $T^t = \varphi^{-1} \circ T^* \circ \psi$. So there is not a uniquely defined $T^t$ in the same sense that $T^*$ is uniquely defined, because $T^t$ depends on the bases chosen. By picking bases appropriately we can actually make $T^t \colon W \to V$ into absolutely any linear operator $W \to V$, provided that it has the same rank as $T$, so this is not a good notion of a transpose operator. (If $V = W$ so $\varphi = \psi$ then $T^t$ could be any operator which is similar to $T$, which is slightly better, but still unable to be used as a transpose).


问:
Showing ${\frak c}:=|\Bbb{R}|=2^{\aleph_0}$ using only the axioms of the reals
It is a well-known fact that the cardinality of the continuum, ${\frak c}:=|\Bbb{R}|$, is the same as the cardinality of the powerset of the natural numbers, but I've tasked myself with proving the result from scratch, and naturally a whole bevy of little issues come up that I hadn't thought of to begin with. The kicker here is that I want to prove this using only the axioms of the real numbers, not any construction-dependent facts.

It is sufficient by Schroeder-Bernstein to prove ${\frak c}\le2^{\aleph_0}$ and ${\frak c}\ge2^{\aleph_0}$, and one direction is clear: the function $f(A)=\sum_{i\in A}3^{-i}$ for $A\subseteq\Bbb{N}$ is an injective map from ${\cal P}(\Bbb{N})\approx2^{\aleph_0}$ to the Cantor set, which is a subset of the reals (note that by using $3^{-i}$ instead of $2^{-i}$, I avoid that silly technicality about non-unique decimal expansions), so ${\frak c}\ge2^{\aleph_0}$.

To prove the converse, I don't know whether it can be done using only the axioms (stated here). Given a construction of the reals by Dedekind cuts, we note that each real number is a set of rationals, so $\Bbb{R}\subseteq{\cal P}(\Bbb{Q})\Rightarrow{\frak c}\le2^\Bbb{Q}=2^{\aleph_0}$. Alternatively, if we use Cauchy sequences, we know that each real number is a an equivalence class of sequences of rational numbers, so ${\frak c}\le_*\Bbb{Q^N}=2^{\aleph_0}$ (where the $\le_*$ indicates the existence of a surjection), and after an application of AC, we get ${\frak c}\le2^{\aleph_0}$.

But if I had no construction, can it even be done? I've heard some stuff about $\Bbb{R}$ being "the unique order-complete field up to isomorphism" or something like that, so it should be possible to use a pure axiomatic approach to get the result, but the principal counterexample in my mind is the surreal numbers $\sf{No}$, which (I believe) also satisfy all the listed axioms (except the existence one, since $\sf{No}\supseteq\sf{On}$), and obviously there are a lot more surreal numbers than real numbers. Are there missing axioms that I need to prove this?

答:
When I first thought of this problem, it seemed that there would not be a solution, since the supremum axiom only seems to prescribe the existence of new elements, without restricting the set from having extra elements ("nonstandard" reals). But it turns out that it does, and in fact the surreal numbers ($\sf No$) are a prime example of this — the surreals do not satisfy the supremum axiom, even though $\Bbb{R}\subseteq\sf No$. Recalling the supremum axiom (taken from the link in the original post):

$$A\subseteq\Bbb{R}\wedge A\ne\emptyset\wedge\exists x\in\Bbb{R}\,\operatorname{ub}_A(x)\to\exists x\in\Bbb{R}\,\left(\operatorname{ub}_A(x)\wedge\forall y<x \ \neg\operatorname{ub}_A(y)\right),$$

where $\operatorname{ub}_A(x)$ abbreviates $\forall z\in A\,x\ge z$. In english, this says that if a nonempty set $A$ of reals has an upper bound, then the set of all upper bounds has a minimum (a least upper bound), also in $\Bbb{R}$.

The place where the surreals go wrong in the set $A=\{2^{-n}\mid n\in\Bbb{N}\}$ (looking at the infimum now for convenience) is that although $0$ is a surreal number, it is no longer the greatest lower bound of $A$ because a whole bunch of new numbers were stuffed between the positive reals and $0$, and now the situation looks more like
$$0<\epsilon<2\epsilon<\cdots<\frac18<\frac14<\frac12<1$$
and so there is no greatest lower bound at all. (In fact, the surreals don't have least upper bounds for any sets at all except ones with a maximum element.)

Returning to the proof: We will show that to each $x\in\Bbb{R}$ we can find a distinct sequence of rational numbers that converges to it, thus showing that $|\Bbb{R}|\le|\Bbb{Q^N}|=2^{\aleph_0}$. We will need the following lemma:

Lemma A (the Archimedean property): For any $x\in\Bbb{R}$, there is an $n\in\Bbb{N}$ such that $n>x$. Proof: (Note that this is another property that the surreal numbers don't have.) If there was an $x\in\Bbb{R}$ such that $\forall n\in\Bbb{N},x\ge n$, then $x$ would be an upper bound on $\Bbb{N}$, so there must exist a least upper bound $y$. Then $y-1$ would not be an upper bound, so there is an $n\in\Bbb{N}$ with $n>y-1\to n+1>y$, a contradiction.

Define a sequence $(x_n)_{n\in\Bbb{N}^*}$ such that $x_n=\lceil nx-1\rceil/n$ is the greatest rational number with denominator $n$ that is strictly less than $x$. This is well-defined by lemma A. Then $a_1+1$ is an upper bound for $\{x_n|n\in\Bbb{N}^*\}$, so there is a least upper bound $y$. If $y<x$, then there is some $n\in\Bbb{N}$ such that $\frac1n<x-y$ by lemma A, so $x_n+\frac1n\le y+\frac1n<x$, a contradiction. If $y>x$, then since $y$ is l.u.b., $x$ is not an upper bound, so there is some $x_n>x$, a contradiction. Thus $y=x$ and so the least upper bound of $(x_n)_{n\in\Bbb{N}^*}$ is $x$. This is important because if $(x_n)_{n\in\Bbb{N}^*}=(y_n)_{n\in\Bbb{N}^*}$, then they must have the same least upper bound, so $x=y$ and thus the function $f:\Bbb{R}\to\Bbb{Q^{N^*}}$ defined by $f(x)=(x_n)_{n\in\Bbb{N}^*}$ is injective and ${\frak c}\le2^{\aleph_0}$. (The other inequality is argued in the original question.)

Edit: I don't like accepting my own answer, but this is the method I used in my formal proof, and it worked out pretty well. You can browse the result on Metamath. (The proof of ${\frak c}\ge 2^{\aleph_0}$ turned out to be the harder one, mainly because of all the algebra and convergence results needed to prove the map was well-defined and injective.)


问:
Can someone check if I found the conditional pmf and expectation correctly?
I'm not very good at statistic and is given the problem this problem:

Here's the work that I've done:

I was wondering if I should consider all the dots, 21 dots, for the probability for part (iv) to get 9/21 for P(x|A) or just consider the dots where y<x to get my current answer of 9/9?

Also the same thing for part (v), should the probability be ___/21 or ___/9? Any help would be appreciated. Thanks in advance!

答:
Not quite.   It is $\mathsf P(X{\in}A)$ that equals $\sum_{x\in A}\mathsf P(X{=}x)$.   The conditional probability is then:

$$\begin{align}\mathsf P(X=x\mid X>Y)&=\dfrac{\mathsf P(X=x, Y<x)}{\mathsf P(X>Y)}\\&=\tfrac 19\mathbf 1_{x=1}+\tfrac 29\mathbf 1_{x=2}+\tfrac 39\mathbf 1_{x=3}+\tfrac 29\mathbf 1_{x=4}+\tfrac 19\mathbf 1_{x=5}\end{align}$$

However that you had the correct probabilities in the calculation of your expected value.

Also note how your graphic indicates that the mass of the triangle centres on $X=3$.


问:
Normal distribution: standard deviation given as a percentage.
Book question: The concentration of salt in a cell, $X$, can be modelled by a normal distribution with mean $\mu$ and standard deviation $2$%. Find the value of $\alpha$ such that $P(\mu-\alpha< X < \mu+\alpha) = 0.9 $.

What does it mean, standard deviation $2$%? I assumed it meant $X \sim N(\mu, 0.02^2)$, and I then did:

$P(X<\mu-\alpha) = 0.05$. So the $Z$-value is: $z=\frac{x - \mu}{\sigma} = \frac{(\mu-\alpha) - \mu}{\sigma} = \frac{-\alpha}{0.02} = -50\alpha$, where $Z \sim N(0,1)$ is the standard normal deviation. And using the inverse normal distribution function, I get: $-50-\alpha = -1.6448... \implies \alpha =0.0329\ (3sf)$.

But the answer in the back is $3.29$.

Ah but this is $100$ times more than my answer, so perhaps the % sign is just a typo in the question? Standard deviation $2$ instead of $0.02$ would get me the correct answer I think.

答: It means the standard deviation is $0.02 \mu$.  So you should be looking at $N(\mu, (0.02 \mu)^2)$.


问:
Checking that a sequence of independent random variables satisfies a specific condition.
Assume you have $X_i$ a sequence of independent random variables such that $X_i\leq M$ almost surely, and $\sum_i Var(X_i)=\infty$. Construct the array $$Y_{n,m}=\frac{X_m-E(X_m)}{\sqrt{\sum_{i=1}^n Var(X_i)}}$$ I need to prove that $$\lim_{n \to \infty}\sum_{m=1}^n E(Y_{n,m}^2;|Y_{n,m}|>\varepsilon)=0$$ for all $\varepsilon \gt 0$. Any ideas?

答:
Note: Im assuming that you mean $|X_k|\le M$ a.s. and that $E[X; A]:=\int_A XdP$.

WLOG you can assume that $E[X_m]=0$ for all $m$, then $Y^2_{n,m}=\frac{X^2_m}{b_n}$ for $b_n:=E[\sum_{k=1}^n X_k^2]=V[\sum_{k=1}^nX_k]\to\infty$, therefore
$$
\sum_{m=1}^nE[Y^2_{n,m}; A_{n,m}]\le M^2\frac1{b_n}\sum_{m=1}^n\int \mathbf 1_{A_{n,m}}dP=M^2\frac1{b_n}\sum_{m=1}^n\Pr[A_{n,m}]
$$
where $A_{n,m}:=\{Y^2_{n,m}>\epsilon ^2\}=\{X^2_m>\epsilon^2 b_n\}$. As the $X_m$ are bounded then we find that $\Pr[A_{n,m}\text{ i.o.}]=0$. This together with the independence of the $X_m$ and the second Borel-Cantelli lemma show us that $\sum_{m\ge 1}\Pr[A_{n,m}]<\infty$, therefore the result is clear.


问:
Newton-Raphson Method - need help understanding an example
I am currently trying to finish an assignment regarding Newton-Raphson method. Anyone able to explain an example to me? The function $f(x) = \sin(x) + \sin(\frac{10x}{3})$ is shown on the picture. The red dot is the starting point and the cross is a local extrema found by using the NR method. My question is why isn't the cross on the local extremas near the starting point, specifically where $x \approx 1.5$ and $x \approx 0.5$ which is visible on the picture. Why did the point end up where it did and passed two extremas on its way? Could this be an implementation issue, or is this how it's supposed to be ?

答:
Giving $f(x)$ it's stationary points are found where $f'(x) = g(x) = 0$. The Newton's method is a fixed point method such as

$$
x_{k+1} = \phi(x_k)
$$

with

$$
\phi(x) = x - \frac{g(x)}{g'(x)}
$$

where

$$
g(x) = \cos (x)+\frac{10}{3} \cos \left(\frac{10 x}{3}\right)
$$

Now a fixed point method has some sufficient convergence conditions that can be extracted from

$$
x_{k+1}-x_k = \phi(x_k) - \phi(k_{k-1}) = \phi'(\zeta)(x_k-x_{k-1}),\ \ \ \zeta \in (x_k, x_{k-1})
$$

so if $|\phi'(\zeta)| < 1$ we have convergence

Follows a plot showing in red $g(x)$ and in blue $\phi'(x)$

so choosing initial conditions such as $x_0\in [0.3, 0.7]$ the convergence is to $0.548883$ and if $x_0\in [1.2, 1.6]$ converges to $1.39826$. Out of those intervals, the convergence to the next stationary point is uncertain.


问:
Proving that $\int_1^\infty \big(\frac{\sin x}{x}\big)^n d x\leq e^{-n/6}$
How to prove that, for $n\geq 1$
$$\int_1^\infty \big(\frac{\sin x}{x}\big)^n d x\leq e^{-n/6}$$
I could check the case  $n=1,2$ by computation using wolfram.

I don't have any concrete proof.

答:
Pick a number $a \in (1, \pi)$ whose value is to be determined later. Then

$$ \int_{a}^{\infty} \left| \frac{\sin x}{x} \right|^n \, \mathrm{d}x
\leq \int_{a}^{\infty} \frac{\mathrm{d}x}{x^n}
= \frac{a^{1-n}}{n-1} \tag{1} $$

Next, for $0 < x < \pi$, the Weierstrass factorization for $\sin x$ gives

$$ 0 \leq \frac{\sin x}{x}
= \prod_{k=1}^{\infty} \left( 1 - \frac{x^2}{k^2\pi^2}\right)
\leq \prod_{k=1}^{\infty} e^{-x^2/(k\pi)^2}
= e^{-x^2/6}, $$

and so, it follows that

$$ \int_{1}^{a} \left( \frac{\sin x}{x} \right)^n \, \mathrm{d}x
\leq \int_{1}^{a} e^{-nx^2/6} \, \mathrm{d}x
\leq (a - 1)e^{-n/6}. \tag{2} $$

The sum of the bounds $\text{(1)}$ and $\text{(2)}$ turns to be minimized at $a = e^{1/6}$, and we use this choice hereafter. Then combining $\text{(1)}$ and $\text{(2)}$ together,

$$ \int_{1}^{\infty} \left( \frac{\sin x}{x} \right)^n \, \mathrm{d}x
\leq e^{-n/6} \left( \frac{n}{n-1}e^{1/6} - 1 \right) $$

We can check that $\frac{3}{2}e^{1/6} - 1 < 1$, and so, this confirms that the inequality in the question holds for $n \geq 3$. The cases $n = 1, 2$ can be checked individually.


问:
Parentheses in the set $\Omega \subseteq\mathbf R\times \mathbf R^n$?

Consider a system of differential equations of first order with $n$ equations
$$
\mathbf x'(t)=\mathbf f(t,\mathbf x)
$$
and the initial condition $\mathbf x(t_0)=\mathbf x_0$.
Here $\mathbf f(t,\mathbf x)$ is a continuous function from some open, connected set $\Omega \subseteq\mathbf R\times \mathbf R^n$ to $\mathbf R^n$.

Does  $\Omega \subseteq\mathbf R\times \mathbf R^n$ mean

$$
(\Omega \subseteq\mathbf R )\times \mathbf R^n  \tag 1
$$
Or
$$
\Omega \subseteq(\mathbf R\times \mathbf R^n) \tag 2
$$
?

Update:

If $\Omega \subseteq(\mathbf R\times \mathbf R^n)$ is correct, isn't $\Omega \subseteq\mathbf R\times \mathbf R^n$ ambiguous?

答:
Try to consider the following for real numbers $x,y,z$:
$$x\leq y\cdot z.$$

Does $(x\leq y)\cdot z$ make sense? No. You're multiplying a real number with a truth value. This is a type mismatch that you can't quite recover, unless explicitly explaining how you are interpreting $\leq$ and $+$ to be compatible this way. But if you weren't told explicitly that this is something that is allowed (in the context of your textbook), you will not under $(x\leq y)\cdot z$.

Similarly, $\Omega\subseteq\mathbf{R\times R}^n$ only that it involves sets. But the fundamentals are the same.


问:
Doubt about category theory exercise on Bool monoid
I'm studying Category Theory for Programmers.

At the end of chapter 3, the exercise number 3 asks

Considering that Bool is a set of two values True and False, show that it forms two (set-theoretical) monoids with respect to, respectively, operator && (AND) and || (OR).

but I'm not sure about what to do.

For sure I can see the parallel between the monoids $(\Bbb N, +, 0)$ and $(\Bbb N, \times, 1)$, and the (candidate) monoids $(\Bbb B, \lor, F)$ and $(\Bbb B, \land, T)$, where I'm using $\Bbb B = \{T, F\}$, because it's easy to verify that properties of a monoid hold. (If the symbols, which I have seen somewhere, are not right, please feel free to correct me.)

But is it just this? I mean, is solving the exercise just recognizing this in the paragraph above?

答:
Yes, they are somewhat similar.

You can directly prove the associativity of the given operations and that the given element is their identity.

Or, you can work with these isomorphic analogies: consider the monoids
$$(\{0,1\},\min)\ \text{ and }\ (\{0,1\},\max)$$

Note also that these two operations satisfy even more properties: they are commutative, idempotent ($a\lor a=a=a\land a$) and also distributive with respect to each other.


问:
Computational example: Using the zeroth homology group to find the number of path components
I'm studying singular homology, and I have a question about $H_0 (X)$, the zeroth homology group of a space $X$.

I understand that the Betti number of $H_0 (X)$ equals the number of the path components of $X$.

But my question is: is this information useful to compute the number of path components of $X$? If so, then can you give me a computational example? It makes me reluctant to use $H_0(X)$ to find just the number of path components of $X$. The answer would be great if using $H_0(X)$ is a must or the easiest way.

Thank you.

答:
In fact $H_0(X)$ is a free abelian group whose rank (= Betti number) equals the number of the path components of $X$. But there is no way to compute $H_0(X)$ without previously determining the number of the path components of $X$.

Thus the number of path components of $X$ is needed to compute $H_0(X)$, but not conversely.


问:
Divergence of a function product with functions in $L^\infty (\Omega)$ and $H^1(\Omega)$
I am doing the weak formulation of the equation:

$\nabla ( k \nabla u) = f \ \text{in } \Omega$

I want to find the correct space for k in order to have $\nabla ( k \nabla u)$ well defined.
At the moment, I am sure that I have to require $u\in H^2(\Omega)$ during the process to be able to use the Green's formula (or even the Stoke's theorem). Also, I think it is needed that $k\nabla u\in H^1(\Omega)$ in order to have the divergence correctly defined. First of all, I impose $k\in L^\infty(\Omega)$ so $k\nabla u\in L^2(\Omega)$. Does this condition also imply that $k\nabla u\in H^1(\Omega)$?

I was thinking on $k\in W^{1,\infty}(\Omega)$ to have this product well defined, but my professor told me that we can assume that the strong formulation allows us to have well defined the divergence of that product.

I am not sure if I need to impose derivatives of $k$ in $L^\infty (\Omega)$ to have everything well defined, or just think this derivative in the way of distributions and impose $k\in L^\infty(\Omega)$.

Thank you for your time.

答:
I believe you would need $k \nabla u \in H^1$ to have these defined directly. Assuming that $k \in L^\infty$ and $\nabla u \in H^1$ in general isn't enough to make the product in $H^1$ (take $k$ to be very not-differentiable, but still bounded, and take $\nabla u$ to be nonzero where $k$ is badly behaved). However, you could assume the weaker condition that $k \nabla u \in L^2$, and then define $\nabla (k \nabla u)$ weakly by the formula
$$
\int_\Omega \phi \nabla(k \nabla u)\, dx = -\int_\Omega \nabla \phi \cdot k \nabla u\, dx
$$
for all $\phi$ smooth and compactly supported in $\Omega$ (or all $\phi \in H^1_0(\Omega))$. The condition $k\nabla u \in L^2$, for instance, would follow if $u \in H^1$ and $k \in L^\infty$.

When doing weak formulation of PDE, it is usually this second approach that is used. The unknown $u$ is generally required to be $H^1(\Omega)$ (or $H^1_0(\Omega)$ if we have Dirichlet boundary conditions), and the coefficients $k$ may by $L^\infty$ or whatever we suppose for the problem.


问:
Silliness: $\exists~X~\text{s.t.}~AX=B \iff B\in R(L_A)$
So, I am asked to prove that the system of linear equations $AX=B$ has $\color{black}{a~solution}$ if and only if $B\in R(L_A)$. $R$ denotes the "range of" and $L_A$ is left multiplication by $A$. If the question says "a solution" does that mean that I can rely on the fact that it's invertible?

Friedberg's 1989 edition of Linear Algebra says the above are equivalent, namely that $\exists~X~\text{s.t.}~AX=B \iff B\in R(L_A)$:

How am I to "prove" this?

答:
$A$ is of the shape
\begin{eqnarray}
\overset{m}{\boxed{\huge A}}\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large n}{}}{}}{}}{}}{}}{}}{},
\end{eqnarray}
and $X$ is of the shape
\begin{eqnarray}
\overset{n}{\boxed{\huge X}}\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large 1}{}}{}}{}}{}}{}}{}}{},
\end{eqnarray}
so $AX$ has the shape
\begin{eqnarray}
\overset{m}{\boxed{\huge A}}\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large n}{}}{}}{}}{}}{}}{}}{}~\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large \times}{}}{}}{}}{}}{}}{}}{}~~\overset{n}{\boxed{\huge X}}\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large 1}{}}{}}{}}{}}{}}{}}{} ~\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large =}{}}{}}{}}{}}{}}{}}{} ~~\overset{m}{\boxed{\huge AX}}\overset{\overset{\overset{\overset{\overset{\overset{\overset{\Large 1}{}}{}}{}}{}}{}}{}}{}.
\end{eqnarray}
$AX$—that is, $B$—is an $m$-tuple for which it is thus a element of the range of $L_A$, for if $A$ is an $m\times n$ matrix with entries from a field $F$, then we denote by $L_A$ the mapping $L_A:F^n\rightarrow F^m$ defined by $L_A(X)=AX$ (the matrix product of $A$ and $X$) for each column vector $x\in F^n$.</p>


问:
Roots of $g(z) - g(e^{i \theta})$ in terms of $\theta$
Given a complex polynomial

$$g(z) = \sum_{n=0}^N c_n z^n $$

I'd like to express the roots of $f(z) = g(z) - g(e^{i \theta})$ as some function of $\theta$.

I've been experimenting with graphing the path of the roots as $\theta$ changes and the result looks like a smooth curve.  Moreover, the roots actually trace paths which sometimes meet up with the paths from other roots to form larger paths.  So it looks like the roots are evenly spaced points on one or more complex curves.

For instance, for $g(z) = .16z^3 + \frac{1}{2}z^2 + z$, the trace looks like (the black circle is the unit circle, for scale):

So I'm guessing there's some nice form for the paths the roots trace and their positions on these paths, but I'm not sure how to begin approaching this problem.

答:
Here's a contribution to the overall problem, too big to fit into a comment. Maybe this can inspire a real proof by someone else.

I think it'll be pretty easy to show that the paths are continuous, so long as you can define the path in a way that accurately "traces" one of the roots around. To this end, let $f:\mathbb{C}\to\mathbb{C}$ be a polynomial. Now fix $z_0\in\mathbb{C}$ and let $c=f(z_0)$. I claim that for every real $\epsilon>0$ there exists $\delta>0$ such that for every $c_1\in\mathbb{C}$, if $|c_1-c|<\delta$, then there exists $z_1\in\mathbb{C}$ with $|z_1-z_0|<\epsilon$ such that $f(z_1)=c_1$. In other words, if we have a solution for $f(z)=c$, then if $c_1$ is not too far away from $c$ then we can find a solution $f(z_1)=c_1$, where $z_1$ is as close as we like to $z$. If $z$ is a single root of $f-c$, then this proof is as easy as considering the inverse, which must be continuous. If $z$ is a multiple root, it's more difficult but I think still doable.

Assuming that my continuity argument is correct, we can say that there are well-defined paths, i.e. there are no jumps. We need to take care with multiple roots, making sure they don't stray onto each other's paths, but I think it's doable.

But each root has a continuous path, and there has to be some sort of parametrization that, with a little care, we can show is periodic. Defining $g:\mathbb{R}^2\to\mathbb{C}$ as $g(x,y)=f(x+yi)$, we can then use the continuity and (real) differentiability of the gradient of $g$ combined with information on how $e^{i\theta}$ changes to show that there's a smooth path.

Do I have anything here, or is it all a load of nonsense? Let me know! :)


问:
How to find the power series representation of $\frac{x-1}{x+2}$
The question is what is the power series representation of $\frac{x-1}{x+2}$. This was my initial solution.

$$\frac{x-1}{x+2} = (x-1)\left(\frac{1}{x+2}\right) = \frac{x-1}{2}\left(\frac{1}{1-(-\frac{x}{2})}\right) = \frac{x-1}{2} \sum_{n=0}^\infty (-1)^n\left(\frac{x}{2}\right)^n $$

Now the solution my textbook has is $$-\frac{1}{2} - \sum_{n=1}^\infty \frac{(-1)^n3x^n}{2^{n+1}}$$

The question is, how do we get that? I see if you take the first two terms of my answer you get $-\frac{1}{2}$ as a constant outside the series notation. What I then have is $$-\frac{1}{2} + (x-1)\sum_{n=2}^\infty(-1)^n\frac{x^n}{2^{n+1}}$$

How do I get the book's answer? I don't see where to go from here.

答:
Simple: they rewrote  the fraction as:
$$\frac{x-1}{x+2}=\frac{(x+2)-3}{x+2}=1-\frac{3}{x+2}=1-\frac32\,\frac1{1+\cfrac x2}$$
and used the expansion of $\:\dfrac1{1+u}$.


问:
proof of Invertible matrix
Let $U$ be a n by n matrix, satisfy $U^T=-U$

Prove that $U-I$ is invertible.

So, I have some hints, $\vec{v}^T\vec{v}$ for $\vec{v} \in Null(U-I)$

答:
If $v \in \text{Null}(U-I)$, then $Uv=v$. Then
$$v^\top v = v^\top (U v) = (U^\top v)^\top v = \cdots$$
Can you use the fact $U^\top = -U$ and finish from here?

Title: proof of Invertible matrix


问:
Turning points of parametric curve

Find the slope of the curve at $t=\frac{1}{4}\pi$.

$$\begin{cases}x=\sin t+\cos t \\ y=\frac{1}{2}\sin(2t)\end{cases}$$

$$\frac{dy}{dx}=\frac{\cos(2t)}{-\sin t+\cos t}$$

$$\left.\frac{dy}{dx}\right|_{\frac{1}{4}\pi}=\lim_{t\to \frac{1}{4}\pi}\frac{\cos(2t)}{-\sin t+\cos t}$$

Multiplying by the conjugate of the denominator won't help, so I applied L'Hôpitals Rule

$$\lim_{t\to \frac{1}{4}\pi}\frac{\cos(2t)}{-\sin t+\cos t}=\lim_{t\to \frac{1}{4}\pi}\frac{-2\sin(2t)}{-\cos t-\sin t}=\sqrt{2}$$

Is there another way to evaluate this limit?

答:
Let  X=1+3sint   and  Y=2-5cost

determine the turning points of this curve in the interval (0;2)

2.classify the turning points in 4.1 as either maximum or minimum

Title: Turning points of parametric curve


问:
calculate $\lim _{n\to \infty}\sum _{ k=1 }^{ n }{ \left| { e }^{ \frac { 2\pi ik }{ n } }-{ e }^{ \frac{ 2 \pi i(k-1) }{ n }} \right|}$
$\lim _{ n\to \infty  } \sum _{ k=1 }^{ n }{ \left| { e }^{ \frac { 2\pi ik }{ n }  }-{ e }^{ \frac { 2\pi i(k-1) }{ n }  } \right|  } $

We know that $e^{i\pi}=-1$ $\rightarrow$ $e^{2i\pi}=1$ $\rightarrow$ $e^{2i\pi k}=1$, $e^{2i\pi(k-1)}$= $\frac{e^{2i\pi k}}{e^{2i\pi}}=\frac{1}{e^{2i\pi }}=1$. Then

\begin{align}
\lim_{n\to \infty} \sum _{k=1}^{n} \left| e^{\frac{ 2\pi ik }{ n }}  -e^{ \frac { 2\pi i(k-1) }{ n }  } \, \, \, \right| &= \lim _{n\to \infty} \sum _{ k=1 }^n \left| (e^{ 2\pi ik })^{ 1/n }-(e^{ 2\pi i(k-1) })^{ 1/n } \right| \\
&=\lim _{n\to \infty} \sum _{ k=1 }^n \left| (1)^{1/n}-(1)^{1/n} \right| =0
\end{align}

I am not convinced by the result. Any suggestion?

Body:
Noting
$$\sum _{ k=1 }^{ n }{ \left| { e }^{ \frac { 2\pi ik }{ n }  }-{ e }^{ \frac { 2\pi i(k-1) }{ n }  } \right|}=\sum _{ k=1 }^{ n }\bigg|{ e }^{ \frac { 2\pi i(k-1) }{ n }}\bigg|{ \left| { e }^{ \frac { 2\pi i }{ n }  }-1 \right|}=\sum _{ k=1 }^{ n }\sqrt{2(1-\cos(\frac { 2\pi}{ n }))}=2n\sin(\frac {\pi}{ n }) $$
one has
$$ \lim_{n\to\infty}\sum _{ k=1 }^{ n }{ \left| { e }^{ \frac { 2\pi ik }{ n }  }-{ e }^{ \frac { 2\pi(k-1) }{ n }  } \right|}=\lim_{n\to\infty}2n\sin(\frac { \pi}{ n })=2\pi. $$


问:
Proof of the DKW inequality
My goal is to prove the following inequality, known as the Dvoretsky-Kiefer-Wolfowitz inequality (1956) :

Let $(X_i)_{i \geqslant}$ be iid random variables. Let $\displaystyle F_n(x)= \frac{1}{n}\sum _{i=1}^n 1_{X_i \leqslant x}$ and $F$ the distribution function of $X_1$. Then there exists a constant $C>0$ such that for every $\varepsilon >0$ : $$\mathbb{P} \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)| > \varepsilon \right) \leqslant  C e^{-2n\varepsilon ^2}$$

I did not find any proof on the web (only the article of DKW of 1956 but it is not understandable to me due to their notations). The only thing I found was the proof that :  $$\mathbb{E} \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)| \right) \leqslant  \frac{c}{\sqrt{n}}$$ in this paper :

https://www.math.ens.fr/enseignement/telecharger_fichier.php?fichier=474 (theorem 3.3)

which is named the DKW inequality.

I was not able to prove the DKW inquality from this result btu here is my try  :

By the Markov inequality and for every function :

$$\mathbb{P} \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)| > \varepsilon \right) \leqslant  \frac{\mathbb{E} \left( f \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)|\right) \right)}{f(\varepsilon)} $$. With $f(x)=e^{tx}$ and using the convexity of $f$ the Jensen inequality gives :
$$\mathbb{P} \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)| > \varepsilon \right) \leqslant  \frac{e^{ctn^{-1/2}}}{e^{t \varepsilon}} $$

But that does not give the correct result.

Question. Does anyone can help me with proving the DKW inequality with the estimate  $\mathbb{E} \left( \sup_{x \in \mathbb{R}} |F_n(x)-F(x)| \right) \leqslant  \frac{c}{\sqrt{n}}$ for start ? Or maybe just giving me a paper with the proof in modern language.

Thank you.

答:
I know this question is old, but just in case anyone else comes here looking for an answer, the following pdf might be helpful:

http://w3.impa.br/~rimfo/estatistica_a16/notas_alunos/shangjie.pdf

Edit: Seems like the link is dead. Here is the internet archive version of it https://web.archive.org/web/20210506145536/http://w3.impa.br/~rimfo/estatistica_a16/notas_alunos/shangjie.pdf

Title: Proof of the DKW inequality


答: If $v$ is a vector such that $(U-I)v=0$ then $Uv=Iv=v$, and taking the transpose $v^\mathsf tU^\mathsf t=-v^tU=v^t$. Multiplying by $v$ on the right we get $v^\mathsf tUv=-v^\mathsf tv=-\|v\|^2$. Since $Uv=v$ we get $v^\mathsf tv=-\|v\|^2$, so $\|v\|^2=-\|v\|^2$, which is only possible if $v=0$. Therefore $\text{null}(U-I)=\{0\}$, so $U-I$ is invertible.

Title: proof of Invertible matrix

Body:
Let $U$ be a n by n matrix, satisfy $U^T=-U$

Prove that $U-I$ is invertible.

So, I have some hints, $\vec{v}^T\vec{v}$ for $\vec{v} \in Null(U-I)$


问:
A problem of optimization
Determine the maximum of $f(x_1,x_2,x_3,\dots,x_n)=\displaystyle\prod_{i \ne j}|x_i-x_{j}|$ for $0\le x_1<x_2<x_3< \dots<x_n<1 $.

It seems that you can always translate $x_i$'s such that $x_n \to 1$.
At the same time one always maximizes the value of $f$ when stretching on the right $x_i$'s, ie when $x_1=0$
So we just need to consider $n-2$ values.
Using dumb calculations (derivatives...), we get that:

for $n=2$, $\max=1$

for $n=3$, $\max=\frac 1 4$

for $n=4$, $\max=\frac{\sqrt{5}}{125}$...

Is there a way to find it in general ?

答:
For now, I'm not convinced that there is a "nice" algebraic solution to this problem, but one can transform it into a convex program which can be solved efficiently. The objective is equal to $$f(x) = \prod_{i>j} (x_i-x_j)^2,$$ subject to the constraint $0 < x_1 < \ldots < x_n < 1$.
Now, let $y_i = x_{i+1} - x_i, i=1,\ldots,n-1$, then $x_{i}-x_{j} = \sum_{k=j}^i y_k$ for $j > i$, and the optimization problem can equivalently be reformulated as:
$$
\begin{split}
\max_y &\left\{f(y)=\prod_{i=1}^{n-1}\prod_{j=i+1}^{n-1}\sum_{k=i}^jy_k\right\} \\
&s.t.\\
&\mathbf{1}^\top y=1,\\
&y\succ 0.
\end{split}
$$

One can solve this by solving the equivalent convex program
$$\begin{split}
\max_y & \left\{ g(y) =\sum_{j>i}\log\left(\sum_{k=i}^j y_k\right)\right\}\\
&s.t.\\
&\mathbf{1}^\top y=1,\\
&y\succ 0,
\end{split}
$$
where the solution to the original problem is recovered from $\exp(2g(y^*))$, with $y^*$ the maximizer of the above program. Maybe we can get close to a solution by examining the Lagrangian
$$
L(y,\lambda) = \sum_{j>i}\log\left(\sum_{k=i}^j y_k\right) + \lambda(1 - \mathbf{1}^\top y),
$$
and finding $y^*$ s.t. $\nabla_y L(y,\lambda) = 0$ with $y\succ 0$.

Hope this is helpful, I will try to do something more later.

Title: A problem of optimization


问:
Find $n,m \geq 1$ s.t. $p(x) = 1 - (1 - x^n)^m$ satisfying $p(\frac{c}{2}) < \epsilon$ and $p(c) > 1 - \epsilon$
Having trouble showing this lemma and its corollary within Stone-Weierstrass. My instructor said this was easy to show, so he did not show it in class. But I cannot seem to do it.

Lemma: Let $\epsilon >0$ and $0 < c < 1$. There exists $n,m \geq 1$ s.t. $p(x) = 1 - (1 - x^n)^m$ satisfying $p(\frac{c}{2}) < \epsilon$ and $p(c) > 1 - \epsilon$.

Corollary: Let $p(x)$ be given as in the above lemma. Then $0 \leq p(x) < \epsilon$ where $x \in [0,\frac{c}{2}]$ and $p(x) \geq 1 - \epsilon$ where $x \in [c,1]$.

I feel like the lemma is more of a statement, and not a lemma. It seems like he is just giving us a function, $p(x)$, and telling us how it is defined. I looked back through my notes, and asked him, and he said that is all we need. So I've kind of ignored that, but I'm just not getting anywhere with the corollary. If I plug in $0$, I get $0$, the lower bound. So I'm assuming by plugging in $c/2$, I have to show the function has its maximum between $0$ and $\epsilon$ at $c/2$.

Similar for the next one, I have to show that at $c$ the function is equal to $1 - \epsilon$ and then I know it's maximum is $1$ from the definition in the lemma. I'm just not sure how to do it, or if my thoughts are on the right track.

答:
Corollary:

For the corollary notice that for all $x \in [0,1]$
$$
p'(x)=mnx^{n-1}(1-x^n)^{m-1} \geq 0.
$$
So $p$ is non-decreasing in $[0,1]$. Notice that $p(0)=0<p(\frac{c}{2})<\epsilon$. Hence $0 \leq p(x)<\epsilon$ for all $x \in [0,\frac{c}{2}]$. And notice that $p(c) \geq 1- \epsilon$. Hence $p(x) \geq 1- \epsilon$ for all $x \in [c,1]$.

Without using differantiation:

Suppose $x<y \in [0,1]$. Then $x^n<y^n$ and $-x^n>-y^n$. Hence $1-x^n>1-y^n$ and $(1-x^n)^m>(1-y^n)^m$. So $-(1-x^n)^m<-(1-y^n)^m$ and $1-(1-x^n)^m<1-(1-y^n)^m$. This implies that $p(x)<p(y)$ and $p$ is increasing.

Lemma:
This is my attempt on proving the Lemma where I used Bernoulli's inequality which is a standard result and with an easy proof. Hope it helps and if there is something wrong with the proof please let me know.

Edit: Bernoulli's inequality states that
$$
(1+x)^r \geq 1+rx
$$
for any integer $r \geq 0$ and for every real number $x > -1$. For a proof of Bernoulli's inequality take a look at Proof by induction of Bernoulli's inequality $ (1+x)^n \ge 1+nx$. It is a simple application of induction.

Notice that we can suppose $\epsilon<1$. Now, since $0<c<1$, we know that $\frac{1}{c} > 1$ and we can choose $k$ the smallest positive integer such that $k>\frac{1}{c}$. Then we have
$$
k-1 \leq \frac{1}{c} \implies k \leq \frac{1}{c}+1<\frac{2}{c}.
$$
Also notice that $-\frac{c^n}{2^n}> -1$ for any $n \in \mathbb{N}$. Taking $x=-\frac{c^n}{2^n}$ and $r=k^n$ we can apply Bernoulli's inequality
$$
\left(1+\left(-\frac{c^n}{2^n}\right) \right)^{k^n} \geq 1-k^n\frac{c^n}{2^n}=1-\left(k\frac{c}{2} \right)^n
$$
Then follows from $k<\frac{2}{c}$ that $\delta_0=(k\frac{c}{2}) < 1$ and
\begin{equation}
\left(1-\frac{c^n}{2^n} \right)^{k^n} \geq 1-{\delta_0}^n.
\end{equation}
Now let's use Bernoulli's inequality again using that $c^n > -1$ for any $n \in \mathbb{N}$. This time take $x=c^n$ and $r=k^n$ and apply the inequality
$$
(1-c^n)^{k^n} = \frac{1}{(kc)^n}(1-c^n)^{k^n}k^nc^n \leq \frac{1}{(kc)^n}(1-c^n)^{k^n}(1+k^nc^n)
$$
$$
(1-c^n)^{k^n} \leq \frac{1}{(kc)^n}(1-c^n)^{k^n}(1+c^n)^{k^n}=\frac{1}{(kc)^n}(1-c^{2n})^{k^n}<\frac{1}{(kc)^n}.
$$
First equality holds because we multiplied and divided by $k^nc^n$ and first equality holds because $k^nc^n<1+k^nc^n$. Then we just used Bernoulli's inequality on $1+k^nc^n$ and used the fact that $0<1-c^{2n}<1$.
Now using that $k>\frac{1}{c}$ we have $\delta_1=\frac{1}{kc}<1$. Then
\begin{equation}
(1-c^n)^{k^n}<{\delta_1}^n.
\end{equation}
Notice that ${\delta_0}^n \to 0$ and ${\delta_1}^n \to 0$ as $n \to \infty$ (because $0<\delta_0,\delta_1<1$). Hence, using the definition of limit, we can choose $n_0$ such that ${\delta_0}^{n_0}<\epsilon$ and ${\delta_1}^{n_0}<\epsilon$. From what we already proved we have
$$
\left(1-\frac{c^{n_0}}{2^{n_0}} \right)^{k^{n_0}} \geq 1-{\delta_0}^n>1-\epsilon
$$
$$
(1-c^{n_0})^{k^{n_0}} < {\delta_1}^n<\epsilon.
$$
By choosing $n=n_0$ and $m=k^{n_0}$ we have
$$
p \left(\frac{c}{2} \right)=1-\left(1-\frac{c^{n_0}}{2^{n_0}}\right)^{k^{n_0}}<1-(1-\epsilon)=\epsilon
$$
$$
p(c)=1-(1-c^{n_0})^{k^{n_0}}>1-\epsilon.
$$


问:
Integration in measure theory, modes of convergence
I have this problem on the integration topic in measure theory, I can't find the way to achieve the equality with the funcion evaluated in zero. I find it somehow related with the Dirac measure, but I can still not completely link it, the exercise is
Let $f:\mathbb{R}^2\rightarrow\mathbb{R}$ continuous and $g_n:\mathbb{R}^2\rightarrow\mathbb{R}$ such that $\int_{\lVert x \rVert\leq 1}g_nd\lambda=1$ and $g_n\rightarrow0$ uniformly at $0<c\leq \lVert x \rVert\leq 1$ for every $c>0$. Show that $\\ \displaystyle\lim_{n\rightarrow\infty}\int_{\lVert x \rVert\leq 1}fg_nd\lambda=f(0)$

答:
Hint:

Since $f$ is continuous on a compact set, $|f(x)| < M$ for some $M$, and all $\|x\| \le 1$.

if $\epsilon > 0$, there is a $\delta$ such that if $\|x\|< \delta$, then $|f(x) - f(0)| < \epsilon/2$, and there is an $n$ such that $|g_n(x)| < \epsilon/4M\pi$ when $\|x\| \ge \delta$.


问:
How many positive semidefinite submatrices can an indefinite matrix with a positive eigenvector/positive eigenvalue have?
Let $A\in\mathbb R^{n\times n}$ be a symmetric matrix such that it has $k<n$ non-negative eigenvalues and $n-k$ negative eigenvalues. I am interested in the following question: can all $k\times k$ principal submatrices of $A$ be positive semidefinite? If not, how many of them can be positive semidefinite?

I was experimenting with Matlab for the case $n=4$, $k=2$, and I couldn't find a way to make $A$ so that all $2\times 2$ matrices were positive semidefinite (somehow $A$ always would get more than two non-negative eigenvalues). Hence the question. I can't figure it out myself.

Edit: there are two cases I already understand: $k=1$ and $k=n-1$.

In the first case it is easy to find a matrix with one positive eigenvalue such that the diagonal is non-negative: say, $A=\begin{bmatrix}0&1&1\\1&0&1\\1&1&0\end{bmatrix}$ (the ones on the off-diagonals may be any positive numbers). For the second case, consider $-A^{-1} = \begin{bmatrix}1&-1&-1\\-1&1&-1\\-1&-1&1\end{bmatrix}/2$. But what if $n>3,1<k<n-1$?

Another edit: one user suggested to use a rectangular $(n\times m)$ (with $m<n$) matrix $X$ such that every set of $k$ rows of $X$ has full rank (like a Vandermonde matrix) and look at $A=cXX^* - I_n$ for some $c>0$ chosen such that $A$ has $k$ non-negative eigenvalues and $k\times k$ PD submatrices. Indeed, this method was successful. So the question is answered, technically, but there is more: the matrix always seems to have a negative eigenvalue with a positive vector.

This leads to the same question, modified by the assumption: suppose that the subspace $V$ spanned by the eigenvectors corresponding to positive eigenvalues contains a positive (entrywise $>0$) vector.

答:
Let $A$ have eigenvalues $\lambda_n \leq \cdots \leq \lambda_1$. By the min-max theorem, we have that

$$\lambda_k = \max_{\dim U = k} \min_{v \in U} \frac{v \cdot Av}{v \cdot v}.$$

For $I \subseteq \{1, \ldots, n\}$, let $\langle I \rangle \subseteq \mathbb{R}^n$ by the span of $\{e_i \mid i \in I\}$. Then for any $v \in \langle I \rangle$, we have that $v \cdot A v = v \cdot A_I v$, where $A_I$ is the principal $I$-submatrix of $A$. When $|I| = k$, then $\dim \langle I \rangle = k$ and hence by the min-max theorem we have
$$ \lambda_k \geq \min_{v \in \langle I \rangle} \frac{v \cdot A_I v}{v \cdot v} = \lambda^I_k, $$
where $\lambda^I_k$ denotes the smallest eigenvalue of $A_I$. Therefore, the smallest eigenvalues of any $k \times k$ principal submatrix are bounded above by $\lambda_k$.

By your assumption on $A$, $\lambda_k \geq 0$, so this doesn't say much about the definiteness of the $k \times k$ principal submatrices. However, you also have that $\lambda_{k + 1} < 0$, so every $(k + 1) \times (k + 1)$ principal submatrix is certainly not positive semidefinite. Perhaps you can do something more precise with the Cauchy interlacing theorem?


问:
The steps to calculate the derivative
$\frac{d}{d\mathbf{w}}Xsig(X^T\mathbf{w})=Xdiag(sig(X^T\mathbf{w})\odot (1-sig(X^Tw)))X^T$

I want to know the step of getting the above result, thank you.
The $sig$ is the element-wise sigmoid function. The convention is denominator layout.

答:
The derivative of the logistic function, $\,s={\rm sig}(y),\,$ considered as an ordinary (scalar) function is
$$\frac{ds}{dy} = (s-s^2) \quad\implies\quad ds = (s-s^2)\,dy$$
Applying the function element-wise to a vector argument $\;(y=X^Tw)\;$
yields vector results
$$\eqalign{
s &= {\rm sig}(y) \\
ds &= (s-s\odot s)\odot dy \\
}$$
The elementwise/Hadamard products can be replaced by multiplication with a diagonal matrix, i.e.
$$\eqalign{
S &= {\rm Diag}(s) \\
ds &= (S-S^2)\,dy \\
}$$
Let's apply the above to the function in the question and calculate its gradient.
$$\eqalign{
 f &= Xs \\
df &= X\,ds \\
   &= X(S-S^2)\,dy \\
   &= X(S-S^2)X^T\,dw \\
   &= XS(I-S)X^T\,dw \\
\frac{\partial f}{\partial w}
   &= XS(I-S)X^T \\
}$$
So the gradient expression in the question is wrong.

Title: The steps to calculate the derivative


问:
$A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A) \cup (A \cap B \cap C)$
I am using the fact that $X = (X - Y) \cup (X \cap Y)$

So far I've got:

$$A \cup B \cup C = (A - B) \cup (B - C) \cup (C - A) \cup (A\cap B)\cup(B\cap C)\cup(C\cap A)$$

This is almost done, except now I have to deal with $(A\cap B)\cup(B\cap C)\cup(C\cap A)$. How can I use this to get to $A\cap B \cap C$?

答:
You won't get $A\cap B\cap C$ in a natural way from this union.

I suggest instead to classify the elements of $A\cup B\cup C$ by the number of sets in $\{A,B,C\}$ to which it belongs, and to show that if it belongs to a single set, or to two of them, but not all, then it is already in $A\setminus B$, or in $B\setminus C$ or in $C\setminus A$.


问:
Proving hash function theorem
Let's say I have some set $X$ such that for any hash function $h$ and random permutation $\pi \in {1,2,..., n}$, we have $$h_\pi(X) = argmin_{x} \pi(x)$$
for $x \in X$.

Equivalently $h_\pi(X)$ is the min element in $X$ over $\pi$. I want to prove the following theorem $$P(h_\pi(X) = h_\pi(Y)) = \frac{|X \cap Y|}{|X \cup Y |}$$
Here, $P(h_\pi(X) = h_\pi(Y))$ is sampled from a uniform random $\pi : [n] \rightarrow [n]$.

Intuitively, I am restating this as the intersection over union of two sets is equal to the joint probability of the min valued element in X and Y equaling each other. But I have no idea why the second portion would ever be true if it's a random permutation. I'm not able to quite wrap my mind around this.

答:
We can show by a simple argument that $h_{\pi}(X)=h_{\pi}(Y)$ iff $h_{\pi}(X\cup Y)\in X\cap Y.$ This implies that
$$P(h_{\pi}(X)=h_{\pi}(Y))=\sum _{z\in X\cap Y}P(h_{\pi}(X\cup Y)=z),$$
but $$P(h_{\pi}(X)=x)=\frac{{\displaystyle {n}\choose {|X|}}(|X|-1)!\cdot (n-|X|)!}{n!}=\frac{1}{|X|},$$ this is because you choose where to send the set $X,$ you permute all but the smallest element(which goes to $x$) and you permute the rest in the complement of $X$ of size $|[n]\setminus X|=n-|X|.$ Notice that this construction does not depend on $x.$

If you replace the later equation in the former, you are done.

Title: Proving hash function theorem


问:
Examine the continuity and differentiability of $f(x)=| \cos x|$

Examine the continuity and differentiability of $f(x)=| \cos x|$

I got the answer to be everywhere continuous and not differentiable
 at $ x=(2n+1) \frac{\pi}{2}, n \in \mathbb Z $

(since modulus function is not differntiable at $\cos x = 0$ i.e. if $f(x)=|x-a|$ then it is not differentiable at $x=a$)

But I want to prove it mathematically  i.e.  proving $$\lim_{x\to c^+}f(x)=\lim_{x\to c^-}f(x)=f(c)$$
  and
  $$\lim_{x\to c^+}\frac{f(x)-f(c)}{x-c}=\lim_{x\to c^-}\frac{f(x)-f(c)}{x-c}$$

Thankyou

答:
Continuity follows because the compision of continuous functions is continuous.
Differentiability outside $\pi\mathbb Z+\frac\pi2$ follows because $|\cdot|$ is differentiable away from $0$ and again composition of differentaible functions is differentiable.
That $f$ is not differentiable at $(n+\frac12)\pi$, however, needs to be checked explicitly (for example $x\mapsto|\cos^2 x|$ would be differentiable in spite of the modulus).

For example, at $c=\frac\pi2$, you have $|\cos x|=\cos x$ for $0<x\le c$ and $|\cos x|=-\cos x$ for $c\le x<c+\frac\pi2$. Then
$$\begin{align}\lim_{x\to c^+}\frac{f(x)-f(c)}{x-c)}&=\lim_{x\to c^+}\frac{-\cos x-0}{x-c}=\sin c=1\\
\lim_{x\to c^-}\frac{f(x)-f(c)}{x-c)}&=\lim_{x\to c^-}\frac{\cos x-0}{x-c}=-\sin c=-1\end{align}$$


问:
Find the surface area of the sphere inside the cylinder
The given equations are of a sphere and cylinder respectively
$$x^2+y^2+z^2=400$$
$$x^2+y^2=256$$
Solving the sphere equation for $z$ yields
$$z=\sqrt{400-x^2-y^2}$$
Now to find $ds$ we take the partial derivative of both $x$ and $y$, then square them to get
$$f_x=\frac{x^2}{400-x^2-y^2}$$
$$f_y=\frac{y^2}{400-x^2-y^2}$$
Then take those and adding one, and getting a common denominator, we get
$$\frac{20}{\sqrt{400-x^2-y^2}}$$
Then converting the above fraction to polar coordinates and taking the iterated integral
$$20\int_0^{16}\int_0^{2\pi}\frac{r}{\sqrt{400-r^2}}\,d\theta\,dr$$
and I get $320\pi$ but I guess I'm incorrect because the website we are using says I'm wrong. So where did I go wrong?

Body:
The surface area inside the cylinder is

$$A=2\int_{S} \sqrt{1+ z_x^2+z_y^2}\> dx dy
= 2\int_{S} \frac{20}{\sqrt{20^2 -(x^2+y^2)}}\> dx dy \\
=2\int_0^{2\pi}\int_0^{16} \frac{20}{\sqrt{20^2 -r^2}}\> rdrd\theta
=640\pi
$$


问:
Expected value - deck of cards problem
Can you tell me if I have solved this correctly?

If we take a random card from a deck and then put the card back in the deck, and then shuffle it, and repeat this $x$ times, what is the expected number of cards that have been drawn at least one time?

So I know the probability of drawing a card is $1$ out of $52$, hence the probability of not drawing a card is $1 - \tfrac{1}{52}$.

If the process is repeated $x$ times then the probability is $\left( 1 - \tfrac{1}{52} \right)^x = \left( \tfrac{51}{52} \right)^x$.

The probability of drawing a card at least one time is $1 - \left(\tfrac{51}{52} \right)^x$.

The expected value is then $52 \left( 1 - \left( \tfrac{51}{52} \right)^x \right)$.

答:
Indeed, that is the way to go.  Indicator Random Variables, and the Linearity of Expectation.

There are 52 cards in the deck.  The probability of drawing a particular card (say card $i$) at least once is $(1-(51/52)^x)$.

So if $X_i$ is the indicator random variable for this event (ie: takes on value 1 when the event occurs, but 0 otherwise), then as this is a Bernoulli random variable, its expectation is the probability for the event: $$\mathsf E(X_i)=(1-(51/52)^x)$$

Which is the identical for all fifty two indicator random variables.

The count of cards that appear at least once is $\sum_{i=1}^{52}X_i$, so by the Linearity if Expectation:$$\mathsf E\left(\sum_{i-1}^{52}X_i\right)=52\,(1-(51/52)^x)$$.

Title: Expected value - deck of cards problem


问:
Munkres Example 14.2 - Dictionary Order
I am going over Munkres' Topology. In Example 14.2 he says:

Consider the set $\mathbb{R} \times \mathbb{R}$ in the dictionary order; we shall denote the general element of $\mathbb{R} \times \mathbb{R}$ by $x \times y$, to avoid difficulty with notation. The set $\mathbb{R} \times \mathbb{R}$ has neither a largest nor a smallest element, so the order topology on $\mathbb{R} \times \mathbb{R}$ has as basis the collection of all open intervals of the form $(a \times b, c \times d)$ for $a <c$, and for $a=c$ and $b<d$.

I have a few questions about this example. To clarify, is he saying if $(a,b)$ and $(c,d)$ are basis of $\mathbb{R}$ then we can denote $(a,b)=x$ and $(c,d)=y$ so we can show $(a,b) \times (c,d)$ a basis for $\mathbb{R} \times \mathbb{R}$ as $x \times y$?

Another point of confusion for me is that when I see $(a,b) \times(c,d)$, I think of Caretsian Products and I picture a rectangle in my mind. However, he talks about $(a \times b, c \times d)$. Of course in this sense, $a \times b$ and $c \times d$ will just be points and he draw lines between these two points. For instance if $a=1, b=2, c=3 \text{ and } d=4$, we get the following picture:

which is different from the usual Cartesian Product. Could you please explain if there is any connection between Cartesian Products and order topology on $\mathbb{R}^2$?

答:
I think I understand my misconceptions now so I will try to answer my own question. I will explain Example 14.4, the set $X=\{1,2\} \times \mathbb{N}$ and assess whether the order topology is the discrete topology or not which hopefully explains my misunderstanding.

First let's see what is the discrete topology on $X$:

$$\mathcal{T} = \{\phi,\{(1,1)\},\{(1,2)\},...,\{(2,1)\},\{(2,2)\},...,\{(1,1),(1,2)\},...,X\}$$

Now in order topology all open intervals $(a,b)$ and $[a_0,b)$ are basis elements. Here we make note that the element $(1,1)$ is the smallest element of $X$.

How does an open interval look like? For instance $((1,1),(1,3))$ is an open interval in $X$. Here $(1,1)$ is not itself an open interval but rather a point. This confusion arises because $(a,b)$ can be interpreted as both a point and an interval. Here we refer to $(a,b)$ as a point. This is why Munkres suggest using $a \times b$ instead. So $(1,1)$ can be written as $1 \times 1$. Here, $1 \times 1$ should not be interpreted as a number but rather it is the point $(1,1)$. What is the interval $((1,1),(1,3))$ equal to? The set $\{(1,2)\}$.

If order topology is the discrete topology, then all the one point sets would be open, that is a requirement of discrete topology.

Indeed, majority of one-point sets are open in the order topology. Any one-point set in can be written as $((x,n-1),(x,n+1))$ or in Munkres' words $(x \times n-1, x \times n+1)$, except $\{(1,1)\}$ and $\{(2,1)\}$. For instance the set $\{(2,10)\}$ = $(2\times 9, 2 \times 11)$.

The one-point set $\{(1,1)\} = [1 \times 1, 1 \times 2)$ since $(1,1)$ is the smallest element.

The set $\{(2,1)\}$ is not open. If it was, we could have written it as $(1 \times n, 2 \times 2)$ for some $n \in \mathbb{N}$. This implies $n$ is the greatest natural number which is a contradiction.

One might wonder what is the open interval $(1\times 1, 2 \times 2)$ equal to? Well

$$(1 \times 1, 2 \times 2) = \{(1,2),(1,3), ..., (2,1)\}$$

For this reason, the order topology on $X$ is not the discrete topology.

In conclusion:

There is no connection between Cartesian Product and the order topology in the sense I was thinking.

Munkres does not mean $(a,b)=x \text{ and } (c,d) = y$. He means $(a,b) = a \times b$ or $(x,y) = x \times y$. It was meant to distinguish between points and intervals. However, as Brian pointed out in comments one could write $(\langle a, b\rangle, \langle c,d \rangle )$ to avoid confusion. I personally think Munkres' notation is very confusing and I wish he had explained a bit more to clarify that.

$(a,b)$ is an element of $\mathbb{R}^2$ and $((a,b),(c,d)) = (a \times b, c \times d)$ is a basis element.

Title: Munkres Example 14.2 - Dictionary Order


问:
implicit differentiation
An equation is defined as $x+y+x^5-y^5=0$.

$a$. Show that the equation determines $y$ as a function of $x$ in a neighbourhood of the origin $(0,0)$.

$b$. Denote the function from $(a)$ by $y=\varphi(x)$. Find $\varphi^{(5)}(0)$ and $\varphi^{(2004)}(0)$.

For the first part,I simply needed to prove that the equation is $C^1$ in the neighbourhood of the origin and that the first derivative w.r.t.y does not vanish at that point. These are the sufficient conditions for the existence of an implicit function in the neighbourhood of the origin.

For the second part, I could do implicit differentiation (in a usual way) had it been for lower orders. But I need to learn the case for higher orders like the question asks. Please give me some hints.

答:
After one derivative, you have
$$
1 + y' + 5x^4 - 5y^4y' = 0.
$$
Now, to find higher derivatives, make sure that you think about the chain rule.  The implicit second derivative equation is
$$
y'' + 20x^3 - 20y^3(y')^2 - 5y^4y'' = 0.
$$
The third derivative equation:
$$
y''' + 60x^2 - 60y^2(y')^3 - 40y^3y'y'' - 20y^3y'y'' - 5y^4y''' = 0.
$$
Notice how several of the terms have a polynomial factor.  With each derivative, the degree decreases.  Can you see what happens after $5$ derivatives?  In the long run?</p>

Title: implicit differentiation