问:
School task for cooperative work
Alice can eat a cake in 10 minutes, a jar of jam in 13 minutes and drink a pan of milk in 14 minutes. Bob can do the same in 6, 6 and 7 minutes. What is the shortest time they can have breakfast with a jar of jam, a pan of milk and a cake?

I have two solutions with different answers:

1-st way.

Alice eats 1/10 of cake in a minute and Bob eats 1/6 of cake in a minute, so they eat 1/10+1/6=4/15 of cake in a minute. So they need 15/4 minutes to eat all the cake.

Alice eats 1/13 of jam in a minute and Bob eat 1/6 of jam in a minute, so they eat 1/13+1/6=19/78 of jam in a minute. So they need 78/19 minutes to eat all the jam.

Alice drinks 1/14 of milk in a minute and Bob drinks 1/7 of milk in a minute, so they drink 1/7+1/14=3/14 of milk in a minute. So they need 14/3 minutes to drink all the milk.

Common time is 15/4 + 78/19 + 14/3 = 2855/228 or 12 minutes and 119/228.

2-nd way.

Alice eats all breakfast for 10 + 13 + 14 = 37 minutes. She eats 1/37 of whole breakfast in a minute.

Bob eats all breakfast for 6 + 6 + 7 = 19 minutes. He eats 1/19 of whole breakfast in a minute.

Together they eat 1/37 + 1/19 = 56/703 of breakfast in a minute.

So they need 703/56 minutes for eating all breakfast or 12 minutes and 31/56.

答:
As the question does not say that they both have to eat/drink each item, here is how we can optimize.

Bob finishes a jar of jam in $6$ minutes. Then starts drinking milk.

Alice starts with eating cake and finishes in $10$ minutes.

At the end of $10$ minutes, the jam is finished, the cake is finished and they are left with $\frac{3}{7}$ of the milk (As Bob finishes $\frac{4}{7}$ in $4$ minutes after finishing jam).

Together they can drink $\frac{3}{14}$ of milk in a minute so in $2$ minutes, they can finish rest of the milk ($3/7$).

So total of $12$ minutes.

Title: School task for cooperative work


问:
Computing Gamma Median by Hand?
I am stuck computing median of Gamma distribution by hand. Let $X$ have gamma distribution with $\alpha = 6$ and $\beta = 2$. I know how to compute the median of this distribution using numerical methods in R, but I am unsure how to compute this quantity by hand. All I know is that the gamma poisson relationship must be invoked. Thus, we could compute the median by solving $1 - P(Y < \alpha) = .5$, where $Y$ ~ $Poisson(x^{*} / \beta)$, with $x^{*}$ representing the median of the gamma distribution. Expanding the Poisson CDF gets really messy, and solving for $x^{*}$ seems really difficult, so any help computing the median by hand would be appreicated. Thanks Stack.

答:
In [1], a sharp bound on the median of gamma distribution is introduced as
$$
n+\frac{2}{3} < median(n) < min(n+log2 , n+\frac{2}{3}+(2n+2)^{-1})
$$
in which the bound decrease with n, the parameter of Gamma distribution $\Gamma(n+1,1) $. It is also mentioned that the asymptotic expansion of median could be derived as
$$
median(n) = n + \frac{2}{3} + \frac{8}{405n} - \frac{64}{5103n^2} + ...
$$
For more information, it's best to review the reference.

[1]: Choi, K. P., On the medians of gamma distributions and an equation of Ramanujan, Proc. Am. Math. Soc. 121, No. 1, 245-251 (1994). ZBL0803.62007.

ContentLicense: CC BY-SA 4.0

Title: Computing Gamma Median by Hand?


问:
minimization of integral of multi-variable function
Let $\alpha \in (0,1) $ be some parameter which we can choose and $Y$ be some random variable (e.g. standard normal distribution), then we can define a function as below (where $v,e < 0$ are two variables):

$S(Y,v,e; \alpha) =  -\frac{1}{\alpha e}\cdot(v-Y) \cdot \mathbf{1}_{(Y \le v)} + \frac{v}{e} - log(-e) - 1 $

If we minimized the expected value with respect to $v$ and $e$, we should get

$$ v=\Phi^{-1}_Y(\alpha)$$

and

$$
e = \frac{1}{\alpha}*\phi_Y( \Phi^{-1}_Y(\alpha) )
$$

答:
Let's first get an analytical expression for $E_Y[S]$ with $Y \sim \mathcal{N}(0,1)$:
\begin{align}
E_Y[S] &= -\frac{1}{\sqrt{2 \pi}} \int_{\mathbb{R}} \frac{1}{\alpha e} (v - y) \mathbf{1}_{\{ y \leq v\}} \exp(-\frac{1}{2} y^2)dy + \frac{v}{e} - \log(-e) -1 \\
&= -\frac{1}{\sqrt{2 \pi}} \int_{- \infty}^{v} \frac{1}{\alpha e} (v - y)  \exp(-\frac{1}{2} y^2)dy  + \frac{v}{e} - \log(-e) -1 \\
& = -\frac{v}{\sqrt{2 \pi}} \int_{- \infty}^{v} \frac{1}{\alpha e}\exp(-\frac{1}{2} y^2)dy +\frac{1}{\sqrt{2 \pi}} \int_{- \infty}^{v} \frac{y}{\alpha e}\exp(-\frac{1}{2} y^2)dy + \frac{v}{e} - \log(-e) -1 \\
&= \frac{-v}{ \alpha e} \Phi_Y(v) - \frac{1}{\alpha e \sqrt{2\pi}}\exp(-v^2/2)+ \frac{v}{e} - \log(-e) -1
\end{align}

Now we are set to get your first equation:
\begin{align}
\frac{\delta}{\delta v} E[ S(Y,v,e; \alpha) ] &= -\frac{1}{\alpha e}  \left( \Phi_Y(v) + \frac{v}{\sqrt{2\pi}}\exp(-v^2 / 2) \right) + \frac{v}{\alpha e \sqrt{2 \pi}} \exp(-v^2 / 2)+\frac{1}{e}\\
&= -\frac{1}{\alpha e} \Phi_Y(v) + \frac{1}{e}
\end{align}

By computing $\frac{\delta}{\delta v} E[ S(Y,v,e; \alpha) ] = 0$ we get the result.

For the second equation:

\begin{align}
\frac{\delta}{\delta e} E[ S(Y,v,e; \alpha) ] &=  \frac{v}{\alpha e^2} \Phi_Y(v) + \frac{1}{\alpha e^2 \sqrt{2\pi}}\exp(-v^2/2) - \frac{v}{e^2} - \frac{1}{e}
\end{align}

We write $\frac{\delta}{\delta e} E[ S(Y,v,e; \alpha) ] =0$ to get:
\begin{equation}
e = \frac{v}{\alpha} \Phi_Y(v) + \frac{1}{\alpha}\phi_Y(v) - v
\end{equation}

To conclude, we use the optimun of $v = \Phi_Y^{-1}(\alpha)$ found in the first equation and the fact that $\Phi_Y(\Phi_Y^{-1}(\alpha)) = \alpha$ to get:

\begin{equation}
e = \frac{v}{\alpha} \alpha + \frac{1}{\alpha}\phi_Y(v) - v = \frac{1}{\alpha} \phi_Y(\Phi_Y^{-1}(\alpha))
\end{equation}

It's not exactly what you are asking for, but I think it's right; I cannot find any typo in my procedure. Maybe the $\frac{1}{1-\alpha}$ it's just $\frac{1}{\alpha}$ in your question.


问:
Calculating derivatives for matrix/vector products
$$
\frac{\sum_{i\in\Omega} (\mathbf q_i-\alpha)^T A(\mathbf q_i-\alpha)}{\sum_{i\in\Omega}((\mathbf q_i-\alpha)^T(\mathbf q_i -\alpha))}
$$

What would be the derivative of the above equation with respect to $\alpha$?

$q, \alpha$: vectors,
A: matrix.

I tried calculating the derivative and I end up getting a zero in the numerator.

Would it be zero or have a numerator${}= \sum_i 2(A-1)(q_i-\alpha)$ ?

答:
Let $\{e_k\}$ denote the standard basis vectors, and use a colon to denote the trace/Frobenius product, i.e.
$$\eqalign{
A:B = {\rm Tr}(A^TB) = {\rm Tr}(B^TA) = B:A \\
}$$
For typing convenience, define the matrices
$$\eqalign{
P &= \alpha{\tt1}^T
 \quad&\implies\quad Pe_k = \alpha \\
Q &= {\tt\large[}q_1\;q_2\;\ldots\,q_n{\tt\large]}
 \quad&\implies\quad Qe_k = q_k \\
R &= (P-Q)
 \quad&\implies\quad Re_k = \alpha-q_k \\
dR &= dP = d\alpha{\tt1}^T \\
}$$
Consider the following function of an arbitrary matrix $M$
$$\eqalign{
\psi &= \sum_{k\in\Omega} (q_k-\alpha)^TM(q_k-\alpha) \\
 &= \sum_{k\in\Omega} (Re_k)^TM(Re_k) \\
 &= \sum_{k\in\Omega} e_k^T(R^TMR)e_k \\
 &= \left(\sum_{k\in\Omega} e_ke_k^T\right):(R^TMR) \\
 &= \Phi :(R^TMR) \\
 &= M:R\Phi R^T \\
}$$
and its differential
$$\eqalign{
d\psi &= M:\big(dR\,\Phi R^T+R\Phi\,dR^T\big) \\
 &= \big(M+M^T\big):dR\,\Phi R^T \\
 &= \big(MR\Phi +M^TR\Phi \big):dR \\
}$$
where $\Phi$ is a diagonal matrix, with ones and zeros along the main diagonal. Depending on what $\Omega$ represents, I assume this could equal the identity matrix $I$ in some (most?) cases.

This function appears in the numerator
$\big(\nu = A:R\Phi R^T\big)$
and in the denominator
$\big(\delta = I:R\Phi R^T\big)$
of your function. So we need to calculate the gradient of their ratio.
$$\eqalign{
\rho &= \delta^{-1}\nu \\
d\rho &= \delta^{-1}d\nu - \nu\delta^{-2}d\delta \\
&= \delta^{-1}(AR\Phi+A^TR\Phi):dR - \nu\delta^{-2}(IR\Phi+I^TR\Phi):dR\\
 &= \delta^{-1}\Big(A+A^T - 2\rho I\Big)R\Phi:d\alpha{\tt1}^T \\
 &= \delta^{-1}\Big(A+A^T - 2\rho I\Big)R\Phi{\tt1}:d\alpha \\
 &= \delta^{-1}\Big(A+A^T - 2\rho I\Big)R\phi:d\alpha \\
\frac{\partial\rho}{\partial\alpha}
 &= \delta^{-1}\Big(A+A^T - 2\rho I\Big)R\phi \\
}$$
where $\phi$ is a vector whose elements equal either one or zero. It is the main diagonal of $\Phi$.


