问:
$\mathcal{B}$ an algebra $\implies f^{-1}(\mathcal{B}) $ an algebra
Im trying to prove the following statement:

Let $f: \Omega \to E$.

$\mathcal{B}$ an algebra on $E$ $\implies f^{-1}(\mathcal{B}) $ an algebra on $\Omega$.

To show that $f^{-1}(\mathcal{B})$ is an algebra, following has to hold:

$\Omega \in f^{-1}(\mathcal{B})$

Stable under complementation

Stable under finite union

My question:

In the first point, since $\mathcal{B}$ is an algebra on $E$, it follows that $E \in \mathcal{B}$. But how do I even know if $f^{-1}(E)$ is defined? Don't we need the restriction that the function needs to be bijective in order to gurantee that $f^{-1}$ is possible?

EDIT (after suggestion by Henno Brandsma)

$\Omega \in f^{-1}(\mathcal{B})$ since $f^{-1}[E] = \Omega$.And $E \in \mathcal{B}$

Then regarding the complement: I take any $A \in \mathcal{B}$ so the complement would be $A^c = E \setminus A$. Note that $A^c \in \mathcal{B}$. So $f^{-1}[E\setminus A]= \Omega \setminus f^{-1}[A]$ and $f^{-1}[A]$ is defined since we know $f^{-1}[E] = \Omega$ and $A \subset E$. So we have the complement of $f^{-1}[A]$ as well.

This one follows from the fact that $f^{-1}[\bigcup_i A_i] = \bigcup_i f^{-1}[A_i]$.

答:
Use that

$f^{-1}[E]=\Omega$

$f^{-1}[E\setminus A] = \Omega\setminus f^{-1}[A]$ for all $A \subseteq E$,

$f^{-1}[\bigcup_i A_i] = \bigcup_i f^{-1}[A_i]$

Note that $f^{-1}[A]$ is always defined, it's just the set $$\{x \in \Omega\mid f(x) \in A\}$$


问:
Triangulation of the topologist's sine curve
Let $X$ be $\{(x,\sin{\frac{1}{x}})\mid x\in(0,1]\}$ together with the vertical set of accumulation points, the vertical line segment at $0$. This is closed subspace of $\mathbb{R}^2$. Is there a triangulation of this space? If there isn't, how would one go about proving this fact? I saw examples, for example in Hocking and Young, of defining a similar simplicial complex, but they omit discussing an explicit homeomorphism.

To be more concrete, let $Y$ be a complex constructed as a collection of $1$-simplices such that there is an "oscillation" on every interval from $1/(2\pi(n+1))$ to $1/(2\pi n)$, together with a vertical set of accumulation points, the vertical $1$-simplex at $0$. It's topology is made by declaring subsets $A\subset Y$ closed if $A \cap \sigma$ is closed in $\sigma$ for all simplices $\sigma$.

Someone tried to explain to me that in the above example, there can't be a homeomorphism, it went as follows. Vertical segment and the "body" of $Y$ are both closed, and they are complements, so they are both open. So $Y$ is open in this topology as union of two open sets. So we are trying to find a homeomorphism that will take an open set to a closed set, which I guess is a contradiction? I am a bit lost in this argument, I would appreciate if someone could verify this is fine. If it is fine, can we construct some complex that will work? Or how could we generalize this contradiction to "arbitrary" complexes? Thanks!

答: The topologist's sine curve $X$ is connected. Assume it has triangulation $K$. This means that the polytope (geometric carrier)  $\lvert K  \rvert$ is homeomorphic to $X$. But a polytope is connected iff it is pathwise connected. Thus $X$ should be pathwise connected, which is not true.

ContentLicense: CC BY-SA 4.0


问:
On using sine and cosine substitutions in integration
When you make a substitution of the form $x=asin\theta$ for sines and cosines, shouldn't you check if the values of x on which we're integrating allows for it? Otherwise, if x becomes greater than |x|, wouldn't there be no possible values of $\theta$?

This is how it seems to work in cases like $\sqrt{9-x^2}$, where, it's obvious that you're safe with substituting $x=3 sin\theta$ or $x=3
cos \theta$, since x can't go beyond |3|.

But I haven't heard of any explicit rule about this. Is there one, and if there isn't, why so?

答:
$I=\int_{0}^{2} \sqrt{4-t^2} dt $ is real and $t=2 \sin x$ works

but in $J=\int_{0}^{3} \sqrt{4-t^2} dt $ is imaginary here $t=2 \sin x$ will work again but you will get imaginary value.

Usually, we discard non-real answers.

Simililarly, in indefinite integration $K=\int \sqrt{4-t^2} dt$, we are supposed to avoid the substitution $t=3 \sin x$, because the integrand will become imaginary for $\sin x>2/3.$


问:
Integrating Chebyshev polynomial of the first kind
I'm trying to evaluate the integral of the Chebyshev polynomials of the first kind on the interval $-1 \leq x \leq 1 $ .
My idea is to use the closed form
$$T_n(x) = \frac{z_1^n + z_2^{-n} }{2}$$
where $z_1 = (x + \sqrt{x^2 - 1})$ and $z_2 = (x - \sqrt{x^2 - 1})$,
giving the following integral:
$$
\int _{-1}^{1}\!1/2\, \left( x+\sqrt {-1+{x}^{2}} \right) ^{n}+1/2\,
 \left( x-\sqrt {-1+{x}^{2}} \right) ^{n}{}{dx}
$$
I'm stuck at integrating $z_1$ and $z_2$. I tried integrating by parts $n$ times, but i'm looking for a general formula. My calculus is pretty rusty so i'm not sure if this is the way to go. Any tips?
Thanks a lot.

答:
Wikipedia has a nice article on the Chebychev polynomials: http://en.wikipedia.org/wiki/Chebyshev_polynomials.

In particular, there is this:

$\int T_n(x) dx = \frac{n T_{n+1}(x)}{n^2-1}-\frac{x T_n(x)}{n-1}$.


问:
minimal polynomial of $\beta \not\in F(\alpha)$ is same as it in $F$?
Give a field $F$, let $\alpha$ is an algebraic element of $F$, let $f(x), g(x)$ are minimal polynomials of $\beta$ over $F$, $\beta$ over $F(\alpha)$, respectively. If $\beta \not\in F(\alpha)$, can I say $f(x)=g(x)$?

I know it is true when $\deg(f(x))=2$:

because $g(x) \mid f(x)$, if $g(x) \neq f(x)$ then $\deg(g(x)) = 1$, so $g(x) = c+x, c \in F(\alpha)$, and $0 = g(\beta) = c+\beta$, so $\beta = -c \in F(\alpha)$, the contradiction.

but for any degree of $f(x)$, is that true? and how to prove that?

答:
In general the minimal polynomial of an algebraic $\beta$ over some field $F$ can change if you adjoin an algebraic $\alpha$ to $F$.

For a simple example, take $\alpha=\sqrt2,\beta=\sqrt[4]2$ over $F=\Bbb Q$.

For a more general load of examples, if the extension $F(\beta)/F$ has any intermediate field, then the minimal polynomial of $\beta$ over that intermediate field will have smaller degree than it does over $F$.

For any natural $n$, there is a polynomial over $\Bbb Q$ of degree $n$ whose splitting field has degree $n!$. If $n\geq3$, then setting $\beta$ to be one root and $\alpha$ to be another, we get that the minimal polynomial of $\beta$ over $\Bbb Q$ has degree $n$ but over $\Bbb Q(\alpha)$ the minimal polynomial of $\beta$ has degree $n-1$. So you can't tell just from the degree, if the degree is greater than $2$, whether the minimal polynomial of $\beta$ will change.

For examples where the minimal polynomial of $\beta$ doesn't change as you extend $F$, you want $F(\beta)$ to be the splitting field of the minimal polynomial of $\beta$. The classic examples of this are the roots of unity over $\Bbb Q$, whose minimal polynomials are the cyclotomic polynomials (the irreducible factors of $x^m-1$).


问:
Spectral Radius of element wise absolute function of a Matrix
Suppose we have a symmetric matrix $A$ with diagonal elements that are all $0$. Is it necessarily true that $\rho(|A|) \geq \rho(A)$, where $\rho(\cdot)$ is the spectral radius function? Using Gershgorin Circle Theorem, one can only conclude that both $\rho(A)$ and $\rho(|A|)$ lie in the interval $(-\max_i \sum_{j \neq i}a_{ij}, \max_i \sum_{j \neq i}a_{ij})$, but that's where I am stuck. Can anyone help me? Specifically, I am interested to know if there's any truth to the following suppositions:

$\rho(|A|) < 1 \implies \rho(A) < 1$

$\rho(A) < 1 \iff \rho(|A|) < 1$

答:
If we equip the space $ \mathbb C^n$ with the euclidian norm $|| \cdot ||_2 $ and define for a matrix $T \in \mathbb C^{n \times n}$ the operator norm by

$$ ||T||= \max\{ ||Tx||_2: ||x||_2=1\},$$

then we have for a symmetric matrix $A$, that

$$\rho(A)=||A||.$$

Now let $A$ be a symmetric matrix. $|A|$ is defined by $|A|=(A^*A)^{1/2}.$ Hence $|A|$ is symmetric.

We get:

$$\rho(|A|)^2=\rho(|A|^2)=\rho(A^*A)=||A^*A||=||A||^2,$$

thus

$$\rho(|A|)=||A||= \rho(A).$$

Remark: this result holds, more general,  for symmetic operators on Hilbert spaces.


问:
Prove $\mathbb{R}^2$ is regular
Prove $\mathbb{R}^2$ is regular. I got stuck on this proof even though the answer was almost given to me Infimum problem lemma to prove $\mathbb{R}^2$ is regular.

Let $p\in \mathbb{R}^2$, $p \notin A$, where $A$ is closed. Then there is some $r>0$ with $B_r(p) \cap A =\varnothing.$ Now I know I need to find an open set containing $A$ disjoint from $B_r(p)$, and this was my issue. I just guessed to take for each $a \in A$, $U_a=\text{inf}\{d(a,p)|a \in A\}$, the infimum of this set. Then would $\cup_{a \in A}U_a$ be an open set containing $A$ disjoint from $B_r(p)$? Now I realize my answer does not make sense without defining the open set containing $A$ dependent on $r$, any hints?

答:
If $p \notin A$ and $A$ is closed, then note that $A^\complement$ is open and $p$ is in it, so by definition there is some $r>0$ such that $B(p,r) \subseteq A^\complement$.

Now $U = B(p, \frac{r}{2})$ is an open neighbourhood of $p$ and $V = \bigcup \{B(a, \frac{r}{2})\mid a \in A\}$ is an open neighbourhood of $A$ and $U \cap V = \emptyset$: if $q \in U \cap V$ then $q \in B(p, \frac{r}{2})$ and for some $a_0 \in A$, $q \in B(a_0, \frac{r}{2})$. But then $d(p, a_0) \le d(p,q) + d(q, a_0) < \frac{r}{2} + \frac{r}{2}= r$ so that $a_0 \in B(p,r)$, contradicting $B(p,r) \subseteq A^\complement$.

To show normality is similar.

Title: Prove $\mathbb{R}^2$ is regular


问:
Find the expectation of lottery game
I came across this problem from a probability practice book. Could someone give me a hint?

Suppose you have N balls and M of them are red(others aren't red). You keep picking one ball out and NOT putting it back until you get one red ball. Find the expectation of a number of balls you need to pick out.

My approach is to use recursion. Let $X_k$ denote the distribution of number of balls I need to pick to get a red ball with k balls in the pool. Then,

$E(X_k)=\frac{M}{k} + \frac{k-M}{k}(1+E(X_{k-1}))$ , with $E(X_M) = 1$

as with M ball left in the pool, it should be immediate to pick a red ball. But then I end up an equation that I couldn't solve.

$E(X_N) = 1+\frac{N-M}{N}(1+\frac{N-1-M}{N-1}(1+...(1+\frac{1}{M+1}(1+1))))$

can anyone give me a hint or guide me please?

答:
Let $\tau$ be the number of balls drawn until the first red ball is drawn. Then for $1\leqslant n\leqslant N-M+1$ we have
$$
\mathbb P(\tau = n) = \frac M{N-(n-1)}\prod_{i=1}^{n-1}\frac{N-M-(i-1)}{N-(i-1)}
$$
So the expected number of balls drawn is
$$
\mathbb E[\tau] = \sum_{n=1}^{M-n+1} n\cdot\mathbb P(\tau = n) = \sum_{n=1}^{N-M+1}\frac M{N-(n-1)}\prod_{i=1}^{n-1}\frac{N-M-(i-1)}{N-(i-1)}.
$$
It turns out this expression has the closed form
$$
1 + \frac{N}{M+1},
$$
as explained in this answer: Expected Value Of Number of Removals From Urn

Title: Find the expectation of lottery game


问:
Is range $(T- \lambda I )$ is invariant under $T$?
In order to prove following theorem

Suppose $V$ is a finite-dimensional complex vector space and $T \in \mathbb L (V)$. Then $T$ has an upper-triangular matrix with respect to some basis of $V$.

my textbook states that range $(T- \lambda I )$ is invariant under $T$, for an eigenvalue $\lambda$.

It gives following proof, but this fact disagrees with the counter example I give below. Can someone point out where is the flaw in my understanding?

Suppose $u \in U=Range(T-\lambda I)$. Then
$Tu=(T-\lambda I)u+ \lambda u$ . Obviously first component $\in U$ (because U equals the range of $T-\lambda I$) and second component $\in U$.
Thus the equation above shows that $Tu \in  U$. Hence U is invariant under T, as claimed.

My counter example :

Consider $T$ as a projection of $R^2$ on $x$-axis. $T(x,y)=(x,0)$. For any vector parallel to $x$-axis, i.e. of the form $(x,0)$,  $T(x,0)=(x,0)$. So $\lambda = 1$ is an eigenvalue of $T$, and the corresponding eigen vectors are in $x$-axis.

So range of $U=Range(T-\lambda I)$ are all vectors in $R^2$ except the $x$-axis. But for any vector in $u\in Range(T-\lambda I),Tu$ is of the form $(x,0)$, and in $x$-axis. So  $Tu \not \in Range(T-\lambda I)$. So $U=Range(T-\lambda I)$ is not invariant under $T$.

EDIT:

Could you please also verify if following are correct, for my example?

Range $T$ = $x$-axis

Null $T$ = $y$-axis

Range $(T-\lambda I)$ = $y$-axis

Null $(T-\lambda I)$ = $x$-axis

If this is true, then Range $(T-\lambda I)$ will be invariant under $T$ as $T(0,y)=(0,0)\in Range (T-\lambda I)$

答:
Yes, $\text{range}(T-\lambda I)$ is invariant under $T$. Here's a quick proof, assuming we're in a finite-dimensional vector space $V$ and $T:V\to V$ is a linear map.

Suppose $v\in \text{range}(T-\lambda I)$. Then, $v = (T-\lambda I) w$ for some $w\in V$. What is $Tv$?

$$Tv = T(T-\lambda I)w = T^2w - \lambda Tw = (T-\lambda I)(Tw) = (T-\lambda I)w'$$
where $w' = Tw$. Clearly, $(T-\lambda I)w' \in \text{range}(T-\lambda I)$. So, $Tv \in \text{range}(T-\lambda I)$. This works for arbitrary $v\in \text{range}(T-\lambda I)$, so $\text{range}(T-\lambda I)$ is invariant under $T$.

In other words, we have shown that
$$T (\text{range}(T-\lambda I)) \subseteq \text{range}(T-\lambda I)$$
which is exactly how one should proceed to prove $T$-invariance of a subspace.

Some words about your particular counterexample: You've correctly identified $\lambda = 1$. Let's find $\text{range}(T-\lambda I)$ for you. Consider some $(x,y)\in\Bbb R^2$.
$$(T-\lambda I)(x,y) = T(x,y) - (x,y) = (x,0) - (x,y) = (0,-y)$$ i.e. the range consists of vectors on the $Y$ axis .

You also want to find $\ker(T-\lambda I)$, so let's see how that works. If $(x,y) \in \ker(T-\lambda I)$, then $$(T-\lambda I)(x,y) = (0,0) \implies (x,0) - (x,y) = (0,0) \implies y = 0$$
i.e. precisely those vectors which are on the $X$-axis.

I leave it to you to find $\text{range}\ T$ and $\ker T$.


问:
Understanding this Poisson Queueing Process
Consider $N$ busses, each which breaks down independently at a rate of $\mu$.  Once a bus breaks down it is sent to a repair shop which can only repair one bus at a time and takes an exponentially distributed amount of time with parameter $\lambda$ to repair it.

I'm trying to find the equilibrium distribution of the number of busses in service.

Could some one explain to me how to set this up?  Am I supposed to do a Q matrix?  Is $\mu$ intended to be determinate, so that the first time around all buses break down at the same time, and then it takes an exponentially distributed amount of time with parameter $\lambda$ for the first bus to exit the repair shop?  Then that would mean it would take twice the random variable for the next one to exit, and so on, but then as soon as one exists it comes back in $\mu$ time.  Like I said I'm just lost as to how to set this up.

Thanks

答:
If we write $N$ for the number of buses in operation, the system you describe is an M/M/$N$/$N$ queue. State $0$ represents the situation where all buses are broken and $N$ when all are working. The queue is finite capacity ($N$ can take values in $\{0, ..., N\}$), arrivals happen when a bus is repaired at rate $\lambda$ and when there are $c$ buses in operation the buses break down at rate $c\mu$. Note repairs can only happen when there is at least one broken bus so there is no $\lambda$ transition from state $N$.

The system has a $Q$ matrix
$$
Q=\begin{pmatrix}
-\lambda & \lambda \\
\mu & -(\mu+\lambda) & \lambda \\
&2\mu & -(2\mu+\lambda) & \lambda \\
&&3\mu & -(3\mu+\lambda) & \lambda \\
&&&&\ddots\\
&&&&(N-1)\mu & -((N-1)\mu+\lambda) & \lambda \\
&&&&&N\mu & -(N\mu) \\
\end{pmatrix}
$$

and therefore stationary distribution can be found by solving $\pi Q = 0$ which gives

$$
\pi_k = \frac{(\lambda/\mu)^k}{k!} \left[\sum_{k=0}^N \frac{\lambda^k}{\mu^k k!} \right]^{-1}.
$$

ContentLicense: CC BY-SA 3.0


问:
Using Groebner Basis to eliminte variables but end with empty set.
I want to infer the relationship between x and y (which is x == y) as the code (mathematica) below.
However l2 gives an empty set {} when I eliminate A, B.

I wonder what's the theorem beind it?

It is because situation A==B==0 ?

Is that possible to add an assumption of A!=0 && B !=0 when computating Groebner Basis?

```<code>l2 = {
   x A - y B,
   A - B
   };
l3 = {
   4 x - 4 y,
   A - B
   };
GroebnerBasis[l2, {}, {A, B}]
GroebnerBasis[l3, {}, {A, B}]
</code>```

Got answer

```<code>{}
{x - y}
</code>```

答: The assumptions $A \neq 0$ and $B \neq 0$ can taken into account by adding variables Ainv, Binv for the inverses of A and B, and adding the polynomials A*Ainv - 1, B*Binv - 1 to the list of generators. Eliminating A, B, Ainv, Binv will then yield {x - y}.


问:
A best approximation $v ∈ V$ of $x$ exists, then show that $v$ is unique.
I have a question regarding functional analysis:

Assume that $X$ is a strictly convex normed linear space and that $V ⊂ X$ is a proper
linear subspace. In addition, assume that for some element $x ∈ X$ a best approximation $v ∈ V$ of $x$ exists. Show that $v$ is unique.

I tried the following:

Suppose $v,v' \in V$ are best approximations of $x \in X$. Then,

$||x-v|| = ||x-v'||$ and the fact that $||x-v'||^2 =||x-v||^2+||v-v'||^2$ we have that $||v-v'|| = 0$. That is, if a best approximation $v \in V$ of $x$ exists then its unique.

Would this be a good approach? I have the feeling that I am missing things. Any help would be grateful. Thanks in advance.

I have read the following definition:

For each $x ∈ X$ there exists precisely one
best approximation in $V$ , namely there is a unique element $v ∈ V$ such that

$||x − v|| = d(x, V ) = inf{{||x − z|| : z ∈ V }}$.
I am not sure how to use this definition.

答:
Suppose $\|x-v\|=\|x-v'\|$ with $v,v'(v\neq v')\in X$. Since $\frac {v+v'} 2 \in X$ we get  $\|x-v\|=\|x-v'\| \leq \|x-\frac {v+v'} 2\|$. This gives $\|x-v\|+\|x-v'\|=\|(x-v)+(x-v')\|$. This implies that $x-v=c(x-v')$ for some scaler $c$. [See link below for definition of strict convexity].

But then $x \in X$ in which case we must have $v=v'=x$.

https://en.wikipedia.org/wiki/Strictly_convex_space


问:
Compute $\sum\limits_{a=1}^{\infty} \sum\limits_{b=1}^{\infty} \sum\limits_{c=1}^{\infty}\frac{ab(3a+c)}{4^{a+b+c}((a+b)(b+c)(a+c)}$
Compute the following sum:

$$
\sum_{a=1}^{\infty} \sum_{b=1}^{\infty} \sum_{c=1}^{\infty}\frac{ab(3a+c)}{4^{a+b+c}((a+b)(b+c)(a+c)}\
$$
I have no head or tail of how to even start this since the summation is interlinked.

答:
The basic idea is that, the final value of the sum doesn't depend on the dummy indices, i.e. whether you choose $(a,b,c)$, $(x,y,z)$ or some other triplet - it simply does not matter. Take advantage of this, and swap the indices $(a,b,c)$ around. How many permutations of these $3$ exist? Exactly $3! = 6$ permutations. I leave it to you to write them down. Now that you know that these $6$ different ways of writing the sum mean exactly the same thing - we're good to go. Denote the sum by $S$, and add all these (six) different representations of the same sum together. Get a nice expression for $6S$, and thus find $S$. See the magic unfold!

$$6S = \sum_{a = 1}^{\infty} \sum_{b = 1}^{\infty} \sum_{c = 1}^{\infty} \frac{ab(3a+c) + ac(3a+b) + bc(3b+a) + ba(3b+c) + ca(3c+b) + cb(3c+a)}{4^{a+b+c} (a+b)(b+c)(c+a)}$$
$$6S = \sum_{a = 1}^{\infty} \sum_{b = 1}^{\infty} \sum_{c = 1}^{\infty} \frac{3a^2b+3a^2c+3b^2c+3b^2a+3c^2a+3c^2b+6abc}{4^{a+b+c} (a+b)(b+c)(c+a)}$$
$$6S = \sum_{a = 1}^{\infty} \sum_{b = 1}^{\infty} \sum_{c = 1}^{\infty} \frac{3(a+b)(b+c)(c+a)}{4^{a+b+c} (a+b)(b+c)(c+a)}$$
$$S = \frac12\sum_{a = 1}^{\infty} \sum_{b = 1}^{\infty} \sum_{c = 1}^{\infty} \frac1{4^{a+b+c}} = \frac12\left(\sum_{a=1}^{\infty}\frac1{4^a}\right)^3 = \frac12\left(\frac13\right)^3 = \boxed{\frac1{54}}$$

If you want to practice this trick that I just mentioned, try to compute the following sum in a similar fashion (it has definitely been asked on this site before):
$$\sum_{m=1}^\infty\sum_{n=1}^\infty\dfrac{m^2n}{3^m(n3^m+m3^n)} = \frac{9}{32}$$


问:
Counting squares in a part of a graph. What is the correct answer?

Consider the following set of points in the $x - y$ plane:
$$
A = \{(a,\ b)\ |\ a,\  b\in \mathbb{Z}, \ 1\leqslant a\leqslant9\quad \text{and} \quad 1\leqslant b\leqslant 5\}.
$$
Find the number of squares whose vertices are points in $A$.

I reached an answer but don't know if it's right or not. (The source doesn't give the answer)

This reflects the essence of the approach.

First, we draw the blue line and choose any $2$ points on it and that will trace a square. The picture depicts $2$ cases. (The squares on the blue line)

Continuing this and advancing rightwards with every line before we reach the final yellow line, where one choice of points is absurd, because that square should go outside the figure itself. So, we have $6$ lines $5$ points long with one choice of points absurd so we need to exclude it.

After the $6\cdot\binom{5}{2} - 1$ squares we have, we only have to count squares in the last $3$ columns of points. Working on with the exact same reason and we have the lines in green, again with one choice of points absurd. So, there are $4\cdot\binom{3}{2}-1$ squares, totaling $$6\cdot\binom{5}{2} + 4\cdot\binom{3}{2} - 2\ \text{squares} = 70\ \text{squares}$$ but I doubt the number is too small.

What is the correct answer? How can it be reached? What will be the answer for the case when $0\leqslant a\leqslant9\ \text{and} \ 0\leqslant b\leqslant 5$? Thanks!

答:
Consiser which points can be as the lower left corner of those squares then:
Squares with
Size 0:$9×5=45$
Size1: $8×4=32$

Size 2: $7×3=21$

Size 3: $6×2=12$

Size 4: $5×1=5$


问:
Equality of Sets
I have three sets say A,B,C and a procedure only to check if a set S is nonempty ( I cannot negate the answer of the procedure to say that the set S is empty). Now using this procedure, how can I check if the three sets are equal i.e. I want a formula which will denote a nonempty-set exactly when the three sets are equal.

Thanks in advance !!

答:
Incomplete: $$X=(A\setminus B)\cup (B\setminus A)\cup (A\setminus C)\cup (C\setminus A)\cup (B\setminus C)\cup (C\setminus B)$$

This is empty if $A=B=C$, and nonempty otherwise.  Unfortunately, you want the opposite.

After a bit of thought, I'm no closer to an answer.  I think the $A,B,C$ is somewhat misleading in this question.  The real problem is this:

Given set $X\subseteq U$, for some universe $U$, and some function $S:\mathcal{P}(U)\rightarrow \{0,1\}$ where $S(X)=\begin{cases} 1 & X=\emptyset\\ 0 & \textrm{ otherwise}\end{cases}$, how can we find set $Y\subseteq U$ such that $S(Y)=1-S(X)$, using only certain specified binary set theoretic operations like $\cup, \cap$.

Title: Equality of Sets


问:
How to differentiate function related to bloom filters?
I am trying to understand a scribe note on choosing the right number of hash functions $k$ for a bloomfilter of size $n$ and $m$ elements. The following is stated:

Suppose we are given the ratio $\frac{m}{n}$ and want to optimize the number $k$. If $$g=\ln(f)=k\ln(1-e^{-kn/m})$$ and we let $p=e^{-kn/m}$. Then the derivative of $g$ is: $$\frac{dg}{dk}=\ln(1-p)+\frac{kn}{m}\cdot\frac{p}{1-p}$$
This confuses me because when I try to differentiate $g$ I get the following: $$\begin{equation} \frac{dg}{dk}=\ln(1-p)+\frac{1}{1-e^{-km/n}} \cdot \frac{e^{-km/n} \cdot m-kn}{m^2} \end{equation}$$

Link to equation (on page 2): http://people.math.gatech.edu/~randall/AlgsF09/bloomfilters.pdf

答:
This is because you also have to differentiate $p$ as it depends on $k$. It goes like this: first note
$$ \frac{d}{dk} p = \frac d{dk} e^{-kn/m} =-\frac{n}{m} e^{-kn/m} =-\frac{n}{m}p$$
Then applying product rule and chain rule,
\begin{align} \frac{dg}{dk} = \frac{d}{dk}(k(\ln(1-p))
&=\ln(1-p) + k\frac{d}{dk}(\ln (1-p))\\
&=\ln(1-p) + k\frac{\frac{d}{dk}(1-p)}{1-p}\\
&=\ln(1-p) + k\frac{0-\frac{dp}{dk}}{1-p}\\
&=\ln(1-p) + k \frac{-\left(-\frac nmp\right)}{1-p}\\
&=\ln(1-p)+\frac{kn}m\cdot\frac{p}{1-p}
\end{align}


问:
Unique solutions for $\frac{A^2}{a}+\frac{B^2}{b}+\frac{C^2}{c}=1,\quad\text{and}\quad a+b+c=1.$

Let $A,B,C$ be strictly positive real numbers satisfying $A+B+C=1$ and let $a, b, c $ be real variables. Suppose $a, b, c$ satisfy the following system of equations:

$$\frac{A^2}{a}+\frac{B^2}{b}+\frac{C^2}{c}=1,\quad\text{and}\quad a+b+c=1.$$

It is clear that  $a=A$, $b=B$ and $c=C$ is one solution to the system. Can I conclude that the solution is unique and there exists no other solutions?

答: The solution is unique only if $a,b,c > 0$. This is because by Titu's lemma: $1 = \dfrac{A^2}{a}+\dfrac{B^2}{b}+\dfrac{C^2}{c} \ge \dfrac{(A+B+C)^2}{a+b+c}= \dfrac{1^2}{1} = 1$, and you have equality which means the $=$ must hold, and this occurs when $A = ak, B = bk, C = ck \implies k =1 \implies a = A, b = B, c = C$ as claimed. For if they are not required to be positive then there is another solution, namely: $a = \dfrac{A^2-B^2}{1-C^2}, b = \dfrac{B^2-A^2}{1-C^2},c = 1$.


问:
Disproving uniform convergence
Given a sequence of functions $f_n$ which is known to be pointwise convergent how would you go about showing that is not uniform convergent?

The particular example I'm working with is $f_n (x)=\frac {nx} {x^2+n^2}$ and I've tried using Theorem 7.9 from Rudin (uniform convergence $\iff M_n=(\sup |f_n(x)-f(x)|) \rightarrow 0$ as $n\rightarrow \infty$) but using that I found $M_n$ to be $\frac {\sqrt n} {1+n}$ by maximising $f_n$ but this gives the wrong result.

edit:
$f:\mathbb R \rightarrow \mathbb R $, sorry about that

答:
There exist a criterion, in some books is an exercise:

Let $(f_n)$ a sequence of real valued functions on $D$. If there exist $(x_n)$ and $(y_n)$ sequences in $D$, such that
$$|x_n-y_n|\to 0$$
but
$$|f_n(x_n)-f_n(y_n)|\not \to 0$$
then, the sequence $(f_n)$ do not converges uniformly on $D$.

In your particular case, take
$$x_n=n\quad \text{ and }\quad y_n=n+\frac{1}{n}.$$

Title: Disproving uniform convergence


问:
area of intersecting part of triangles
Let ABCD be a rectangle and AC one of its diagonals.Length of AD is 4m and of AB is 1 m.A line is drawn from point D towards the midpoint of BC which we will label E.Let DE intersect AC at F.How do we figure out the area of the triangle EFC?Any hint or link to previous solutions will be appreciated.</p>

答:
Hint You can easily show that $$A\left( \widehat { ABE }  \right) =A\left( \widehat { AEC }  \right) =\frac { 1 }{ 4 } A\left( ABCD \right) $$

because $E$ is midpoint. The most important part is to see $$AD=2EC\quad and\quad AD//EC$$

and therefore $$AF=2FC\quad and\quad A\left( \widehat { AEF }  \right) =2A\left( \widehat { FEC }  \right) $$

Title: area of intersecting part of triangles


问:
ODE with $\alpha\in \mathbb{C}$
What about the classical methods for solve ODE's when appear complex coefficients? How can we deal with the following ODE:

$$\ddot x(t) - \alpha x(t)=0,$$

where $\alpha\in \mathbb{C}\setminus \{0\}$ and $x:\mathbb{R}\to \mathbb{C}$ ?.

答:
Write

$$x(t)=y(t)+i z(t) \ \ \text{and} \ \ \alpha=a+ib \tag{1}$$

where $x$ and $y$ are real-valued functions.

Plug (1) into your initial ODE ; separate real and imaginary parts, giving:

$$\begin{cases}\ddot y(t) = a y(t) - b z(t)\\
\ddot z(t) = b y(t) + a z(t)\end{cases}$$

Then follow the classical procedure (bringing back to a first degree system) as described for example here.

Title: ODE with $\alpha\in \mathbb{C}$


答:
$$g=k\ln(1-e^{-kn/m})$$ and

$$\frac{dg}{dk}=\ln(1-e^{-kn/m})+k\frac{\dfrac nme^{-kn/m}}{1-e^{-kn/m}}=\ln(1-p)+\frac{kn}m\frac{p}{1-p}.$$

I don't see any problem.

You can also work this out as follows:

$$\frac{dp}{dk}=-\frac nm p$$

and

$$\frac{d(k\log(1-p)}{dk}=\log(1-p)-k\frac{\dfrac{dp}{dk}}{1-p}
\\=\log(1-p)+\frac{kn}m\frac{p}{1-p}.$$

Title: How to differentiate function related to bloom filters?

Body:
I am trying to understand a scribe note on choosing the right number of hash functions $k$ for a bloomfilter of size $n$ and $m$ elements. The following is stated:

Suppose we are given the ratio $\frac{m}{n}$ and want to optimize the number $k$. If $$g=\ln(f)=k\ln(1-e^{-kn/m})$$ and we let $p=e^{-kn/m}$. Then the derivative of $g$ is: $$\frac{dg}{dk}=\ln(1-p)+\frac{kn}{m}\cdot\frac{p}{1-p}$$
This confuses me because when I try to differentiate $g$ I get the following: $$\begin{equation} \frac{dg}{dk}=\ln(1-p)+\frac{1}{1-e^{-km/n}} \cdot \frac{e^{-km/n} \cdot m-kn}{m^2} \end{equation}$$

Link to equation (on page 2): http://people.math.gatech.edu/~randall/AlgsF09/bloomfilters.pdf


问:
How to determine the smoothness and strong convex factor of a convex function?
Given a function $f:\mathbb{R^n}\rightarrow \mathbb{R}$ that is differentiable. We say $f$ is $\beta$-smooth if
$$\|\nabla f(x)-\nabla f(y)\| \leq \beta\|x-y\|$$
for all $x,y \in \mathbb{R}^n$.

We say f is $\alpha$-strongly convex ($\alpha >0$) if for all $x\in \mathbb{R}^n$, $$f(x)-f(y) \leq \nabla f(x)^\top(x-y)-\frac{\alpha}{2}\|x-y\|^2$$

My Question: is there any general or principled way to determine the value of $\alpha$ and $\beta$ ? Either analytic or numerical way would be appreciated!

For example (source here), a quadratic function $f(x) = x^TAx + b^Tx + c$ has $\alpha = \sigma_{\min}(2A)$ and $\beta = \sigma_{\max}(2A)$ where $\sigma_i$ is the $i$-th eigenvalue.

Thanks in advance!

答:
In general, these are computationally difficult problems. For example, "merely" deciding convexity of a multivariate polynomial of degree 4 (or higher even degree) is strongly NP-hard, i.e. unless P=NP, there is no polynomial time algorithm or pseudo-polynomial time algorithm for this problem. Also deciding strict convexity and strong convexity of polynomials of even degree of four or higher is NP-hard. These results are recently proved in https://arxiv.org/pdf/1012.1908.pdf

On the other hand, many convex functions that we encounter in practice have special structures, e.g., formed from simpler convex functions that we know their smoothness or convexity properties. Then, there is more hope to figure out specialized methods for your questions.


问:
What class of topological spaces is this?
It is well-known but apparently I have forgotten the answer to the below question. Which topological spaces $V$ have this property:

For every open subset $U\subset V$ there exists a non-zero continuous function $f\colon V\to \mathbb{R}$ such that $\overline{\{x\in V\colon f(x)\neq 0\}}\subset U$?

Is it normality by chance?

答:
This is implied by complete regularity + $T_1$, also called Tychonoff, a property weaker than normality.

If $U$ is a (non-empty) open set, find a non-empty open $V$ such that $\overline{V} \subset U$ (by regularity) and for some $p \in V$ a continuous function $f: V \rightarrow [0,1]$ with $f(p) = 1$ and $f([X \setminus V] = \{0\}$, by complete regularity. Then $\overline{\left\{x \in V: f(x) \neq 0\right\}} \subset \overline{V} \subset U$, as required.

It doesn't seem to be equivalent to it, as Brian pointed out. But it is true in all Tychonoff ($T_{3\frac{1}{2}}$) spaces.


问:
Any space $X$ can be embedded as a dense subset of a Lindelöf space.
I have the following statement to prove, but I'm not sure how to go about doing so.

Any space $X$ can be embedded as a dense subset of a Lindelöf space.

There is a hint associated to this exercise,

[Hint: Adjoin a point $p$ to $X$ whose nbhds are the sets $\{p\}\cup E$, where $E$ is a subset of $X$ whose complement in $X$ is Lindelöf.]

答:
The hint gives the game away, but there is one subtlety:

Define $Y = X \cup \{p\}$ as sets, where $p = \infty$ or any point not in $X$.
Let $\mathcal{L}$ be the set of all closed subsets of $X$ that are Lindelöf (in the subspace topology).

Let $\mathcal{T}_Y$ be the topology with subbase $$\{\{p\} \cup E\mid X\setminus E \in \mathcal{L}\} \cup \mathcal{T}_X$$

and note that $i: X \to Y$ defined by $i(x)=x$ is an embedding and $Y$ is Lindelöf (taking any open cover, of $Y$ consider first what the open set containing $p$ is etc.; it's similar to the one-point compactification that way).

$X$ (rather, its topological copy $i[X]$) will only be dense in $Y$ if $X$ is not itself Lindelöf, but we can assume that WLOG anyway.


问:
Differential of $0$-form
If I have a $1$-form that in local coordinates can be written as $\alpha=\alpha_i dx^i$ and a vector field $X=\xi^j \frac{\partial}{\partial x^j}$, if I apply $\alpha$ to $X$ I should obtain the following:

$$\alpha(X)=\alpha_idx^i\Bigl(\xi^j \frac{\partial}{\partial x^j}\Bigr)=\color{red}{\alpha_i\xi^j dx^i\Bigl(\frac{\partial}{\partial x^j}\Bigr)}=\alpha_i\xi^j\delta^j_i=\alpha_i\xi^i$$
$\textbf{My question:}$ I can't understand the red expression, in particular why $\alpha_i dx^i\bigl(\xi^j\frac{\partial}{\partial x^j}\bigr)=\alpha_i\xi^j dx^i\bigl(\frac{\partial}{\partial x^j}\bigr)$; why can I put outside the $\xi^j$ (that is a $0$-form) outside the differential as it is a constant?

答:
If $\alpha = \alpha_i \mathrm{d}x^i$ is a $1$-form and $X = X^j \partial_j$ is a vector field, the notation $\alpha(X)$ has to be understood as a function on $M$ defined by
$$\alpha(X)(p) = \alpha_p (X_p).$$
Now, for a fixed point $p \in M$, $\alpha_p$ is a linear form on $T_pM$ and $X_p = X^j(p) \partial_j(p)$ is a vector. Hence, by linearity
$$
\alpha(X)(p) = \alpha_i(p) \mathrm{d}x^i|_p\left(X^j(p)\partial_j(p) \right) = \alpha_i(p)X^j(p)\mathrm{d}x^i|_p \left(\partial_j(p) \right) = \alpha_i(p)X^j(p) \delta^i_j = \alpha_i(p)X^i(p).
$$
And this tells us that $\alpha(X)$ is the function on $M$
$$
\alpha(X) : p \mapsto \alpha_i(p)X^i(p).
$$

Edit Forget about the manifold. Suppose you have a vector space $V$ with basis $(e_1,\ldots,e_n)$ and dual basis of $V^*$ $(e^1,\ldots,e^n)$. Then if $X = X^i e_i \in V$ is a vector and if $\alpha = \alpha_j e^j \in V^*$ is a linear form on $V$, then by definition of the dual basis
$$
\alpha(X) = \alpha_iX^i.
$$
Now, remember that a tangent bundle $TM$ is a familly of vector spaces $(T_pM)_{p\in M}$. Do not think about any differentiable structure or anything. A vector field is a familly $(X_p)_{p\in M}$ with $X_p \in T_pM$. A $1$-form is a familly of covectors $(\alpha_p)_{p\in M}$ with $\alpha_p \in T_pM^*$.

Fix $p\in M$, apply the above reasoning to $V = T_pM$, $X = X_p$ and $\alpha = \alpha_p$.

Comment You seem to be confused about the differential. But the in the expression $\mathrm{d}x^i (X^j\partial_j)$, you are not taking any differential. You are just applying the $1$-form "$\mathrm{d}x^i$" to the vector $"X^j \partial_j"$.

Title: Differential of $0$-form


问:
Solve $ y=({\rm d}y/{\rm d}x)^2 $
It is obvious that we can differentiate both sides of the equation with respect to $x$ and then discuss the result. But can we just make a square root of both sides and integrate?

Sorry the original version is so naive. The following is more detailed.

If we take square root
$$\pm \sqrt y=\frac{{\rm d}y}{{\rm d}x}$$
then
$$\frac{{\rm d}y}{\sqrt y}=\pm {\rm d}x$$
$$2\sqrt y=\pm x+c$$
The solutions are
$$y=(\frac{\pm x+c}{2})^2$$ or $y=0$

If we differentiate both sides with respect to $x$
$$y'=2y'y''$$
$$y'(2y''-1)=0$$
If we choose $y'=0$, then $y=c$. And plug it in to the original equation, we get $c=0$.

If we choose $y''=\frac12$, then $y=\frac14x^2+dx+f$. Plugging in, we get $y=\frac14x^2+dx+d^2$, which is enough.

(How could the non-trivial solutions differ???-this is a solved question now.)

Now, everything is great. From this example, I know that there are something a little bit different with the liner differential equation in a nonlinear one. Sometimes, one needs to plug in the solution with constants under some circumstances to determine some constant. Besides, the form of the solution of a nonlinear differential equation could be more complicated-it could be piecewise-combined. One could choose a set of solution satisfying the equation and match them at every boundary of each segment correspondingly. Thank @Allawonder and @Gae. S. for pointing them out.

答:
The solutions do not differ.

$$(c\pm x)^2=x^2\pm 2cx+c^2$$

does match

$$x^2+4dx+4d^2$$ with $$\pm c=2d.$$

Notice that, as mentioned by @gaes, as $y=0$ is a solution you can switch from a solution to another when $y=0$, and there are in fact five possible modes.

Title: Solve $ y=({\rm d}y/{\rm d}x)^2 $


问:
On the notion of sheaf
Citing form Borceux, Handbook of categorical algebra, in the preface to volume 3:

The crucial idea behind the notion of a sheaf is to work not just with a "plain" set of elements, but with a whole system of elements at various levels. Of course, reasonable rules are imposed concerning the interactions between the various levels: an element at some level can be restricted to all lower levels and, if a compatible family of elements is given at various individual levels, it is possible to "glue" the family into an element defined at the global level covered by the individual ones. The various notions of sheafs depend on the way the words "level", "restriction" and "covering" are defined.

The easiest examples are borrowed from topology, where the various "levels" are the open subsets of a fixed space $X$: for example a continuous function on $X$ may very well be defined "at the level of the open subset $U\subseteq X$", without being the restriction of a continuous function defined on the whole of $X$.

Could someone explain me the bold part?

答: It means you can break the domain $X$ into small pieces of open sets. A family of functions on these pieces with compatible condition determines a function on $X$. The bolded sentence means you do not need to care whether the functions on the small pieces are restricted from the functions on $X$ (but this is always the case!).</p>

Title: On the notion of sheaf


问:
Given $V= \pi \int_{1}^{c}-y \sqrt{1-y^2}\,\mathrm{d}y$, Find $f^\prime\left(x\right)$
Suppose that I have a function, $f\left(x\right)$ s.t. $f\left(x\right) > 0$ on $\left[0,a\right]$ and $f\left(0\right)=1$ and $f\left(a\right) = c$. The volume $V$ of the function is $$V= \pi \int_{1}^{c}-y \sqrt{1-y^2}\,\mathrm{d}y$$ (and $y=f\left(x\right)$). How do I obtain $f^\prime\left(x\right)$? On the surface, this looks like a question where I should integrate the volume. However, I have no way of finding out $f^\prime\left(x\right)$ using the fundamental theorem since the bound $c$ is unknown. Help would be appreciated.

答:
As you gave to less context I can only guess what you meant.

You start with the function $$V(a):=\pi\int_1^{f(a)}-y\sqrt{1-y^2}\mathrm dy.$$
As you mentioned that you want to apply the fundamental theorem this brings you to
$$V'(a)=\pi\left(\frac{\rm d}{\mathrm dx}\int_1^{x}-y\sqrt{1-y^2}\mathrm dy\right)_{x=f(a)}\cdot \left(\frac{\mathrm d f(a)}{\mathrm da}\right)=-\pi f(a)\sqrt{1-f^2(a)}\cdot f'(a). $$
Thus the derivation is given by
$$f'(x)=-\frac{V'(x)}{\pi f(x)\sqrt{1-f^2(x)}}.$$


问:
Divisor for two terms
I am currently reading a book on basic number theory and in the first chapter the author uses the fact that if $d \mid x$ and also $d\mid y$, then it is true that $d$ is a divisor to both sides of the equation:
$$
x = y +r
$$

I see that it is true, but how could you prove that? I mean, if $x$ and $y$ are even, then the $\gcd(x,y)$ is even and the rest $r = 0$, hence for any other divisor $c < \gcd(x,y)$ the rest $r$ will of course be even.

What about if $\gcd(x,y)$ is odd? Or is this a bad way to approach a proof for above statement? How would you do to prove it?

Best regards,

答:
We are given that $d\mid x$ and $d\mid y$. So there are integers $m, n$ such that $$\;\;x = md, \quad \text{and}\quad y = nd$$

Then given  $x = y + r \iff x - y = r$, we have $$x - y = md - nd = (m-n)d = r.$$

Hence $d\mid r$, as well, since $m, n$ are integers.

Then what can you say about $d$ with respect to the right-hand side: $$y + r = nd + (m-n)d = (n+m-n)d\quad?$$

Title: Divisor for two terms


问:
Definition of Simple Connectedness.
I came accross the following defintion of simple-connectedness:

Given:

$S^1 =\{ (x,y)  \in R^2 \ | \ x^2+y^2 = 1 \}$

$K^2 =\{ (x,y)  \in R^2 \ | \ x^2+y^2 \le 1 \}$

With $\underline S^1, \underline K^2$ being subspaces of $\underline R^2$.

Definitions:

A loop in $\underline X$ is a continuous map  $f: \underline S^1 \rightarrow \underline X $.

A loop is contractable if there exists a continuous extension $F: \underline K^2 \rightarrow \underline X$ of $f$.

$\underline X$ is called simply-connected if $\underline X$ is path-connected and every loop in it is contractible.

I understand the definition of the loop as it describes a continuous path from point $x$ to itself, which is  a loop in its literal meaning.

What I don't get is the definition of contractibility. I don't see how extending $f$ as described above somehow leads to the ability of going around holes in $X$ to make the space simply-connected.

It is also a definition, which is similar to how simple-connectedness is described in Wikipedia. Describing its meaning might benefit others as well.

答: For each $t\in[0,1]$ and each $z\in S^1$, let $f_t(x)=F(tz)$. Then $f_1=f$ and $f_0$ is constant. And, due to continuity, $f_t$ is close to $f_1$ if $t$ is close to $1$ and $f_t$ is close to $F(0)$ if $t$ is close to $0$. So, the $f_t$'s deform the loop $f_1(=f)$ into a single point.

Title: Definition of Simple Connectedness.


问:
Are $\bigcap\{Y\in\wp(S):X\subseteq Y\}$ and $X$ sets equal?
$S$ is a set, $\wp(S)$ is the power set of $S$.

$\forall X\subseteq S$, are $\bigcap\{Y\in\wp(S):X\subseteq Y\}$ and $X$ sets equal?

I think that since $X$ is a subset of $S$ and $Y$ satisfies the condition $X\subseteq Y$, so $X$ must exist in $\{Y\in\wp(S):X\subseteq Y\}$, and $X$ is the set with the least elements, so $\bigcap\{Y\in\wp(S):X\subseteq Y\}$ = $X$.

Is my understanding correct? If it is wrong, could you cite a counterexample?

Thank you!

答:
Here is a correct proof:

As $X$ is contained in each $Y$, it is trivial that $X$ is contained in their intersection.

Conversely, split the intersection in two:
$$\bigcap_{X\subseteq Y\strut}Y=X\cap\Bigl(\bigcap_{X\varsubsetneq Y\strut}Y\Bigr)$$
is contained in $X$, as any intersection of $X$ with another set.


问:
Why we define an orthogonal matrix $A$ to be one that $A^TA=I$
Why we define an orthogonal matrix $A$ to be one that $A^TA=I$ rather than just let its rows and columns be orthonormal ?

Note: I ask this because I think that it's more natural to first defined $A$ with orthonormal columns and rows, then prove $A^TA=I$.

答:
The definitions you mention are actually equivalent and it's quite easy to see why. Let $A = [a_1 \, a_2 \, \cdots \, a_n]$. Observe that the columns of $A$ being orthonormal is equivalent to

$$a_i \cdot a_j = \delta_{ij},$$

where $\delta_{ij}$ is the Kronecker symbol. Now consider the matrix product

$$A^TA  = \begin{bmatrix}
a_1^T \\
a_2^T \\
\vdots \\
a_n^T \end{bmatrix}[a_1 \, a_2 \, \cdots \, a_n],$$

whose $(i,j)$-entry is exactly the scalar product $a_i \cdot a_j$. Do you now see how these definitions are equivalent?

Addendum/edit: Now, this does not exactly answer the question as to why we often prefer one definition over the other. The answer is that it is more compact and more useful when doing computation. Definition this kind, i.e. that can be expressed (perhaps more intuitively) in words are defined in a symbolic and more compact way, to ease computation and shorten proofs. Here is another example: We can define a stochastic matrix as a matrix whose entries are non-negative and where the sum over each column is 1. However, this is wordy and seems cumbersome to check. We can equivalently define it as follows:

Let $S = [1 \, 1 \, \cdots \, 1]$ be the $1 \times n$ matrix filled with ones. An $n \times n$ matrix $A$ is stochastic if all its entries are non-negative and it satisfies

$$SA = S.$$

This is more compact and versatile than our first definition.


问:
Symbol for Mutual Inclusive events
is there any symbol for mutual inclusive(opposite of Mutually exclusive) events in probability.

I meant to say is for OR we have U symbol in Set Theory. Likewise is there any symbol for Mutual Inclusiveness.

答:
You want to say that two events $A$ and $B$ satisfy

If $A$, then $B$;

If $B$, then $A$.

That is, $A$ if and only if $B$.  Thus $A$ and $B$ are mutually inclusive if and only if $A$ and $B$ happen simultaneously.  We might say that $A$ and $B$ are equivaent events, or that $A$ and $B$ are concurrent events. (I don't think either notation is standard.)

Symbolically, I suppose you'd want to use $A \equiv B$ or $A=B$ (denoting the fact that mutual inclusion is an equivalence relation).  I don't think any particular form is standard.

Title: Symbol for Mutual Inclusive events


问:
Prove that ideal is whole ring

Prove that if $I$ is an ideal of the ring $M_2(\mathbb{R})$ and $X= \begin{bmatrix}0&1\\0&0\end{bmatrix}\in I$, then $I=M_2(\mathbb{R})$.

I think the question is wrong because
there is no matrix $A\in M_2(\mathbb{R})$ such that $AX=I_2$ or $XA=I_2$, so $I_2$ is not in this ideal hence $I\neq M_2(\mathbb{R}).$

Am I correct?

答: Hint: Consider $AX$ and $XA$ where $A$ is a permutation matrix.

Title: Prove that ideal is whole ring


问:
Approach to address errors from float precision limits by its storage limit

Background

In computer, the limited float precision due to the storage limit e.g. 64 bit can cause problems. Trying to understand what approaches are available and being used to cope with or overcome the precision limitations.

The original issue is numpy - why numerical gradient log(1-sigmoid(x)) diverges but $\log(\operatorname{sigmoid}(x))$ does not?. While trying to implement a numeric gradient (f(x+k)-f(x-k)) / 2k  of the logistic log loss function, encountered a problem of float calculation gets unstable. When $f(x)$ and $k$ gets smaller such as 1e-8, $\log(\operatorname{sigmoid}(x))$ started diverging while $\log(\operatorname{sigmoid}(x))$ does not.

When the values are relatively large such as 1e-5, the issue does not happen, at least in the range of x.

The reason trying to make k smaller is to prevent log(0) to become np.inf by adding a small number u e.g. 1e-5 but log(x+1e-5) causes a deviation of numerical gradient from the analytical one. To minimize the impact, I try to make it smallest possible and start having this issue.

Logistic log loss functions

y in the figure is binary true/false label T and p is the activation sigmoid(x),

Question

I believe there are science and engineering fields which require high precision calculations. I like to understand

What kind of float numerical calculation problems exist.

Which mathematics topics or areas to look into.

What approaches are being used to address limited precision/storage issues in computing.

Code

Logistic log loss and analytical gradient.

```<code>import numpy as np
import inspect
from itertools import product
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline

def __sigmoid(X):
    return 1 / (1 + np.exp(-1 * X))

def __logistic_log_loss(X: np.ndarray, T: np.ndarray):
    return -(T * np.log(__sigmoid(X)) + (1-T) * np.log(1-__sigmoid(X)))

def __logistic_log_loss_gradient(X, T):
    Z = __sigmoid(X)
    return Z-T

N = 1000
left=-20
right=20

X = np.linspace(left,right,N)
T0 = np.zeros(N)
T1 = np.ones(N)

# --------------------------------------------------------------------------------
# T = 1
# --------------------------------------------------------------------------------
fig, ax = plt.subplots(figsize=(8,6))
ax.plot(
    X,
    __logistic_log_loss(X, T1),
    color='blue', linestyle='solid',
    label="logistic_log_loss(X, T=1)"
)
ax.plot(
    X,
    __logistic_log_loss_gradient(X, T1),
    color='navy', linestyle='dashed',
    label="Analytical gradient(T=1)"
)

# --------------------------------------------------------------------------------
# T = 0
# --------------------------------------------------------------------------------
ax.plot(
    X,
    __logistic_log_loss(X, T0),
    color='magenta', linestyle='solid',
    label="logistic_log_loss(X, T=0)"
)
ax.plot(
    X,
    __logistic_log_loss_gradient(X, T0),
    color='purple', linestyle='dashed',
    label="Analytical gradient(T=0)"
)

ax.set_xlabel("X")
ax.set_ylabel("dL/dX")
ax.set_title("Logistic log loss and gradient")
ax.legend()
ax.grid(True)
</code>```

Numerical gradient

```<code>def t_0_loss(X):
    return [
        #logistic_log_loss(P=sigmoid(x), T=0)
        -np.log(1.0 - __sigmoid(x)) for x in X
    ]

def t_1_loss(X):
    return [
        #logistic_log_loss(P=sigmoid(x), T=1)
        -np.log(__sigmoid(x)) for x in X
    ]

N = 1000
left=-1
right=15

# Numerical gradient
# (f(x+k)-f(x-k)) / 2k
k = 1e-9

X = np.linspace(left,right,N)
fig, axes = plt.subplots(1, 2, figsize=(10,8))

# --------------------------------------------------------------------------------
# T = 0
# --------------------------------------------------------------------------------
axes[0].plot(
    X,
    ((np.array(t_0_loss(X + k)) - np.array(t_0_loss(X - k))) / (2*k)),
    color='red', linestyle='solid',
    label="Diffed numerical gradient(T=0)"
)
axes[0].plot(
    X[0:-1:20],
    ((np.array(t_0_loss(X + k)) - np.array(t_0_loss(X))) / k)[0:-1:20],
    color='black', linestyle='dotted', marker='x', markersize=4,
    label="Left numerical gradient(T=0)"
)
axes[0].plot(
    X[0:-1:20],
    ((np.array(t_0_loss(X)) - np.array(t_0_loss(X - k))) / k)[0:-1:20],
    color='salmon', linestyle='dotted', marker='o', markersize=5,
    label="Right numerical gradient(T=0)"
)

axes[0].set_xlabel("X")
axes[0].set_ylabel("dL/dX")
axes[0].set_title("T=0: -log(1-sigmoid(x))")
axes[0].legend()
axes[0].grid(True)

# --------------------------------------------------------------------------------
# T = 1
# --------------------------------------------------------------------------------
axes[1].plot(
    X,
    ((np.array(t_1_loss(X + k)) - np.array(t_1_loss(X - k))) / (2*k)),
    color='blue', linestyle='solid',
    label="Diffed numerical gradient(T=1)"
)
axes[1].plot(
    X[0:-1:20],
    ((np.array(t_1_loss(X + k)) - np.array(t_1_loss(X))) / k)[0:-1:20],
    color='cyan', linestyle='dashed', marker='x', markersize=5,
    label="Left numerical gradient(T=1)"
)
axes[1].plot(
    X[0:-1:20],
    ((np.array(t_1_loss(X)) - np.array(t_1_loss(X - k))) / k)[0:-1:20],
    color='yellow', linestyle='dotted', marker='o', markersize=5,
    label="Right numerical gradient(T=1)"
)

axes[1].set_xlabel("X")
axes[1].set_ylabel("dL/dX")
axes[1].set_title("T=1: -log(sigmoid(x)")
axes[1].legend()
axes[1].grid(True)
</code>```

答:
Solution by Reza.B.

Let z=1/(1+p), p= e^(-x). You can see then log(1-z)=log(p)-log(1+p), which is more stable in terms of rounding errors (we got rid of division, which is the main issue in numerical instabilities).

Reformulation

$
\begin{align*}
P&=exp(-X)
\\
log(exp(-X)) &= -X
\\
Z &=sigmoid(X) = \frac {1}{1+exp(-X)} = \frac {1}{1+P}
\\
log(Z) &= log(\frac {1}{1 + exp(-X)}) \\
&= log(1) - log(1+exp(-X)) \\
&= -log(1+P)
\\
\\
log(1-Z) &= log(\frac {exp(-X)}{1+exp(-X)})\\
&= log(P)-log(1+P)
\end{align*}
$

Then the logistic log loss function is reformulated as:

$
\begin{align*}
L &= - \left[ \;
Tlog(Z) + (1-T)log(1-Z)
\; \right]
\\
&= Tlog(1+P) - log(P) + log(1+P) +Tlog(P) - Tlog(1+P) \\
& = (T-1)log(P) + log(1+P) \\
&= (1-T)X + log(1+P)\\
&= (1-T)X + log(1+exp(-X))
\\
\\
L(T=0) &= X + log(1+exp(-X))\\
L(T=1) &= log(1+exp(-X))\\
\end{align*}
$

Result

The errors have been resolved.

```<code>def t_0_loss(X):
    L = X + np.log(1 + np.exp(-X))
    return L.tolist()

def t_1_loss(X):
    L = np.log(1 + np.exp(-X))
    return L.tolist()

%%timeit
((np.array(t_0_loss(X + k)) - np.array(t_0_loss(X - k))) / (2*k))
((np.array(t_1_loss(X + k)) - np.array(t_1_loss(X - k))) / (2*k))
---
599 µs ± 65.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
</code>```

Previous erroneous version was:

```<code>47 ms ± 617 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
</code>```

Body:
Solution by Reza.B.

Let z=1/(1+p), p= e^(-x). You can see then log(1-z)=log(p)-log(1+p), which is more stable in terms of rounding errors (we got rid of division, which is the main issue in numerical instabilities).

Reformulation

$
\begin{align*}
P&=exp(-X)
\\
log(exp(-X)) &= -X
\\
Z &=sigmoid(X) = \frac {1}{1+exp(-X)} = \frac {1}{1+P}
\\
log(Z) &= log(\frac {1}{1 + exp(-X)}) \\
&= log(1) - log(1+exp(-X)) \\
&= -log(1+P)
\\
\\
log(1-Z) &= log(\frac {exp(-X)}{1+exp(-X)})\\
&= log(P)-log(1+P)
\end{align*}
$

Then the logistic log loss function is reformulated as:

$
\begin{align*}
L &= - \left[ \;
Tlog(Z) + (1-T)log(1-Z)
\; \right]
\\
&= Tlog(1+P) - log(P) + log(1+P) +Tlog(P) - Tlog(1+P) \\
& = (T-1)log(P) + log(1+P) \\
&= (1-T)X + log(1+P)\\
&= (1-T)X + log(1+exp(-X))
\\
\\
L(T=0) &= X + log(1+exp(-X))\\
L(T=1) &= log(1+exp(-X))\\
\end{align*}
$

Result

The errors have been resolved.

def t_0_loss(X):
    L = X + np.log(1 + np.exp(-X))
    return L.tolist()

def t_1_loss(X):
    L = np.log(1 + np.exp(-X))
    return L.tolist()

%%timeit
((np.array(t_0_loss(X + k)) - np.array(t_0_loss(X - k))) / (2*k))
((np.array(t_1_loss(X + k)) - np.array(t_1_loss(X - k))) / (2*k))
---
599 µs ± 65.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

Previous erroneous version was:

47 ms ± 617 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)


答: Your proof is wrong because the ideal generated by one element in a non-commutative setting does not only include its left multiples and right multiples.</p>

Title: Prove that ideal is whole ring

Body:
Prove that if $I$ is an ideal of the ring $M_2(\mathbb{R})$ and $X= \begin{bmatrix}0&1\\0&0\end{bmatrix}\in I$, then $I=M_2(\mathbb{R})$.

I think the question is wrong because
there is no matrix $A\in M_2(\mathbb{R})$ such that $AX=I_2$ or $XA=I_2$, so $I_2$ is not in this ideal hence $I\neq M_2(\mathbb{R}).$

Am I correct?


问:
How should I think about this ring?
I don't know much abstract algebra or ring theory. I have come across a ring, and it would be really great if somebody could help me to understand what else in mathematics it relates to, or how to visualize what is going on in this ring (especially for multiplication).

The underlying set is $\mathbb R \times \mathbb R,$ so the elements are pairs of real numbers. Addition of $(a,b)$ and $(c,d)$ is defined as $(a,b) \oplus (c,d) = (a + c, b + d).$ Multiplication of $(a,b)$ and $(c,d)$ is defined as $(a,b) \odot (c,d) = (a \times c, (a \times d) + (b \times c)).$

I noticed that if we write $(a,b)$ as $b/a$ then $\oplus$ and $\odot$ look like Farey addition, and standard fraction addition, respectively. Although I suspect somebody can point out much deeper relationships between this ring and other ideas from mathematics. I'm not even sure what the ring is called. It is mentioned in the Kock-Lawvere Axiom.

答:
This is a common construction in ring theory called a trivial extension or split-null extension in the literature.

It can be thought of as the quotient $\mathbb R[x]/(x^2)$, where $(a,b)$ corresponds to $a+bx+(x^2)$ in the quotient.  In this form the construction is also named dual numbers, but that monicker is not applied more generally, really.

Here’s a second way: Given an $R,R$ bimodule $M$, one can think of the set of matrices of the form $\begin{bmatrix}a&m\\ 0&a\end{bmatrix}$ where $a\in R$ and $m\in M$ as a ring using matrix addition and multiplication.  When you abbreviate that matrix to $(a,m)$, and $M=R$ is commutative, it boils down to the quotient above.

I mentioned this second way because it sort of shows a connection to a more general construction called a triangular matrix ring. Given an $R, S$ bimodule $M$, you can form a ring out of $\begin{bmatrix}R&M \\
 0&S\end{bmatrix}$ with the obvious operations.  The second way above is a subring of that.

Most generally if you have an $R,S$ bimodule $M$ and an $S,R$ bimodule $N$, you have a ring $\begin{bmatrix}R&M\\ N&S\end{bmatrix}$ which is called a Morita context ring.

Title: How should I think about this ring?


答:
This is just $\Bbb R[\varepsilon]/(\varepsilon^2)$ where $(a,b)$ corresponds to $[a+b\varepsilon]$.

In algebraic geometry, it is related to tangent spaces.

Title: How should I think about this ring?

Body:
I don't know much abstract algebra or ring theory. I have come across a ring, and it would be really great if somebody could help me to understand what else in mathematics it relates to, or how to visualize what is going on in this ring (especially for multiplication).

The underlying set is $\mathbb R \times \mathbb R,$ so the elements are pairs of real numbers. Addition of $(a,b)$ and $(c,d)$ is defined as $(a,b) \oplus (c,d) = (a + c, b + d).$ Multiplication of $(a,b)$ and $(c,d)$ is defined as $(a,b) \odot (c,d) = (a \times c, (a \times d) + (b \times c)).$

I noticed that if we write $(a,b)$ as $b/a$ then $\oplus$ and $\odot$ look like Farey addition, and standard fraction addition, respectively. Although I suspect somebody can point out much deeper relationships between this ring and other ideas from mathematics. I'm not even sure what the ring is called. It is mentioned in the Kock-Lawvere Axiom.


问:
Help understanding Question - Abstract Algebra - Commutative Law and Rings
Let $R$ be a ring. Define a function $e : R[X]\times R \to R$ by the rule
$e\left(\sum_{k=0}^n a_k X^k,r\right) = \sum_{k=0}^n a_k r^n$.
In other words, given the input of a polynomial $f \in R[X]$ and an element $r\in R$,
$e(f,r)$ is obtained by substituting $r$ for $x$ in $f$.

Prove that, if $R$ is a commutative ring, then
$e(f,r) +e(g,r) = e(f +g,r)$ and
$e(f,r)· e(g,r) = e(f g,r)$
for any two linear polynomials $f$,$g \in R[x]$ and any $r ∈ R$.

So my understanding is that $f$ and $g$ are 2 random polynomials,
what I'm having difficult understanding is how would I show this satisfies the commutative law (as shown above), does $e$ mean its a whole other function?

What I've tried to do is to insert two polynomials, e.g. - $r+1$ and $r+2$ into the given function, but does this prove that $R$ is a commutative ring?
tip and help on understanding this question would be helpful.

答: If $f$ and $g$ a linear polynomial, then $f(X)=aX+b$ and $g(X)=cX+d$, with $a,b,c,d\in R$. Besides,$$(fg)(X)=(aX+b)(cX+d).$$So\begin{align}e(fg,r)&=(ar+b)(cr+d)\\&=acr^2+(ad+bc)r+bd\text{ (since $R$ is commutative)}\\&=e(f,r)\cdot e(g,r).\end{align}Proving that $e(f+g,r)=e(f,r)+e(g,r)$ is even simpler.


问:
Adjoint map $\text{Ad}:G\rightarrow \text{Aut}(\mathfrak{g})$ is smooth.
Let $G$ be a lie group and let $\mathfrak{g}$ its lie algebra. Its not clear to me that $\text{Ad}:G\rightarrow \text{Aut}(\mathfrak{g})$ is smooth.

It is clear to me that if we have a matrix group any $g\in G$ gives that $\text{Ad}(g)$ is smooth. Because $Ad(g)Y=gYg^{-1}$ consists of rational polynomials in each entry. However this does not tell us that $Ad$ is smooth,  only that it sends each $g$ to a smooth.

How can we see that $Ad:G\rightarrow \text{Aut}(\mathfrak{g})$ is smooth? One approach might be to use that it is a group homomorphism between lie groups and then we need only show that it is continuous.

I do not think this question is a duplicate of (Adjoint action smooth (in Tapp's book)?) because it seems to me that this question on explains why each $\text{Ad}(g)$ is smooth, not $\text{Ad}$

答: The direct way to prove this is as follows: Consider the map $F:G\times G\to G$ defined by $F(g,h):=ghg^{-1}$. This is obviously smooth, so its tangent map $TF:TG\times TG\to TG$ is smooth, too. Now we can restrict in the second component to to submanifold $T_eG=\mathfrak g$. On the other hand, the zero vector field $0:G\to TG$ is a smooth map. Hence we conclude that the map $G\times\mathfrak g\to TG$ defined by $(g,X)\mapsto TF(0(g),X)$ is smooth. But from the construction, it follows immedately that $TF(0(g),X)$ can be computed as $\tfrac{d}{dt}|_{t=0}gexp(tX)g^{-1}$. Hence we see that $TF(0(g),X)=Ad(g)(X)\in T_eG$, so we have actually proved that $(g,X)\mapsto Ad(g)(X)$ is smooth as a map $G\times\mathfrak g\to\mathfrak g$. But choosing a basis $\{X_i\}$ for $\mathfrak g$ with dual basis $\{\lambda_i\}$ for $\mathfrak g^*$ you get the entries of the matrix of $Ad(g)$ with respect to the basis $\{X_i\}$ as $a_{ij}=\lambda_i(Ad(g)(X_j))$. So these matrix entries depend smoothly on $g$, which exactly says that $Ad$ is smooth as a map $G\to GL(\mathfrak g)$.


问:
Help with visualising the confidence interval.
I’m trying to understand the confidence interval by reference to the diagram below:

•   I want to guess a parameter that we know to be 0.88. The vertical line represents the parameter’s value.

•   I choose a confidence interval of 95%. The length of each horizontal line is such that 95 out of 100 of them include the population parameter.

•   If I choose a 99% confidence interval, then each horizontal line will lengthen until 99 out of 100 of them include the parameter.

•   If I choose a 90% confidence interval, then each horizontal line will contract until 90 out of 100 of them include the parameter.

So, what sense is there in saying that we have a 95% confidence interval of, say, 0.86 to 0.91? In my textbook, it says, “We are 95% confident that the actual parameter proportion is between 86% and 91%”.

Shouldn’t we have many confidence intervals, e.g. the 100 confidence intervals represented by each blue line above and in the table below, of which 95 of them will include the actual parameter:

Would it be better to say: “There is a 95% probability that one of the confidence intervals I select using my selection procedure will contain the parameter. An example of one of those confidence intervals that I could have selected is [0.86, 0.91]. (Yet, once I select this confidence interval, it either does (100%) or does not (0%) contain the parameter)".  In other words, how do I answer textbook questions without turning it into a philosophical discussion?

答:
The text book seems to give a wrong definition of confidence interval. Like you remark correctly, the confidence interval is a interval such that when an experiment is repeated a sufficiently large number of times(*), x% of these confidence intervals contain the population parameter.

The problem with the definition as given in the book is that in frequentist statistics you do not assign probabilities to population parameters, so it does not make sense to talk about the probability (and even less to talk about "confidence", because what does that mean if it does not mean "probability"?).


问:
Stable discretization for a given ODE
Given the ODE
$$ \ddot{X} + \frac{3}{t}\dot{X} + F(X) = 0,$$
what would be a stable explizit discretization?

One can rewrite the ODE as a first order equation of the form
$$
\dot{Y}_1 = Y_2 \\
\dot{Y}_2 =-\frac{3}{t}Y_2-F(Y_1),
$$
by setting $Y_1:=X, Y_2:=\dot{X}$.
Then one can apply a Runge-Kutta-method or just a simple Euler, but how do I check that the method should be stable since the ODE considered here is not autonomous.

答:
EDIT: You are asking about stability, then this may help you:

Under certain assumptions you may be able to prove that your two dimensional system is locally one-sided Lipschitz continuous (depending on where you seek a solution, and what $F$ is, looks like you need a Lipschitz constant of F being > 1), and then use a B-stable RK method (B-stable in the sense of Butcher, ambiguous term). Then I need more information. B-stability is briefly described on the Wikipedia page of RK methods.

Title: Stable discretization for a given ODE


问:
Evaluating a definite integral by introducing change of variables
In a Physics class, I encountered the following integral: $$\int_{0}^{\infty} \left(\frac{x^2}{\exp\left(x-a\right)+1}-\frac{x^2}{\exp\left(x+a\right)+1}\right)\,\mathrm{d}x\text{,}$$

where $a$ is a constant. It is stated to yield: $$\int_{0}^{\infty}\left(\frac{x^2}{\exp\left(x-a\right)+1}-\frac{x^2}{\exp\left(x+a\right)+1}\right)\,\mathrm{d}x=\frac{1}{3}\left[\pi^2a+a^3\right]$$

I first introduced a change of variables: $$y:=x-a$$ $$z:=x^\prime+a$$ This gives: $$\int_{0}^{\infty}\frac{x^2}{\exp\left(x-a\right)+1}\,\mathrm{d}x-\int_{0}^{\infty}\frac{\left(x^\prime\right)^2}{\exp\left(x^\prime+a\right)+1}\,\mathrm{d}x^\prime=\int_{-a}^{\infty}\frac{\left(y+a\right)^2}{e^y + 1}\,\mathrm{d}y-\int_{a}^{\infty}\frac{\left(z-a\right)^2}{e^z+1}\,\mathrm{d}z$$ However, when introduced to a computer, the definite integrals are stated to have no solution. I actually expected to get integrals of the form: $$\int_{0}^{\infty}\frac{y}{e^y+1}\,\mathrm{d}y=\frac{\pi^2}{12}$$ What am I missing here?

答:
You are on the right track. Continue by renaming $z$ to $y$ and writing
\begin{align}
\int \limits_0^\infty x^2 \left(\frac{1}{\mathrm{e}^{x-a}+1} - \frac{1}{\mathrm{e}^{x+a}+1}\right) \, \mathrm{d} x &= \int \limits_{-a}^\infty \frac{(y+a)^2}{\mathrm{e}^y + 1} \, \mathrm{d} y - \int \limits_a^\infty \frac{(z-a)^2}{\mathrm{e}^z + 1} \, \mathrm{d} z \\
&= \int \limits_{-a}^a \frac{(y+a)^2}{\mathrm{e}^y + 1} \, \mathrm{d} y + \int \limits_a^\infty \frac{(y+a)^2 - (y-a)^2}{\mathrm{e}^{y} + 1} \, \mathrm{d} y \\
&= \int \limits_{-a}^0 \frac{(y+a)^2}{\mathrm{e}^y + 1} \, \mathrm{d} y + \int \limits_0^a \frac{(y+a)^2 - 4 a y}{\mathrm{e}^y + 1} \, \mathrm{d} y + \int \limits_0^\infty \frac{4ay}{\mathrm{e}^y + 1} \, \mathrm{d} y \\
&= \int \limits_{-a}^0 \frac{(a + y)^2}{\mathrm{e}^y + 1} \, \mathrm{d} y + \int \limits_0^a \frac{(a - y)^2}{\mathrm{e}^y + 1} \, \mathrm{d} y + \int \limits_0^\infty \frac{4ay}{\mathrm{e}^y + 1} \, \mathrm{d} y \, .
\end{align}
Now substitute $y \to - y$ in the first integral and add it to the second integral. Since you know the value of the third integral, this yields
\begin{align}
\int \limits_0^\infty x^2 \left(\frac{1}{\mathrm{e}^{x-a}+1} - \frac{1}{\mathrm{e}^{x+a}+1}\right) \, \mathrm{d} x &= \int \limits_0^a (a - y)^2 \left[\frac{1}{\mathrm{e}^{-y} + 1} + \frac{1}{\mathrm{e}^y + 1}\right] \, \mathrm{d} y + 4 a \int \limits_0^\infty \frac{y}{\mathrm{e}^y + 1} \, \mathrm{d} y \\
&= \int \limits_0^a (a-y)^2 \, \mathrm{d} y + 4 a \frac{\pi^2}{12} \\
&= \frac{a}{3}(\pi^2 + a^2)
\end{align}
for $a \in \mathbb{R}$ as desired. Note that we had to combine the two integrals over $y$ and $z$ in a particular way to obtain this result, which is why some computer programs may be unable to evaluate them individually.


问:
If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod a$ and $z\equiv y\pmod b$

If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod{a}$ and $z\equiv y\pmod{b}$

What I have so far:

Let $z \equiv x\pmod{\frac{a}{\gcd(a,b)}}$ and $
z \equiv y\pmod b
 $. Then by the chinese remainder theorem there is a unique $z\pmod{\text{lcm}(a,b)}$ which satisfies this...

Is this the right approach here? I can't figure out how to get from $$z \equiv x\pmod{\frac{a}{\gcd(a,b)}}$$ what I need.

答:
Existence: $\, x\!+\!ja = z = y\!+\!kb\, \Rightarrow\, (a,b)\mid ja\!-\!kb = y-x,\,$ so $\, y-x = e(a,b)\,$ for some $\,e.$

Bezout $\Rightarrow\exists\, c,d\!:\,  ac\!-\!bd = (a,b),\,$ so  $\,ace\!-\!bde = e(a,b) = y\!-\!x\,$
so  $\, x \!+\! (ce)a = z = y\!+\!(de) b$

Uniqueness: $ $  mod $\, a,b\!:\ z'\equiv z\,\Rightarrow\, a,b\mid z'-z\,\Rightarrow\ {\rm lcm}(a,b)\mid z'-z$


问:
Is there a known representation for this set derived from a Lie group $\subseteq \text{SU}(n)$?
Let $G \subseteq \text{SU}(n)$ be a Lie group for $n \in \mathbb{N}$, with a proper Lie subgroup $H \subset G$ having Lie algebra $\mathfrak{h}$ such that $H = e^{\mathfrak{h}}$. Let $g_0 \in G$ be an element of $G$.

I know that $\mathfrak{h}$ constitutes a linear subspace of $\mathfrak{su}(n)$, and hence is represented by a vector space spanned by skew-Hermitian matrices. Hence let $\{b_i\}_{i = 1}^{m}$ be a basis for $\mathfrak{h}$, where each $b_i$ is an order-$n$ skew-Hermitian matrix.

Now, consider the set $$H' = g_0H=\{g_0h\;|\;h \in H\}.$$ If $g_0 \notin H$, this cannot be a Lie group since it doesn't contain the identity, however it is clearly a differentiable manifold $\subseteq \text{SU}(n)$.

My question is: Is there a special name for such a set? Does it have an associated algebra (not a Lie algebra, but some equivalent with a matrix representation)? In particular, is the algebra representable by some linear or linear-affine space whose basis can be computed in a straightforward way from $\{b_i\}$?

答:
What you consider is commonly called a left coset of $H$ in $G$ (which is standard language in group theory). In a Lie group, such a left coset is a submanifold which is diffeomorphic to $H$ (with the diffeomorphism given by left multiplication by $g_0$). Moreover, you can make that space of all left cosets into a smooth manifold, which is exactly the homogeneous space $G/H$. This comes with a smooth projection $p:G\to G/H$ whose fibers (i.e. the pre-images of points) are exactly the left cosets.

I don't think that there is something like an algebra associated to it. Indeed in each point of a coset that tangent space to the coset consists exactly of the values of the left invariant vector fields $L_X$ with $X\in\mathfrak h$, the Lie algebra of $H$. So the corresponding subspace of $\mathfrak g$ is $\mathfrak h$ itself.


问:
Convergence of the series $\sum_ {n\geq1} \frac {(f(n) +P(n)) \pmod {Q(n)}} {D(n)}$

Under what conditions does the series $$\sum_ {n = 1}^\infty \frac {(f(n) +P(n)) \pmod{ Q(n)}} {D(n)}$$  converge?

Here $\text{P}$, $\text{Q}$ and $\text{D}$ are polynomials, with $\text{deg}(Q)= \text{deg}(D)-1$.

Also $f(n)= \displaystyle \sum_{r=2}^{k} a_{r} r^n$ where $ \{a_{r} \}_{r=2}^k$ are real numbers and k is a natural number with k>2. k and the degree of P must be larger than the degree of Q.

Here and here particular cases of this question have been answered by the user @SangchulLee.
I'd like to know in which cases this series converges. (I assume they are rare but Sangchul Lee has already found some). I'm getting somewhere with this so don't flag me yet!

答:
As noted in the comments, heuristically the series will diverge if $f(n) \neq 0$. A literature search through equidistribution theorems would be the first thing to do if you wanted to prove it.

So, suppose $f(n) = 0$. Sangchul's classification for the $D(n) = n^2$ case generalizes to the present case without difficulty. The tweaks:

$B$ is now $B(x)$, with $\deg B(x) < \deg Q(x) < \deg D(x)$.

First case: $\{B(n)/Q(n)\}$ still becomes $B(n)/Q(n)$ for $n$ large and $\sum_{i=1}^\infty B(n)/D(n)$ still converges since $\deg D(x) - \deg B(x) \geq 2$.

Second case: the lower bound becomes $\epsilon \sum_{k=1}^\infty \frac{Q(ak+b)}{D(ak+b)} + O(1)$. Since $\deg D(x) - \deg Q(x) = 1$, this still diverges by comparison with the harmonic series.

Third case: the sum becomes $\sum_{n=1}^\infty \frac{Q(n)}{D(n)} \left\{\frac{P(n)}{Q(n)}\right\}$ where the term in braces remains equidistributed mod $1$. This again diverges by comparison with the harmonic series.

Conclusion: the series $\sum_{n=1}^\infty \frac{P(n) \pmod{Q(n)}}{D(n)}$ with $\deg Q(x) = \deg D(x) - 1$ converges if and only if $P$ is of the form
$$P(x) = Q(x) \sum_{k=0}^n c_k \binom{x}{k} + B(x)$$
where $B(x)$ is a real polynomial with $\deg B(x) < \deg Q(x)$.

Hence there's no more interesting cases than the ones already found, so long as you believe the exponential heuristic.


问:
Find shortest length of rod divided into 10 pieces in a geometrical progression

A rod one metre in length is divided into $10$ pieces whose lengths are in geometrical progression. The length of the longest piece is eight times the length of the shortest piece. Find, to the nearest millimetre, the length of the shortest piece.

I am working through a pure maths book as a hobby. I believe the length of shortest piece = $a$. Length of longest piece $= ar^{9}$, because

$$\frac{ar^{9}}{a} = 8 \implies r^{9} = 8 \implies r^{3} = 2 \implies r = 2^{\frac{1}{3}}$$

$$S_n = \frac{a(r^{10} - 1)}{r - 1} = \frac{a((2^{1/3})^{10} - 1)}{r - 1} = \frac{a(2^{10/3} - 1)}{r -1}$$

$$\implies \frac{9.9079}{4/3} = 1000 \implies a \approx 135$$

but the book says the answer is $29$ mm.

答:
Your mistake is in the last step. It should be:

$S_n =\frac{a \cdot (2^{10/3} - 1)}{2^{1/3} - 1} \approx a \cdot 34.93$

or $a \approx 28.63 \approx 29$

as given in the solution


问:
what is a path called that visits every vertex of a graph at least once?
As I understand it, a Hamiltonian path visits every vertex of a graph exactly once. Is there a name for a path which visits every vertex at least once?

Some graphs may be such that a cycle visiting every vertex, must visit some vertices more than once. I'd like to talk about the shortest such cycles.

答:
A path doesn't repeat vertices by definition, so any path which does this would be a Hamilton path.

In order to allow vertices to be repeated, you should instead call it a "walk" or "trail" (the difference between the two is whether edges can be used more than once; in a walk they can). I would therefore call this a "covering walk". It seems this terminology has been used before: see this book. However, I would define it if I was going to use it.

An alternative is "spanning walk"; see this paper.


问:
Show that $X$ is bounded in $L^{2}$ iff $\sum_{n \geq 0} \mathbb{E}\left(\Delta_{n}^{2}\right)<\infty$.
Let $X=\left(X_{n}\right)_{n \geq 0}$ be a martingale in $L^{2},$ let :
$$
\Delta_{0}=X_{0}, \quad \Delta_{n}=X_{n}-X_{n-1}, n \geq 1
$$

Show that $X$ is bounded in $L^{2}$ iff $\sum_{n \geq 0} \mathbb{E}\left(\Delta_{n}^{2}\right)<\infty$.

I've already shown that :

$$E(\Delta^2_n) = E(X^2_n)-E(X^2_{n-1})$$ and that $\{\Delta_n\}_n$ is an orthogonal system in $L^2$, I'm not sure if that would help though.

Body:
Hint

$$X_n^2=X_0^2+\sum_{i=1}^n(X_{i}^2-X_{i-1}^2)$$


问:
Let $V = \{x \in \mathbf{R}^3 \mid x_1+2x_2 -x_3=0 \}.$ Determine $\dim V$.

Let $V = \{x \in \mathbf{R}^3 \mid x_1+2x_2 -x_3=0 \}.$ Determine $\dim V$.

The dimension is the number of vectors in the basis set. Here $x_1,x_2$ and $x_3$ are scalars not vectors so how can the dimension be determined here? Also $x_3 = x_1+2x_2$ so $x_3$ is a linear combination of $x_1$ and $x_2$. This somehow suggest that $\dim V = 2$, but I'm not sure. What can I do?

答:
Observe that each vector $x \in V$ can be written on the form

$$\begin{bmatrix}
x_1 \\
x_2 \\
x_1 + 2x_2 \end{bmatrix} = x_1 \begin{bmatrix}
1 \\
0 \\
1\\ \end{bmatrix} + x_2 \begin{bmatrix}
0 \\
1 \\
2 \end{bmatrix}$$

Hence, these two vectors span $V$. They are clearly linearly independent, so they form a basis, and the dimension is 2.

Rank-Nullity Theorem-Approach: Observe that $V$ is the null space of the matrix

$$A = \begin{bmatrix}
1 & 2 & -1 \\
0 & 0 & 0 \\
0 & 0 & 0 \end{bmatrix}.$$

$A$ is clearly a rank 1 matrix, so by the Rank-Nullity Theorem

$$\dim V = \dim (\text{Nul} (A)) = 3-\text{rank}(A)=2$$


问:
One equation equivalent to two equations
Two circles can intersect. I want to find one equation with a set of solutions equivalent to two equations.
$$o_1:x^2-2a_{1}x+{a_1}^2+y^2-2b_{1}y+{b_1}^2-{r_1}^2=0\\
o_2:x^2-2a_{2}x+{a_2}^2+y^2-2b_{2}y+{b_2}^2-{r_2}^2=0$$
Now addition gives an another circle. Subtraction gives a line – if I subtract zero from two sides of $o_1$ equation and do the same on $o_2$ equation, I have got :
$$o_1:(-2a_{1}+2a_{2})x+(-2b_{1}+2b_{2})y+{a_1}^2-{a_2}^2+{b_1}^2-{b_2}^2-{r_1}^2+{r_2}^2=0\\
o_2:(-2a_{2}+2a_{1})x+(-2b_{2}+2b_{1})y+{a_2}^2-{a_1}^2+{b_2}^2-{b_1}^2-{r_2}^2+{r_1}^2=0$$
I thinked I can add to both side anything. Result is one equation that is by no means equivalent to the system of equation I staryed with. Can you point my fault ?

答:
Whatever the transformation you apply, the original equations remain. You thought from

$$\begin{cases}o_1\\o_2\end{cases}$$
(two circles)
to
$$\begin{cases}o_1-o_2\\o_2-o_1\end{cases}$$
(twice the same straight line),

but in fact your system is now

$$\begin{cases}o_1\\o_2\\o_1-o_2\\o_2-o_1\end{cases}$$ (the two circles and twice the line).

The solutions are still two, one or no intersection points.

Note that any linear combination of the initial equations gives you the equation of a circle (or exceptionally a straight line), that goes through the same common intersection.


问:
Find the expectation of lottery game
I came across this problem from a probability practice book. Could someone give me a hint?

Suppose you have N balls and M of them are red(others aren't red). You keep picking one ball out and NOT putting it back until you get one red ball. Find the expectation of a number of balls you need to pick out.

My approach is to use recursion. Let $X_k$ denote the distribution of number of balls I need to pick to get a red ball with k balls in the pool. Then,

$E(X_k)=\frac{M}{k} + \frac{k-M}{k}(1+E(X_{k-1}))$ , with $E(X_M) = 1$

as with M ball left in the pool, it should be immediate to pick a red ball. But then I end up an equation that I couldn't solve.

$E(X_N) = 1+\frac{N-M}{N}(1+\frac{N-1-M}{N-1}(1+...(1+\frac{1}{M+1}(1+1))))$

can anyone give me a hint or guide me please?

答:
I liked your approach of searching for a recurrence relationship! Its definitely something I would have tried!

Let us think of a slightly different game which you should be able to see is identical to your one.

Let us get $N$ black cards and $M$ red cards. Lets shuffle these well. Notice that your problem is the same as the expected number of cards we must pick of the top until a red card appears.

Let us think of a way to answer that question. Firstly we can add a joker aswell that will be seen as a start position. We can consider the red and joker as "special cards" and the black cards as standard.

Now notice in a well shuffled deck we have  $M+1$ special cards, the $M$ red and $1$ joker and $N$ standard cards. Hence we have a total of $N+M+1$ cards. Hence the expected difference between consecutive special cards is $\frac{N+M+1}{M+1}$

So lets draw cards like this. We consider the joker as the "top of the deck" so we shuffle the cards then locate the joker and start drawing from there. We already saw that the expected difference between consecutive special cards, i.e the joker and the first red card is  $\frac{N+M+1}{M+1}$ so this is our answer.

$\frac{N+M+1}{M+1} = 1 + \frac{N}{M+1}$ if you wanted it in a more concise way

Quick notice that all this joker shinanigans does nothing to change the "randomness" or fairness. It is a perfectly valid way of dealing cards randomly. Try it out.

Title: Find the expectation of lottery game


问:
Probability example for homework
There's a highway between two towns. To reach the other, people must pay 10 dollars for cars and 25 dollars for bigger vehicles. How big income can we expect if the 60 percent of vehicles are cars and there are 25 incoming vehicles per hour?

What kind of distribution does it follow, and how to calculate with that?

答:
First of all, among  $25$ incoming vehicles per hour, $25\cdot 60%=15$ are cars

and the number of bigger vehicles be $25-15=10$

Now we can calculate payment from the $10$ cars and  the rest $10$  bigger vehicles

Title: Probability example for homework


答:
$V=\{x\in\mathbb{R}^3\,|\,x\cdot(1,2,-1)=0\}$.

Thus, $V$ is the plane that contains the origin and is orthogonal to $(1,2,-1)$.
Hence, $\dim V=2$.

Body:
Let $V = \{x \in \mathbf{R}^3 \mid x_1+2x_2 -x_3=0 \}.$ Determine $\dim V$.

The dimension is the number of vectors in the basis set. Here $x_1,x_2$ and $x_3$ are scalars not vectors so how can the dimension be determined here? Also $x_3 = x_1+2x_2$ so $x_3$ is a linear combination of $x_1$ and $x_2$. This somehow suggest that $\dim V = 2$, but I'm not sure. What can I do?


问:
Method of variation of parameters for the following DE
$$\frac{d^2 y}{dx^2}-y=e^{-x}\sin(e^{-x})+\cos(e^{-x})$$
solved the CF part facing issue with PI

Body:
$y''-y=0$ has solutuons
$y_1=e^x, y_2=e^{-x}, W(x)=-2$
Solution of $$Y"(x)-Y(x)=e^{-x}\sin e^{-x}+\cos e^{-x}=f(x)~~~(1)$$
Can be written as $$Y(x)=C_1(x) y_1(x)+ C_2(x) y_2(x),~~~~(2)$$ where
$$C_1(x)=-\int \frac{y_2 f(x)}{W} dx+D_1, ~~~C_2=\int \frac{y_1 f(x)}{W} dx+D_2$$
So $$C_1(x)=\frac{1}{2}\int -e^{-x}[e^{-x}\sin e^{-x}+\cos e^{-x}] dx$$
$$C_1(x)=\frac{1}{2} \int (t\sin t+ \cos t) dt=-t \cos t+2\sin t=-e^{-x}\cos e^{-x}+2 \sin e^{-x}.$$
$$C_2(x)=\frac{-1}{2}\int \sin e^{-x}+e^{x} \sin e^{-x} dx=\frac{-1}{2}e^{x}\cos e^{-x}.$$
Insewrting them in (2), we get the complete solutions with $D_1,D_2$ as undetermined constants.


问:
Prove that $\mathbb{Q}(\sqrt{2},\sqrt[3]{3})=\mathbb{Q}(\sqrt{2}\sqrt[3]{3})=\mathbb{Q}(\sqrt{2}+\sqrt[3]{3})$
Showing that $\mathbb{Q}(\sqrt{2},\sqrt[3]{3})$ has degree 6 over $\mathbb{Q}$ is straighforward:
It contains $\mathbb{Q}(\sqrt{2})$ and $\mathbb{Q}(\sqrt[3]{3})$ which are degree 2 and 3 over $\mathbb{Q}$ and since 2 and 3 are coprime it follows that $[\mathbb{Q}(\sqrt{2},\sqrt[3]{3}):\mathbb{Q}]=6$.

Then since $\mathbb{Q}(\sqrt{2}\sqrt[3]{3})\subset \mathbb{Q}(\sqrt{2},\sqrt[3]{3})$ and $x^6-72$ is the minimal polynomial of $\sqrt{2}\sqrt[3]{3}$ it follows that  $[\mathbb{Q}(\sqrt{2},\sqrt[3]{3}):\mathbb{Q}(\sqrt{2}\sqrt[3]{3})]=1$ and so $\mathbb{Q}(\sqrt{2},\sqrt[3]{3})=\mathbb{Q}(\sqrt{2}\sqrt[3]{3})$.

But I can't figure out how to prove the last equality. Any help is appreciated!

答:
So after some thinking, I came up with two solutions:

Solution 1

Let $\alpha=\sqrt{2},\beta=\sqrt[3]{3}$ and $\gamma=\alpha+\beta$. Let $L=\mathbb{Q}(\alpha, \beta)$, $K=\mathbb{Q}(\gamma)$ and suppose that $\alpha,\beta\not\in K$. Since if one of $\alpha,\beta$ is in $K$, we get the other one for free it follows that $L=K(\alpha)=K(\beta)$. Then the minimal polynomial of $\alpha$ in $K[X]$ is of degree 2 since $\alpha$ is a root of $X^2-2$ and we assumed $\alpha\not\in K$. Since $X^3-3$ has one real root and two non-real roots it follows that it is the minimal polynomial of $\beta$ in $K[X]$. Hence we conclude
$$2=[K(\alpha):K]=[L:K]=[K(\beta):K]=3.$$
Which is a contradiction and so $L=K$ as desired.

Solution 2

We know that $\gamma-\alpha=\beta$ so $(\gamma-\alpha)^3=3$. Expanding the left side we get
$$\gamma^3-3\gamma^2\alpha+6\gamma-\alpha^3=3$$
and so $\alpha=\frac{\gamma^3+6\gamma-3}{2+3\gamma^2}\in K$. Therefore $\beta=\gamma-\alpha\in K$ and so $K=L$.


问:
Estimate for a $\operatorname{E}_1$ sum
For $r>0$ we define
$$\operatorname{E}_1(r) := \int_{r}^\infty \frac{e^{-t}}{t}dt.$$
This defines a positive strictly decreasing function with logarithmic singularity at $r=0$. Breaking the integral at $t=1$ gives you the estimate
$$\operatorname{E}_1(r) \le \max(0,-\log(r))+e^{-r}.$$
I need to estimate
$$f(r):=\sum_{n =1}^\infty \operatorname{E}_1(n^2r).$$
Is there a $C>1$ with
$$f(r) \le C \operatorname{E}_1(r)$$
for all $r>0$? If so, what is the least such $C$?

Or do we have
$$
f(r)<-C\log(r)
$$
for some $C>1$ for small values of $r$?

答:
Obviously, $$f(r)=\int^\infty_r\sum^\infty_{n=1}e^{-n^2t}\,\frac{dt}t.\tag1$$ But
$$\lim_{h\to0}\sum^\infty_{n=1}h\,e^{-n^2h^2}=\int^\infty_0e^{-x^2}\,dx=\frac{\sqrt{\pi}}2,$$ with $h=\sqrt{t}$ we get
$$\sum^\infty_{n=1}e^{-n^2t}\sim\frac12\,\sqrt{\frac{\pi}t}.$$ Plugging this into (1), we have $$f(r)\sim\sqrt{\frac{\pi}r}.$$

Title: Estimate for a $\operatorname{E}_1$ sum


问:
Dividing $7$ balls into $5$ baskets and finding the probability each basket has at least 1 ball
We are given $7$ balls and $5$ baskets. We want to place each ball into a basket and the probability of each ball assigned to a specific basket is independent of each other. How do we find the probability that there is at least $1$ ball in each basket?

I am aware that we will need to use the inclusion exclusion formula, but how do I find the probabilities?

Let $P(A_i)$ be the probability that the $i^{th}$ basket has an "occupant". We want to find
$$P(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5) = 1-P(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5)^c = 1- \bigcup_{i=1}^5 A_i$$

How do I find the probabilities from here?

EDIT: Balls are distinguishable.

答:
It does not matter whether balls are identical or distinct. This is a question on probability and not a question on arrangements. Here we treat balls distinct.

Applying P.I.E, number of arrangements where none of the boxes are empty

$ = 5^7 - 5 \cdot 4^7 + {5 \choose 2} 3^7 - {5 \choose 3} 2^7 + {5 \choose 4} 1^7 = 16800$.

Total number of arrangements without restrictions $ = 5^7$

So the probability $ = \displaystyle \frac{16800}{5^7}$.

Another way to go about it is using Stirling Number of the second kind which will return number of ways to arrange $7$ balls into $5$ indistinguishable groups. You then multiply it by $5!$ as boxes are distinct.

So desired probability $ = \displaystyle \frac{5! \cdot StirlingS2[7,5]}{5^7} = \frac{5! \cdot 140}{5^7}$ which is same as above.

EDIT:

While you started with P.I.E which is a more general approach, I wanted to show that you can surely attempt to solve it directly as well given numbers are small.

$7$ balls in $5$ boxes and none of the boxes are empty. So either one of the boxes has $3$ balls or two of the boxes have $2$ balls each. Rest of the boxes will have $1$ ball each.

case $1$: Number of ways to select $3$ balls that are together is $\displaystyle {7 \choose 3} = 35$

case $2$: Number of ways to select two set of $2$ balls is $\displaystyle \ \frac{1}{2} {7 \choose 2} {5 \choose 2} = 105$

Now we assign these groups to boxes by multiplying by $5!$.

So number of permissible arrangements $ =  (105+35) \cdot 5!$. We divide it by $5^7$ to find probability.


问:
Lower Bounds on Markov's Inequality

Problem 20.3
If $R$ is a nonnegative random variable, then Markov’s Theorem gives an upper
bound on $Pr[R \geq x]$ for any real number $x \gt Ex[R]$. If b is a lower bound on R, then Markov’s Theorem can also be applied to $R - b$ to obtain a possibly different bound on $Pr[R \geq x]$.

a)  Show that if $b > 0$, applying Markov’s Theorem to $R - b$ gives a smaller
upper bound on $Pr[R \geq x]$ than simply applying Markov’s Theorem directly to R.

b) What value of $b > 0$ in part (a) gives the best bound?

This question is from Mathematics for Computer Science text book (MIT text for discrete math course). I would like to receive some help with this problem and if possible to send any resources to check if my solution is right or not. I am using the textbook but the problem is that I don't have a way to verify my solutions.

答:
Since $R-b\ge 0$ by assumption, a simple application of the Markov's inequality gives $$\Pr(R\ge x)=\Pr(R-b\ge x-b)\le \frac{\text{Ex}[R-b]}{x-b}=\frac{\text{Ex}[R]-b}{x-b}.$$
Now, observe that $$f(b):=\frac{\text{Ex}[R]-b}{x-b}\le \frac{\text{Ex}[R]}{x}$$ holds on $0\le b < \text{Ex}[R]$ and that $f(b)$ is monotonically decreasing on $0\le b < \text{Ex}[R]$ (you can sketch a graph and verify these results).

Moreover, notice that the upper bound $\frac{\text{Ex}[R]-b}{x-b}$ on $\Pr(R\ge x)$ approaches to $0$ as $b\uparrow \text{Ex}[R].$ So, you can make this upper bound tighter and tighter by selecting $b$ to be closer to $\text{Ex}[R]$ from left. Thus, the best (tightest) bound would be when $b$ is the largest lower bound on $\text{Ex}[R].$ However, I'm not sure if I would call it the best bound (although it is certainly the tightest) since this requires further assumptions that $R\ge b$ (so that $R-b$ remains non-negative) and obviously this assumption becomes stronger as we increase $b$.

Edit:

"I still don't get how did you reach the conclusion that $f(b)\le \text{Ex}[R] / x.$":  Simple analysis using derivatives. Also, note that I wrote $f(b)\le \text{Ex}[R] / x$ holds on $[0,\text{Ex}[R])$. In fact, this inequality doesn't hold if $b\in(-\infty,0)\cup(x,\infty).$ I suppose you are familiar with calculus and how functions behave.

Note that $\text{Ex}[R]$ and $x$ are non-negative constants, such that $\text{Ex}[R]<x$. So, you can modify $f(b)$ as $$ f(b)=\frac{\text{Ex}[R]-b}{x-b}=\frac{x-b}{x-b}-\frac{x-\text{Ex}[R]}{x-b}=1-\frac{c}{x-b},$$
where $c=x-\text{Ex}[R]$ is a positive constant. Hence, $$\frac{df}{db}=\frac{-c}{(x-b)^2},$$ which is always negative since $c>0$. We have $b<E[R]<x$, so that we don't have to worry about the function being undefined (i.e., $b=x$). As you mentioned $(\text{Ex}[R]-b)/(x-b)$ and $\text{Ex}[R]/x$ are equal when $b=0$ and noting that $\text{Ex}[R]/x$ is just a constant horizontal line, we clearly have $$\frac{\text{Ex}[R]-b}{x-b}<\frac{\text{Ex}[R]}{x}$$ on the interval $(0,\text{Ex}[R])$ since $df/db$ is negative. Obviously, this inequality holds on $(0,x)$ as well but this is not necessary. So, yes if you don't want to include equality just get rid of $0$.

Title: Lower Bounds on Markov's Inequality


问:
N-Players Gambler's Ruin ranking stability regarding stacks proportionality
I'm interested in N-Player Gambler's Ruin game with p = 0.5 and for each iteration :

randomly pick two players

make them exchange one chip

The result I'm interested in is the ranking probability of the players.
After running some simulations, it seems to me that for 3-player case considering chips stacks of [5, 3, 2] or [50, 30, 20], the probability for each player to be ranked first, second or third is the same (the computation time is not).

Is it true that for N players the ranking probabilities will remain constant when multiplying the stacks by any strictly positive integer number ?

If so, can you point out a known result from which it can be deduced ?

答:
For $n=2$, scaling the initial stack list by a positive integer factor doesn't affect the distribution of winning probabilities.

For $n > 2$, the winning probabilities are still unaffected by a scaling of the initial stack list.

To explain the invariance, choose a given player and regard the other $n-1$ players as a team. Then the invariance for $n=2$ implies the invariance for $n > 2$.

However for $n > 2$, we can't claim such invariance for ranks greater than $1$.

To demonstrate this, take $n=3$.

For a given initial stack list $X=[x_1,x_2,x_3]$, let $P_X$ be the $3{\times}3$ matrix whose $ij$-th entry $P_X[i,j]$ is the probability that player $i$ finishes with rank $j$.

Then for $X=[1,2,3]$ we get
$$
{\large{P_X}}
=
\pmatrix{
\dfrac{1}{6}
&\dfrac{259}{1182}
&\dfrac{121}{197}
\\
\dfrac{1}{3}
&\dfrac{241}{591}
&\dfrac{51}{197}
\\
\dfrac{1}{2}
&\dfrac{147}{394}
&\dfrac{25}{197}
\\
}
$$
whereas for $Y=[2,4,6]$ we get
$$
{\large{P_Y}}
=
\pmatrix{
\dfrac{1}{6}
&\dfrac{537964919}{2460583662}
&\dfrac{252086911}{410097277}
\\
\dfrac{1}{3}
&\dfrac{502077053}{1230291831}
&\dfrac{106039167}{410097277}
\\
\dfrac{1}{2}
&\dfrac{306154879}{820194554}
&\dfrac{51971199}{410097277}
\\
}
$$
Comparing $P_X,P_Y$, while the first column entries (the winning probabilities) are the same, the entries for the other columns (ranks $2$ and $3$), though numerically very close, are not the same.

As regards how the above matrices were computed, here's an example to illustrate the process . . .

Assume an initial stack list of $[a_0,b_0,c_0]$, where $a_0,b_0,c_0$ are positive integers with $b_0\le c_0$.

Let $s=a+b+c$.

For positive integers $a,b,c$ with $b\le c$ and $a+b+c=s$, let $p[a,b,c]$ be the probability that player $1$ finishes with rank $3$ (i.e., player $1$ is the first to tap out), given a current stack list of $[a,b,c]$.

For each such triple $a,b,c$ we have the equation
\begin{align*}
p[a,b,c]
=&\left({\small{\frac{1}{6}}}\right)\Bigl(\\[0pt]
&{\phantom{\left({\small{\frac{1}{6}}}\right)\Bigl(}}{\phantom{+}}\;\,p[a-1,b+1,c]+p[a+1,b-1,c]\\[0pt]
&{\phantom{\left({\small{\frac{1}{6}}}\right)\Bigl(}}+p[a-1,b,c+1]+p[a+1,b,c-1]\\[0pt]
&{\phantom{\left({\small{\frac{1}{6}}}\right)\Bigl(}}+p[a,b-1,c+1]+p[a,b+1,c-1]\\[0pt]
&{\phantom{\left({\small{\frac{1}{6}}}\right)}}\;\,\Bigr)\\[4pt]
\end{align*}
where on the $\text{RHS}$ we apply the substitutions
$$
\left\lbrace
\begin{align*}
p[0,v,w]&=\,1\\[4pt]
p[u,0,w]&=\,0\\[4pt]
p[u,v,0]&=\,0\\[4pt]
p[u,v,w]&=\,p[u,w,v]\;\,\text{if $v > w > 0$}\\[4pt]
\end{align*}
\right.
$$
Thus we have a system of linear equations, one equation for each qualjfying triple $a,b,c$.

Then for an initial stack list of $[1,2,3]$ we get a system of $6$ linear equations in $6$ unknowns which yields
$$
p[1,2,3]=\frac{121}{197}\approx .6142131980
$$
and for an initial stack list of $[2,4,6]$ we get a system of $30$ linear equations in $30$ unknowns which yields
$$
p[2,4,6]=\frac{252086911}{410097277}\approx .6147002800
$$


问:
How to show that a set does not contain a specific string
If I have a set $S$ defined as the smallest set $S$ over an alphabet $A=\left\{ \star, \urcorner,(,), a_0,a_1, \dots \right\}$ ( $S\subseteq \cup_{k \in \mathbb{N}} A^k$) satisfying:

$\bullet \ a_0, a_1, \ldots$  $\in S$

$\bullet $ if $\alpha \in S$ then $ ( \urcorner \alpha) \in S$,

how can I then show for example that $( \alpha \urcorner )$ or $\alpha ()$ is not in the recursively defined set $S$, where $\alpha$ is some element of $S$ (or even  $S\subseteq \cup_{k \in \mathbb{N}} A^k$, for greater generality). Of course I can "see" that this is the case, but how can I prove it ?

Maybe because it seems so easy to see that strings like the above can't be in $S$ I can't up with a proof. (Of course, if $\star \alpha$  were in $S$, intuitively it would be clear, that $S$ woulsn't be the smallest set anymore, but how would I then prove this ?)

答:
Added Remark: This is a solution to the previous incarnation of the question, which was quite different (it asked one to show that no word of shape $\star\alpha$ is in the set).  This is not a solution of the altered question!

It is obvious, and does not require proof (unless, weirdly, it is demanded that you prove it).

What do we mean by "smallest set $S$"?  In the context of this kind of definition, it means the intersection of all the sets satisfying your two bulleted conditions.

Now let $W$ be the set of all words over the alphabet that contains everything except the $\star$,  Then $W$ obviously satisfies the bulleted conditions.  It follows by the definition of $S$ that $S \subset W$, since $W$ is one of the sets that was intersected to make $S$.  And it is clear that no word of the form $\star\alpha$ is in $W$.

Remark about changed question The strategy of a proof does not change much for the altered questions. (But if the question changes again, the strategy might have to change).  For example, look at the set $Z$ of words that do not end with  $()$ or with $($.  It is clear that if $\alpha$ is in $Z$, then the string produced by the second bulleted condition is in $Z$.  So $Z$ is one of the sets intersected to produce $S$.  This implies that $S$ does not contain any string of shape $\alpha()$.


问:
Eigenvalue and algebraic multiplicity
Let $A\in\mathbb{R}^{n}$ be a symmetric and invertible matrix. $\alpha\in\mathbb{R}^{1\times n}$.
$$B=A+\alpha^{T}\alpha A^{-1}$$

All eigenvalues of $B$ are real.

If $a$ is an eigenvalue of $A$ with algebraic multiplicity $k$, then it is also an eigenvalue of $B$ with multiplicity at least $k-1$.

I got stucked at the beginning since $B$ is not always symmetric.

答:
Hints. (I am more accustomed to the convention that a vector in $\mathbb R^n$ denoted by a single letter is a column vector. So, I will write $B=A+uu^TA^{-1}$ instead, where $u=\alpha^T\in\mathbb R^{n\times1}$ is a column vector.)

Note that $A^2+uu^T$ is positive definite. Hence $B=(A^2+uu^T)A^{-1}$ is similar to some real symmetric matrix.

Let $X\in \mathbb R^{n\times k}$ be a matrix whose $k$ columns span the eigenspace of $A$ for the eigenvalue $a$. Then
$$
BXv=aXv+uu^TXv
$$
for any $v\in\mathbb R^k$. What is the dimension of the subspace of all vectors $v$ such that $u^TXv=0$?

Title: Eigenvalue and algebraic multiplicity


问:
If rational $a$, $b$, $c$ satisfy ${1\over{a+bc}}+{1\over{b+ac}}={1\over{a+b}}$, show $\sqrt{(c − 3)(c + 1)}$ is rational
Suppose $a, b, c$ are rational numbers such that $a + bc, b + ac$ and $a + b$ are non-zero, and satisfy
$${1\over{a+bc}}+{1\over{b+ac}}={1\over{a+b}}$$
Prove that $\sqrt{(c − 3)(c + 1)}$ is rational.

答:
A good approach is to try to show that the radicand is a perfect square.

Since $a, b, c$ are rational, therefore $a+bc, b+ac$ and $a+b$ are rational.

Also the given relation is rational.

So try to show that $(c-3)(c+1)$ is a perfect square.


问:
How can I prove $\lim_{m \to \infty}\lim_{n \to \infty} a_{m , n} = \lim_{n \to \infty}\lim_{m \to \infty} a_{m , n}$?
$\{a_{m , n}\}$  is a double sequence of real numbers with the following property.

For every $\epsilon$  we will get a natural number $k$ such that $|a_{m , n} - a_{p , q}| < \epsilon$  for all natural numbers $m , n , p , q > k$.

How can I prove that $$\lim_{m \to \infty}\lim_{n \to \infty} a_{m , n}  ,\quad  \lim_{n \to \infty}\lim_{m \to \infty} a_{m , n} $$   exist, and $$\lim_{m \to \infty}\lim_{n \to \infty} a_{m , n} = \lim_{n \to \infty}\lim_{m \to \infty} a_{m , n}?$$

Can anyone please help me? I think I can show the second part once I am able to prove the first part.

答:
The given condition does not imply the existence of the horizontal and vertical limits. Example:
$$
a_{m,n} = \frac{(-1)^{m+n}}{\min(m,n)} \, .
$$
For $m , n , p , q > k$ with $k >2/\epsilon$ is
$$
 |a_{m , n} - a_{p , q}| \le |a_{m , n}| + |a_{p , q}| \le \frac 1k + \frac 1k < \epsilon \, ,
$$
but $\lim_{m \to \infty} a_{m , n}$ does not exist for any $n$, and $\lim_{n \to \infty} a_{m , n}$ does not exist for any $m$.

$$
\begin{matrix}
1 & -1 & 1 & -1 & 1 & -1 & \cdots \\
-1 & \frac 12 & -\frac 12 & \frac 12 & -\frac 12 & \frac 12 & \cdots \\
1 & -\frac 12 & \frac 13 & -\frac 13 & \frac 13 & -\frac 13 & \cdots \\
-1& \frac 12 & -\frac 13 & \frac 14 & -\frac 14 & \frac 14 & \cdots \\
1& -\frac 12 & \frac 13 & -\frac 14 & \frac 15 & -\frac 15 & \cdots \\
-1& \frac 12 & -\frac 13 & \frac 14 & -\frac 15 & \frac 16 & \cdots \\
\vdots &\vdots &\vdots &\vdots &\vdots &\vdots & \ddots
\end{matrix}
$$

However, if the horizontal and vertical limits
$$
 b_n = \lim_{m \to \infty} a_{m , n} \\
 c_m = \lim_{n \to \infty} a_{m , n}
$$
exist for all $m$ respectively $n$, then the iterated limits $\lim_{n \to \infty} b_n$ and $\lim_{m \to \infty} c_m$ exist as well, and they are equal.