问:
Prove by induction $\left(1-\frac{1}{2}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$
Prove by induction $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{4}\right)\left(1-\frac{1}{8}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$

What would be the best way to solve this by the induction method?

Body:
Hint: Prove that
$$
\left(\frac{1}{4}+\frac{1}{2^{n+1}}\right)
\left(1-\frac{1}{2^{n+1}}\right)
\ge
\frac{1}{4}+\frac{1}{2^{n+2}}
$$


问:
Coloring Two Faces of an Icosahedron
Suppose that you have a solid regular icosahedron (a polytope with 20 sides all of which are
equilateral triangles), and all the sides are white.

(a) In how many ways can exactly two sides be painted red?

(b) In how many ways can one side be painted red and another one side painted blue?

Two colorings considered the same if one can be converted into the other by
rotating the icosahedra in space.

I tried doing it by mapping which sides connected to others, but it didn't seem to help. Any help would be greatly appreciated!

答:
Following @JMoravitz's idea, consider what happens if you color one triangle red and you color a neighboring triangle that shares an edge blue.  All such colorings are equivalent.  The same is true for red-red colorings. On the other hand, if you color a triangle that only shares one vertex blue, then there are two such inequivalent colorings. However, there there is only one red-red coloring.

To complete these arguments, you to first explain why any given triangle can always be rotated to the one initially colored red. Then consider rotations about the centroid of the red triangle.  In the case of red-red colorings, you need to consider a rotation about the shared vertex---this interchanges the two red triangles.

This takes care of the 9 triangles that are distance one (measured in terms of moves from one triangle to a neighboring one that shares an edges) or two away from the initial triangle.  There are 6 more triangles that are distance three away, 3 distance four away, and only one that is distance five away.  You can visualize the distance as the distance between the vertices of the dual graph, the dodecahedral graph.

Title: Coloring Two Faces of an Icosahedron


问:
Show $g^s\in L^1((0,1),\mathbb{R})$ for $s≤1$

Let $g:(0,1)\rightarrow\mathbb{R}$, $g(x)=\frac1{x(1-\ln(x))^2}$. Show that $g^s\in L^1((0,1),\mathbb{R})$ for $s ≤ 1$ and $g^s\notin L^1((0,1),\mathbb{R})$ for $s > 1$.

So for this I tried looking at the singular cases:

For $s=0$ : trivial.

For $s=1$ : $\int^1_0g(x) dx = \big[\frac1{1-\ln(x)}\big]^1_0=1$

For $s=-1$ : $\int^1_0g(x)^{-1} dx=\int^1_0x(1-\ln(x))^2=$ (after long computation) $= \frac54$

I tried also for $s=2$ but it takes too much computation and time, I don't think it's the objective of this exercise.

I know the singular cases are not enough, and I should find something to show it holds for all s,
but in my theory there is not anything about power of functions neither examples. Do you have any hint/tricks?

答:
You do not need to compute the integrals explicitly; it is enough to show that the integrals are (in)finite depending on the value of $s$. One approach is to compare the integrals $\int_{(0,1)} |g(x)|^s \, dx$ with integrals of the form $\int_{(0,1)} x^{\beta} \, dx$ for suitably chosen $\beta$.

Case 1: $s \in [0,1)$: Since $\ln(x) \to - \infty$ as $x \to 0$, we have $(1-\ln(x))^2 \to \infty$ as $x \to 0$. In particular, $$|g(x)|^s = \frac{1}{x^s} \frac{1}{(1-\ln x)^{2s}} \leq \frac{1}{x^s}$$ for small $x>0$, say, for $x \in (0,r)$. Consequently, $$\int_{(0,r)} |g(x)|^s \, dx \leq \int_{(0,r)} \frac{1}{x^s} \, dx \stackrel{s<1}{<} \infty.$$ Noting that $g$ is continuous, hence bounded, on $[r,1]$, we also get $\int_{[r,1]} |g(x)|^s \, dx < \infty$, and so, in conclusion, $g \in L^s((0,1))$.

Case 2: $s>1$: The exponential function grows faster than any polynomial. This implies that we can find for every $\epsilon>0$ some constant $C=C(\epsilon)$ such that $|\ln(x)| \leq C x^{-\epsilon}$ for small $x$, say $x \leq r=r(\epsilon)$. This implies

$$g(x) \geq \frac{1}{x} \frac{1}{(2 \ln(x))^2} \geq \frac{1}{C^2} \frac{1}{x} x^{2\epsilon}$$

for small $x$. Consequently,

$$\int_{(0,1)} |g(x)|^s \, dx \geq \frac{1}{C^2} \int_{(0,r)} \frac{1}{x^s} x^{2\epsilon s} \, dx.$$

As $s>1$, we can choose $\epsilon>0$ small enough such that $2\epsilon s < \frac{1-s}{2}$. Then $s-2\epsilon s>1$, and therefore $\int_{(0,r)} \frac{1}{x^s} x^{2\epsilon s} \, dx=\infty$. Thus, $g \notin L^s((0,1))$ for $s>1$.


问:
What does $\doteqdot$ mean?
I am reading the following document of Solitary waves page $14$. And I found the following symbol $\doteqdot$.

What does  $\doteqdot$ mean? For example:
$$y_t \doteqdot -c_0y_x $$

答:
Search "Geometrically equal to" on this page

https://www.w3.org/TR/MathML2/isoamsr.html

I don't know what that means, but it's the right symbol.

Title: What does $\doteqdot$ mean?


问:
Understanding Integration by Substitution 'Scale factor'
I was hoping to gain some intuition as to the process of integration by substitution and how exactly it works when evaluating a definite integral in one dimension.

So when evaluating a definite integral in one dimension, $\int_a^b f(x) dx$, you divide the $x$-axis between $a$ and $b$ into $n$ equal sections of length $\delta x$ and then you have that $\int_a^b f(x) dx = lim_{n \rightarrow \infty} \sum_{i=1}^{n}f(x_i)\delta x$

So then when you use integration by substitution to evaluate the equivalent integral, you use a change of variables, $u(x)$ which means you are now integrating along a new $u$-axis between limits $u(b)$ and $u(a)$. You compute the integral in the exact same way to obtain $\int_{u(a)}^{u(b)} f(x(u)) du$. However you then have to multiply by the 'scale factor' $\frac{dx}{du}$, and I'm having difficulty understanding this. I guess that the problem is that since the difference between $u(b)$ and $u(a)$ on the $u$-axis is in general different from the difference between $b$ and $a$ on the $x$-axis that this means that $du$ and $dx$ are not equal in size and thus multiplying by the 'scale factor' basically has the effect of making every section of length $du$ back into the 'proper length' $dx$. Is this the case?

答:
Yes, intuitively you're right.

So if $u = g(x)$.

Then $\frac{du}{dx} = g'(x)$

Then we can intuitively think in terms of differentials

$du = g'(x)dx$

So $dx = \frac{du}{g'(x)}$

So you can substitute this $dx$ back into the integrand to get

$\int_a^b f(x) dx$

$\int_{u(a)}^{u(b)} f(x(u)) dx$

$=\int_{u(a)}^{u(b)} f(x(u)) \frac{du}{g'(x)}$

If you want to be completely rigorous though, we're using the chain rule in reverse... the "integration by substitution" theorem is proven here:

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

In reality the cross multiplying by $dx$ is just a mnemonic... a book-keeping tool that works well to accomplish what the theorem is saying. I guess there is a theory of differentials that could make this multiplying by dx rigorous.


问:
Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.
Prove $L=\{ 1^n|  n\hspace{2mm}\text{is a prime number} \}$ is not regular.

It seems to use one Lemma: Pumping Lemma.

答: By Pumping lemma there exists $m \geq 1$ such that every word $1^p \in L$ with $p \geq m$ can be written as $1^p = xyz$ for some $x, y, z \in \{ 1\}^*$, $|y| \geq 1$ so that $xy^kz \in L$ for all $k$. Let $p$ be a prime larger that $m$ and let $k = p + 1$ to get a contradiction. </p>

ContentLicense: CC BY-SA 3.0


问:
$ \lim_{x \to +\infty} \frac{f(x+1)}{f(x)} = k$ with $0 \leq k<1 $ find the nature of $\int_{0}^{+\infty} f(t)dt$
let$ \:f: \mathbb{R}_{+} \to \mathbb{R}_{+}^{*}$ continious

$ \lim_{x \to +\infty} \frac{f(x+1)}{f(x)} =  k$ with $0 \leq k<1  $

find the nature of $\int_{0}^{+\infty} f(t)dt$

using the definition of the limit, it exists $(A,α) \in \mathbb{R}_{+}\times [0;1[
$ such as $ \forall x \geq A, \frac{f(x+1)}{f(x)} \leq α$
using recurence we have $ \forall n \in \mathbb{N},\forall x \geq A, f(x+n) \leq α^n f(x) $, thus $\lim_{n \to +\infty} f(x+n)=0$ with $x \geq A $ set, thus  $\lim_{x \to +\infty} f(x)=0$

then we have, $\frac{f(n+1+x)}{f(n+x)} \leq \frac{α^{n+1}}{α^n}$ thus (comparaison with a geometric serie) $\sum f(x+n) $converges with $x \geq A $ set

To sum up $\exists A \in \mathbb{R}_{+} : \forall x \geq A, \sum f(x+n) $converges
and I cannot go further;

答:
Hint:

Show that $f(x)$ is decreasing for $x\geq A$. Then you can use your idea of the geometric series to trap the integral along the tail between two Riemann sums, one with left end point method and the other with right end point method. This is essentially the integral test.

Obviously, $f$ integrates on $[0,a)$ since $f$ is continuous and the set is bounded.


问:
determining whether $H$ is a nonplanar graph

Determine, with justification, whether the graph $H$ below is nonplanar.

I think it's nonplanar as I can find a $K_{3,3}$ subdivision for it. I can describe the subdivision as follows. Join vertex $8$ to vertex $9$ (as they are connected by the path $812349$). Then add an edge from vertex $4$ to vertex $9$ (as they are connected by the path $439$). Add an edge from $4$ to $7$ as they're connected by the path $4397$. Now delete the edges $18, 12, 23, 34, 14, 39, 37, 79,29$ (since we added edges $49$ and $89$, there are $9$ edges remaining). Delete the vertices of the resulting graph with degree zero, which are $1, 2,3.$ The result is the $K_{3,3}$ graph with vertices $5,7,9$ on one side of the graph and vertices $8,6,4$ on the other, which shows that $H$ has a $K_{3,3}$ subdivision, and hence is nonplanar.

I think my reasoning may be incorrect as I obtained the subdivision incorrectly. If so, is there a way to obtain a correct $K_{3,3}$ subdivision? I know the $5$ vertices of degree $4$ are all joined by a path to each other, so that might be useful.

答:
I know this isn't exactly what you asked for, but there's another, easier way to prove the graph is non-planar, based on Tutte's conflict graph theorem.  Because the graph has a Hamilton cycle, it's easy to tell whether or not it's planar.  Let's redraw the graph:

To attempt to embed the graph in the plane, we can start by placing the graph nodes at the vertices of a regular polygon, in the order of the cycle, and represent the remaining edges as diagonals.  Consider the diagonals of the polygon.  If two of them intersect when they are both drawn inside the polygon, then they will also intersect if both are drawn (as graph edges) outside the polygon.  Now look at the three diagonals colored red.  Each intersects both the others, so at least two must be drawn inside or at least two must be drawn outside, and there is no planar embedding.

The conflict graph is the graph whose vertices are the diagonals, in which two vertices are adjacent if the two diagonals intersect when drawn in the same region.  A graph with a Hamilton cycle is planar if and only if the conflict graph is bipartite.

(I had to change the labelling of the vertices, because Geogebra won't accept a number as the label of a point.)


问:
Proving regular expression with induction - $(a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast} \cup (ab \cup ba)^{\ast}$
Let $L_{a}$ be the language $\{w \in \{a,b\}^{\ast} : |w|_{a} =  |w|_{b}\}$ and let $L_{b}$ be the language $\{w \in \{a, b\}^{\ast} : $ aa or bb is substring of $w\}$. We claim that
$L_{a} \cup L_{b}$ is regular, and, for such we will prove that the regular expression

$R = (a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast} \cup (ab \cup ba)^{\ast}$  describes $L_{a} \cup L_{b}$.

Proof. We will prove that $L(R) = L_{a} \cup L_{b}$.

Proof of $L(R) \subseteq L_{a} \cup L_{b}$.

Suppose that $w \in L(R)$, we will prove that $w \in L_{a} \cup L_{b}$ by induction on $|w|$.
If $|w| = 0$, we have $w = \epsilon$, thus, $w \in L_{a}$ and therefore
$w \in L_{a} \cup L_{b}$. For $|w| = 1$, this case is not possible since
$a \notin L(R)$ and $b \notin L(R)$, but since, $a \notin L_{a}$ and $b \notin L_{b}$,
thus for this case in particular $L(R)$ does not contradict the definitions of $L_{a}$
and of $L_{b}$.

If $|w| = 2$, then we have the following possibilities: if $w = aa$ or $w = bb$, then we have that $w \in L_{b}$, hence $w \in L_{a} \cup L_{b}$.
If $w = ab$ or $w = ba$, then twe have that $w \in L_{a}$ , therefore $w \in L_{a} \cup L_{b}$.

If $|w| \geq 3$, then we have that $w = aax$, or $w = bbx$, or $w = abx$, or $w = bax$
with $x \in L(R)$. The cases that $w = aax$ or $w = bbx$, we have that $w \in L_{b}$ for
any $x \in L(R)$, hence $w \in L_{a} \cup L_{b}$. The cases that $w = abx$, or $w = bax$,
we have that $w \in L_{a} \cup L_{b}$ if and only if $x \in L_{a} \cup L_{b}$. But since
$x \in L(R)$ and $|x| < |w|$ we have $x \in L_{a} \cup L_{b}$ by induction hypothesis. Thus,
if $x \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast})$, then $x$ have substring $aa$ or substring $bb$, hence $x \in L_{b}$, and thus  $w \in L_{b}$. Obviously, the cases in which $|w|_{a} = |w|_{b}$, $w$ is also in $L_{a}$. Therefore $w \in L_{a} \cup L_{b}$.

However, if $w = abx$, or $w = bax$, and $x$ does not have $aa$ and does not have $bb$ as substring, then we have that $x \in L((ab \cup ba)^{\ast})$, and by the induction hypothesis  $x \in L_{a}$, thus we have $w \in L_{a}$. Therefore $w \in L_{a} \cup L_{b}$.

Therefore, given that we take a arbitrary $w$ of $L(R)$, then we can conclude that $L(R) \subseteq L_{a} \cup L_{b}$.

Proof of $L_{a} \cup L_{b} \subseteq L(R)$.

Suppose that $w \in L_{a} \cup L_{b}$, we will prove that $w \in L(R)$  by induction on $|w|$. Since $w \in L_{a} \cup L_{b}$ then $w \in L_{a}$ or $w \in L_{b}$. If $|w| = 0$, we have that $w = \epsilon \in L_{a}$, thus $w \in L(R)$. If $|w| = 1$, this case is not possible by the same reason stated previously.

If $|w| = 2$, then we have the following possibilities: If $w \in L_{a}$, we have that $w = ab$ or $w = ba$ hence
$w \in L((ab \cup ba)^{\ast}) \subseteq L(R)$. If $w \in L_{b}$, we have that $w = aa$ or $w = bb$ thus
$w \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$.

If $|w| \geq 3$, then we have the following possibilities: $w = aax$, or $w = bbx$, or $w = abx$, or $w = bax$
with $x \in L_{a} \cup L_{b}$. Since $|x| < |w|$, by the inductive hypothesis we have that $x \in L(R)$ and therefore
$x \in U \cup V$ with $U \subseteq L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast})$ and $V \subseteq L((ab \cup ba)^{\ast})$.
The cases that $w = aax$, or $w = bbx$, we have $x \in U$, but since $aax$ and $bbx$ are in
$L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$, we see that $w \in L(R)$. If
$w = abx$, or $w = bax$, we have the following cases:

If $w = abx$ and $ x \in U$, then we have that $abx \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$,
therefore $w \in L(R)$.
\item If $w = abx$ and $ x \in V$, then we have that $abx \in L((ab \cup ba)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$.

If $w = bax$ and $ x \in U$, then we have that $bax \in L((a \cup b)^{\ast}(aa \cup bb)(a \cup b)^{\ast}) \subseteq L(R)$,
therefore $w \in L(R)$.

If $w = bax$ and $ x \in V$, then we have that $bax \in L((ab \cup ba)^{\ast}) \subseteq L(R)$, therefore $w \in L(R)$.

Since we exhausted all possibilities, given that we take an arbitrary $w$ of $ L_{a} \cup L_{b}$, then we can conclude that $ L_{a} \cup L_{b} \subseteq L(R)$.

So, as we show that $ L(R) \subseteq L_{a} \cup L_{b}$ and $ L_{a} \cup L_{b} \subseteq L(R)$,
we can conclude that $ L(R) = L_{a} \cup L_{b} $. $\square$

Is my proof okay? I am always getting confused in the inductive hypothesis, if I always using the correct number of symbols when I assume that ||≥ for some ∈ℕ.

答:
I’m a little pressed for time and have not actually gone through the details of your argument, because I would prove regularity of $L=L_a\cup L_b$ rather differently. It’s true that this language is $L(R)$, but the fact that $L_a\cap L_b\ne\varnothing$ makes the proof a bit less straightforward than is really necessary.

Let

$$R_a=(a\cup b)^*(aa\cup bb)(a\cup b)^*\,.$$

Clearly $w\in L(R_a)$ iff there are $x,y\in\{a,b\}^*$ such that $w=xaay$ or $w=xbby$ iff $w$ has $aa$ or $bb$ as a substring iff $w\in L_a$, so $L(R_a)=L_a$.

If we can now find a regular expression $R_c$ that describes

$$L\setminus L_a=\big\{w\in\{a,b\}^*:|w|_a=|w|_b\text{ and }|w|_{aa}=|w|_{bb}=0\big\}\,,$$

we’ll be in business, because then clearly $L=L(R_a)\cup(R_c)=L(R_a\cup R_c)$. And this isn’t hard: any word that has equal numbers of $a$s and $b$s but does not contain $aa$ or $bb$ as a substring must alternate $a$s and $b$s and have even length, so it must be of the form $abab\ldots ab$ or the form $baba\ldots ba$. In other words, we can let $R_c=(ab)^*\cup(ba)^*$; it’s straightforward then to prove by induction on $|w|$ that for any $w\in\{a,b\}^*$, $w\in L\setminus L_a$ iff $w\in L(R_c)$. (I suspect that you can do that without too much trouble, but if you run into problems, just ask.)


问:
Removing the subtractive cancellation of $(a+x)^n - a^n$ as x approaches zero
$$(a+x)^n - a^n = \\
e^{n\ln(a+x)}-e^{n\ln(a)} = \\
?$$

This looks simple but I'm stumped.

I've tried to solve this another way too:

$$ f(a) = a^n \\ \frac{\delta f}{\delta a} = \lim_{x\rightarrow 0}\frac{(a+x)^n-a^n}{x}  \\ \\
(a+x)^n - a^n = \frac{(a+x)^n-a^n}{x}x = \frac{\delta f}{\delta n}x=a^n\ln(a)x:x\rightarrow0\\$$

How do I finish the first one, and is the second one correct?

答:
Hint: Apply the binomial theorem:
$$(a+x)^n=a^n+nxa^{n-1}+\cdots+nax^{n-1}+x^n.$$
Your second method is incorrect because if you take $f(x)=x^n$, then $f'(x)=nx^{n-1}$. You are taking $f(x)=a^x$.


答:
To prove a statement by induction, we must first prove the statement works for $n=1$, then extend that statement by supposing that the given statement is true for $n$, then proving it maintains truth for $n+1$. I am also assuming $n$ is an positive integer.

The logic behind that is if the statement works for $n=1$, then it will work for $n+1=2$, and if it works for $n=2$... well you get the point.

In this case for $n=1$, we have $(1- \frac{1}{2})\geq \frac{1}{4} + \frac{1}{2^{(1)+1}}$

or $\frac{1}{2} \geq \frac{1}{4} + \frac{1}{4}$ which is true.

Now since that statement is true for $n=1$, its time to do the induction step.

We can now assume $(1- \frac{1}{2^n})\geq \frac{1}{4} + \frac{1}{2^{n+1}}$ holds true for n.

Consider $n+1$:
$(1- \frac{1}{2^{n+1}})\geq \frac{1}{4} + \frac{1}{2^{(n+1)+1}}$

Simplifying gives you $(1- \frac{1}{2^{n+1}})\geq \frac{1}{4} + \frac{1}{2^{n+2}}$

Taking it one step further: $1- \frac{1}{2}\cdot\frac{1}{2^{n}}\geq \frac{1}{4} + \frac{1}{4}\cdot\frac{1}{2^{n}}$

$1\geq \frac{1}{2^n}$ or $2^n \geq 1$, which is true because n is a positive integer.

So if $(1- \frac{1}{2^n})\geq \frac{1}{4} + \frac{1}{2^{n+1}}$ is true for $n$, it will work for $n+1$

And that's all you need to prove an induction.

Title: Prove by induction $\left(1-\frac{1}{2}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$

Body:
Prove by induction $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{4}\right)\left(1-\frac{1}{8}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$

What would be the best way to solve this by the induction method?


问:
What is the notation to logical OR a series?
I am looking for something similar to Sigma summation notation, but for logical or.  If I have a series of function results that I would like to OR together, how do I denote that?</p>

答:
Maybe make $\lor$ or $\land$ bigger using wedge and vee like this

\bigvee\limits_{i=1}^n x_i $\bigvee\limits_{i=1}^n x_i$

\bigwedge\limits_{i=1}^n x_i $\bigwedge\limits_{i=1}^n x_i$

Could also use \bigoplus $\bigoplus\limits_{i=1}^n x_i$ for xor.

Note that if the symbol exists in small but not in big shape, you can build your own nevertheless using this construction:

§ will give \operatorname*{\Large{§}}\limits_{i=1}^n $\operatorname*{\Large{§}}\limits_{i=1}^n x_i$


问:
Moving Objects in POV-Ray
I´m looking for a way to move objects in POV-Ray.
Let´s say, I got $n$ Points in 3D. They are all in one plane.
Now I want to create a bodie with the shape of the points as its base and a given hight.
At first I need to generate the shape in the origin, but
I don´t know how to find the rotation and translation from there to move the object through my original points. Hope, someone can help.

Thanks in advance

Edit

For example:
$A(1,1,1)$, $B(2,2,2)$ and $C(-1,-1,0)$ create a triangle. Now I want to create a prism
by giving the triangle a height of $2$.
In POV-Ray (as I understand) I need to generate the triangle in 2D, then give it a height, so its always "standing" on the $xy$-plane. And then I need to find a movement to bring the body back through its original points.

sketch

答:
Given three non-collinear points $A,B,C$, make
three orthogonal vectors:
one is in the normal direction wrt the plane through $A,B,C$,
and the other two must belong to that plane.
Note that you need to take care of the sign of the normal.

Prepare a transformation matrix,
which would transform this orthogonal triple into $X,Y,Z$ at the origin.

Transform vectors $A,B,C$ into $A_0,B_0,C_0$, which would then be located in $XZ$-plane.

Use $x$ and $z$ coordinates of $A_0,B_0,C_0$ to construct the boundary of the prism object.

Add the inverse transform at the end of the prism object to move it back.

Fortunately, POV-Ray already has convenient macros
that make this procedure straightforward.

```<code>// -w800 -h600 +a0.3
#version 3.7;
global_settings { assumed_gamma 1.2 }
#include "colors.inc"
#include "transforms.inc"
background{White}

#local h=1;
#local A=<2,0,0>;
#local B=<0,3,0>;
#local C=<0,0,4>;

#local O=(A+B+C)/3;
#local N=-vcross(B-O,C-O);

camera {
  orthographic
  location A+2*N
  look_at O
}
light_source { A+20*N color White }
light_source { B+20*N color White }

#local X1=vnormalize(A-O);
#local Y1=N;
#local Z1=vcross(vnormalize(A-O),N);

#local T=transform{Matrix_Trans(X1, Y1, Z1, O)};
#local invT=transform{T inverse};

#local A0=vtransform(A, invT);
#local B0=vtransform(B, invT);
#local C0=vtransform(C, invT);

prism {
  linear_sweep
  linear_spline
  0, // sweep the following shape from here ...
  h, // ... up through here
  4, // the number of points making up the shape ...
  <A0.x,A0.z>, <B0.x,B0.z>, <C0.x,C0.z>, <A0.x,A0.z>
  texture{pigment { color rgbt<0,1,0,0.1> } finish{diffuse 0.1}}
  transform{T}
}

sphere{A,0.1 pigment { color rgb<1,0,0> }}
sphere{B,0.1 pigment { color rgb<0,1,0> }}
sphere{C,0.1 pigment { color rgb<0,0,1> }}
sphere{O,0.2 pigment { color rgb<0,1,1> }}

sphere{A+h*N,0.1 pigment { color rgb<1,0,0> }}
sphere{B+h*N,0.1 pigment { color rgb<0,1,0> }}
sphere{C+h*N,0.1 pigment { color rgb<0,0,1> }}
sphere{O+h*N,0.2 pigment { color rgb<0,1,1> }}
</code>```

This procedure can an easily adjusted to handle an arrays of $n$ points:

```<code>// -w800 -h600 +a0.3
#version 3.7;
global_settings { assumed_gamma 2.0 }
#include "colors.inc"
#include "metals.inc"
#include "transforms.inc"
background{White}

#local h=1;
#local A=<2,0,0>;
#local B=<0,3,0>;
#local C=<0,0,4>;
#local D=<1/2.25,4/3,4/3>;

#local O=(A+B+C)/3;
#local N=-vcross(B-O,C-O);

camera {
  orthographic
  location A+2*N
  look_at O
}
light_source { A+20*N color White*0.3 }
light_source { B+20*N color White*0.2 }

#local X1=vnormalize(A-O);
#local Y1=N;
#local Z1=vcross(vnormalize(A-O),N);

#local T=transform{Matrix_Trans(X1, Y1, Z1, O)};
#local invT=transform{T inverse};

#local n=4;
#local P=array[n]{A,B,C,D};
#local P0=array[n];

#local i=0;
#while(i<n)
  #local P0[i]=vtransform(P[i], invT);
  #local i=i+1;
#end

prism {
  linear_sweep
  linear_spline
  -h/2, // sweep the following shape from here ...
  h/2, // ... up through here
  n+1, // the number of points making up the shape ...
  #local i=0;
  #while(i<n)
    <P0[i].x,P0[i].z>,
    #local i=i+1;
  #end
  <P0[0].x,P0[0].z>
  texture{pigment { color rgb<0,1,0> } finish{F_MetalB}}
  transform{T}
}

  #local i=0;
  #while(i<n)
    sphere{P[i]+h/2*N,0.1 pigment { color rgb vnormalize(P[i]) } finish{F_MetalB}}
    #local i=i+1;
  #end
</code>```

Title: Moving Objects in POV-Ray

Body:
Given three non-collinear points $A,B,C$, make
three orthogonal vectors:
one is in the normal direction wrt the plane through $A,B,C$,
and the other two must belong to that plane.
Note that you need to take care of the sign of the normal.

Prepare a transformation matrix,
which would transform this orthogonal triple into $X,Y,Z$ at the origin.

Transform vectors $A,B,C$ into $A_0,B_0,C_0$, which would then be located in $XZ$-plane.

Use $x$ and $z$ coordinates of $A_0,B_0,C_0$ to construct the boundary of the prism object.

Add the inverse transform at the end of the prism object to move it back.

Fortunately, POV-Ray already has convenient macros
that make this procedure straightforward.

// -w800 -h600 +a0.3
#version 3.7;
global_settings { assumed_gamma 1.2 }
#include "colors.inc"
#include "transforms.inc"
background{White}

#local h=1;
#local A=<2,0,0>;
#local B=<0,3,0>;
#local C=<0,0,4>;

#local O=(A+B+C)/3;
#local N=-vcross(B-O,C-O);

camera {
  orthographic
  location A+2*N
  look_at O
}
light_source { A+20*N color White }
light_source { B+20*N color White }

#local X1=vnormalize(A-O);
#local Y1=N;
#local Z1=vcross(vnormalize(A-O),N);

#local T=transform{Matrix_Trans(X1, Y1, Z1, O)};
#local invT=transform{T inverse};

#local A0=vtransform(A, invT);
#local B0=vtransform(B, invT);
#local C0=vtransform(C, invT);

prism {
  linear_sweep
  linear_spline
  0, // sweep the following shape from here ...
  h, // ... up through here
  4, // the number of points making up the shape ...
  <A0.x,A0.z>, <B0.x,B0.z>, <C0.x,C0.z>, <A0.x,A0.z>
  texture{pigment { color rgbt<0,1,0,0.1> } finish{diffuse 0.1}}
  transform{T}
}

sphere{A,0.1 pigment { color rgb<1,0,0> }}
sphere{B,0.1 pigment { color rgb<0,1,0> }}
sphere{C,0.1 pigment { color rgb<0,0,1> }}
sphere{O,0.2 pigment { color rgb<0,1,1> }}

sphere{A+h*N,0.1 pigment { color rgb<1,0,0> }}
sphere{B+h*N,0.1 pigment { color rgb<0,1,0> }}
sphere{C+h*N,0.1 pigment { color rgb<0,0,1> }}
sphere{O+h*N,0.2 pigment { color rgb<0,1,1> }}

This procedure can an easily adjusted to handle an arrays of $n$ points:

// -w800 -h600 +a0.3
#version 3.7;
global_settings { assumed_gamma 2.0 }
#include "colors.inc"
#include "metals.inc"
#include "transforms.inc"
background{White}

#local h=1;
#local A=<2,0,0>;
#local B=<0,3,0>;
#local C=<0,0,4>;
#local D=<1/2.25,4/3,4/3>;

#local O=(A+B+C)/3;
#local N=-vcross(B-O,C-O);

camera {
  orthographic
  location A+2*N
  look_at O
}
light_source { A+20*N color White*0.3 }
light_source { B+20*N color White*0.2 }

#local X1=vnormalize(A-O);
#local Y1=N;
#local Z1=vcross(vnormalize(A-O),N);

#local T=transform{Matrix_Trans(X1, Y1, Z1, O)};
#local invT=transform{T inverse};

#local n=4;
#local P=array[n]{A,B,C,D};
#local P0=array[n];

#local i=0;
#while(i<n)
  #local P0[i]=vtransform(P[i], invT);
  #local i=i+1;
#end

prism {
  linear_sweep
  linear_spline
  -h/2, // sweep the following shape from here ...
  h/2, // ... up through here
  n+1, // the number of points making up the shape ...
  #local i=0;
  #while(i<n)
    <P0[i].x,P0[i].z>,
    #local i=i+1;
  #end
  <P0[0].x,P0[0].z>
  texture{pigment { color rgb<0,1,0> } finish{F_MetalB}}
  transform{T}
}

  #local i=0;
  #while(i<n)
    sphere{P[i]+h/2*N,0.1 pigment { color rgb vnormalize(P[i]) } finish{F_MetalB}}
    #local i=i+1;
  #end


问:
Is $\sin^2 x $ the same as $\sin x^2$?
I have seen $\sin^2 x$ in an equation and I don't understand how you can square $\sin$. So does $\sin$ squared $x$ equal $\sin x$ squared? Closed it has been answered

答:
Generally $\sin^{2}x$ is used as shorthand for $(\sin x)^{2} = (\sin x) \cdot (\sin x)$, which is different from $\sin x^{2}$.  You can make it less ambiguous by writing the latter as $\sin(x^{2})$.

Edit: You just have to be careful when you see $\sin^{-1}x$, which does not mean $(\sin x)^{-1} = \frac{1}{\sin x}$, but rather the inverse sine, or $\arcsin x$.

Title: Is $\sin^2 x $ the same as $\sin x^2$?


问:
Show that $\frac{\tan x}x$ with $x\in (0, \frac\pi 2)$ is a strictly increasing function
Show that $\dfrac{\tan(x)}{x}$,  $x\in \left(0, \dfrac{\pi}{2}\right)$ is a strictly increasing function.

$$f(x)=\frac{\tan(x)}{x},\quad f'(x)={\frac {x\tan^2(x)-\tan (x) +x}{{x}^{2}}}.$$
How to conclude?

答:
Chatroom Question

I answered this question in the main Mathematics chatroom:

How can i prove $\frac{x}{tan(x)}$ is decreasing for $x \in (0,1) $?

using this integral
$$
\frac{x}{\tan(x)}=\int_0^1\frac{\mathrm{d}t}{1+t^2\tan^2(x)}\tag1
$$
which is decreasing for $x\in\left[0,\frac\pi2\right]$ since $\tan(x)$ is increasing. Therefore, its reciprocal, $\frac{\tan(x)}x$, is increasing for $x\in\left[0,\frac\pi2\right]$.

Motivation

If $\frac{x}{\tan(x)}$ decreases, then so would $\frac{\tan^{-1}(x)}x$. Therefore, I started with
$$
\begin{align}
\frac{\tan^{-1}(x)}x
&=\frac1x\int_0^x\frac{\mathrm{d}t}{1+t^2}\tag2\\
&=\int_0^1\frac{\mathrm{d}t}{1+t^2x^2}\tag3\\
\frac{x}{\tan(x)}
&=\int_0^1\frac{\mathrm{d}t}{1+t^2\tan^2(x)}\tag4
\end{align}
$$
Explanation:

$(2)$: the integral for arctangent

$(3)$: substitute $t\mapsto tx$

$(4)$: substitute $x\mapsto\tan(x)$


问:
Strategies for proving that a set is denumerable?
This concept has been troubling me. For example, I want to prove that $$\mathbb Q \times \mathbb Q \sim \mathbb N.$$

This is what my professor has told us:

$$\mathbb Q \sim \mathbb N$$

$$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N \times \mathbb N \sim \mathbb N$$
$$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N$$

But this isn't a complete proof because I haven't shown why $\mathbb Q \sim \mathbb N$, and I'm not sure how to do that. I know that if a set is denumerable, that means that it is equinumerous with $\mathbb N$. And I also know that if one is equinumerous with another, that means that there exists a bijection between the two sets. I'm just having trouble putting all of these ideas together into one proof.

答: You'll agree that $\mathbb{Z}$ is equipotent to $\mathbb{N}$; $\mathbb{Q}$ is defined as a quotient of $ \mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, thus the cardinality of $\mathbb{Q}$ is less or equal to that of $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, which is the same as the cardinality of $\mathbb{N}$. Of course you have the opposite "inequality" (think of $\mathbb{N}$ as included in $\mathbb{Q}$, even if it's not correct), and you  conclude by Schroeder-Bernstein theorem.</p>


答:
Carl Gauss (the most famous person to live on Earth in the 19th century, except for people who did not work in the physical and mathematical sciences) wrote (correctly in my view) that the notation $\sin^2 x$ ought to mean $\sin(\sin x)).$ But in his time it had already become conventional to use that notation to mean $(\sin x)^2,$ and that is what everybody learns in secondary school today and for many decades past.

The notation $\sin x^2$ usually means $\sin(x^2),$ and the latter is how I would normally write it.

Title: Is $\sin^2 x $ the same as $\sin x^2$?

Body: I have seen $\sin^2 x$ in an equation and I don't understand how you can square $\sin$. So does $\sin$ squared $x$ equal $\sin x$ squared? Closed it has been answered


问:
Proving $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$
For $n=5$, we get $\binom{10}{5}<4^4$. Asumme inductively that $\binom{2n}{n}<4^{n-1}$ for all positive integers $n\geq 5$. Then I need to prove that $\binom{2(n+1)}{n+1}<4^{n}$ for all positive integers $n\geq 5$. I've been looking around a bit, and I've found that the expression $\binom{2n}{n}$ is precisely a central binomial coefficient. Thus $\sum_{k=0}^{n+1}\binom{n+1}{k}^2=\binom{2(n+1)}{n+1}$. How can I use this to finish my proof?

答:
Lets think of this problem set theoretically.

Consider a set of $2n$ elements.

Then number all possible $n$-element subsets (subset whose cardinality is $n$) is ${2n}\choose{n}$.

The cardinality of the $power$ set (Set of all possible subsets) is $2^{2n}$ = $4^n$\

So clearly ${2n}\choose{n}$ $<$ $4^n$. But will it be less than $4^{n-1}$ $?$ (If yes then why?)


问:
How does the central limit theorem enable the approximation of probabilities?
My text book states the following about the Central Limit Theorem and then launches into examples.

Let $X_1, X_2 .... X_n$ be a sequence of independent and identically
distributed random variables  each having mean $\mu$ and variance
$\sigma^2$ .

Then for n large, the distribution of $X_1+....+X_n$
is approximately normal with mean $n\mu$ and variance
$n\sigma^2$.

It follows from the central limit theorem that
$\frac{X_1+...+X_n - n\mu}{\sigma \sqrt{n}}$ is approximately a
standard normal variable; thus, for n large, $P \left\{
> \frac{X_1+....X_n-n\mu}{\sigma\sqrt{n}}<x \right\} \approx P\{Z<x\}$
where Z is a standard random normal variable.

I feel like something is missing here. Although I know how to use Z-Tables to look up probabilities, the explanation here fails to explain why I can use the Z-Tables.

How does it "follow from" the central limit theorem?

What has the Z introduced here got to do with calculating probabilities?

答:
To be able to explain this very thoroughly requires an understanding of a few advanced calculus concepts. Going by how the CLT is phrased in your text I'm going to assume that those ideas haven't been covered.

Before I do attempt an explanation I will suggest that if you have an interest/time to learn about these ideas in more depth, that you should work through Spivak's Calculus from start to finish. It provides the level of rigour needed to grasp these ideas fully. I struggled for a long time trying to understand the CLT rigourously and that was because I didn't have the foundations in place. This book illuminated my path.

So to your question.

I'll attempt to explain it in a very simple way and will reference the more advanced theorems needed in parentheses.

Like you said you know how to look up Z scores and find their probabilities. That is the last step in the process known as the Central Limit Theorem.

We begin with a sequence of i.i.d random variables, $X_{1}, X_{2}, \cdots$. This sequence of random variables could be infinite. As you should know each $X_{i}$ has its own distribution. One of the things we ask ourselves in statistics is "What would happen if we took a sum of all our random variables?". We will call this $S_{n}$, it is defined as:

$$S_{k} = \frac{1}{n}(X_{1} + X_{2} + \cdots + X_{n})$$

From calculus there is the idea of a sequence of numbers, here it is a similar idea except we don't know what the numbers are before hand. So as an example say each random variable $X_{i}$ is defined as follows:

$$X_{i} = \{0,1,2\}$$

That means each sequence of random variables, $X_{1}, X_{2}, \cdots, X_{n}$ will have some sort of combination of any of those three numbers.

Now back to our sum defined as $S_{k}$. This is just a sum of the terms in the sequence. It is also a random variable. Now $S_{k}$ can also be looked at as a sequence. Its values will just be the sums of the random variables.

In some instances sequences of numbers will converge to another number (advanced concept). In this scenario we have a concept called the Law of Large Numbers which states that this sequence of sums $S_{k}$ will converge to the mean, $\mu$. (advanced theorem). (the $n\mu$ you have in your statement is similar, but to make the explanation easier I did it this way).

Now you've probably asked "where the hell is the $Z$?". Well using the terms $S_{k}$ we will define another term called $Z_{n}$.

$$Z_{n} = \frac{S_{k} - \mu}{\sigma \sqrt{n}}$$

Doing this is called standardizing the random variable and it is done in practice a lot. Observe now that this again will be a sequence of terms, $Z_{1}, Z_{2}, \cdots$. And as well $Z_{n}$ are also random variables.

Going back all the way to the start we said each $X_{i}$ is i.i.d, that means they each have their own CDF, this will follow all the way to the $Z_{n}$ as well. That means there is a sequence of distribution functions $F_{1}, F_{2}, \cdots$. Each of these distribution functions take on the all the same values because each $Z_{i}$ takes on a set of values. That is $F_{1}(z), F_{2}(z), \cdots$.

So we have a situation now where we have a sequence of distribution functions $F_{1}(z), F_{2}(z), \cdots$. But what are these distribution functions? Binomial, Uniform, Poisson, etc?

It doesn't matter! Because what the CLT tells us is that this sequence of distribution functions will converge to a special distribution function: The standard normal distribution. (there is an advanced theorem on the idea of convergence of sequences of functions being used here)

Now why is that important as you asked? Well even though it might seem like it in the courses you take, in the wild it is more difficult to calculate probabilities using all of the different distribution functions we have created. So we can use the CLT to approximate the probabilities of phenomena which may themselves be distributed according to some other probability distribution (binomial, poisson, etc)

So it is a long answer but hopefully it is still simple enough to grasp the idea. If you want a really short TL;DR: Lot's of advanced mathematics make it work.  But I hope you do take interest in the machinery underneath the hood. Ask any questions if you have and I'll try to answer.


问:
Simplify $\tan^{-1}(x)+\tan^{-1}(-1/x)?$
As the question says, I want to simplify $\tan^{-1}(x)+\tan^{-1}(-1/x)?$.

There is not necessarily a solution to this, but is there any way to simplify the question above? It can be in terms of anything

答:
Provided that you have shown that $\left|\tan^{-1}(x)+\tan^{-1}\left(-\frac{1}{x}\right)\right|<\frac{\pi}{2}$, you can use the identity $\tan^{-1}(x)-\tan^{-1}(y)=\tan^{-1}\left(\frac{x-y}{1+xy}\right)$ to deduce that
\begin{align*}
\tan^{-1}(x)+\tan^{-1}\left(-\frac{1}{x}\right) &= \tan^{-1}(x)-\tan^{-1}\left(\frac{1}{x}\right)\\
&= \tan^{-1}\left(\frac{x-\frac{1}{x}}{1+x\cdot\frac{1}{x}}\right)\\
&= \tan^{-1}\left(\frac{x-\frac{1}{x}}{2}\right)
\end{align*}


问:
Why does $\|T\| = \sup\{\|Tx\|_{W} : \|x\|_{V} = 1 \}$ make sense?
I am currently in the phase of my class on the analysis of metric spaces where we have transitioned to studying the normed vector space $B(V,W)$ — the space of all continuous linear maps $T : V \to W$ $($where $(V,||\cdot||_{V})$ and $(W, \|\cdot\|_{W})$$)$.

With this new transition, we have also considered the operator norm on $B(V,W)$, $$\|T\|_{B(V,W)} = \sup\limits_{\|x\|_{V} \neq 0} \frac{\|Tx\|_{W}}{\|x\|_{V}}.\tag1$$ While this is clearly a norm on $B(V,W)$, I have seen other authors write this norm as $$\|T\|_{B(V,W)} = \sup_{\|x\|_{V} = 1}\|Tx\|_{W}$$ or $$\|T\|_{B(V,W)} = \sup\{\|Tx\|_{W} : |\|x\|_{V} =1\}.$$ How is this the same as $(1)$? I understand that the only requirement here is that the $\|x\|_{V} \neq 0$, but I also understand that we can write $\|T\|_{B(V,W)}$ as $$\inf\{C : \|Tx\|_{W} \leq C\|x\|_{V}\quad\forall x \in V\}.$$ In other words,

$\|T\|_{B(V,W)}$ satisfies $\|Tx\|_{W} \leq \|T\|_{B(V,W)}\|x\|_{V}$, and $\|T\|_{B(V,W)}$ is the smallest constant satisfying this inequality

according to my textbook $($N.L. Corothers' Real Analysis$)$.

Note: I know that $B(V,W)$ may be written as $L(V,W)$, but I am just referring to the notation in my book.

答:
The function
$$ x \mapsto \frac{\|Tx\|}{\|x\|} $$
is invariant on the span of $x$ (sans zero) because $T$ is linear. (Exercise: check this.)

So taking the supremum of this function over all $x\in V$ is the same as taking the supremum over the unit circle.

More formally,

 $$\sup_{x\in V} \frac{\|Tx\|}{\|x\|} = \sup_{x\in V} \bigg\|T\bigg(\frac{x}{\|x\|}\bigg)\bigg\| = \sup_{\|x\|=1}\|Tx\|$$


问:
Kreyszig's definition of finite dimensional vector spae
In his book on functional analysis Kreyszig gives the following definition:

Definition. A vector space $X$ is said to be finite dimensional if there is a positive integer $n$ such that $X$ contains a linearly independent set of $n$ vectors whereas any set of $n+1$ or more vectors of $X$ is linearly dependent. $n$ is called the dimension of $X$, written $n=\text{dim } X$. By definition, $X=\{0\}$ is finite dimensional and $\text{dim } X=0$. If $X$ is not finite dimensional, it is said to be infinite dimensional. If $\text{dim } X=n$, a linearly independent $n$-tuple of vectors of $X$ is called a basis for $X$.

He then proves the following basic theorem

Theorem. Let $X$ be an $n$ dimensional vector space. Then any proper subspace $Y$ of $X$ has dimension less than $n$.

Proof. If $n=0$, then $X=\{0\}$ and has no proper subspace. If $\text{dim } Y=0$, then $Y=\{0\}$, and $X \neq Y$ implies $\text{dim } X\geq 1$. Clearly, $\text{dim } Y\leq \text{dim } X=n$. If $\text{dim } Y$ were $n$, then $Y$ would have a basis of $n$ elements, which would also be a basis for $X$ since $\text{dim } X=n$, so that $X=Y$. This shows that any linearly independent set of vectors in $Y$ must have fewer than $n$ elements, and $\text{dim } Y<n$.

Questions:

Why is the last sentence in the proof necessary? It seems like a contradiction has already been reached at this point.

Am not sure the statement $\text{dim } Y\leq \text{dim } X$ is so clear given his definitions. We cannot have $\text{dim } Y=m>n$, but how can we rule out the case of $\text{dim } Y=\infty$?

We idea to rule out $\text{dim } Y=\infty$ is the following argument:

If $\text{dim } Y=\infty$, then in particular $\text{dim } Y\neq n$. Hence either there exist a set of $n+1$ linearly independent vectors in $Y$ or every set of $n$ vectors in $Y$ is linearly dependent. By definition of $\text{dim } X=n$ it must be that the latter holds. Now we repeat the argument to obtain that every set of $n-1$ vectors in $Y$ is linearly dependent. After $n$ steps we reach the conclusion that $Y=\{0\}$, contradiction.

Is this correct?

答:
The last sentence appears to be there for emphasis.

The basic logic that establishes $\dim Y\leq\dim X$ also works for the case $\dim Y=\infty$: if $\dim Y>n$ then $\dim Y$ contains an independent set of size $n$. The fact that this also holds for $\dim Y=\infty$ doesn't follow immediately from the definition but it's not hard to prove. With $U$ a vector space, let $N$ be the set of all $k$ such that $U$ contains a set of $k$ independent vectors. $N$ is always non-empty since it contains $0$, and it is closed downwards (if $l<k$ and $k\in N$ then $l\in N$). The dimension of $U$ is just the maximum of $N$, or $\infty$ if the maximum doesn't exist. In either case it's clear that if $n<\dim U$, $n\in N$.

Your argument works but it's a little overkill since it stands on its own as a complete proof of the original theorem. To see this, notice that the only way you ever use the assumption that $\dim Y=\infty$ is to say that $\dim Y$ is not any of the numbers $0$ through $n$. So you're essentially proving by contradiction that $\dim Y\leq n$.


问:
How to prove that $\lim_{x\to\infty}\frac{(\log_2 x)^3}{x^n}=0$

I need help with proving the following $$\lim_{x\to\infty}\frac{\left({\log}_2x\right)^3}{x^n}=0\ , \quad \forall n>0.$$

I used wolframalpha and got it

and I had kind of an intuition because of the limit $\frac{\ln(x)}x$ , and still I have no idea how to formaly proof it.

Will appreciate any help!

Body: If $K,L$ are positive and $B>1$ then, with $C=1/\ln B$, we have (for $x>1$)$$\frac {(\log_Bx)^K}{x^L}=\frac {(C\ln x)^K}{x^L}=\frac {(C\ln x)^K}{(x^{L/K})^K}=$$ $$=\frac {(\,C(K/L)\ln (x^{L/K})\,)^K}{(x^{L/K})^K}=$$ $$=C^K(K/L)^K\left(\frac {\ln (x^{L/K})}{x^{L/K}}\right)^K.$$


问:
Smallest positive integer that starts with 2016 and is divisible by 2017
I have the following quiz but I don't really know how to solve it.

Find the smallest positive integer that starts (in decimals) with 2016 and is divisible by 2017.

Why to they specify the decimals in brackets?

First thought was to divide 2016 by 2017. 2016/2017 = 0.999504.
Should the integer start with 2016? I find it confusing. Can someone help?

答:
Another solution:

20160   mod 2017 = 2007   No solution with 1 digit because     2017 - 2007 = 10

201600  mod 2017 = 1917   No solution with 2 digits because    2017 - 1917 = 100

2016000 mod 2017 = 1017   No solution with 3 digits because    2017 - 1017 = 1000

20160000 mod 2017 = 85
This leads to the last 4 digits solution 2017 - 85 = 1932


问:
Show that $[2x]+[2y] \geq [x]+[y]+[x+y]$
Prove that $[2x]+[2y] \geq [x]+[y]+[x+y]$ whenever $x$ and $y$ are real numbers.

The $[]$ symbol is the greatest integer or floor function.

I have proved this fact by cases, but I stumbled upon what I believe to be another way to prove the above inequality, and I was wondering if my sequence of statements are legitimate.

I make use of two lemmas that I have proved

Lemma 1.   If $x$ is a real number and m is an integer, then $[x+m] = [x]+m$.

Lemma 2.   $\displaystyle [x]+\left[x+\frac{1}{2} \right] = [2x]$.

My proof begins with an "obvious" statement

$$x+y \leq x+y+1$$

I then take the floor of the inequality to get

$$[x+y] \leq [x+y]+1$$             (1)

which is true in virtue of lemma 1.

Furthermore, if I add the following statements

$$[x+1/2] \leq x + 1/2$$
$$[y+1/2] \leq y + 1/2$$

I procure

$$\left[x+\frac{1}{2} \right]+\left[y+\frac{1}{2}\right] \leq x+y+1$$

which by definition of the floor function renders the equation

$$[x+y]+1 = \left[x+\frac{1}{2} \right]+\left[y+\frac{1}{2} \right]$$        (2)

Substituting (2) for (1), I have

$$[x+y] \leq \left[x+\frac{1}{2} \right]+\left[y+\frac{1}{2} \right]$$

I then add $[x]$ and $[y]$ to the above inequality to produce

$$[x]+[y]+[x+y] \leq [x]+\left[x+\frac{1}{2} \right]+[y]+\left[y+\frac{1}{2} \right]$$

And in virtue of Lemma 2, the right hand side of the inequality becomes

$$[x]+[y]+[x+y] \leq [2x]+[2y].$$

I personally don't see anything wrong, except maybe for the implication made to establish (2).

Solving these kinds of problems is solely for personal gratification, so I will greatly appreciate feedback.

Thanx.

答:
Let $x=m+\theta_1$ and $y=n+\theta_2$ where $n,m\in\Bbb{Z}$ and $0\le\theta_1,\theta_2<1$

Case I: $0\le\theta_1<\dfrac12$ and $0\le\theta_2<\dfrac12$

Now   \begin{align}
\lfloor 2x\rfloor +\lfloor 2y\rfloor&=\lfloor 2m+2\theta_1\rfloor+\lfloor 2n+2\theta_2\rfloor\\
&=2m+2n\\
\end{align} since $0\le\theta_1<\dfrac12$ and $0\le\theta_2<\dfrac12\implies 0\le2\theta_1<1$ and $0\le2\theta_2<1$

and   \begin{align}
\lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor &=\lfloor m+\theta_1\rfloor+\lfloor n+\theta_2\rfloor+\lfloor m+n+\theta_1+\theta_2\rfloor\\
&=m+n+(m+n)\\
&=2m+2n,
\end{align} since $0\le\theta_1<\dfrac12$ and $0\le\theta_2<\dfrac12\implies 0\le\theta_1+\theta_2<1$

$\color{red}{So\quad \lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor=\lfloor 2x\rfloor +\lfloor 2y\rfloor}$

Case II: $0\le\theta_1<\dfrac12$ and $\dfrac12\le\theta_2<1$
\begin{align}
\lfloor 2x\rfloor +\lfloor 2y\rfloor&=\lfloor 2m+2\theta_1\rfloor+\lfloor 2n+2\theta_2\rfloor=2m+(2n+1),
\end{align} since $0\le\theta_1<\dfrac12$ and $\dfrac12\le\theta_2<1\implies 0\le2\theta_1<1$ and $1\le2\theta_2<2$

and  since $0\le\theta_1<\dfrac12$ and $\dfrac12\le\theta_2<1\implies \dfrac12\le\theta_1+\theta_2<\dfrac32$  \begin{align}
\lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor &=\lfloor m+\theta_1\rfloor+\lfloor n+\theta_2\rfloor+\lfloor m+n+\theta_1+\theta_2\rfloor\\
&=m+n+(m+n)=2m+2n, \text{if}\quad\dfrac12\le\theta_1+\theta_2<1\\
&=2m+2n+1, \text{if}\quad 1\le\theta_1+\theta_2<\dfrac32
\end{align}

$\color{red}{So \quad\lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor\le\lfloor 2x\rfloor +\lfloor 2y\rfloor}$

Case III: $\dfrac12\le\theta_1<1$ and $0\le\theta_2<\dfrac12$. $\color{blue}{\textbf{[Same as Case II]}}$

Case IV: $\dfrac12\le\theta_1<1$ and $\dfrac12\le\theta_2<1$

\begin{align}
\lfloor 2x\rfloor +\lfloor 2y\rfloor&=\lfloor 2m+2\theta_1\rfloor+\lfloor 2n+2\theta_2\rfloor=(2m+1)+(2n+1)=2m+2n+2,
\end{align} since $\dfrac12\le\theta_1<1$ and $\dfrac12\le\theta_2<1\implies 1\le2\theta_1<2$ and $1\le2\theta_2<2$

and  since $\dfrac12\le\theta_1<1$ and $\dfrac12\le\theta_2<1\implies 1\le\theta_1+\theta_2<2$  \begin{align}
\lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor &=\lfloor m+\theta_1\rfloor+\lfloor n+\theta_2\rfloor+\lfloor m+n+\theta_1+\theta_2\rfloor\\
&=m+n+(m+n+1)=2m+2n+1\\
\end{align}

$\color{red}{So \quad\lfloor x\rfloor +\lfloor y\rfloor+\lfloor x+y\rfloor\le\lfloor 2x\rfloor +\lfloor 2y\rfloor}$


问:
3 Variable Limit
I cannot seem to solve this 3-variable limit:
$$
{\lim_{(x,y,z) \to (0,0,0)}}\frac{x^2y^2z^2}{x^2+y^2+z^2}
$$
I searched this up on symbolab and it said to convert to polar coordinates. However they immediately set z equal to r which doesn't make sense to me. If there is a 3rd variable I thought I had to convert it to cylindrical coordinates, but I still can't just let z = r or can I? Any help is appreciated.

Title: 3 Variable Limit

Body:
$$L={\lim_{(x,y,z) \to (0,0,0)}}\frac{x^2y^2z^2}{x^2+y^2+z^2}$$
Since $x^2 \le x^2+y^2+z^2$ we have :
$$0 \leq \left|\frac{x^2y^2z^2}{x^2+y^2+z^2}\right| \leq {(yz)^2}$$
$$\implies L=0$$


问:
Throw dice till numbers are the same
Let's consider the following experience : we throw two dices till same number on two dices appears. I want to calculate expected sum of all dices appeared.

My work so far

I wanted to do it (and also I found it very intuitive) to do it by wold's decomposition theorem. The sum then will be presented by formula $E[S_n]=E[T]E[X_1]$, where $T$ is the stopping time.

How to calculate $E[T]$ ?

$P(Y=1)=\frac16$

$P(Y=2)=\frac56 \cdot \frac16$

$P(Y=n)=(\frac{5}{6})^{n-1} \cdot \frac16$

So :

$$E[Y]=\sum_{i=1}^\infty i \cdot P(Y=i)=1 \cdot \frac16 +2 \cdot \frac56 \cdot \frac16+...$$

And it's type of series $\sum_{i=1}^{\infty} i(1-p)^{i-1}p$ where $p \in [0,1]$ and this sum equals to $\frac1p$. So my sum above equals to 6 and that's exactly $E[T]$

why it would be good to use wold's theorem? Because it's very easy to calculate either $E[X_1]$ or $E[T]$ (calculated above). However, I don't know how should I define set $T=\inf\{...\}$ that will show that equality $E[S_n]=E[T]E[X_1]$ holds. I'm not sure how to strictly justify it.

答:
Let $E_1$ be the expected sum of a single throw given that the two dice are the same, and let $E_2$ be the expected sum of a single throw given that the two dice are different.

The probability that the two dice are the same is $\frac16$. So $E$, the expected total sum, satisfies
$$E=\frac16 E_1 + \frac56 (E_2+E)$$

And by linearity of expectation, $E_1$ and $E_2$ are both equal to $7$. So you can easily solve for $E$.

Title: Throw dice till numbers are the same


问:
How to compute $\int_{-\infty}^{\infty} \frac{1+\cos(x)}{(x -\pi)^2}dx$?
I want to compute $$\int_{-\infty}^{\infty} \frac{1+\cos(x)}{(x -\pi)^2}dx$$

My approach is $$\int_{-\infty}^{\infty} \frac{1+\cos(x)}{(x -\pi)^2}dx=\int_{-\infty}^{\infty} \frac{1}{(x -\pi)^2}dx+\int_{-\infty}^{\infty} \frac{\cos(x)}{(x -\pi)^2}dx.$$

However, the first term on the RHS does not exist since there is a singularity $\pi$.

How to overcome this problem?

Now follow the hint, I get $$\int_{-\infty}^{\infty} \frac{\sin x}{x}dx$$

BTW, if I want to use residue calculus to do this problem, how to do it?  I am confused the pole at origin. Thanks!

答:
$u=x-\pi,du=dx$
$$\int_{-\infty}^\infty\frac{1+\cos(x)}{(x-\pi)^2}dx=\int_{-\infty}^\infty\frac{1+\cos(u+\pi)}{u^2}du=\int_{-\infty}^\infty\frac{1-\cos(u)}{u^2}du$$
and now if we look at this for $u\to\infty$:
$$\frac{1-\cos(u)}{u^2}\approx\frac 1{u^2}$$
and we can also calculate that:
$$\lim_{u\to 0}\frac{1-\cos(u)}{u^2}=\frac12$$
so we can determine that the function is finite for the domain its in and is convergent due to the comparison test.

You can also use the fact that:
$$1-\cos(x)=2\sin^2\left(\frac x2\right)$$


问:
Show that sets are pairwise disjoint
Let $A, B \subset X$. Show that the sets $A$ \ $B$, $B$ \ $A$, $A \cap B \subset X$ are pairwise disjoint and that their union is $A \cup B$.

I know that $A$ \ $B$ is $A \cap B^{c}$ and I can write  $B$ \ $A$ as $B \cap A^{c}$, but how can I show that they are pairwise disjoint?

答: Suppose there is some $x \in (A \setminus B) \cap (B\setminus A)$. Then $x \in A \setminus B$ and $x \in B \setminus A$. So, $x \in A$ and $x\notin A$. By contradiction $(A \setminus B) \cap (B\setminus A)=\emptyset$. Try a similar reasoning for the other cases.

Title: Show that sets are pairwise disjoint


问:
Prove that $\sigma$-algebras $A_1,\ldots,A_n$ are independent if and only if $A_i$ is independent of each $A_1,\ldots,A_{i-1}$, for all $i=2,\ldots,n$
Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space, $k\in\mathbb N$ and $\mathcal F_1,\ldots,\mathcal F_k\subseteq\mathcal A$. Remember the following terminology

$(\mathcal F_1,\ldots,\mathcal F_k)$ is called independent if $$\operatorname P\left[\bigcap_{i\in I}A_i\right]=\prod_{i\in I}\operatorname P\left[A_i\right]\tag1$$ for all $I\subseteq\{1,\ldots,k\}$ and $A_i\in\mathcal F_i$ for all $i\in I$.

$\mathcal F_1$ and $\mathcal F_2$ are called independent (or $\mathcal F_1$ is called independent of $\mathcal F_2$) if $(\mathcal F_1,\mathcal F_2)$ is independent.

Moreover, remember the following basic results:

Let $K\subseteq\{1,\ldots,k\}$ and $(I_k)_{k\in K}$ be a disjoint subdivision of $\{1,\ldots,k\}$. If $(\mathcal F_1,\ldots,\mathcal F_k)$ is independent, then $\left(\bigcup_{i\in I_k}\mathcal F_i\right)_{k\in K}$ is independent.

If $\mathcal F_i\cup\{\emptyset\}$ is closed under finite intersections for all $i\in\{1,\ldots,k\}$, then $(\mathcal F_1,\ldots,\mathcal F_k)$ is independent if and only if $(\sigma(\mathcal F_1),\ldots,\sigma(\mathcal F_k))$ is independent.

Question: (a) Are we able to show $(\mathcal F_1,\ldots,\mathcal F_k)$ is independent if and only if $\mathcal F_i$ is independent of $\mathcal F_1\cup\cdots\cup\mathcal F_{i-1}$ for all $i\in\{2,\ldots,k\}$?

(b) Or do we need to replace $\mathcal F_1\cup\cdots\cup\mathcal F_{i-1}$ by $\sigma(\mathcal F_1\cup\cdots\cup\mathcal F_{i-1})$ and/or assume that each $\mathcal F_i$ is a $\sigma$-algebra?

答:
For (a) we have the following simple counterexample. Let $\Omega=\{0,1,2,3\}$, $\mathcal A$ be the family of all subsets of $\Omega$ and $P(A)=|A|/|\Omega|$ for each $A\in\mathcal A$. Let $k=3$.
For each integer $i$ from $1$ to $k$ put $A_i=\{0,i\}$ and $\mathcal F_i=\{A_i\}$. Since
$$P(A_i\cap A_j)=\frac 14=\left(\frac 12\right)^2=P(A_i)P(A_j)$$
for each distinct integers $i,j$ from $1$ to $k$, we see that $\mathcal F_2$ is independent from $\mathcal F_1$ and $\mathcal F_3$ is independent from $\mathcal F_1\cup \mathcal F_2$. On the other hand, $(\mathcal F_1, \mathcal F_2, \mathcal F_3)$ is not independent, because
$$P(A_1\cap A_2\cap A_3)=\frac 14\ne \left(\frac 12\right)^3=P(A_1)P(A_2)P(A_3).$$

Concerning (b) we can prove that $(\mathcal F_1, \mathcal F_2,\dots, \mathcal F_k)$ is independent under weaker assumptions, which are sufficient to justify the following sequence of equalities for any choice $A_i\in\mathcal F_i$ for each $i$

$$P(A_1\cap \dots \cap A_k)=$$ $$P(A_1\cap \dots \cap A_{k-1})P(A_k)=$$ $$P(A_1\cap \dots \cap A_{k-2})P(A_{k-1})P(A_k)=$$ $$\dots$$ $$P(A_1)\cdots P(A_k).$$


问:
Find all continuous functions $f: \mathbb{R} \rightarrow \mathbb{N}$ and all continous functions $f: \mathbb{N} \rightarrow \mathbb{R}$.
Find all continuous functions $f: \mathbb{R} \rightarrow \mathbb{N}$ and all continuous functions $f: \mathbb{N} \rightarrow \mathbb{R}$.

My thinking process went something like this. For the case of $f: \mathbb{R} \rightarrow \mathbb{N}$, if I think about the function in the $xOy$ plane, if we would have any point at which the value would change from one natural number to some other natural number then at that point we would have a jump discontinuity. So every number from the domain $\mathbb{R}$ needs to be mapped to the same natural number in order to have a continuous function. Thus, we need the function to be something like

$$f:\mathbb{R} \rightarrow \mathbb{N} \hspace{1cm} f(x) = n$$

for any $n \in \mathbb{N}$.

In the case of $f: \mathbb{N} \rightarrow \mathbb{R}$ again thinking about the function in the plane $xOy$, the values of the function at two consecutive points $n$ and $n+1$ are not 'tied' together by anything, there's just empty space, so the function is nowhere continuous. Thus, there are no continuous functions $f: \mathbb{N} \rightarrow \mathbb{R}$.

I hope my reasoning is correct. But my real problem is about the writing process of this proof. Obviously I can't write on the paper all of this story that I just came up with. But how can I create a rigorous proof with what I just wrote (with definitions and all of that fluff). Thinking in terms of pictures is nice, but I have to formalize my thinking with definitions, theorems, and the like and in that regard I am lacking terribly. So how can I approach the writing of this proof?

答: Since this is an Introduction to Analysis class, I think it is most likely that the topology on these spaces are the standard topology on $\mathbb{R}$ and the subspace topology on $\mathbb{N}$. The subspace topology on $\mathbb{N}$ is equivalent to the discrete topology on $\mathbb{N}$, so every function $f:\mathbb{N} \to \mathbb{R}$ is continuous. On the other hand, the inclusion $i:\mathbb{N} \hookrightarrow \mathbb{R}$ is continuous. So then if we have a continuous function $f:\mathbb{R} \to \mathbb{N}$, the composition $i \circ f$ is continuous. But then, if $| \text{im}f | \neq 1$ (i.e. if $f$ does not collapse $\mathbb{R}$ to a single point), then we have a continuous function $i \circ f$ that sends the connected space $\mathbb{R}$ to a disconnected subset. But if $g: X \to Y$ is a continuous function, $X$ is connected if and only if $\text{im} g$ is connected. So the only functions $f: \mathbb{R} \to \mathbb{N}$ that are continuous are those that map the reals to a singleton.


问:
Prove $010010001...0^i1$ is irregular without using pumping lemma
I think that we can prove it either using pigeonhole principle and a contradiction or showing that if it's regular then there's only one way to show it's DFA and since the number of states are finite and we can't make use of loops we have a contradiction.
But I somehow think the latter one is pumping lemma itself so I didn't spend so much efforts on it.</p>

答:
For each $n\in\Bbb Z^+$ let $u_n=0^n1$. Let $w_1=u_1$, and for $n\in\Bbb Z^+$ let $w_{n+1}=w_nu_{n+1}$; your language is $L=\{w_n:n\in\Bbb Z^+\}$, and you can use the Myhill-Nerode theorem to prove that $L$ is not regular. I will use the terminology and notation of the article at the link.

For $w\in L$ let $[w]$ be the $R_L$-equivalence class of $w$, and let $w_m$ and $w_n$ be distinct members of $L$. Without loss of generality we may assume that $m<n$. Then $u_{m+1}$ is a distinguishing extension for $w_m$ and $w_n$, since $w_mu_{m+1}=w_{m+1}\in L$, but $w_nu_{m+1}\notin L$. Thus, $[w_n]=\{w_n\}$ for each $n\in\Bbb Z^+$, so $L$ has infinitely many $R_L$-classes and is therefore not regular.


问:
Binomial Theorem Derivative
Derive the binomial theorem with respect to $x$ (then setting $x$ to an appropriate value) to evaluate the sum $$\sum_{k=1}^n k\cdot(-3)^k{n \choose k}$$ for $n > 0$. Write your function as a function of $n$.

So, I have taken the derivative of the binomial theorem of $(n)(1+x)^{n-1}$.

That derivative looks kinda similar to the sum, so I tried plugging in -4 for k to get the -3, but that leaves me with negative factorials.

答: Set $f_n(x) = (1-3x)^n.$ Expand $f_n$ using the binomial theorem. Then write $f_n'(x)$ in two ways: as the derivative of $(1-3x)^n$ and as the derivative of the expansion. Then set $x=1.$

Title: Binomial Theorem Derivative


问:
Does the Huntington axiom follow from $x \vee x = x$ and $\neg \neg x = x$?
Let’s consider algebras with the following axioms in addition to commutativity and
associativity:
$$x \vee x=x$$
$$\neg \neg x = x$$

Does the Huntington axiom ( $\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$ ) follow from the axioms?
If
yes prove it by showing how the axioms entail it, if not, give an interpretation that
contradicts it, but satisfies the axioms above together with the commutativity and
associativity axioms.

This is a homework assignment for my AI class, but I have no idea where to start. Could you give me some pointers?

答:
Based on the comments I think I have the solution now:

Let's define $\neg x = x$, that is consistent with $\neg \neg x = x$, and let $x \vee x$ be the logical AND operation, that's associative, commutative, and $x$ AND $x=x$ holds.

Now let's work with the Huntington axiom:
$$\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$$
Using $\neg x = x$ we get:
$$(x \vee y) \vee (x ∨ y) = x$$
Then applying $x \vee x = x$ yields
$$(x \vee y) = x$$

But for the logical AND operation if $x$ is true and $y$ is false $x$ AND $y$ is false, and that a contradicts with the result. So we found a counterexample, and that means that the Huntington axiom does not follow from the given axioms.


问:
What kind of math topics exist?

What kind of math topics exist?

The question says everything I want to know, but for more details: I enjoy studying mathematics but the problem is that I can't find any information with a summary of all math topics, collected together. I also googled this and took a look at other websites and searched this website but without success.

So if someone knows most of the topics, then please let me know them. The topics I am looking for are the ones from basics, to the university, and beyond university limit. Any comprehensive information you can provide would be useful.

Further thanks and have a nice day.

答:
You might want to start at the Mathematical Atlas. It gives a visual map of domains of mathematics, and how they are inter-related: you can click on any "bubble" to learn more about each area. There is also a menu to the right-hand side: for example, see A Gentle Introduction to the Mathematics Subject Classification Scheme, also referred to as MSC.

The Mathematics Subject Classification was developed to help categorize publications and research in mathematics.

See also the entry in Wikipedia: Lists of Mathematical Topics. This list includes topics which may sound more familiar to you, and groups them together in a sort of classification, each topic with its own link, so you can further explore any/all of them, at your leisure.

The purpose of this list is not similar to that of the Mathematics Subject Classification formulated by the American Mathematical Society....This list has some items that would not fit in such a classification, such as list of exponential topics and list of factorial and binomial topics, which may surprise the reader with the diversity of their coverage.

Title: What kind of math topics exist?


问:
positive Markov Matrix
For a positive Markov matrix which satisfy 1) every element is positive 2) each column sums to 1. It's easy to prove that 1 is a eigenvalue and every $ | \lambda | \leq 1  $. However, is there any way to prove that $ \lambda \neq -1  $ ?

答:
This is an immediate result from applying Gerschgorin Discs -- in particular draw this out!

The symbol manipulation using triangle inequality is below, but the sketch is probably even more compelling.

Since each $a_{k,k} \gt 0$ and each row sum is 1 (with positive only components), each disc $k$ has radius

$r_k =\sum_{j\neq k}\big \vert a_{k,j}\big \vert  =\sum_{j\neq k} a_{k,j}$

Then the boundary of disc $k$ is given by

$a_{k,k} + e^{i\theta}r_k$  for $\theta \in [0,2\pi)$
and

$\big \vert a_{k,k} + e^{i\theta}r_k\big \vert \leq \big \vert a_{k,k}\big \vert + \big \vert e^{i\theta}r_k\big \vert =  a_{k,k} + r_k \big \vert e^{i\theta}\big \vert +a_{k,k} + r_k   =1$

by Triangle Inequality, with equality iff $a_{k,k}$ and $e^{i\theta}r_k$ are on the same ray emanating from the origin -- i.e. iff they are both on the positive half of the real line ($\theta =0$).

Now this holds for all $k\in\big\{1,2,...,n\big\}$ so we have a uniform bound-- the maximum modulus for an eigenvalue of $A$ is 1 and this can only be reached on the ray given by the positive half of the real-line, i.e. when $\lambda =1 $. And conversely $-1$ is outside the boundary of every Gerschgorin Discs so $-1$ cannot be an eigenvalue of $A$.

Title: positive Markov Matrix


答:
Hint:

Differentiating the binomial formula, you obtain
$$n(1+x)^{n-1}=\sum_{k=0}^n k\binom nk x^{k-1},$$
which is almost your sum. What should you take for $x$?

Title: Binomial Theorem Derivative

Body:
Derive the binomial theorem with respect to $x$ (then setting $x$ to an appropriate value) to evaluate the sum $$\sum_{k=1}^n k\cdot(-3)^k{n \choose k}$$ for $n > 0$. Write your function as a function of $n$.

So, I have taken the derivative of the binomial theorem of $(n)(1+x)^{n-1}$.

That derivative looks kinda similar to the sum, so I tried plugging in -4 for k to get the -3, but that leaves me with negative factorials.


问:
$L^1$-integrability
My question comes from some problems I had with the boundedness of the Hilbert transform. In any case:

If a function $f$ is weak-$L^1(\mathbb{R})$ and $L^2(\mathbb{R})$, is it possible to say that it is also $L^1(\mathbb{R})$?

Thanks a lot.

答:
Consider $f(x)=\frac{1}{x}\chi_{[1,\infty)}(x)$, which is $L^2$ but not $L^1$ because of the singularity at $\infty$. But
$$|\{x\mid |f(x)|>\frac{1}{\lambda}\}\leq\frac{1}{\lambda}$$ so $f$ is w-$L^1$.

Title: $L^1$-integrability


问:
Is it possible to express "any set B composed of any two elements from set A" using set theory notation?
I have a set A with three elements. I'd like to express another set B in terms of a limited number of elements (two in this example) from set A.

In this case I realize that there would be a number of possible B sets, but I'm interested in expressing that B could be any of those sets.

Alternatively, set C which is one of the possible B sets.

Is this possible, or should I be looking for some other notation than set theory?

答:
It's not uncommon to use binomial coefficients for this purpose:
$\tbinom{M}{c}=\{S\subseteq M\mid |S|=c\}$. The motivation fur this notation is that $\tbinom{|M|}{c}=\left| \tbinom{M}{c}\right|$. But, as you see in this answer, this notation isn't optimal for inline math. It's, however, quite common in graph theory (see https://mathoverflow.net/questions/36714/notation-for-a-graph-without-any-edges).

Another possibility is writing $\wp_c(M)$ for this set, as it is a subset of the power set.


问:
What's wrong with my simplification of $\frac1i$?
Supposedly, $\frac1i=-i$.
However, my simplification reaches another result:
$$\frac1i=\frac{\sqrt1}{\sqrt{-1}}=\sqrt{\frac1{-1}}=\sqrt{-1}=i\text.$$
What's wrong with my process?

答:
The formula $\sqrt{\frac{a}{b}} = \frac{\sqrt{a}}{\sqrt{b}}$ is only guaranteed to be valid when $a,b$ are positive real numbers.

For complex numbers, all bets are off.


答:
From your work that $E[y]=6$ (on average it will take $6$ rolls of two dice):

You can say that you will have an average of $12$ single die rolls.

A single die roll has expected value $3.5$ (this is true even in the case that the die is part of a roll of doubles).

Can you take it from there?

Title: Throw dice till numbers are the same

Body:
Let's consider the following experience : we throw two dices till same number on two dices appears. I want to calculate expected sum of all dices appeared.

My work so far

I wanted to do it (and also I found it very intuitive) to do it by wold's decomposition theorem. The sum then will be presented by formula $E[S_n]=E[T]E[X_1]$, where $T$ is the stopping time.

How to calculate $E[T]$ ?

$P(Y=1)=\frac16$

$P(Y=2)=\frac56 \cdot \frac16$

$P(Y=n)=(\frac{5}{6})^{n-1} \cdot \frac16$

So :

$$E[Y]=\sum_{i=1}^\infty i \cdot P(Y=i)=1 \cdot \frac16 +2 \cdot \frac56 \cdot \frac16+...$$

And it's type of series $\sum_{i=1}^{\infty} i(1-p)^{i-1}p$ where $p \in [0,1]$ and this sum equals to $\frac1p$. So my sum above equals to 6 and that's exactly $E[T]$

why it would be good to use wold's theorem? Because it's very easy to calculate either $E[X_1]$ or $E[T]$ (calculated above). However, I don't know how should I define set $T=\inf\{...\}$ that will show that equality $E[S_n]=E[T]E[X_1]$ holds. I'm not sure how to strictly justify it.


问:
Expected Value for a Game with Multiple Rounds
I was wondering what the general approach is for calculating the expected value of a game that has multiple rounds?

For example, say in my game that I first flip a fair coin. If it's heads, then I get 10 dollars and move on to the next round. If it's tails, I pay 5 dollars and do not move onto the next round. In the second round I roll a fair 6-sided die. If it's a 1 then I get 30 dollars, otherwise I pay 10 dollars.

How should I go about calculating the expected value for playing a game like this?

答:
during the first round you have a $0.5$ probability of moving on to the second, and a $0.5$ probability of losing. So your expected value just based on that first round would be

$E(X)=\sum{}x*f(x)$ or $0.5*-5 +0.5*10 = 2.5$.

But since there's a second round, we need to include the expected value of the second round.

That would be $\frac{1}{6} * 30 +\frac{5}{6}* -10$, or $-3.333$.

So the final answer should be $0.5*-5 +0.5*(10-3.333) = 0.833333$.


问:
Prove by induction $\left(1-\frac{1}{2}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$
Prove by induction $\left(1-\frac{1}{2}\right)\left(1-\frac{1}{4}\right)\left(1-\frac{1}{8}\right)\ldots\left(1-\frac{1}{2^{n}}\right)\geq\frac{1}{4}+\frac{1}{2^{n+1}}$

What would be the best way to solve this by the induction method?

答:
$$
(1-\delta)(1-\varepsilon) = 1 - \delta - \varepsilon + \delta\varepsilon > 1 - (\delta + \varepsilon)
$$


问:
How do I find the probability mass function of this new set.
Let X be a random variable with $\mathsf P[X\in{0,1,2}]=1, \mathsf{E}[X]=4/3,$ and $\mathsf{Var}[X]=5/9,$ how would I go about finding the PMF of the set $Y=|X-1|? $

答:
Let the probabilities of obtaining $0, 1, 2$ as $a,b,c,$ respectively, where $a+b+c=1.$

Then, we have $\mathsf{E}[X] = (0 \cdot a) + (1\cdot b ) + (2 \cdot c) = b + 2c = \frac43 .$

Likewise, $\mathsf{E}[X^2] = (0^2 \cdot a) + (1^2\cdot b ) + (2^2 \cdot c) = b + 4c = (b + 2c) + 2c = \frac43 + 2c.$

Then, $$\frac59 = \mathsf{Var}[X] = \mathsf{E}[X^2] - (\mathsf{E}[X])^2 = \left (\frac43 + 2c \right ) - \left(\frac 43 \right)^2 $$

Solving for $c$ gives $$ c = \frac12 \implies b = \frac13 \implies a = 1-b-c = \frac16$$

Then the PMF of $X$ is $$X =
\begin{cases} 0, \quad \mathsf{Pr} = 1/6 \\
1,  \quad \mathsf{Pr} = 1/3 \\
2,  \quad \mathsf{Pr} = 1/2 \end{cases}
\quad \implies \quad
X -1 =
\begin{cases} -1, \quad \mathsf{Pr} = 1/6 \\
0,  \quad \mathsf{Pr} = 1/3 \\
1,  \quad \mathsf{Pr} = 1/2 \end{cases}
$$

Or $$
Y = |X -1| =
\begin{cases}
0,  \quad \mathsf{Pr} = 1/3 \\
1,  \quad \mathsf{Pr} = 1/2 + 1/6 = 2/3 \end{cases}
$$

In other words, $Y$ is a Bernoulli distribution with parameter $\frac23.$


问:
Find the limit: $\lim_{n \to +\infty}(\frac{1^p + 2^p + ... + n^p}{n^p} - \frac{n}{p + 1})$, where $p \in \mathbb{N}$
Find the limit: $\lim_{n \to +\infty}(\frac{1^p + 2^p + ... + n^p}{n^p} - \frac{n}{p + 1})$, where $p \in \mathbb{N}$.

I've got an idea to transform this sequence into $lim_{n\to +\infty}(\frac{x_n}{y_n})$ and to use Stolz's theorem.

But in 2 days I didn't get ideas for this transformation.

答:
Hint:

You should try showing that, in general:

$$\sum_{k=1}^{n} k^p = \frac{n^{p+1}}{p+1} + \frac{1}{2}n^p+ q(n)$$

where $q(n)$ is a polynomial in $n$ of the $(p-1)$-th degree. Can you use this to simplify the expression that you're taking the limit of?


问:
Integral relation between Hermite and Laguerre polynomials
I'd like to proove the following integral relation

$$ \frac{1}{2^m m!} \frac{1}{\sqrt{\pi}} \int_{-\infty}^{\infty}\,\mathrm{d}\zeta \, e^{-\zeta^2} H_m(\zeta+\zeta_1)H_m(\zeta+\zeta_2) = L_m(-2\zeta_1\zeta_2)$$

where $H_m(x)$ is the $m$th Hermite polynomial and $L_m(x)$ is the $m$th Laguerre polynomial.
I tried proving it with these realtions I found on Wikipedia

$$ H_m(x+y)=\sum_{k=0}^m \binom{m}{k}H_k(x)(2 y)^{(n-k)}$$

and

$$ L_m(x)=\sum_{k=0}^m \binom{m}{k}\frac{(-x)^k}{k!}$$

by using the othonormality of the Hermite polynoms, but I got stuck at some point. Can you help me here?

答:
The solution is most easily constructed if you use the Hardy-Hille formula for Hermite polynomials.  (I gave a different kind of proof in MSE 3694450.)  To do so, we'll make a generating function from the left hand side of the equation:
$$ I_m(x,y):=\frac{1}{\sqrt{\pi}} \frac{2^{-m}}{m!} \int_{-\infty}^\infty dt\  e^{-t^2} H_m(t+x) \ H_m(t+y) $$
$$ F(x,y,z)=\sum_{m=0}^\infty z^m I_m(x,y) = \frac{1}{\sqrt{\pi}} \int_{-\infty}^\infty dt\  e^{-t^2}  \sum_{m=0}^\infty \frac{z^m}{m!2^m}H_m(t+x) \ H_m(t+y) $$
$$ =  \frac{1}{\sqrt{\pi(1-z^2)}} \int_{-\infty}^\infty dt\  e^{-t^2}
\exp{\big( \frac{2z(t+x)(t+y) - ((t+x)^2 + (t+y)^2)z^2}{1-z^2} \big) }
$$
where in the last step the Hardy-Hille formula was used. Do the Gaussian integral and algebra.  You'll find
$$ F(x,y,z)=\frac{1}{1-z} \exp{\big(\frac{2\ xy \ z}{1-z} \big)} $$
However, it is well known that the Laguerre polynomials have the generating function

$$\frac{1}{1-z} \exp{\big(\frac{-q \ z}{1-z} \big)}= \sum_{n=0}^\infty L_n(q) z^n $$

Equate coefficients of z to complete the proof.


问:
Viewing groups as objects of the concrete category $\mathsf{Grp}$
Sometimes I ask questions about how structures (groups, topological spaces etc.) ought to be defined, and oftentimes a categorial solution is suggested. Here is a recent example.

Now from my relatively ignorant point of view, it would seem that these solutions have dire limitations. Indeed, they seem unworkable. Of course, I'm probably wrong. Hence the following question.

Lets view $\mathsf{Grp}$ as a concrete category - that is, a category equipped with a forgetful functor to $\mathsf{Set}$ - and lets take the statement "$G$ is a group" to mean "$G$ is an object of $\mathsf{Grp}$". However, $\mathsf{Grp}$ will only be defined up to categorial equivalence.

Under these definitions, does it make sense to speak of "the binary operation of a group $G$?" And if not, how does one get around this?

答:
There is a perfectly good way of defining the category $\mathbf{Grp}$ up to equality; people who say it is only defined up to categorical equivalence are being too dogmatic.

For the purposes of recovering the binary operation of a group, all you need is to identify a group $F 2$ freely generated by two generators, $x$ and $y$, and a group $F 1$ freely generated by one generator, $z$. The group $F 1$ has the following universal property: the map $\mathrm{Hom}(F 1, G) \to G$ sending a homomorphism $f : F 1 \to G$ to the element $f(z)$ is a bijection. There is then a unique group homomorphism $\delta :  F 1 \to F 2$ sending $z$ to $x y$, as well as $i_1 : F 1 \to F 2$ sending $z$ to $x$ and $i_2 : F 1 \to F 2$ sending $z$ to $y$. Once these are known, the induced maps $\mathrm{Hom}(F 2, G) \to \mathrm{Hom}(F 1, G)$ allow us to recover the binary operation on $G$: $i_1$ and $i_2$ jointly induce a bijection $\mathrm{Hom}(F 2, G) \to \mathrm{Hom}(F 1, G) \times \mathrm{Hom}(F 1, G) \cong G \times G$, and using this identification, the map
$$G \times G  \cong \mathrm{Hom}(F 2, G) \to \mathrm{Hom}(F 1, G) \cong G$$
induced by $\delta : F 1 \to F 2$ is readily seen to be the binary operation of $G$.

It is straightforward to see that some extra input is required, because $\mathbf{Grp}$ has an involution that preserves underlying sets and sends a group $G$ to the opposite group $G^{\mathrm{op}}$, so we cannot distinguish between the operation $(x, y) \mapsto x y$ and the operation $(x, y) \mapsto y x$ just by knowing the functor $U : \mathbf{Grp} \to \mathbf{Set}$.


问:
Is the "ancestor" relationship impossible to define in first-order logic?
Definition: Given a binary relationship $R$, an ancestor relationship $R^*$ exists between $a$ and $b$ iff there is a chain of relationships $R$ connecting $a$ and $b$, for example, $Rax$, $Rxy$ and $Ryb$.

$R^*$ is trivial to define in logic programming (whose logical aspect is often said to be a subset of first-order logic). However, a paper I was reading claimed that $R^*$ cannot be defined in first-order logic. Is this true?

A Prolog definition of ancestor given parent:

$$
\begin{align}
ancestor(X, Y) & \leftarrow parent(X, Y)
\\
ancestor(X, Y) & \leftarrow parent(X, Z) \land ancestor(Z, Y)
\end{align}
$$

答: The main reason is that First-Order Logic uses Tarskian semantics and logic programming uses Herbrand semantics. This has various consequences when it comes to expressiveness and other properties like compactness and completeness. For more details, see for example The Herbrand Manifesto or Herbrand Semantics, where your example (transitive closure) is discussed.</p>


问:
Triple Integral over a Superquadric
How do I solve the following:

$\iiint _V (x^2+y^2+z^2) dxdydz $, where $V=\{x^{2n}+y^{2n}+z^{2n} \leq 1\}$ is a superquadric?

答:
By symmetry,
$$ \iiint _V (x^2+y^2+z^2) dxdydz=24\iiint_{V^+} x^2 dxdydz $$
where
$$ V^+=\{x^{2n}+y^{2n}+z^{2n} \leq 1, x\ge0,y\ge0,z\ge0\}. $$
Let
$$ x=r^{\frac1n}\sin^{\frac1n}(\theta)\cos^{\frac1n}(\phi), x=r^{\frac1n}\sin^{\frac1n}(\theta)\cos^{\frac1n}(\phi),z=r^{\frac1n}\cos^{\frac1n}(\theta). $$
Then $V^+$ becomes
$$ \bar{V}^+=\{(r,\theta,\pi): 0\le r\le1, 0\le\theta,\phi\le\frac{\pi}{2}\}. $$
Now
$$ \det\frac{\partial(x,y,z)}{\partial r\partial \theta\partial\psi}=\frac{1}{n^3}r^{\frac{3}{n}-1} \sin ^{\frac{2}{n}-1}(\theta ) \cos ^{\frac{1}{n}-1}(\theta ) \sin
   ^{\frac{1}{n}-1}(\phi ) \cos ^{\frac{1}{n}-1}(\phi ) $$
and then
\begin{eqnarray}
&&\iiint _V (x^2+y^2+z^2) dxdydz\\
&=&24\iiint_{V^+} x^2 dxdydz\\
&=&24\int_0^1\int_0^{\pi/2}\int_0^{\pi/2} r^{\frac2n}\sin^{\frac2n}\theta\cos^{\frac2n}\phi \det\frac{\partial(x,y,z)}{\partial r\partial \theta\partial\phi}drd\theta d\phi\\
&=&\frac{24}{n^3}\int_0^1\int_0^{\pi/2}\int_0^{\pi/2}r^{\frac{5}{n}-1} \sin ^{\frac{4}{n}-1}(\theta ) \cos ^{\frac{1}{n}-1}(\theta ) \sin
   ^{\frac{1}{n}-1}(\phi ) \cos ^{\frac{3}{n}-1}(\phi )drd\theta d\phi\\
&=&\frac{24}{n^3}\int_0^1r^{\frac{5}{n}-1}dr\int_0^{\pi/2}\sin ^{\frac{4}{n}-1}(\theta ) \cos ^{\frac{1}{n}-1}(\theta )d\theta \int_0^{\pi/2}  \sin
   ^{\frac{1}{n}-1}(\phi ) \cos ^{\frac{3}{n}-1}(\phi )d\phi\\
&=&\frac{24}{n^3}\cdot\frac{n}{5}\cdot \frac{\Gamma \left(\frac{2}{n}\right) \Gamma \left(\frac{1}{2n}\right)}{2 \Gamma
   \left(\frac{5}{2n}\right)}\cdot\frac{\Gamma \left(\frac{1}{2n}\right) \Gamma \left(\frac{3}{2n}\right)}{2 \Gamma
   \left(\frac{2}{n}\right)}\\
&=&\frac{6}{5n^2}\frac{ \Gamma^2 \left(\frac{1}{2n}\right)\Gamma \left(\frac{3}{2n}\right)}{\Gamma
   \left(\frac{5}{2n}\right)}.
\end{eqnarray}
Here
$$ \int_0^{\pi/2}\sin^{-1+p}(t)\cos^{-1+q}(t)dt=\frac{\Gamma \left(\frac{p}{2}\right) \Gamma \left(\frac{q}{2}\right)}{2 \Gamma
   \left(\frac{p+q}{2}\right)} $$
is used.

Title: Triple Integral over a Superquadric


问:
Throw dice till numbers are the same
Let's consider the following experience : we throw two dices till same number on two dices appears. I want to calculate expected sum of all dices appeared.

My work so far

I wanted to do it (and also I found it very intuitive) to do it by wold's decomposition theorem. The sum then will be presented by formula $E[S_n]=E[T]E[X_1]$, where $T$ is the stopping time.

How to calculate $E[T]$ ?

$P(Y=1)=\frac16$

$P(Y=2)=\frac56 \cdot \frac16$

$P(Y=n)=(\frac{5}{6})^{n-1} \cdot \frac16$

So :

$$E[Y]=\sum_{i=1}^\infty i \cdot P(Y=i)=1 \cdot \frac16 +2 \cdot \frac56 \cdot \frac16+...$$

And it's type of series $\sum_{i=1}^{\infty} i(1-p)^{i-1}p$ where $p \in [0,1]$ and this sum equals to $\frac1p$. So my sum above equals to 6 and that's exactly $E[T]$

why it would be good to use wold's theorem? Because it's very easy to calculate either $E[X_1]$ or $E[T]$ (calculated above). However, I don't know how should I define set $T=\inf\{...\}$ that will show that equality $E[S_n]=E[T]E[X_1]$ holds. I'm not sure how to strictly justify it.

答:
One way is to just manually take all sums. The first part is where all of them are equal sums, the second is where one of them is $1$ and other is between $2$ and $6$, so on..

The last part is for the rolls to continue with $\frac{5}{6}$ probability.

It can surely be optimized but given it is just two dice, this works.

$E(X) = \displaystyle \frac{1}{36} (2 + 4 + 6 + 8 + 10 + 12) + \frac{2}{36}(3 + 4 + 5 + 6 + 7) + \frac{2}{36}(5 + 6 + 7 + 8) + \frac{2}{36}(7 + 8 + 9) + \frac{2}{36} (9 + 10) + \frac{2}{36}(11) + \frac{5}{6}E(X).$

$E(X) = \displaystyle \frac{42}{36} + \frac{50}{36} + \frac{52}{36} + \frac{48}{36} + \frac{38}{36} + \frac{22}{36} + \frac{5}{6}E(X)$

$E(X) = \displaystyle \frac{252}{6} = 42$.

Title: Throw dice till numbers are the same


问:
Let $(R, +, \cdot)$ be a finite ring without zero divisors, show that $R$ has a neutral element for $\cdot$.
I have to prove the question in the title, but I am having some difficulties.

Here's a sketch what I've already tried:

Choose $a \in R$.
Because $R$ is finite, there exist positive integers $i$ and $j$ ($i\neq j$) so that $a^i = a^j \Leftrightarrow a^ia = a^ja \Leftrightarrow a^ia - a^ja = 0 \Leftrightarrow a^j(a^{i-j}a - a) = 0$.

Because $R$ doesn't have any zero divisors and $a^j \neq 0$, we must have $a^{i-j}a - a = 0$ and thus, $a^{i-j}a = a$.

So now I think that $a^{i-j}$ is the neutral element for $\cdot$ but I'm not sure how to proceed.

Could anyone help me?

Thanks!!

答:
So at this point, you have $a^{i-j}a = a$. We want to show that $a^{i-j}$ is in fact the identity element for $\cdot$. Now, this amounts to saying that for any $b \in R$, $a^{i-j}\cdot b = b$. So we have the following:

$a^{i-j} \cdot b = c
\iff a \cdot a^{i-j} \cdot b = a \cdot c
\iff a^{i-j}a \cdot b = a \cdot c
\iff ab = ac $.

But since we have no zero divisors, this means that $b = c$.


问:
Minimizing the expectation over a set, wrt to the Gaussian measure
I have recently read a proof [1] where, at the last step, the authors use an inequality which basically amounts to a lower bound on
$\int_\mathbb{R} \mathbf{1}_A(x)|x| \phi(x)dx$, where $\phi$ is the Gaussian pdf ($\phi(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}}$) and $A$ is a Borel set subject to $\int_\mathbb{R} \mathbf{1}_A(x)\phi(x)dx = p$. The bound they use is $p^2/2$; I was wondering if this was tight (up to a constant factor), or if one could improve this to get better than a square dependence on $p$:
$$
\min_{A\in\mathcal{B}_\mathbb{R}} \int_\mathbb{R} \mathbf{1}_A(x)|x| \phi(x)dx\qquad\\
\text{s.t.} \int_\mathbb{R} \mathbf{1}_A(x)\phi(x)dx = p
$$

Does anyone know if a result of this type is known? Any help or suggestion is welcome.

Clement.

[1] Theorem 4 of Testing halfspaces In In Proc. 20th Annual Symposium on Discrete Algorithms (SODA (2009) by Kevin Matulef, Rocco A. Servedio, Ronitt Rubinfeld

答:
One looks for the minimal $E[|X|;X\in A]$ with $P[X\in A]=p$, where $X$ is standard normal. The optimal set $A$ is some $A=(-a,a)$ (see Edit below), then
$$
E[|X|;X\in A]=\frac2{\sqrt{2\pi}}(1-\mathrm e^{-a^2/2}),\qquad
P[X\in A]=\frac2{\sqrt{2\pi}}\int_0^a\mathrm e^{-x^2/2}\mathrm dx.
$$
When $a\to0$, $E[|X|;X\in A]\sim a^2/\sqrt{2\pi}$ and $P[X\in A]\sim2a/\sqrt{2\pi}$, thus, no better lower bound than
$$
E[|X|;X\in A]\geqslant cP[X\in A]^2,\qquad c=\sqrt{2\pi}/4,
$$
can hold for every $a$. Let us prove the bound above is indeed universal.

Getting rid of irrelevant multiplicative constants, one sees that the claim holds if and every if $u(a)\geqslant0$ for every $a\geqslant0$, where
$$
u(a)=1-\mathrm e^{-a^2/2}-\frac12\left(\int_0^a\mathrm e^{-x^2/2}\mathrm dx\right)^2.
$$
Note that $u(0)=0$ and that, for every $a\geqslant0$,
$$
u'(a)=\mathrm e^{-a^2/2}\left(a-\int_0^a\mathrm e^{-x^2/2}\mathrm dx\right)\geqslant0,
$$
thus the claim holds. Finally, the optimal universal lower bound is
$$
\int_\mathbb{R} \mathbf{1}_A(x)\phi(x)dx = p\implies\int_\mathbb{R} \mathbf{1}_A(x)|x| \phi(x)dx\geqslant\frac{\sqrt{2\pi}}4\,p^2.
$$
Edit: Assume that $P[X\in A_+]=P[0\leqslant X\leqslant a_+]$ where $A_+=A\cap(0,+\infty)$ and define $A_0=A_+\cap(0,a_+)$, $A_1=(0,a_+)\setminus A_+$ and $A_2=A_+\setminus(0,a_+)$, thus $(0,a_+)=A_0\cup A_1$, $A=A_0\cup A_2$ and $P[X\in A_1]=P[X\in A_2]$ with $A_1\subseteq(0,a_+)$ and $A_2\subseteq(a_+,+\infty)$.

Thus, $E[|X|;X\in A_1]\leqslant a_+P[X\in A_1]$ and $E[|X|;X\in A_2]\geqslant a_+P[X\in A_2]$, that is, $E[|X|;X\in A_1]\leqslant E[|X|;X\in A_2]$. Adding $E[|X|;X\in A_0]$ to both sides, one gets $E[|X|;0\leqslant X\leqslant a_+]\leqslant E[|X|;X\in A_+]$.

Likewise, replacing $A_-=A\cap(-\infty,0)$ by $(-a_-,0)$ where $P[X\in A_-]=P[-a_-\leqslant X\leqslant 0]$ yields $E[|X|;X\in A_-]\geqslant E[|X|;-a_-\leqslant X\leqslant 0]$ hence $E[|X|;X\in A]\geqslant E[|X|;-a_-\leqslant X\leqslant a_+]$ where $P[X\in A]=P[-a_-\leqslant X\leqslant a_+]$.

It remains to show that $E[|X|;-a_-\leqslant X\leqslant a_+]\geqslant E[|X|;-a\leqslant X\leqslant a]$ where $a$ is uniquely defined by the condition $P[-a_-\leqslant X\leqslant a_+]=P[-a\leqslant X\leqslant a]$. This is done as above, comparing $|X|$ on the two parts of $(-a_-,a_+)\triangle(-a,a)$.

Finally, $E[|X|;X\in A]\geqslant E[|X|;|X|\leqslant a]$, where $P[X\in A]=P[|X|\leqslant a]$.


问:
Prove that the lim sup of this sequence is $\ge$ than $0$
Let $\sum a_n$ be a convergent series of arbitrary terms. If $p_n$ increases monotonely to $+\infty$ in such a way that $\sum \frac1{p_n}$ is divergent, then we have $$\limsup \frac{p_1a_1+p_2a_2+\ldots+p_na_n}{n} \ge 0$$
I only know that:

$\frac{p_1a_1+\ldots+p_na_n}{p_n} \to 0$ as $n\to +\infty$ by Kronecker's lemma, hence we need only to look at the case $\limsup \frac{p_n}{n} = +\infty$. I'm not sure if this is useful, but I think that we should apply summation by parts here, however I don't know how to use the fact that $\sum\frac1{p_n}$ is divergent. Can you give me a hint?

答:
Let's go for a contrapositive. We shall keep the assumption that $(p_n)$ is monotonically increasing (not necessarily strictly) and eventually positive. And, since we want a contrapositive, we shall assume that
$$\limsup_{n \to \infty} \frac{p_1a_1 + p_2a_2 + \ldots + p_na_n}{n} < 0\,.$$
Thus there is an $\varepsilon > 0$ and an $n_0$ such that for all $n > n_0$ we have
$$S_n := \sum_{k = 1}^{n} a_kp_k \leqslant -\varepsilon n\,.$$
We can assume that $n_0$ is so large that $p_n > 0$ for $n > n_0$. Now let $n > n_0$. We then have
\begin{align}
\sum_{k = n_0+1}^{n} a_k
&= \sum_{k = n_0+1}^{n} \frac{S_k - S_{k-1}}{p_k} \\
&= -\frac{S_{n_0}}{p_{n_0+1}} + \sum_{k = n_0+1}^{n} S_k\biggl(\frac{1}{p_k} - \frac{1}{p_{k+1}}\biggr) + \frac{S_n}{p_{n+1}} \\
&\leqslant -\frac{S_{n_0}}{p_{n_0+1}} -\varepsilon \Biggl[\sum_{k = n_0+1}^{n} k\biggl(\frac{1}{p_k} - \frac{1}{p_{k+1}}\biggr) + \frac{n}{p_{n+1}}\Biggr] \\
&= -\frac{S_{n_0}}{p_{n_0+1}} - \varepsilon\Biggl[\frac{n_0}{p_{n_0+1}} + \sum_{k = n_0+1}^{n} \frac{k - (k-1)}{p_k}\Biggr] \\
&= -\frac{S_{n_0}}{p_{n_0+1}} - \varepsilon\frac{n_0}{p_{n_0+1}} - \varepsilon \sum_{k = n_0+1}^{n} \frac{1}{p_k}\,.
\end{align}
From this inequality we deduce

if $\sum a_n$ converges, then $\sum_{n > n_0} \frac{1}{p_n}$ converges too (and if we additionally assume that $p_n \neq 0$ for all $n$ we can drop the $n > n_0$ condition).

if $\sum_{n > n_0} \frac{1}{p_n} = +\infty$, then $\sum a_n = -\infty$.

Thus we have proved two contrapositives, for dropping different parts of the hypothesis, and consequently we proved that if $\sum a_n$ converges, $(p_n)$ is monotonically increasing, never $0$, and $\sum \frac{1}{p_n} = +\infty$, then
$$\limsup_{n \to \infty} \frac{p_1a_1 + p_2a_2 + \ldots + p_na_n}{n} \geqslant 0\,.$$


问:
determining whether a graph on $8$ vertices is nonplanar

Determine, with justification, whether the graph $G$ below is nonplanar.

I'm not sure whether the graph is planar. I can't really see how to find a planar embedding for it, despite having attempted to draw it with no edges crossing.

答: Your graph is indeed planar, as shown here: