问:
enumerating permutations with exactly $k$ inversions
For a few days, I've been unsuccessfully trying to come up with an algorithm that enumerates the permutations of a set (of cardinality $= n$) with exactly $k$ inversions.

Could you help me?

Thanks!

答:
In $q-$ calculus (recall that $[n]_q=\frac{1-q^n}{1-q}$) there is the concept of $q-$factorial and is not hard to show that $$[n]_q!=[1]_1\cdots [n]_q=\sum _{i=0}^{\binom{n}{2}}A_{n,k}q^k,$$ where $A_{n,k}$ is the number of permutations of size $n$ with exactly $k$ inversions.

The proof of that is just by multiplying out and noticing that if you have a permutation of size $n-1$ with $\ell$ inversions, then you can create a permutation of $n$ by inserting $n$ in one of the available slots. Depending on where you put it, you will create a certain number of inversions. For example if $\pi = 21$ with $1$ inversion, I can place $3$ in these ways
$$\color{red}{3}21,2\color{red}{3}1,21\color{red}{3}.$$ Creating $1+\color{red}{2},1+\color{red}{1},1+\color{red}{0}$ inversions. Use this recursion to enumerate them.

Edit:
Here you have what I meant in Python/Sage

```<code>def tal(n,k):
    if n==1:
        if k==0:
            return [[1]]
        return []
    s = []
    for j in range(0,n):
        if k-j<0:
            break
        t = tal(n-1,k-j)
        for x in t:
            y = x[:len(x)-j]
            y.append(n)
            y.extend(x[len(x)-j:])
            s.append(y)
    return s
tal(5,3)
</code>```

Body:
In $q-$ calculus (recall that $[n]_q=\frac{1-q^n}{1-q}$) there is the concept of $q-$factorial and is not hard to show that $$[n]_q!=[1]_1\cdots [n]_q=\sum _{i=0}^{\binom{n}{2}}A_{n,k}q^k,$$ where $A_{n,k}$ is the number of permutations of size $n$ with exactly $k$ inversions.

The proof of that is just by multiplying out and noticing that if you have a permutation of size $n-1$ with $\ell$ inversions, then you can create a permutation of $n$ by inserting $n$ in one of the available slots. Depending on where you put it, you will create a certain number of inversions. For example if $\pi = 21$ with $1$ inversion, I can place $3$ in these ways
$$\color{red}{3}21,2\color{red}{3}1,21\color{red}{3}.$$ Creating $1+\color{red}{2},1+\color{red}{1},1+\color{red}{0}$ inversions. Use this recursion to enumerate them.

Edit:
Here you have what I meant in Python/Sage

def tal(n,k):
    if n==1:
        if k==0:
            return [[1]]
        return []
    s = []
    for j in range(0,n):
        if k-j<0:
            break
        t = tal(n-1,k-j)
        for x in t:
            y = x[:len(x)-j]
            y.append(n)
            y.extend(x[len(x)-j:])
            s.append(y)
    return s
tal(5,3)


问:
If $\mathcal C$ is semiadditive, then $\text{Hom}(a,b)$ in $\mathcal C$ is monoid.
Let $f,g\in\text{Hom}(a,b)$. I want to define $f+g$ and show $f+g=g+f$.

Take $f\times g\in \text{Hom}(a,b\oplus b)$ such that
$$\pi_b^1\circ(f\times g)=f\\\pi_b^2\circ(f\times g)=g$$

Take $\nabla_b\in \text{Hom}(b\oplus b, b)$ such that
$$\nabla_b\circ i_b^1=\nabla_b\circ i_b^2=\text{id}_b$$

Take $\varphi\in\text{Hom}(b\oplus b,b\oplus b) $ such that
$$\varphi\circ i_b^1=i_b^2\\\varphi\circ i_b^2=i_b^1$$

Then, since $(\nabla_b\circ \varphi)\circ i_b^1=(\nabla_b\circ\varphi)\circ i_b^2=\text{id}_b$, $\nabla_b\circ \varphi=\nabla_b$.

Take $\psi\in\text{Hom}(b\oplus b,b\oplus b)$ such that
$$\pi_b^1\circ\psi=\pi_b^2\\\pi_b^2\circ\psi=\pi_b^1$$

Samely, $\psi\circ (f\times g)=g\times f$.

If I could show $\varphi=\psi$, then :

$$
\begin{align}f+g=&\nabla_b\circ (f\times g)\\=&\nabla_b\circ \varphi\circ (f\times g)\\=&\nabla_b\circ \psi\circ (f\times g)\\=&\nabla_b\circ (g\times f)=g+f\end{align}$$

But I don't know how to show $\varphi=\psi$. How do I show this, or is my approach wrong?

答:
$\require{AMScd}$I don't understand your notation, or your definition of $f+g$: if you define
$$
A \overset{\Delta_A}\to A\oplus A \overset{f\oplus g}\to B\oplus B \overset{\nabla_B}\to B
$$ this sets up a commutative binary operation simply because the diagram
$$
\begin{CD}
A @>>> A\oplus A @>f\oplus g>> B\oplus B @>>> B \\
@|@V\sigma_AVV@VV\sigma_BV@|\\
A @>>> A\oplus A @>>g\oplus f> B\oplus B @>>> B
\end{CD}
$$ is commutative, if the vertical arrows are the symmetry isomorphisms.

ContentLicense: CC BY-SA 4.0


问:
How to simplify $(\lnot p \rightarrow \lnot q) \land p$ and match the right statement?
The problem is as follows:

"If Maria does not leave her house then she does not catch a cold, but Maria leaves her house" is equivalent to:

I. Maria does not leave her house.

II. It is not true that, Maria leaves her house and catches a cold.

III. Maria leaves her house.

Given these statements which of the alternatives match the right answer?

The alternatives given in my book are as follows:

$\begin{array}{ll}
1.&\textrm{Only III}\\
2.&\textrm{I and II}\\
3.&\textrm{Only II}\\
4.&\textrm{II and III}\\
\end{array}$

In my attempt to solve this problem I translated the statement in these terms of propositional logic.

If Maria does not leave her house then she does not catch a cold, but Maria leaves her house

Then

$\textrm{Maria leaves her house = p}$

$\textrm{Maria catches a cold = q}$

Then:

$(\lnot p \rightarrow \lnot q) \land p$

But how to simplify this expression?. Can someone help me?. Is this the right or the appropiate way to translate what it was mentioned?.

答: Here's the intuitive way to think about what's going on.  In a world where Maria does in fact leave her house, the implication, "If Maria does not leave her house, then consequences follow" gives you no information at all.  So the only piece of actual information you have is that Maria leaves her house.</p>


问:
rate of escape free group with 2 generators
I want to find rate of escape (drift) on free group (with d generators).

From here (page 2): https://arxiv.org/pdf/math/0506129.pdf I know the answer = 1

But I can't fully figure out why

I know there exist next way to compute drift (from Vershik: Dynamic theory of growth in groups: https://www.deepdyve.com/lp/iop/dynamic-theory-of-growth-in-groups-entropy-boundaries-examples-ZH4dbCaiRQ?key=iop-publishing - sorry, I don't have a pdf version to make a screenshot for now):

Let $G = <a_1, ..., a_d, a_1^{-1}, ..., a_d^{-1}> = <S>$, (I will assume d = 2) let $\mu$ - measure with support $S$ (we also assume it is probabilistic and uniform, i.e. $\mu(S) = 1, \mu(g) = \frac{1}{2d}, g \in S$. We then introduce $\mu^{*n}$ - $n^{th}$ convolution ($\mu^{*n}(A) = (\mu \times ... \times \mu){(g_1, ..., g_n): g_i \in S, g_1 \cdot ... \cdot g_n \in A \subset G}$) and the space $(G^{\infty}, \mu^{\infty})$, $G^{\infty}$ - space of trajectories (we can think of it as infinite sequence of elements in S), $\mu^{\infty}$ - measure on that space (it will be nonzero on sets $A_{w_n} = $ {all paths with first n letters fixed} (and it can be easily calculate: $w_n$ as a n-length word, so we can associate in with some element $g_n$ in G, so $\mu^{\infty}(A_{w_n}) = \mu^{*n}(g_n) = $ number of ways represent $g_n$ as a product of n elements from S divided by number of words of length n

Next, drift for G is $l_\mu = \lim_{n \to \infty}\frac{E_{\mu^{*n}}L(g)}{n}$, L(g) - "length" of word g. So, for fixed n, $E_{\mu^{*n}}L(g)$ is "expected reduced length" of n-length word in alphabet S

Vershik in his note has the following lemma: for almost every $\omega = (w_1, w_2, ..., w_n, ...) \in G^{\infty}$, $\lim_{n \to \infty}\frac{L_n(\omega)}{n}$ converge to 1 (by measure), where $L_n$ - length of $w_1 \cdot ... \cdot w_n$

To prove that we introduce $T: G^{\infty} \to G^{\infty}$ - left shift. I can proof that: $T$ - ergodic and $T$ with $L_n$ satisfy the conditions in Kingman's subadditive ergodic theorem, so $\lim_{n \to \infty}\frac{L_n(\omega)}{n}$ converge to some constant, but why is it converge to exactly 1?

Vershik in his notes said that converge by measure follows from almost sure convergence. So I guess $\mu^{\infty}(\omega \in G^{\infty}: lim_{n \to \infty}\frac{L_n(w)}{n} \neq 1) = 0$ must be some obvious statement, but I don't understand why. For fixed n we have $3^n$ reduced (honestly it is $4 \cdot 3^{n-1}$, but it doesn't matter) words and $4^n$ words, so number of reduced words of fixed length n divided by number of words of fixed length tends to 0, so we need observe some set of "almost reduced words" I guess, and show that "this set converge to whole $G^{\infty}$" or something like that

答:
The speed (rate of escape) on the free group with $d$ generators  is not 1 but rather $1-1/d$. In each step (when not in the identity) the walk will move forward with probability $(2d-1)/(2d)$ and backward with probability $1/(2d)$. See Chapter 13 in [1] for more on speed of random walks and in particular a formalization of this argument.

[1] https://rdlyons.pages.iu.edu/prbtree/


问:
The Ergodic Theorem and Bernoulli r.v.
Let $X_1, X_2, X_3, X_4$ be i.i.d. Bernoulli (1/5) random variables. When $i\ge 5$, we produce $X_i$ based on $X_1,...,X_{i-1}$ as follows: If $X_{i-1}=X_{i-2}=X_{i-3}=X_{i-4}=0$, then we set $X_i=1$; and in all the other cases we set $X_i$ to be a Bernoulli (1/5) random variable, independent of $X_1,...,X_{i-1}$. Prove that $\frac{1}{n}\sum_{i=1}^{n}X_i$ converges almost surely when $n\to \infty$ and find the distribution of the limit random variable.

Trying something:

According to the Ergodic Theorem, we know that $X_n=\frac{1}{n}\sum_{i=1}^{n}X_i$ converges almost surely to μ. If $X_{i-1}=X_{i-2}=X_{i-3}=X_{i-4}=0$, then we set $X_i=1$. This corresponds to a Markov chain with memory (4th order) as following:

$$P(X_i=1\mid X_{i-1}=0,X_{i-2}=0,X_{i-3}=0,X_{i-4}=0)=?$$

This case applies if, for example $i=10$, then $\left[ X_1, X_2,X_3,X_4,X_5,0,0,0,0,1\right]$. Otherwise, the outputs should be like this: $\left[ X_1, X_2,X_3,X_4,X_5,X_6,X_7,X_8,X_9,X_{10}\right]$.

The transition matrix should be something like:

$$T=\left[
         \begin{array}{ccc}
         \dfrac{4}{5} & \dfrac{1}{5}   \\
         \dfrac{4}{5} & \dfrac{1}{5}   \\
        \end{array}
    \right]$$

However, it may be affected by the condition above. Any hint?

Thanks for your help!

答:
In this kind of puzzle usually the answer is easy to guess and proving it is hard, but in this instance it's the other way around.

Consider the 1st order Markov chain $M$ whose state space is all 16 bitstrings of length 4, with the transition rule that $0000$ transitions to $0001$ with probability $1$, and all other bitstrings $xyzw$ transition to $yzw0$ with probability $4/5$ and to $yzw1$ with probability $1/5$.  The stated behavior of the $X_n$ sequence is such that the 4-tuples $T_n=(X_n,X_{n+1},X_{n+2},X_{n+3})$  in fact are a realization of $M$. Equivalently, the $X_n$ sequence is an order 4 Markov chain, that is, a chain with memory 4.   It is easy to check that $M$ is aperiodic and transitive, hence ergodic, hence the fraction of times such that $T_n\in S$ converges almost surely to $\pi(S)$, where $\pi$ is the unique stationary distribution for $M$, for all subsets $S$ of 4-long bitstrings.  Your problem is solved by the particular $S$ consisting of eight bitstrings of form $xyz1$.

The job of finding $\pi$ is more intricate than I expected.  For bitstring $s$, it seems (and I don't have a succinct explanation why) that $\pi(s)$ depends only on the number of $1$s in $s$,
and that $\pi(0000)=256/2101$, $\pi(0001)=320/2101$, $\pi(0011)=80/2101$, $\pi(0111)=20/2101$, and $\pi(1111)=5/2101$.

Added, 26,27 Dec:  A 5 state Markov chain $Y_n$ can be used to give this result, at well.  Here $Y_n=\min\{i\ge0: X_{n-i}=1\}$ encodes the idea that  "at time $n$, the most recent $1$ was seen $Y_n$ turns ago, that is, at time $n-Y_n$".  Its transition matrix is
$$\pmatrix{1/5&4/5&0&0&0\\1/5&0&4/5&0&0\\1/5&0&0&4/5&0\\1/5&0&0&0&4/5\\1&0&0&0&0}$$
and its stationary distribution is easy to work out:
$$\pi=(\pi_0,\ldots,\pi_4)=\left(\frac{625}{2101},\frac{500}{2101},\frac{400}{2101},\frac{320}{2101},\frac{256}{2101}\right).$$  Your answer is the limiting fraction of time that $Y_n=0$, namely $\pi_0=625/2101=1/\sum_{i=0}^4(4/5)^i$. The expected return time to $Y_n=0$ is $1/\pi_0=2101/625$.

Title: The Ergodic Theorem and Bernoulli r.v.


问:
Finding Expected Value of vector length?
We build a vector of digits, such that every time we pick a number randomly from {0,1,2,3,...,9} (For each digit the possibility of picking it is equal this 1/10 and not related to previous choices). We stop building out vector at the first time each digit appears at least once (Which means the last digit appears exactly once or else we can have a shorter vector which is a contradiction) Now I want to calculate Expected value of length of the vector created.

How can I solve this, I tried with indicators but don't think of any specific indicator what will be helpful here.

答:
Let's consider a similar problem.

Suppose I had a set of $p$ elements, and a subset of $q\leq p$ elements. What is the expected number of draws with replacement from the set of $p$ elements before we get one of the $q$ elements?

The answer is $\frac pq$.

So, our answer is $$\frac{10}1+\frac{10}2+\ldots+\frac{10}{10}=\frac{7381}{252}$$


问:
Calculate the matrix M(T) representing T relative to input basis E and output basis E'
Let$\  T:P_2(\mathbb R)\to\mathbb R^2 $
be the transformation
$\ T(p(x))=(p′(−1),p′′(0))$

$\ E=\{1, x, x^2\}$ the standard basis of $P_2(\mathbb R)$

$\ E′={(1,0), (0,1)}$ the standard basis of $\mathbb R^2$

I have to write matrix $M(T)$ with $T$ relative to input basis $E$ and output basis $E'$.

I have been trying different things for hours but couldn't solve it. Any help is appreciated.

I tried doing

$\ p(1) \,\leadsto\, (1', 1'') = (0, 0)$

$\ p(x) \,\leadsto\, (x', x'') = (1, 0)$

$\ p(x^2) \,\leadsto ((x^2)', (x^2)'')= (-2,2)$

so the matrix is

$$
    \begin{pmatrix}
    0 & 1 & -2 \\
    0 & 0 & 2 \\
    \end{pmatrix}
$$
That's what I tried to do but it is wrong. I can do the same type of question for different linear transformations and different bases but for some reason I'm stuck at this.

答:
It is probably better to do it abstractly first. Let $e_1,e_2,e_2$ be the basis for the domain, and $f_1,f_2$ the basis for the codomain. Then the matrix entries for $T$ are given by
$$
Te_j=T_{1j}f_1+T_{2j}f_2.
$$
So here
$$
T(1)=(0,0),\qquad T(x)=(1,0)=f_1,\qquad T(x^2)=(-2,2)=-2\,f1+2f_2.
$$
So the matrix you found is right,
$$
T=\begin{bmatrix} 0&1&-2\\ 0&0&2\end{bmatrix}.
$$


问:
Why is $0/\lim_{x\to0} x$ undefined, when $\lim_{x\to2} (x^2-4)/(x-2)$ is defined?
For $\lim\limits_{x\to2}\ (x^2-4)/(x-2)$,
we are able to cancel out $x-2$ and rewrite it as $\lim\limits_{x\to2} x+2 $
But in maths, we are not able to cancel out $0$ values so $x-2$ is not zero, and it totally makes sense. $x$ is aproaching to 2 but it is NEVER 2, it's extremely close to 2 but never 2.

Here is my main problem,
$0/\lim_{x\to0}x$

I am told that this is undefined but I don't understand why.
I mean, as we have done above, $x$ is something extremely close to $0$ but its never $0$ and '$0$ divided by something not $0$ ' is not undefined. It is $0$, so why isn't the answer $0$ then?

答:
$ \lim_{x\to0} 0/x $ is equal to zero for the reasons you suggest.

note $ \lim_{x\to0} x =0$

so
$0/ \lim_{x\to\infty} x  = 0/0$ is undefined


问:
Show that a sequentially relative compact set in a metric space has a finite $\varepsilon$-net
We say that $K \subset X$ is relatively compact, if for every sequence $\{x_n\}_{n \in \mathbb{N}} \subset K$ has a Cauchy sub-sequence.

We say that $N_\varepsilon$ is an $\varepsilon\text{-net}$ of $A \subset X$ if for every $a \in A$ there is $y \in N_\varepsilon$ such that $d(a, y) < \varepsilon$.

Now, let $X$ be a metric space. I want to show that if $K \subset X$ is relatively compact, then for every $\varepsilon > 0$ there is a finite $\varepsilon\text{-net}$ for $K$.

My problem here is that $X$ is not necessarily complete, and that means that $\overline K$ is not necessarily compact.

$\overline K$ not being compact makes it harder for me to build the finite $\varepsilon\text{-net}$ for $K$.

I thought maybe covering $K$ with open balls of radius $\varepsilon$ but I am not sure what to do from there, or how the fact that each sequence in $K$ has a Cauchy sub-sequence helps here.

Help would be appreciated.

答: HINT: Suppose that $\epsilon>0$, and there is no finite $\epsilon$-net in $K$; then you can recursively choose an infinite sequence whose points are all at least $\epsilon$ away from one another.


问:
Why is $\frac{987654321}{123456789} = 8.0000000729?!$
Many years ago,
I noticed that $987654321/123456789 = 8.0000000729\ldots$.

I sent it in to Martin Gardner at Scientific American
and he published it in his column!!!

My life has gone downhill since then:)

My questions are:

Why is this so?

What happens beyond the "$729$"?

What happens in bases other than $10$?

ContentLicense: CC BY-SA 3.0

Body:
In base $n$ the numerator is $$p = n^{n-1} - \frac{n^{n-1}-1}{(n-1)^2}$$ and the denominator is $$q = \frac{n(n^{n-1}-1)}{(n-1)^2}-1.$$

Note that $p = (n-2)q + n-1$ and for the quotient we get

\begin{align}
\frac{p}{q} &= n-2 + \frac{(n-1)^3}{n^n} \frac{1}{1 - \frac{n^2-n+1}{n^n}} \\
&= n-2 + \frac{(n-1)^3}{n^n} \sum_{k=0}^{\infty} \left(\frac{n^2-n+1}{n^n}\right)^k.
\end{align}

Indeed for $n=10$ this is

$$\frac{987654321}{123456789} = 8 + \frac{729}{10^{10}}\sum_{k=0}^{\infty}\left(\frac{91}{10^{10}}\right)^k
$$


问:
Minimal value of a product , Number theory
Let $a$ and $b$ two integers
Such that (a+b) is solution to the equation $x^2+ax+b=0$ .
Find the minimal value of the product $ab$.

• Please help  i'm really stuck on this , i cannot find any good bounds . This problem appeared in a morroccan national olympiad.

答:
So ve have to solve $$2a^2+3ab+b^2+b=0$$ in integers. Let $d=\gcd(a,b)$ and $x,y$ such that $a=dx$ and $b=dy$, then $x,y$ are relatively prime and we have $$d(2x^2+3xy+y^2)=-y$$ so $y=dz$ for some integer $z$ and now we have $$2x^2+3dxz+d^2z^2 =-z\implies z\mid 2x^2\implies z\mid 2$$ since $x,z$ are relatively prime. So we have 4 posible values for $z$, I will start only one, the rest are simillary.

$z=2$ then $x^2+3dx+2d^2=-1$ so $(x+2d)(x+d)=-1$ so ...


问:
Elementary extension considered as a submodel
If we have a model $N$ and its elementary extension $M$, $N\prec M$ can we consider not only $N$ as a submodel of $M$ but also vice versa $M$ up to an isomorphic copy $M^*$ a submodel of $N$, $M^*\preceq N$  ; is this observation correct? I have come across this issue in other question.

I think so because of the snippet below at least if $M$ and $N$ are elementary equivalent and then if $N$ has cardinality $\lambda$ and $M$ cardinality $\lambda^+$ then we can view $N^*$ as a submodel of $M$ ? Please see the definition 1.0.25 which should mimic saturation in $\lambda^+$ over $\lambda$.

答: This is certainly not true in general.  For instance, $N$ could have greater cardinality than $M$, so there is not even a subset of $M$ of the same cardinality as $N$, let alone an elementary submodule that is isomorphic to $N$.


问:
What do we call linear maps from the base field to a vector space?
This is just a terminological question for some notes I'm writing: Let $V$ be a vector space over a field $F$. A linear map $T:V\to F$ is called a linear functional.

What do we call a linear map $v\colon F\to V$? I'm inclined to call them cofunctionals, but I don't think this is standard.

[Linear functionals are also called "covectors". So maybe "cocovectors"? Then the natural identification $L(F,V)\cong V$ ($v\mapsto v(1)$) would identify vectors and cocovectors, which is nice.]

Edit: Just for motivation, these maps $F\to V$ are helpful for writing down general linear maps in terms of functionals and 'cofunctionals' (which are easy to deal with), and apply that to study ideals of linear operators, for example.

If $T:V\to V$ is linear with $dim(V)<\infty$, then $T=\sum_k (Tp_k)q_k=\sum_k p_k(q_kT)$, where the $q_k$ are a basis for $V^*$ (dual of $V$) and the $p_k$ are right-inverses of the $q_k$.

The $q_k$ and $q_kT$ are functionals, and $p_k$ and $Tp_k$ are 'cofunctionals'.

答:
There is a canonical identification $\operatorname{Hom}(\Bbb F,V)\cong V$ for any $\Bbb F$-vector space $V$. (Here $\operatorname{Hom}$ is the set of $\Bbb F$-linear maps from $\Bbb F$ to $V$.) The map is exactly as you describe and takes $f$ to $f(1)$.

So in my opinion, it would make sense to say linear maps $f\colon V\to \Bbb F$ are covectors and maps $g\colon \Bbb F\to V$ are vectors. However, there is not much to be gained here. It would just cause confusion, as we already think of vectors as elements in the underlying set $V$.

One thought I just had: this is only tangentially related, but one way to define the tangent space of a point $p$ in a smooth manifold $M$ is by equivalence classes of curves $\gamma\colon \Bbb R\to M$ (or $\gamma\colon(-\varepsilon,\varepsilon)\to M$ for any $\varepsilon>0$). The point is that a $\gamma$ represents the tangent vector $\gamma'(0)$ in the tangent space of $\gamma(0)$. It is not entirely coincidental here that we basically identify maps $f\colon\Bbb R\to M$ with certain vectors. (Dually, a map $g\colon M\to \Bbb R$ defines a covector at each point.)


问:
Can a sequence cover all the real numbers in $(0,1)$
Or even more generally, can a real sequence $(a_n)_n$ cover a whole interval $(a,b)$? By covering I mean, $\forall x \in (a,b), \exists n \in \mathbb N$ s.t. $a_n=x$.

I think the answer is that there cannot be such a sequence, but I cannot prove or disprove this. Does the result directly follow from the fact that any real interval is uncountable but the sequences are indexed on a countable set $\mathbb N$?

答:
Correct. Formally, a sequence (of members of $\Bbb R$) is a function $\Bbb N \to \Bbb R$. Since $|\Bbb N| = \aleph_0 < c = | \Bbb R|$, then no sequence can enumerate all of the members of $\Bbb R$ (rather, the function in question can never be surjective).

Of course, you can see how this applies to the interval $(0,1)$ since $|(0,1)| = |\Bbb R|$.

Interestingly, in topology, there is a related notion called a "net" which is like a generalization of a sequence, where the domain of the function need not be $\Bbb N$, just any directed set with a preorder relation on it. I suggest checking the links for formal definitions, but, intuitively, you can already see how it works.

In that context, your net could be, say, a function $f : (0,1) \to (0,1)$, e.g. $x \mapsto x$, or a function $f : \Bbb R \to (0,1)$, e.g. $x \mapsto 1/(1+e^x)$ -- whatever set you wish to use as your indexing set for your net.


问:
Calculating $a^p+b^p$ given $a^2+b^2=c$
If one has $a^2+b^2=c$ where $a$,$b$ and $c$ are real numbers, is there any way to calculate $a^p+b^p$ where $p$ may be any real number? If there is, would you please explain with an example with $p=3$?</p>

答:
Since $1^2 + 7^2 = 5^2 + 5^2$, the number $c$ does not uniquely describe $a$ and $b$.  Therefore, you can get not find $a^p + b^p$.

See Numbers which are the sum of two squares in two or more different ways for a list of more such examples.

Title: Calculating $a^p+b^p$ given $a^2+b^2=c$


问:
Rudin: Real & Complex Analysis Thm 1.10
$\textbf{Theorem:}$ If $\mathcal{F}$ is any collection of subsets of $X$, there exists a smallest $\sigma$-algebra $\mathcal{M}^{*}$ in $X$ such that $\mathcal{F} \subset \mathcal{M}^{*}$.

$\textbf{Proof:}$ Let $\Omega$ be the family of all $\sigma$-algebras $\mathcal{M}$ in $X$ which contain $\mathcal{F}$. Since the collection of all subsets of $X$ is such a $\sigma$-algebra, $\Omega$ is not empty. Let $\mathcal{M}^{*}$
be the intersection of all $\mathcal{M} \in \Omega$. It is clear that $\mathcal{F} \subset \mathcal{M}^{*}$ and that $\mathcal{M}^{*}$ lies in
every a-algebra in X which contains $\mathcal{F}$.

To complete the proof, we have to
show that $\mathcal{M}^{*}$ is itself a a-algebra.
If $A_n \in \mathcal{M}^{*}$ for $n = 1,2,3, \dots $ and if $\mathcal{M} \in \Omega$, then $A_n \in \mathcal{M}$, so $ \cup A_n \in \mathcal{M}$,
since $\mathcal{M}$ is a a-algebra. Since $\cup A_n \in \mathcal{M}$ for every $\mathcal{M} \in \Omega$, we conclude that
$\cup A_n \in \mathcal{M}^{*}$. The other two defining properties of a a-algebra are verified in the same manner. $\square$

I understand $\mathcal{M}^{*}$ being an intersection of all the $\sigma$-algebras $\mathcal{M}$ on $X$, that contain $\mathcal{F}$. Follows the proof of $\mathcal{M}^{*}$ being a $\sigma$-algebra - since it's intersection of all $\mathcal{M} \in \Omega$, then if the $A_n$ sets are in $\mathcal{M}^{*}$, they must also be in all of the $\mathcal{M}$'s, so the countable union is there as well (the same applies for the complements, $\varnothing$ and the whole space).

Can we therefore generalize, that any intersection of $\sigma$-algebras must also be a $\sigma$-algebra?

答:
Yes - for any collection of $\sigma$-algebras $\mathcal{M}$, just go through the steps of the proof for  the set $\mathcal{F}=\bigcap_{\mathcal{M}\in\Omega}\mathcal{M}$.

It is usually the case that the intersection of a set of sub<blah>s is a sub<blah>, and that the intersection of all the sub<blahs> containing <foo> is the smallest sub<blah> containing <foo>. This is certainly true for <blah>  = set, group, ring, field, for instance. It is also true for things like topologies, $\sigma$-algebras, and other mathematical structures consisting of nice collections of subsets of a set.

Title: Rudin: Real & Complex Analysis Thm 1.10


问:
Showing that the union of transitive relations need not be transitive.
I have a counterexample of the following statement but I am not sure if it is correct:

Suppose $R_1$ and $R_2$ are relations on A. If $R_1$ and $R_2$ are transitive, then $R_1 \cup R_2$ is transitive. Prove or provide a counterexample.

To me, this is of the form:

If:

$$((x,y)\in R_1 \land (y,z) \in R_1 \implies (x,z)\in R_1) \land ((x,y)\in R_2 \land (y,z) \in R_2 \implies (x,z)\in R_2) $$

Then:

$$ ((x,y)\in R_1 \lor (x,y) \in R_2) \land ((y,z)\in R_1 \lor (y,z)\in R_2) \implies ((x,z)\in R_1 \lor (x,z)\in R_2)   $$

My counterexample:

\begin{align*}
A&=\{ 1,2,3\} \\
R_1&= \{(1,2)\} \\
R_2&= \{(2,3)\}
\end{align*}

Then if we take $x=1,y=2,z=3$, it should yield the following:

If:

$$(\underbrace{(x,y)\in R_1 \land (y,z) \in R_1}_{\text{false}} \implies \underbrace{(x,z)\in R_1}_{\text{false}}) \land (\underbrace{(x,y)\in R_2 \land (y,z) \in R_2}_{\text{false}} \implies \underbrace{(x,z)\in R_2}_{\text{false}}) $$

Then:

$$ (\underbrace{(x,y)\in R_1 \lor (x,y) \in R_2)}_{\text{true}} \land (\underbrace{(y,z)\in R_1 \lor (y,z)\in R_2)}_{\text{true}} \implies (\underbrace{(x,z)\in R_1 \lor (x,z)\in R_2}_{\text{false}})   $$

I know it's a mess, but it's the best I can do to illustrate my idea clearly. Could anyone please help? Thank you so much!

答:
As noted in the comments, your counterexample is perfectly valid, though you seem to overthink a bit. All you need to note are the following:

$R_1,R_2$ are both singletons

$R_1$ is transitive since $(1,2),(1,2) \in R_1$ and $(1,2) \in R_1$

$R_2$ is transitive since $(2,3),(2,3) \in R_2$ and $(2,3) \in R_2$

$R_1 \cup R_2$ is not transitive since $(1,2),(2,3) \in R_1 \cup R_2$ but $(1,2) \not \in R_1 \cup R_2$

Thus the union of transitive relations is not necessarily transitive. (In fact, even if $R_1,R_2$ are equivalence relations, their union still need not be one, and need not even be transitive, as you can see explained here.)

Mostly just posting this to get this out of the unanswered queue. Posting as Community Wiki in particular since I have nothing further to add.


问:
Understanding the definition and notation of the second order differential
We're reaching the end of a differential calculus course I'm taking (distance learning), and I'm realizing that I don't fully understand the objects I'm manipulating. In particular, I'm not quite getting the definition and notation of the second order differential:
$$
[d^2f(a)](h,k):=\big[[d(df)(a)](h)\big](k)
$$

I can see (I think, although I'm starting to have doubts) how the first order works $[df(a)](h)$: $df(a)$ is a linear function that satisfies
$$
\lim_{h\to0}\frac{f(a+h)-f(a)-[df(a)](h)}{\Vert h\Vert}=0.
$$

In the case of a univariate real function, for instance, one could write (using a first order Taylor expansion)

$$
[df(a)](h)=f'(a)(h-a)+f(a)
$$
a "linear" function of $h$,  tangential to $f$ at $a$,  whose slope is that of $f$ at $a$.

Now, trying to decipher the notation of the second order differential: I interpret $\big[[d(df)(a)](h)\big](k)$ to mean $$\big[d[df(a)](h)\big](k)$$ in which $h$ would be a point by which the linear function $d[df(a)](h)$ of $k$ is defined. But the notation $[d^2f(a)](h,k)$ suggests that $a$ only is a point, and that $[d^2f(a)]$ is a (bilinear) function of, well, two variables.

These "questions" came as I was trying to understand the following relation, given for the univariate real function case:
$$
[d^2f(a)](h,k)=hkf''(a)
$$
which I really don't. I'm sorry if this a bit of a mess, but so it is in my mind _:). Any help appreciated!

EDIT: Ivo, thank you very much for the level of detail.

答:
Let's focus on getting domains and codomains right, and assume that all derivatives exist, for whatever we need to.

Assume that $f:\Bbb R^n \to \Bbb R^k$ is given. For $p\in \Bbb R^n$, we have a linear map $Df(p):\Bbb R^n \to \Bbb R^k$. This gives rise to a (non-linear!) map $Df:\Bbb R^n \to {\rm Lin}(\Bbb R^n,\Bbb R^k)$. This last set is a vector space (isomorphic to $\Bbb R^{kn}$), and so we can look at $$D(Df)(p):\Bbb R^n \to {\rm Lin}(\Bbb R^n,\Bbb R^k).$$Given $v \in \Bbb R^n$, we have $D(Df)(p)(v) \in {\rm Lin}(\Bbb R^n,\Bbb R^k)$, which is to say that $D(Df)(p)(v)(w) \in \Bbb R^k$, for $v,w\in \Bbb R^n$. This expression is linear in $v$ and $w$, and since the way of writing it just following the definitions is so horrible, we write it simply as $$D^2f(p)(v,w).$$Then, $D^2f(p)$ is a bilinear map taking values in $\Bbb R^k$. Why? Because $$D(Df):\Bbb R^n \to {\rm Lin}(\Bbb R^n, {\rm Lin}(\Bbb R^n,\Bbb R^k))$$but ${\rm Lin}(\Bbb R^n, {\rm Lin}(\Bbb R^n,\Bbb R^k))$ is isomorphic to the space ${\rm Lin}_2(\Bbb R^n,\Bbb R^k)$ of $\Bbb R^k$-valued bilinear forms in $\Bbb R^n$. The isomorphism is given by $${\rm Lin}(\Bbb R^n,{\rm Lin}(\Bbb R^n,\Bbb R^k))\ni T \mapsto ((v,w)\mapsto T(v)(w))\in {\rm Lin}_2(\Bbb R^n,\Bbb R^k).$$In the one dimensional case, $n=k=1$, we have that $Df(p)(h)= f'(p)h$. So $Df:\Bbb R \to {\rm Lin}(\Bbb R,\Bbb R)$ is given by $p \mapsto (h\mapsto f'(p)h)$. Under the isomorphism ${\rm Lin}(\Bbb R^n,\Bbb R^k)\cong \Bbb R^{kn}$ with $k=n=1$, $h \mapsto f'(p)h$ reads only $f'(p)$. The derivative of this is $f''(p)$ and, well, the matrix representing a bilinear form $\Bbb R \times \Bbb R \to \Bbb R$ is $1\times 1$, and the number inside is $f''(p)$ for $D^2f(p)$. Another way to see it is like this:$$D^2f(p)(h)(k)= \left(\frac{\rm d}{{\rm d}t}\bigg|_{t=0} Df(p+th)\right)(k) = \frac{\rm d}{{\rm d}t}\bigg|_{t=0} f'(p+th)k = f''(p)hk.$$


问:
Generate a uniform distribution of orientations
I am rendering images of a 3D object and am trying to generate a uniform distribution of orientations for this object. I am unsure of how to do this, and considerations that are necessary to take into account.

Is a uniform distribution of orientations equivalent to a uniform distribution of rotations as apparent to a rendering camera? That is, if I generate uniform orientations, will it look uniform to the camera?

How do I generate a uniform distribution of orientations? Is it possible to generate uniform points on a d-sphere to get a set of rotations? If so, would this mean generating points on a 3D sphere or a 4D hypersphere?

答:
One good way to generate a uniformly distributed point on the unit sphere in $\mathbb R^n$ is to take $(Z_1,\ldots,Z_n)$ independent with standard normal distribution, and
divide by the norm $\sqrt{Z_1^2 + \ldots + Z_n^2}$.  To get a uniformly distributed  orthogonal $n \times n$ matrix, take $n^2$ independent standard normal $Z_{ij}$ and orthonormalize by Gram-Schmidt.


问:
maximum possible number of paths in an acyclic digraph
I have been trying to find a general formula for the maximum possible number of paths in an acyclic digraph.  The method I used was to simply draw several differently sized digraphs with the maximum amount of links, count each path and see if I noticed any patterns.

Here is what I found:

The pattern I noticed is that the maximum possible paths from "start" to "end" seems to be equal to $ 2^{n-2} $, where n = number of nodes in the digraph.  I was wondering if anyone could possibly explain a more mathematical approach to solving this problem.

答:
1- Finding the Number of Subsets of a Set

Let's start with stating the obvious: Every path from start to end must contain the start and end nodes and can include as many or as less nodes in between. In other words, its a given that the start and end nodes are included in the path, so we play around with the remaining (N-2) nodes. In set theory lingo that translates to: For a DAG that has N-2 intermediate nodes. Any number of these nodes can be included. How many different paths are possible?

C(N-2, 0) + C(N-2, 1) + C(N-2, 2) + C(N-2, 3) + ....... + C(N-2, N-2)

For simplicity, let n = N-2

C(n, 0) = How many ways we can choose zero intermediate nodes between start and end = n!/(n-k)! * k! = n!/(n! * 0!) = 1
C(n, 1) = How many ways we can choose 1 intermediate nodes between start and end ... etc

Below is a visual illustration of the possible paths for a sample DAG:

visual explanation 1

2- Children and chairs

Another way to find the upper limit mathematically is as follows:
For each one of the intermediate nodes (excluding start and end node) there is one of two options: Either be part of the path, or no. This can be expressed as follows: If we have 3 intermediate nodes, we can treat them as chairs.
2 * 2 * 2 = 2^3 = 8 paths

visual description 2

K = number of paths = 2^(N-2)

Time comlexity = E + k*V = E + 2^(N-2)*V, where E = number of Edges, V = number of vertices


答: You don't generalize, that's precisely what they do! (i.e. showing that any intersection of $\sigma$-algebras is also a $\sigma$-algebra). To see this, just take $\mathcal F = \bigcap_{\mathcal M \in \Omega} \mathcal M$. The meaning of "smallest" is in the sense of inclusion, i.e. every other smaller $\sigma$-algebra is included in that minimal $\sigma$-algebra.</p>

Title: Rudin: Real & Complex Analysis Thm 1.10

Body:
$\textbf{Theorem:}$ If $\mathcal{F}$ is any collection of subsets of $X$, there exists a smallest $\sigma$-algebra $\mathcal{M}^{*}$ in $X$ such that $\mathcal{F} \subset \mathcal{M}^{*}$.

$\textbf{Proof:}$ Let $\Omega$ be the family of all $\sigma$-algebras $\mathcal{M}$ in $X$ which contain $\mathcal{F}$. Since the collection of all subsets of $X$ is such a $\sigma$-algebra, $\Omega$ is not empty. Let $\mathcal{M}^{*}$
be the intersection of all $\mathcal{M} \in \Omega$. It is clear that $\mathcal{F} \subset \mathcal{M}^{*}$ and that $\mathcal{M}^{*}$ lies in
every a-algebra in X which contains $\mathcal{F}$.

To complete the proof, we have to
show that $\mathcal{M}^{*}$ is itself a a-algebra.
If $A_n \in \mathcal{M}^{*}$ for $n = 1,2,3, \dots $ and if $\mathcal{M} \in \Omega$, then $A_n \in \mathcal{M}$, so $ \cup A_n \in \mathcal{M}$,
since $\mathcal{M}$ is a a-algebra. Since $\cup A_n \in \mathcal{M}$ for every $\mathcal{M} \in \Omega$, we conclude that
$\cup A_n \in \mathcal{M}^{*}$. The other two defining properties of a a-algebra are verified in the same manner. $\square$

I understand $\mathcal{M}^{*}$ being an intersection of all the $\sigma$-algebras $\mathcal{M}$ on $X$, that contain $\mathcal{F}$. Follows the proof of $\mathcal{M}^{*}$ being a $\sigma$-algebra - since it's intersection of all $\mathcal{M} \in \Omega$, then if the $A_n$ sets are in $\mathcal{M}^{*}$, they must also be in all of the $\mathcal{M}$'s, so the countable union is there as well (the same applies for the complements, $\varnothing$ and the whole space).

Can we therefore generalize, that any intersection of $\sigma$-algebras must also be a $\sigma$-algebra?


问:
Recurrence Relation - how to derive a proper series
I have a problem with understanding the way of deriving a series based on a given recurrence relation.

Let us consider the following recurrence relation:
$$
f(n) = b + a f(n-1)
$$
for some values $a$ and $b$.

My goal is to a find a general formula for $f(n)$. I suppose that I can do it using a series as follows
$$
f(n) = b + a f(n-1) = b + a(b + a f(n-2)) = \ldots = \sum_{i=0}^{\infty} b a^i.
$$

The second approach to this problem can be as follows:
I write a recurence formula for $n+1$ element, i.e.
$$
f(n+1) = b + a f(n) \Rightarrow f(n) = -\frac{b}{a} + \frac{1}{a} f(n+1)
$$
and therefore
$$
f(n) = -\frac{b}{a} + \frac{1}{a}f(n+1) = -\frac{b}{a} + \frac{1}{a} \left(-\frac{b}{a} + \frac{1}{a}f(n+2)\right) = \ldots = -\sum_{i=1}^{\infty}\frac{b}{a^i}
$$

I obtained two different answers. I cannot understand which of these approaches is correct and why.

I suppose that this is a basic issue in mathematics, but I have never learn about it and I am just curious how to work with such recurence relations.

答:
We can consider in this way: Suppose we have some constant $c$ such that $$f(n)+c=af(n-1)+b+c=a[f(n-1)+c].$$Then it follows that $b+c=ac$, so $c=b/(a-1)$ provided $a\neq 1$. As a result, $$f(n)+\frac{b}{a-1}=af(n-1)+b+\frac{b}{a-1}=a\left[f(n-1)+\frac{b}{a-1}\right].$$
We then have $$f(n)+\frac{b}{a-1}=a^{n-1}\left[f(1)+\frac{b}{a-1}\right].$$That is, $$f(n)=a^{n-1}f(1)+\frac{a^{n-1}-1}{a-1}\cdot b.$$

If $a=1$, the case is even easier: $f(n)$ is an arithmetic progression. $$f(n)=f(1)+(n-1)b.$$


问:
Solution of cubic equations in terms of quadratic equations
Is there a general way in which a cubic equation of $3$rd degree can be represented by a quadratic equation of $2$nd degree such that $2$ solutions of a cubic equation is equal to $2$ solutions of corresponding quadratic equation.

For example $2$ solutions of equation $Ax^3+Bx^2+Cx-(A+B+C)=0$ is equal to $2$ solutions of quadratic equation $Ax^2+(A+B)x+(A+B+C)=0$.

But here the last term of cubic equation is $-(A+B+C)$.

If the last term is arbitrarily some constant number not equal to $-(A+B+C)$ then what quadratic equation will give the $2$ solution of cubic equation $Ax^3+Bx^2+Cx+D=0$ such that $D$ is not equal to $-(A+B+C)$

答:
Given the equation $\quad x^3 - 4x^2 - 7x + 10 = 0 \quad $ we can guess that it has one or more rational roots and, by the rational root theorem, we can "guess" these by using the "factors" or the first and last term. The factors of the last term are $\pm1,\pm2,\pm5,\pm10$ and if we try the first one, we find

$$\quad ( x^3 - 4x^2 - 7x + 10)/(x-1)=x^2 - 3 x - 10\quad$$

From here, it is easy to use the quadratic equation to solve it. On the other hand it is just as easy to try all the factors of $10$ and then find that

$$( x^3 - 4x^2 - 7x + 10)\quad  = \quad (x - 1) (x + 2)(x - 5)  = 0$$

In your other example $\quad 100y^3-120y^2+21y-1=0 \quad$ we have $(y-1)$ as a factor and it also yields a solvable quadratic. In both these equations, one factor must be found before the quadratic can be solved. One way to find the [single] factor to be divided (see synthetic division) is to use the cubic equation. If we use your last equation as an example we have coeficients $\quad a=100\quad b=-120\quad c=21\quad d=-1\quad $ and then

$$x=\sqrt[\Large{3}]{\biggl(\frac{-b^3}{27a^3 }+\frac{bc}{6a^2}-\frac{d}{2a}\biggr)+\sqrt{\biggl(\frac{-b^3}{27a^3}+\frac{bc}{6a^2}-\frac{d}{2a}\biggr)^2+\biggl(\frac{c}{3a}-\frac{b^2}{9a^2}\biggr)^3}}\\
+\sqrt[\Large{3}]{\biggl(\frac{-b^3}{27a^3 }+\frac{bc}{6a^2}-\frac{d}{2a}\biggr)-\sqrt{\biggl(\frac{-b^3}{27a^3}+\frac{bc}{6a^2}-\frac{d}{2a}\biggr)^2+\biggl(\frac{c}{3a}-\frac{b^2}{9a^2}\biggr)^3}}-\frac{b}{3a}$$


问:
How to integrate by using "Integration by parts"?
A simple harmonic oscillator whose Action is given by:

$S=\displaystyle\int dt\left(\frac{1}{2}\cdot m\left(\frac{dx}{dt}\right)^2-\frac{1}{2}m\omega x^2\right)$

here x is a function of time i.e $x(t)$ . Use the above equation  and by doing integration by parts show that :
$S=\displaystyle\int dt\left(-\frac{1}{2}\cdot m\cdot x\left(\frac{d^2x}{dt^2}\right)-\frac{1}{2}m\omega x^2\right)$
(here the upper limit is $t_1 = x_1$ and lower limit is $t_2 = x_2$)

I know what integration by parts is which is by defining a $u$ and $v$ functions according to simplicity then integrate according to it. Here I have to calculate everything with respect to Time how will I handle variable here which doesn't depends on time will I take them as constant ? and how did the second part$\left(-\frac{1}{2}m\omega x^2\right)$ remained the same? Please help me with the procedure.

My solution from @Y Tong hint ,

$=\int \frac{1}{2}\cdot m \frac{dx}{dt} dx-\int \frac {1}{2}m\omega x^2 dt$

taking , $\frac{1}{2}m \frac{dx}{dt}=u$ and $dx=v$

$=\int\frac{1}{2}m \frac{dx}{dt} x \biggr\rvert_{\mathbf{t_1}}-\int \frac{1}{2}m \frac{d}{dt}(\frac{dx}{dt})x $

Eventually I got ,

$=-\int \frac{1}{2}m \frac{d}{dt}(\frac{dx}{dt}) x -\int \frac{1}{2} m \omega x^2 dt$

And I am stuck here to generalize it into proven part . Can anyone help with the next steps ?

答:
You want to use $\int udv=uv|_{t_1}^{t_2}-\int v du$ which is due to $(uv)'=u'v+uv'$.

Take $u=\frac12 m\frac{dx}{dt}$ and $dv=dx$, you have $\int_{t_1}^{t_2}\frac12 m\frac{dx}{dt} dx=\frac12 m\frac{dx}{dt} x|_{t_1}^{t_2}-\int_{t_1}^{t_2} \frac12 mx \frac{d^2x}{dt^2}dt.$ The variation should be there but for typical applications of the least action principle, you will fix the ends, so it doesn't matter. However, the potential term should have been $\frac12m\omega^2 x^2$ instead of $\frac12 m\omega x^2,$ or you won't even have matching units.


问:
What is $var[X(0)+X(0.5)]$, where $X(t)$ is a stationary process?
So I have that $\{X(t);t ∈ R\}$, with mean $\mu_X = 0.5$ is stationary Gaussian stochastic process and its autocorrelation function is $R_X(\tau)=0.5e^{-\pi\tau^2/4} $ $\forall \tau \in R. \quad$ What I want to know is $var[X(0)+X(0.5)],$ i.e. the variance. The answer to the question is :

$V[X(0)+X(0.5)] = 2R_X(0)+2R_X(0.5)-4\mu_X^2.$

Now I know that $V[X(0)+X(0.5)] = V[X(0)]+V[X(0.5)]+2cov[X(0),X(0.5)]$ but I dont know how they got the second part. Can somebody explain the whole procedure of they got to that conclusion?

Body:
We will write $R$ and $\mu$ instead of $R_x$ and $\mu_X$.

We have $$K(s,t) = cov(X(s), X(t)) = EX(s) X(t) -  EX(s) EX(t)  = R(t-s) - \mu^2,$$
because $EX(t) = \mu$ doesn't depend on $t$.

Further
$$V(X(0) + X(\frac12)) = cov(X(0) + X(\frac12), X(0) + X(\frac12)) = $$
$$=cov(X(0), X(0)) +cov(X(0), X(\frac12)) + cov(X(\frac12), X(0)) + cov(X(\frac12), X(\frac12))  =$$
$$ =cov(X(0), X(0)) + 2 cov(X(0), X(\frac12)) + cov(X(\frac12), X(\frac12)) $$
$$=K(0,0) + 2K(0, \frac12) + K(\frac12,\frac12)=$$
$$ =(R(0-0) - \mu^2) + 2(R(\frac12-0) - \mu^2) + (R(\frac12-\frac12) - \mu^2)$$
$$ = 2R(0) + 2R(\frac12) - 4 \mu^2.$$


问:
Maximum number of path for acyclic graph with start and end node
Say given an acyclic graph with n nodes,
which includes a starting node s0 and ending node e0,
what is the maximum number of path from s0 to e0?</p>

Body:
1- Finding the Number of Subsets of a Set

Let's start with stating the obvious: Every path from start to end must contain the start and end nodes and can include as many or as less nodes in between. In other words, its a given that the start and end nodes are included in the path, so we play around with the remaining (N-2) nodes. In set theory lingo that translates to: For a DAG that has N-2 intermediate nodes. Any number of these nodes can be included. How many different paths are possible?

C(N-2, 0) + C(N-2, 1) + C(N-2, 2) + C(N-2, 3) + ....... + C(N-2, N-2)

For simplicity, let n = N-2

C(n, 0) = How many ways we can choose zero intermediate nodes between start and end = n!/(n-k)! * k! = n!/(n! * 0!) = 1
C(n, 1) = How many ways we can choose 1 intermediate nodes between start and end ... etc

Below is a visual illustration of the possible paths for a sample DAG:

visual explanation 1

2- Children and chairs

Another way to find the upper limit mathematically is as follows:
For each one of the intermediate nodes (excluding start and end node) there is one of two options: Either be part of the path, or no. This can be expressed as follows: If we have 3 intermediate nodes, we can treat them as chairs.
2 * 2 * 2 = 2^3 = 8 paths

visual description 2

K = number of paths = 2^(N-2)

Time comlexity = E + k*V = E + 2^(N-2)*V, where E = number of Edges, V = number of vertices


问:
Solve $\sin(3x)\sin(4x)=\cos(4x)\cos(5x)$ (problem from a Swedish 12th grade ’Student Exam’ from 1931)
The equation
$$\sin(3x)\sin(4x)=\cos(4x)\cos(5x)\tag{1}$$
can be transformed by expanding in powers of $\cos(x)$ and letting $r=\cos(x)$;
$$128r^9-256r^7+160r^5-32r^3+r=0,$$
‘factor out’ the solution $r=0$;
$$128r^8-256r^6+160r^4-32r^2+1=0,$$
letting $s=2r$;
$$8s^4-32s^3+40s^2-16s+1=0,$$
letting $t=s-1$;
$$8t^4-8t^2+1=0,$$
letting $u=t^2$;
$$8u^2-8u+1=0,$$
which can be solved using the quadratic formula.
Going back through the steps gives the solutions to (1) as
$$x=\pm\arccos(...)+k\cdot2\pi$$
(18 solutions + period of $2\pi$).

Is there a simpler way to solve this equation?

答:
Hint.

Calling $a = 4x$ and $b = x$ we have

$$
\sin(a-b)\sin (a)-\cos(a)\cos(a+b) = \cos(b)\sin^2(a)-\cos(b)\cos^2(a) = \cos(b)\left(\sin(a)-\cos(a)\right)\left(\sin(a)+\cos(a)\right)=0
$$

or

$$
\cos(x)(\sin(4x)-\cos(4x))(\sin(4x)+\cos(4x))=0
$$


答:
The first comes closer, but neither of them is correct, I’m afraid. For starters, there are infinitely many sequences satisfying the given recurrence, so you need to specify an initial value, say $f(0)$, to pin down which one of them you have. Then your summation is actually finite:

$$\begin{align*}
f(n)&=b+af(n-1)\\
&=b+a\big(b+af(n-2)\big)\\
&=b+ab+a^2f(n-2)\\
&=b+a\big(b+ab+a^2f(n-3)\big)\\
&=b+ab+ab^2+a^3f(n-3)\\
&\;\;\vdots\\
&=b\sum_{i=0}^{k-1}a^i+a^kf(n-k)\\
&\;\;\vdots\\
&=b\sum_{i=0}^{n-1}a^i+a^nf(0)\\
&=\frac{b(a^n-1)}{a-1}+a^nf(0)\,,
\end{align*}$$

Of course this doesn’t work if $a=1$, since the denominator of that last fraction is $0$, but in that case the recurrence is just $f(n)=b+f(n-1)$, and the calculation is

$$\begin{align*}
f(n)&=b+f(n-1)\\
&=b+\big(b+f(n-2)\big)\\
&=2b+f(n-2)\\
&=2b+\big(b+f(n-3)\big)\\
&=3b+f(n-3)\\
&\;\;\vdots\\
&=kb+f(n-k)\\
&\;\;\vdots\\
&=nb+f(0)\,.
\end{align*}$$

There are other ways to derive these closed forms, but this is the one that is closest to what you were trying to do.

Title: Recurrence Relation - how to derive a proper series

Body:
I have a problem with understanding the way of deriving a series based on a given recurrence relation.

Let us consider the following recurrence relation:
$$
f(n) = b + a f(n-1)
$$
for some values $a$ and $b$.

My goal is to a find a general formula for $f(n)$. I suppose that I can do it using a series as follows
$$
f(n) = b + a f(n-1) = b + a(b + a f(n-2)) = \ldots = \sum_{i=0}^{\infty} b a^i.
$$

The second approach to this problem can be as follows:
I write a recurence formula for $n+1$ element, i.e.
$$
f(n+1) = b + a f(n) \Rightarrow f(n) = -\frac{b}{a} + \frac{1}{a} f(n+1)
$$
and therefore
$$
f(n) = -\frac{b}{a} + \frac{1}{a}f(n+1) = -\frac{b}{a} + \frac{1}{a} \left(-\frac{b}{a} + \frac{1}{a}f(n+2)\right) = \ldots = -\sum_{i=1}^{\infty}\frac{b}{a^i}
$$

I obtained two different answers. I cannot understand which of these approaches is correct and why.

I suppose that this is a basic issue in mathematics, but I have never learn about it and I am just curious how to work with such recurence relations.


答:
Your formulas can't be true because they do not depend on $n$. Indeed, in the first formula you will at some point end to $(b+af(0))$ which can't lead to further computation using the recursive formula. As for your second formula, indeed you will never stop because the index of $f(n)$ is always increasing, but you have to be careful when dealing with infinity. In your recursive formula, you always have a $f(n+p)$ at then end which then suddenly disappear when $n\rightarrow +\infty$ for some reasons. One way to obtain a formula for $f(n)$ is to write
$$ (\star)\hspace{0.5cm}\ \frac{f(k+1)}{a^{k+1}}-\frac{f(k)}{a^k}=\frac{b}{a^k} $$
Summing this from $k=0$ to $k=n-1$ gives (I suppose $a\neq 1$ otherwise the result is straightforward)
$$ \frac{f(n)}{a^n}-f(0)=\sum_{k=0}^{n-1}\frac{b}{a^k} $$
Therefore
$$ f(n)=f(0)a^n+\sum_{k=0}^{n-1}ba^{n-k}=f(0)a^n+\sum_{k=1}^n ba^k $$
Letting $n\rightarrow +\infty$ gives your first formula $\displaystyle \lim\limits_{n\rightarrow +\infty}f(n)=\sum_{k=1}^{+\infty}ba^k$
(You only get the limit because in order continue an infinite amount of times your recursive formula you need to have "$n=+\infty$", this is a bit messy but it helps to understand where is your error). However, this only works if $a<1$ because of the infinite sum and the limit $\lim\limits_{n\rightarrow +\infty}f(0)a^n=0$. When $a>1$ this result does not work at all (in particular if $f(0)<0$ you can end up with a $\infty-\infty$ indeterminated form) but summing $(\star)$ from $k=n$ to $k=N-1$ gives
$$ \frac{f(N)}{a^N}-\frac{f(n)}{a^n}=\sum_{k=n}^{N-1}\frac{b}{a^k} $$
Thus
$$ f(n)=\frac{f(N)}{a^{N-n}}-\sum_{k=n}^{N-1}\frac{b}{a^{k-n}}=\frac{f(N)}{a^{N-n}}-\sum_{k=0}^{N-n-1}\frac{b}{a^k} $$
Letting $N\rightarrow +\infty$ leads to $\displaystyle f(n)=\lim\limits_{N\rightarrow +\infty}\frac{f(N)}{a^{n-N}}-\sum_{k=0}^{+\infty}\frac{b}{a^k}$. While the series converges because $a>1$, we do not know what happens for $\lim\limits_{N\rightarrow +\infty}\frac{f(N)}{a^{N-n}}$ (in fact we could know because we have a precise formula for $f(N)$). This is the error in your formula 2., $f(N)$ fades out with the dots and you are ignoring what happens with this $f(N)$, maybe it blows out or vanishes but you can't know without further study.


问:
need to show image of $f$ contains the unit disk.
$f$ be non constant analytic on the closed unit disk,$|f|=1$ if $|z|=1$,we need to show image of $f$ contains the unit disk.

My thoughts:
whenever $|\omega|<1$ if I show that $g(z)=f(z)-\omega$ has a root in $D$ the we are done

On $|z|=1$ $|f(z)-g(z)|=|\omega|<1=|f(z)|$ Hence by Rouches Theorem $f(z)$ has a root in $D$

答:
Assume $f$ does not have a zero. Applying the maximum modulus principle to $1/f(z)$ gives a contradiction ($f$ constant, contradicting the hypothesis), so we find that any analytic function that has modulus $1$ on $|z|=1$ has a zero. </p>

<p>Fix $a$ in the open unit disk. Consider the Blaschke factor switching $0$ and $a$. Composing $f(z)$ with this factor gives another analytic function with modulus $1$ on the unit circle, so the composition has a zero in the unit disk. But this means $f(z)$ takes on the value $a$ in the unit disk. </p>

Body:
Assume $f$ does not have a zero. Applying the maximum modulus principle to $1/f(z)$ gives a contradiction ($f$ constant, contradicting the hypothesis), so we find that any analytic function that has modulus $1$ on $|z|=1$ has a zero.

Fix $a$ in the open unit disk. Consider the Blaschke factor switching $0$ and $a$. Composing $f(z)$ with this factor gives another analytic function with modulus $1$ on the unit circle, so the composition has a zero in the unit disk. But this means $f(z)$ takes on the value $a$ in the unit disk.


问:
How to find the horizontal and vertical asymptote
So I'm having trouble figuring out the horizontal asymptote for function given by

$$
f(x) = \arctan(x) + \frac{3x}{x-2}.
$$

I've figured out that the vertical asymptote is $x= 2$, but I can't find the horizontal asymptote.

答:
Domain of $f(x)$ is $\mathbb{R}-\{2\}$

The point excluded in the domain $x=2$ is a vertical asymptote because
$$\underset{x\to 2^-}{\text{lim}}f(x)=-\infty;\;\underset{x\to 2^+}{\text{lim}}f(x)=+\infty$$
The limits at infinity
$$\underset{x\to +\infty }{\text{lim}}\left(\frac{3 x}{x-2}+\arctan x\right)=3+\frac{\pi }{2}$$

$$\underset{x\to -\infty }{\text{lim}}\left(\frac{3 x}{x-2}+\arctan x\right)=3-\frac{\pi }{2}$$

therefore there are two distinct horizontal asymptotes $y=3+\frac{\pi }{2}$ at $+\infty$ and  $y=3-\frac{\pi }{2}$ at $-\infty$

See the picture below
$$...$$

$$...$$


问:
Maximum entropy principle for Poisson distribution
I know that certain probability distributions may be derived from the requirement that entropy be maximal along with a constraint such as fixed variance. In the case of fixed variance, for example, one finds the normal distribution. In particular, the maximisation is over the set of all (!) continuous PDFs with that fixed variance.

Now my question is, is there a similarly general derivation of the Poisson distribution as a maximum entropy distribution? E.g. fixing that mean and variance are equal and maximising entropy? I have found a couple of articles but they always seem to prove maximality on a restricted set of discrete PDFs. Is it because there is no more general maximum entropy principle for the Poisson distribution? If so, is it because the discrete case is simply more complex than the continuous one?

答:
I guess the $k!$ comes from a permutation term.

Supose a composite system. Subsystem A has $n_a$ elements, while Subsystem B has $n_b$ elements. There are ${n_a+n_b}\choose{n_a}$ possible permutations. Consider that elements in A may be in $m_a$ states, while elements in B may be in $m_b$ states. You may think that each subsystem is a bag with a given number of pockets. There will be
$$
 {{n_a+n_b}\choose{n_a}} m_a^{n_a} m_b^{n_b}
$$
different states for the composite system, given the partion of the elements. Considering all states have the same probability, the probability of having a patition with $n_a$ elements in A is proportional to the number of possible states for the composite system. Using the binomial theorem we have that the probability of a given partion is

$
P(n_a)={{n_a+n_b}\choose{n_a}} m_a^{n_a} m_b^{n_b}/(m_a+m_b)^{(n_a+n_b)}
$

Assuming that $m_b$ grows to infinity, while $(n_a+n_b)/m_b=\mu$ remains constant, yields Poisson
$$
P(n_a)=e^{-\mu}\mu^{n_b}/n_a!
$$


问:
Careful proof of set inclusion
Consider the two topologies:

$\tau_{1}=\{\{m\in \mathbb{N}:m<n\}:n\in \mathbb{N}\}\cup \{\mathbb{N}\}$ and $\tau_{2}=\{A\subseteq \mathbb{N}: 0\in A\}\cup \{\emptyset\}$.

I know that the $\tau_1$ topology is contained in the $\tau_2$ topology, because:

\begin{equation}
\{\emptyset,\{0\},\{0,1\},\{0,1,2\},\cdots,\mathbb{N}\}\subseteq \tau_2
\end{equation}

I wonder how to prove it with mathematical rigour. Can someone help me?
Thank you!

答:
Let $U \in \tau_1$. Then, by definition, either $U = \mathbb{N}$ or $U \in \{ \{m\in \mathbb{N} : m < n\} \mid n \in \mathbb{N}\}$. Suppose the former. Then clearly $0 \in U$< so $U \in \tau_2$. Now suppose the latter. Then there is some $n \in \mathbb{N}$ s.t. $U = \{m \in \mathbb{N} : m < n\}$. Then either $n =0$ or $0 < n$. Suppose $n =0$, then there are no natural number $< 0$, so $U = \{m \in \mathbb{N} : m <n\} = \emptyset \in \tau_2$, so $U \in \tau_2$. Now suppose $0 < n$, then clearly $0 \in U = \{m \in \mathbb{N} : m < n\}$. Thus $U \in \tau_2$.

Thus in any case $U \in \tau_2$. Thus, for every $U \in \tau_1, U \in \tau_2$, which is the definition of $\tau_1 \subseteq \tau_2$.

Title: Careful proof of set inclusion


问:
derivative of the laplacian operator
Assumes $\Delta \phi = \nabla\cdot\nabla\phi$ and
$$
f(\phi) = \Delta\phi
$$
then, what is
$$
\frac{df(\phi)}{d\phi}
$$

no clue how to solve this

答: In a rough sense, if you are taking a functional derivative, you can see $\Delta \phi$ as an infinite dimensional matrix multiplied to the vector space of functions, so the result is a constant matrix $\Delta$.

Title: derivative of the laplacian operator


问:
Random products of Jordan blocks — what distribution are they converging to?
Let
$$
 M_1=\left(
\begin{array}{cc}
 1 & 1 \\
 0 & 1 \\
\end{array}
\right),
\qquad
M_2=\left(
\begin{array}{cc}
 1 & 0 \\
 1 & 1 \\
\end{array}
\right),\qquad
v = \left(
\begin{array}{c}
 1 \\
 1 \\
\end{array}
\right)
$$

and consider the $n$-fold random product, for $n \in \mathbb N$.
More precisely, let

$$\Psi_n := \log \| M_{i_1}M_{i_2}\cdots M_{i_n}v \|_{L^1}:$$
where each $i_k$ are i.i.d., equal to 1 or 2 with equal probability.

Scaling by $2^{-n}$, in this question we consider  $\Phi_n$ as a compactly supported probability measure on $\mathbb R$ (i.e. a weighted sum of Dirac deltas).

Central Limit Theorem

For probability measures $\mu_n, \mu$, we here say

$$\mu_n\stackrel{\text{dist.}}\longrightarrow \mu$$

if, for each $-∞ < a \leq b < ∞$,

$$\mu_n\big([a,b]\big) \to \mu([a,b]) .$$

Under certain hypotheses on the $M_i$, one would see, for generic $v$, that $\Psi_n$ satisfies a kind of Central Limit Theorem:

I.e., that there exist constants $\lambda_\ast > 0$ and $\sigma >0$ such that

$$ \frac{\Psi_n - n \lambda_\ast}{\sigma^2\sqrt n} \stackrel{\text{dist.}}\longrightarrow N(0,1) \qquad\text{as }n \to ∞,$$

where $N(0,1)$ is the standard normal distribution.

Reality

Calculating some histograms in Mathematica, the shape of $\Psi_n$ seems to not be converging to a Gaussian, but to some kind of skewed distribution: see pictures below.

Questions:

What can $\Phi_n$ be converging to, if anything?

How would one prove that $\Phi_n$ is not converging to a Gaussian?

答:
This is a partial answer, but given the lack of other answers hopefully it is helpful.

When you say that $\Psi_{n}$ should converge to normal, be careful: the CLT says only that
$$ Z_{n} = \frac{\frac{\Psi_{n}}{n} - \lambda^{\ast}}{\sigma/\sqrt{n}} $$
converges to anything normal, and really that is only true if $\frac{1}{n}\Psi_{n}$ behaves sufficiently like a sample mean ($\Psi_{n}$ is not a sum, so this is not obvious).

The CLT theorem depends on the original sampling distribution. For instance, it does not apply if the sampling distribution is Cauchy. More generally, if the sampling distribution comes from a family of stable distributions, the CLT does not necessarily apply (I assume there are other ways for the CLT to fail, but I find this a  particularly illuminating case).

Lastly, as pointed out by Peter Morfe in the comments, the paper "Central Limit Theorems for Linear Groups" (Benoist and Quint 2016) seems to answer this problem.


问:
Why are let binders part of the kernel in Coq/Lean?
I've been looking into the implementations of CIC-based theorem provers - mainly Coq and Lean - and it seems that both of them have let binders as part of the kernel, with their own typing and reduction rules.

I get why let binders are useful, but it seems to me they could just be syntactic sugar:
let x:T = y in z --> (fun x:T, z)(y) Is there a type-theoretic reason they're in the kernel as a separate concept, or is it for implementation/software efficiency reasons?

答:
let is not derivable as syntactic sugar in type theory. That only works if types cannot depend on let-defined names. For example, trying to desugar let A : Set = Bool in λ (x : A). not x yields (λ (A : Set) (x : A). not x) Bool which is ill-typed.

We can either add let to core syntax, or unfold all let-s during elaboration. The latter may cause a size explosion in elaboration output, and let-s are very useful in the surface language, so the straightforward solution is to have let as primitive.


问:
expected number of flips until $k$ consecutive misses or number of flips finish
I followed the argument given in the answers for this question to find the expected number of misses in a sequence of coin-tosses with success probability $p$. The stopping condition for tossing is either until the $k^{th}$ consecutive miss or until the number of rounds reach $n$, whichever comes first. We can consider tail as a miss and head as hit.

The question in the link differs from my question. In my question stopping happens only when $k$ consecutive miss happens or rounds reach $n$. In the linked question stopping happens when $k$ miss happens.

The probability that $k^{th}$ consecutive miss happen at $i^{th}$ trial can not be simply represent in terms of $i$ and $k$ as the number of hits or misses before the start of the sub-sequence of $k$-consecutive miss is still unknown. There can be many misses and hits before the start of the sub-sequence which results in stopping. Similarly there can be unknown number of misses or hits before reaching the end of round ($n$).

Is it even possible to represent this number in a closed form ? Any help and suggestions ?

答:
Hint(very detailed hint): Let $A(n)$ be the probability to have $n$ trials where you can not miss more than $k-1$ times. Then, you will have that
$$\mathbb{E}[X]=nA(n)+\sum _{i=k}^ni\cdot P(X=i)=nA(n)+k\cdot (1-p)^k+\sum _{i=k+1}^ni\cdot p\cdot (1-p)^kA(i-k-1).$$
Now, you can get a closed form for $A(m)$ by factoring the misses and the success in the following way, suppose a miss is denoted by $1$ and a success is denoted by $0,$ then
$$0^c1^{a_1}0^{b_1}1^{a_1}\cdots 0^{b_{j-1}}1^{a_j}0^d,$$
where the $1\leq a_i<k$ and $1\leq b_j$ and $0\leq c+d,$ and $$\sum a_s,\, c+d+\sum b_s=b.$$

 So fix the number of misses to be $\ell$ then
$$A(m)=\sum _{\ell =0}^m\mathcal{A}(\ell,m-\ell)(1-p)^{\ell}p^{m-\ell},$$
where $\mathcal{A}(a,b)$ is the number of ways you can have $a$ misses and $b$ succeses where each chunk of misses has less than $k$ consecutive misses.

To get $\mathcal{A}(a,b)$ consider the number of chunks (consecutive misses) that you can have, call this $j$ then
$$\mathcal{A}(a,b)=\sum _{j = 1}^a\text{#ways to have $a$ misses and $b$ successes with exactly $j$ chunks}.$$
Notice that now we can use Stars and Bars because we are trying to place the $a$ misses in $j$ boxes(also inclusion exclusion, cause they have to be less than $k$) and you have to place the $b$ successes in $j+1$ boxes with some conditions, also possible using Stars and Bars. Use multiplication principle.


问:
Sequence of iteration in Newton Raphson method.
To find  positive square root of $a>0$ by solving equation $x^2-a$ by Newton-Raphson mathod, if $x_n$ denotes $n$th iterate with $x_0>0, x_0\neq\sqrt{a}$, then the sequence $(x_n) $ is

$1.$ strictly increasing.

$2.$ strictly decreasing.

$3.$ constant.

$4.$ not convergent.

According to me if I start from right of  square root of $a$ we get decreasing sequence and if started from left then increasing sequence. How can be some option correct ? For me it seems all options as incorrect. Please comment. Thank you.

答:
This is not intended to be a complete answer, but more of a guide to how to approach this and similar problems.

The first thing to do is some experimentation. For this I would recommend 'geogebra', which is a program for experimenting with graphs and plane geometry. You pick a value of a, and plot your function. Then pick a value of $x_0$. From here you need to construct the Newton - Raphson method one iteration at a time, which should be quite instructive as to how it works. Plot point at $(x_0,0)$, then a vertical line through this point, then a tangent where it intersects the graph, where this tangent intersects the axis is $x_1$. Do this a few more times so you can see what the method is doing until it disappears and each step is too small.

At this point you should be able to vary the values of $a$ and $x_0$, and see what the method does for various cases. I suggest you do this yourself and reach your own conclusions before reading on. Firstly, for $x_0 >\sqrt{a}$ the sequence is decreasing. This is because of the curvature of the function. Secondly, for $0<x_0<\sqrt{a}$ we have $x_1>\sqrt{a} $, which then proceeds as previously. Hopefully with the visual representation it should be obvious that these are true, but it may also be instructive to try to prove these statements.


问:
Graph with expansion of $K_5$ has subgraph which is expansion of $K_{3,3}$.
Just wondering how my proof looks...

Statement: if a nonplanar graph has $v \geq 6$, connectivity $c \geq 3$, and a subgraph which is an expansion of $K_5$, then it also has a subgraph which is an expansion of $K_{3,3}$ (the 'utility' graph consisting of 3 houses all 3 of which are connected to 3 utility companies but not to each other).

Proof: We know an expansion introduces vertices with degree 2, and so if $c \geq 3$ as given, then an expanded vertex must have an additional edge connected to it (else we erase the two adjacent vertices and are left with a disconnected vertex, implying $c \leq 2$).

Additionally, this edge must be connected to another vertex in the $K_5$ expansion (if it were connected to two vertices in $K_5$ and one vertex outside $K_5$ we would remove the outside vertex and have a disconnected graph).

Now, we can then form $K_{3,3}$ by choosing the expanded vertex to be a utility, and 3 of its adjacent vertices part of the $K_5$ expansion to be the houses. Of course, since $K_5$ is complete we can find two more houses and utilities since there are paths between each vertex.

This does not give us a graph isomorphic to $K_{3,3}$, but isomorphic to an expansion, because it may be the case that between the original $K_5$ vertices, there are expanded vertices.

答:
I don't think the proof of the OP works, to see why look at the comment section.

Proof :

First, we consider the case when no expanded vertices are present in $K_5$, it is necessary to have at least another vertex but we can have as many as we want, anyway we must check if the new component created preserves $c \geq 3$, the only way to make sure this happens is to connect $3$ vertices of $K_5$ to the new component each with at least an edge, it's easy to see how to construct a $K_{3,3} $-expanded from that.

Now, It is easy to prove that $K_{3,3} $-expanded is a subgraph if one of the following facts happens:

If two expanded vertices on different edges are connected  with a path composed by edges all not included in $K_5$.

If a expanded vertex is connected to a vertex of $K_5$ with a path composed by edges all not included in $K_5$.

Now we'll see that this always happens : say you have a expanded vertex on $K_5$, then you need to connect it to another vertex: if this vertex belongs to $K_5$ we are done, otherwise if it is a vertex belonging to another component, this component has to be connected to $K_5$ with at least $3$ vertices so we will have the first fact (connection to a expanded vertex on different edge) or the second fact (connection to a vertex of $K_5$) satisfied. Otherwise, if it is connected to another expanded vertex on another edge then the first fact is satisfied.

Note that connecting all expanded vertices on the same edge with a vertex not included in $K_5$ or connecting one to each other does not preserve $c \geq 3$ because it's easy to see that $c=2$ in this case.

If someone finds something wrong don't hesitate to write a comment!


问:
Binomial distribution and overselling airline tickets
i am having trouble figuring out how to answer this question.

A big Boeing jumbo jet has 400 seats for a trans–Atlantic flight from JFK Airport in New York. The probability that any particular passenger will not show up for this flight is 0.03, independent of other passengers. The average fare paid by a passenger who succeeds in boarding is \$400. A passenger who shows up but cannot board is given \$800 and a free flight later on.

Given that the airline can sell 400 + m tickets, calculate the m that maximizes expected revenue.

the answer is between 10 and 14 inclusive. i can't figure out how to set this up.

so far i have made one function for revenue:

$$\text{revenue}(m) = (400 + m) \cdot 400$$

because i assume that a minimum of 400 tickets will be sold. $m$ represents the number of extra tickets sold.

the cost function is where i'm really struggling.

i think each make-up ticket will cost the airline 400 because the value is 800, but the passenger has already paid 400, which leaves an additional cost of 400 for the airline to pick up.

but i'm not sure how to use the binomial distribution here. i know that i need to multiply it by the cost to the airline of each individual reimbursement, which i think is 400. but i'm not sure what the number of trials or successes should be, or even if this is how i should be thinking about this question.

any advice? thanks in advance.

答:
If $400+m$ people are sold tickets, and each of these people fail to show up independent of each other with probability $0.03$, then the number of people who won't show up (which we'll denote as $N$) follows a $\text{Binomial}(400+m,0.03)$ distribution.

If $N \ge m$, then the number of people who showed up is $400+m-N \le 400$, so everyone has a seat. Thus, the airline's revenue is $400(400+m)$.

If $N < m$, then the number of people who showed up is $400+m-N > 400$. The airline gets $400(400+m)$ dollars from the ticket sales, but loses $1200(m-N)$ dollars from having to give $m-N$ passengers $800$ dollars in compensation and a free flight later on.

So the total revenue is $$\text{revenue}(m,N) = \begin{cases}400(400+m) & \text{if} \ N \ge m \\ 400(400+m) - 1200(m-N) & \text{if} \ N < m\end{cases}. $$

Since $N$ follows a $\text{Binomial}(400+m,0.03)$ distribution, $$\text{Pr}\{N = n\} = \dbinom{400+m}{n}\cdot 0.03^{n} \cdot 0.97^{400+m-n},$$ and so, the expected revenue by selling $m$ tickets is $$\sum_{n = 0}^{400+m}\text{Pr}\{N = n\} \cdot \text{revenue}(m,n).$$ Now, you just need to figure out what value of $m$ maximizes this sum.


问:
Measurable sets modulo measure 0 and boolean algebra clarification
This is a clarification question on the meaning of a phrase.

I'm reading through Manin's "Mathematical Logic for Mathematicians," and he defines a boolean algebra $B$ as a set that include distinguished $0$ and $1$ with an operation $'$ of rank 1, two operations $\land$ and $\lor$ of rank 2, with the following axioms:

$(A')' = A$.

$\land$ and $\lor$ are associative and commutative.

$\land$ and $\lor$ distribute over each other.

DeMorgan-like laws for $\land$ and $\lor$.

Both $\land$ and $\lor$ are idempotent.

$1 \land a = a$.

$0 \lor a = a$.

This is not the first time I've seen a boolean algebra, but what confuses me is his word choice in the following passage:

An example is the algebra of measurable subsets (modulo measure-zero subsets) of a probability space $M$ with standard set-theoretic interpretations of the operations.

I've not done any measure theory, and while I've encountered questions involving measurable sets in some geometry, I don't understand what he means by "modulo measure-zero subsets."

Is it just that he identifies all measure-zero subsets to be the same, i.e., the element $0$?

答:
Expanding @DonThousand 's comment as an answer. Your interpretation is correct.

The relation between sets that contains pairs whose symmetric difference is of measure $0$ is an equivalence relation. The boolean operations naturally work on the blocks of the partition corresponding to that equivalence relation. The set of those blocks is the example referred to.


答:
The standard algorithmic solution to the "modular exponentiation" problem is to use "Square and Multiply Algorithm". Let me illustrate:

Suppose you need to calculate $$x^c \bmod n$$

Represent the exponent $c$ in binary:

$$c = \sum_{i=0}^{l-1} c_i 2^i$$ where $c_i$ is $0$ or $1$ and $0 \leq i \leq l-1$

Then use the following algorithm:

```<code>SAM (x, c, n){
z = 1

for i = l-1 downto 0 {
   z = z^2 mod n
   if (c_i = 1)
      z = zx mod n
   }

return z
}
</code>```

Note that there are always $l$ squarings. The number of multiplications is equal to the number of $1$'s in the binary representation of $c$, which is an integer between $0$ and $l$. Thus the total number of modular multiplications is at least $l$ and at most $2l$

I used the above algorithm and found the value $178$

$x = 142, c = 381 = \{101111101\}, n = 773$

Here $l = 9$,

hence the number of squarings $= l = 9$ and

number of multiplications $ = $ number of $1$'s in the binary representation of $381 = 7$

```<code>SQUARE: 1
MULTIPLY: 142
SQUARE: 66
SQUARE: 491
MULTIPLY: 152
SQUARE: 687
MULTIPLY: 156
SQUARE: 373
MULTIPLY: 402
SQUARE: 47
MULTIPLY: 490
SQUARE: 470
MULTIPLY: 262
SQUARE: 620
SQUARE: 219
MULTIPLY: 178
===============
FINAL: 178
</code>```

Body:
Calculate $142^{381}$ mod $773$ without a calculator .

Attempt:

$$142^{(3\cdot 127)}=142^{381}$$
By try some number's
$$142^1\equiv142\pmod{773}$$
$$142^2\equiv66\pmod{773}$$
$$142^3\equiv96\pmod{773}$$

Lets check the gcd between $773,142$
$$\gcd(773,142)$$
$$773=142\cdot 5+63$$
$$142=63\cdot 2+16$$
$$63=16\cdot3+15$$
$$16=15\cdot 1+1$$
$$15=1\cdot15+0$$
$$\gcd(773,142)=1$$
How to find the answer from here ?

Body:
The standard algorithmic solution to the "modular exponentiation" problem is to use "Square and Multiply Algorithm". Let me illustrate:

Suppose you need to calculate $$x^c \bmod n$$

Represent the exponent $c$ in binary:

$$c = \sum_{i=0}^{l-1} c_i 2^i$$ where $c_i$ is $0$ or $1$ and $0 \leq i \leq l-1$

Then use the following algorithm:

SAM (x, c, n){
z = 1

for i = l-1 downto 0 {
   z = z^2 mod n
   if (c_i = 1)
      z = zx mod n
   }

return z
}

Note that there are always $l$ squarings. The number of multiplications is equal to the number of $1$'s in the binary representation of $c$, which is an integer between $0$ and $l$. Thus the total number of modular multiplications is at least $l$ and at most $2l$

I used the above algorithm and found the value $178$

$x = 142, c = 381 = \{101111101\}, n = 773$

Here $l = 9$,

hence the number of squarings $= l = 9$ and

number of multiplications $ = $ number of $1$'s in the binary representation of $381 = 7$

SQUARE: 1
MULTIPLY: 142
SQUARE: 66
SQUARE: 491
MULTIPLY: 152
SQUARE: 687
MULTIPLY: 156
SQUARE: 373
MULTIPLY: 402
SQUARE: 47
MULTIPLY: 490
SQUARE: 470
MULTIPLY: 262
SQUARE: 620
SQUARE: 219
MULTIPLY: 178
===============
FINAL: 178


问:
Two variables function limit
In an exercise of a limit of a function of two variables in the solution I read this inequality:

$$ \frac{x^2y^2}{(x^2+y^2)^\frac{3}{2}} \le \frac{1}{2}\sqrt{x^2+y^2} $$

how did they arrive at this result?

答:
You can clearly see that the inequality is homogeneous. Now just assume $x^2+y^2=1$ and the inequality is trivial!
But as Jack D'Aurizio stated, the RHS constant is 1/4 not 1/2.

Title: Two variables function limit


答: That inequality is equivalent to$$x^2y^2\leqslant\frac12\sqrt{x^2+y^2}(x^2+y^2)^{3/2}=\frac{(x^2+y^2)^2}2.$$Besides,$$(x^2+y^2)^2-2x^2y^2=x^4+y^4\geqslant0.$$

Title: Two variables function limit

Body:
In an exercise of a limit of a function of two variables in the solution I read this inequality:

$$ \frac{x^2y^2}{(x^2+y^2)^\frac{3}{2}} \le \frac{1}{2}\sqrt{x^2+y^2} $$

how did they arrive at this result?


问:
Recurrence Relation - how to derive a proper series
I have a problem with understanding the way of deriving a series based on a given recurrence relation.

Let us consider the following recurrence relation:
$$
f(n) = b + a f(n-1)
$$
for some values $a$ and $b$.

My goal is to a find a general formula for $f(n)$. I suppose that I can do it using a series as follows
$$
f(n) = b + a f(n-1) = b + a(b + a f(n-2)) = \ldots = \sum_{i=0}^{\infty} b a^i.
$$

The second approach to this problem can be as follows:
I write a recurence formula for $n+1$ element, i.e.
$$
f(n+1) = b + a f(n) \Rightarrow f(n) = -\frac{b}{a} + \frac{1}{a} f(n+1)
$$
and therefore
$$
f(n) = -\frac{b}{a} + \frac{1}{a}f(n+1) = -\frac{b}{a} + \frac{1}{a} \left(-\frac{b}{a} + \frac{1}{a}f(n+2)\right) = \ldots = -\sum_{i=1}^{\infty}\frac{b}{a^i}
$$

I obtained two different answers. I cannot understand which of these approaches is correct and why.

I suppose that this is a basic issue in mathematics, but I have never learn about it and I am just curious how to work with such recurence relations.

答:
$$f(n)=a f(n-1)+b$$
substitute $n\to n+1$
$$f(n+1)=af(n)+b$$
Subtract the two relations
$$f(n+1)-f(n)=af(n)-af(n-1)$$
reorder
$$f(n+1)-(a+1)f(n)+af(n-1)=0$$
the equation characteristic is
$$x^2-(a+1)x+a=0\to x_1=1;\;x_2=a$$
the general solution is
$$f(n)=h+ka^n$$


问:
Regularized sum of $1+(1+\frac1{2^2}) + (1+\frac1{2^2}+\frac1{3^2})+\cdots$, or $\sum_{k=1}^\infty \sum_{j=1}^k\frac1{j^2}$?
For my exercises on divergent summation I try to find a regularization of
$$   S^{^\star}_2 \underset{\mathcal R}= \sum_{k=1}^\infty \sum_{j=1}^k \frac1{j^2} \tag 1
$$
It is not difficult to derive the formula for the partial sums introducing the harmonic numbers of order $1$ and $2$
$$H_1(N)=\sum_{k=1}^N \frac1{k} \\
  H_2(N)=\sum_{k=1}^N \frac1{k^2} \tag {2.1}$$
and writing
$$ S_2(N) = (N+1) \cdot H_2(N) - H_1(N) \tag {2.2}$$
When going to the limit $N \to \infty$ and the serial summation according to eq 2.1 cannot be done, we can -using the $\psi$ (or "digamma", in Pari/GP  psi(1+N))-function-   approximate  $$H_1(N) \sim \gamma + \psi(1+N)  \tag {3.1}$$  and for $H_2(N)$ the derivative of the $\psi()$:
$$ H_2(N) \sim \zeta(2)-\psi^{(1)}(1+N) \tag {3.2}
$$

I don't see how I can proceed now. I'd assume for the regularization in the case for $N$ in the limit I can use $\gamma$ for the $H_1^{^\star}$.

Q:But how can I the do the $H_2$-part for the limit formula for eq (3.2) resp. (2.2)?

A bit background: In a treatize on the triangle of Eulerian numbers (pg.8) I hand-waving-generalize the triangle towards negative row numbers, and for the row-sum of the $-2$'nd row I get those formal sums.

update I just found my 2013-question about the same subject, and there was an answer but which I could not then believe it is a final answer, and still I'm unsure whether (and how) I can proceed to a "fixed statement" see earlierquestion The user @did gave the answer
$$
\lim_{n\to\infty}\left(s_2(n)-n\frac{\pi^2}6+\log n\right)=\frac{\pi^2}6-1-\gamma \qquad \text{introduced by me: } =\zeta(2)-1 - \gamma
$$

Body:
Your question doesn't make much sense.

For $\Re(s) > 3$
$$\sum_{n\ge 1} ((n+1)^{3-s}-n^{3-s}) \sum_{m=1}^n m^{-s} = -\zeta(2s-3)$$

Then $$\lim_{s\to 2} -\zeta(2s-3)= \infty$$
but $$\lim_{t\to 0^+}-\Re(\zeta(2(2+it+t^3)-3)=-\gamma$$


问:
Help with inequality please
Once again I have come across an olympiad-type problem which probably requires some sort of insight even though it looks simple. The question is as follows:

Let $a$, $b$ and $c$ be positive real numbers. Prove that:

$(a+b)(b+c)(c+a)$ $\geqslant$ $8(a+b-c)(b+c-a)(c+a-b)$

I have tried to multiply out the LHS but unfortunately it didn't get me much...

I found that if one of $a$, $b$ or $c$ is greater than or equal to the sum of the other two, then the inequality is trivially true, since LHS is positive while RHS isn't.

Would there be a quick and easy formula or known inequality that I could use to make this problem simpler? Or is this just a 'bash-and-solve' type question?

Any help, comments or edits are greatly appreciated! Thanks! :)

This question appeared in the South African Mathematics Olympiad in 2008.

答:
Given $\quad(a+b)(b+c)(c+a)  \ge   8(a+b-c)(b+c-a)(c+a-b)\quad$ show $x\ge y$
$$x=(a+b)(b+c)(c+a) \quad=a^2 b + a^2 c + a b^2 + 2 a b c + a c^2 + b^2 c + b c^2$$
$$y=8(a+b-c)(b+c-a)(c+a-b) \\ =
-8 a^3 + 8 a^2 b + 8 a^2 c + 8 a b^2 - 16 a b c + 8 a c^2 - 8 b^3 + 8 b^2 c + 8 b c^2 - 8 c^3$$

We negate the RHS and subtract it from both sides by addition so $x-y \ge 0$

$$x-y\quad =\quad a^2 b + a^2 c + a b^2 + 2 a b c + a c^2 + b^2 c + b c^2\\
+8 a^3 - 8 a^2 b - 8 a^2 c - 8 a b^2 + 16 a b c - 8 a c^2 + 8 b^3 - 8 b^2 c - 8 b c^2 + 8 c^3\\
=8a^3-7a^2b-7a^2c-7ab^2+18abc-7ac^2+8b^3-7b^2c-7bc^2+8c^3\quad \ge\quad 0\\
\implies 8(a^3+b^3+c^3)\quad\ge\quad 7(a^2b+a^2c+ab^2+ac^2+b^2c+bc^2)$$
If $\quad a=b=c=1\quad$ then $\quad 24\ge 42\quad $which is a contradiction.

If $\quad a=b=c=2\quad$ then $\quad 192 \ge 336\quad $ which is a contradiction.

If $\quad a=b=c=3\quad$ then $\quad 648 \ge 1134\quad $ which is a contradiction.

This math could be wrong but it appears that the original statement is reversed.

Title: Help with inequality please


问:
Any set can be well-ordered; doesn't that imply $(0,1)$ has a smallest real number?
I came across the above theorem ( also known as  Zermelo's theorem) in real analysis. Since any set can be well-ordered so can the set (0,1) which means there must exist a least element of the set.

That number, say 'p' is either rational or irrational ( I don't think we have a third option here).
If 'p' rational, then there must be an irrational number 'q' such that 0< q <p (The proof is trivial)
Likewise, if 'p' is irrational then there must exist a 'q' such that '0< q <p'

Thus a contradiction and no such 'p' exists and thus (0,1) is not well-ordered.

What am I missing here?

答:
The well ordering states:

For every set $S$ there exists some total order $\tilde{<}$ with the property that every non-empty set has a least element.

where I write $\tilde{<}$ to distinguish this order from any more common one. Note that the order is not intrinsic to the set - one can well order the rationals, for instance, by saying that, for rationals in lowest terms (with positive denominators), we define
$$\frac{a}b\,\tilde{<}\,\frac{c}d$$
if $|a|+|b| < |c|+|d|$ or if $|a|+|b|=|c|+|d|$ and $a<c$. We could get loads of other orders by choosing any bijection $f:\mathbb N\rightarrow\mathbb Q$ and saying that $p_1\,\tilde{<}\,p_2$ whenever $f^{-1}(p_1) < f^{-1}(p_2)$ in the natural numbers - or, in fact, we could do this with any bijection from a set with a known well-order.

None of these would be the usual ordering on the rational numbers - since the usual order is not a well-order, as you prove. The confusion is that your proof regards $(\mathbb Q,<)$ as an ordered set - that is, a set with additional structure on it - whereas the well-ordering theorem regards $\mathbb Q$ itself - a set with no extra structure.

Said otherwise, you proved that $((0,1), <)$ is not a well order for a specific $<$. All the well-ordering theorem says is that there is some $((0,1),\tilde <)$ that is a well-order - so your proof really just rules out one possible order, but doesn't contradict the existence of some other order.


答:
The key word there is "can". The statement "S can be well-ordered" means "There is an ordering on S that is a well-ordering". It doesn't mean "Every ordering of S is a well-ordering". The standard ordering of  $\mathbb R$ is not a well ordering. Any well ordering of $\mathbb R$ will not correspond to anything resembling a "normal" ordering (and, in fact, claiming that $\mathbb R$ can be well ordered requires the axiom of choice, which means that no ordering can be explicitly stated).

There is a distinction between $\mathbb R$ as a set and $\mathbb R$ as a mathematical object. When we speak of the real numbers as a mathematical object, we are speaking of not only the set of real numbers, but also the structure associated with $\mathbb R$, such as addition, multiplication, and ordering. Zermelo's theorem says that sets can be well ordered. That means that if we take just the space of $\mathbb R$, and ignore the normal structure, we can apply another structure such that the resulting object is well ordered.

Title: Any set can be well-ordered; doesn't that imply $(0,1)$ has a smallest real number?

Body:
I came across the above theorem ( also known as  Zermelo's theorem) in real analysis. Since any set can be well-ordered so can the set (0,1) which means there must exist a least element of the set.

That number, say 'p' is either rational or irrational ( I don't think we have a third option here).
If 'p' rational, then there must be an irrational number 'q' such that 0< q <p (The proof is trivial)
Likewise, if 'p' is irrational then there must exist a 'q' such that '0< q <p'

Thus a contradiction and no such 'p' exists and thus (0,1) is not well-ordered.

What am I missing here?


问:
Free online mathematical software
What are the best free user-friendly alternatives to Mathematica and Maple available online?

I used Magma online calculator a few times for computational algebra issues, and was very much satisfied, even though the calculation time there was limited to $60$ seconds.

Very basic computations can be carried out with Wolfram Alpha. What if one is interested in integer relation detection or integration involving special functions, asymptotic analysis etc?

Thank you in advance.

Added: It would be nice to provide links in the answers so that the page becomes easily usable. I would also very much appreciate short summary on what a particular software is suitable/not suitable for. For example, Magma is in my opinion useless for doing the least numerics.

答: If you have to deal with multivariate polynomial rings, Singular and Macaulay2 come to mind. I have not  tried the software much, but I definitely would in cases like the above.</p>

Title: Free online mathematical software


问:
Determine whether or not the poset $(\mathbb{N}, \propto)$ has a least element

Define a relation $\propto$ on the natural numbers $\mathbb{N}$ by declaring that for $x, y \in \mathbb{N}$, $x \propto y \iff (x=y)$ or $(3x \leq y)$

a) Show that $\propto$ is a partial order on $\mathbb{N}$

b) Determine whether or not the subset $\{2, 6, 8\}$ of $\mathbb{N}$ is totally ordered with respect to $\propto$. Explain your answer.

c) Determine whether or not the poset $(\mathbb{N}, \propto)$ has a least element.

For part a), I showed that it was reflexive, transitive and antisymetric.

For part b) I determined that the subset was NOT totally ordered because 6 $\not \propto 8$ and $8 \not \propto 6$

I'm unsure about part c). My guess is that there is no least element because $1 \not \propto 2$ so $1$ cannot be the least element. However $\forall n \in \mathbb{N}$ with $n>1$, $n \not \propto 1$, so there is no number $n \not = 1$ which is the least element.

But I'm sure I'm phrasing this really badly...

答:
You have the right idea.

Suppose $n \ne 1$ is a least element under $\propto $. Since you assume $\Bbb N = \Bbb Z^+$, then $n \ge 2$. Then $n \propto 1$ in particular. However, $n \ne 1$, and since $n \ge 2$, then $3n \ge 6$; thus $3n \not \le 1$ and $n \not \propto  1$

So the only remaining candidate is $n=1$. However, $1 \not \propto 2$ because $3 \cdot 1 \not =3\le 2$.

Thus, all possible candidates have been removed, and $\propto $ has no least element in $\Bbb N$. (Though if you were to include zero, then $0$ would be the least element, since $0 \cdot x = 0 \le y$ for all $y \in \Bbb N$.)

Mostly just posting this to get this out of the unanswered queue. Posting as Community Wiki in particular since I have nothing further to add.


问:
An Olympiad geometry question on area lemma.
In ABC, E, F, G are points on AB, BC, CA respectively such that $\frac{AE}{EB} = \frac{BF}{FC} = \frac{CG}{GA} = \frac{1}{3}$. K, L, M are the intersection points of the lines AF and CE, BG and AF, CE and BG, respectively. Suppose the area of ABC is 1; find the area of KLM.

I know there is a general formula when dividing in m:n ie. $\frac{(m-n)^2}{m^2+mn+n^2}$

P.S. please no Bary/ Complex

To verify the result, I put $m=n$ and it worked. Also, I tried the area lemma, Ceva's theorem but to no use. I tried this problem for a long time and then realised that Menelaus worked but as this excercise was in the area and ratio section, that felt like 'cheating' as I want to know the author's intended method.

Thanks!

答:
Let [.] denote areas. Evaluate the area ratio

$$\frac{[CBM]}{[EBM]}= \frac{[CBG]}{[EBG]}
= \frac{\frac 14 [ABC]}{\frac 34 [ABG]}= \frac{\frac 14 [ABC]}{\frac 34 \frac 34[ABC]}
=\frac 49 $$

which leads to the area $[CBM]$, and likewise $[ACK]$, $[BAL]$

$$[CBM] = \frac{4}{4+9} [CEB] = \frac{4}{13}\frac 34[ABC]
=\frac{3}{13} = [ACK] = [BAL] $$
Then
$$[KLM] = [ABC] -[CBM]- [ACK]-[BAL] =1-3\cdot\frac{3}{13}=\frac 4{13}$$

The derivation applies to general ratio $m:n$ as well
$$\frac{[CBM]}{[EBM]}=\frac{m(m+n)}{n^2}\implies
\frac{[CBM]}{[CBE]}=\frac{m(m+n)}{m(m+n)+n^2} $$
$$\implies [CBM]= \frac{m(m+n)}{m(m+n)+n^2}\cdot\frac{n}{m+n}
=\frac{m n}{m^2+mn +n^2}$$
$$[KLM] = 1-3[CBM]= \frac{(m-n)^2}{m^2+mn +n^2}
$$


问:
Closest point on ray to triangle in 3D
There's a great many articles on finding the intersecting of a ray and a triangle, or the closest point on a triangle to some other point. However, I can't find anything for finding the closest points between a ray and a triangle.

Perhaps a bit more formally, given the triangle defined by points A, B, and C, and a ray defined by an origin O and a direction D, find the two points P and Q where P is on the ray, Q is on the triangle, and the distance between P and Q is minimal.

I've tried to start with editing a ray-triangle intersection algorithm, but I don't think that's going to work. A lot of them seem to find where the ray intersects with the plane defined by the triangle, but that's not necessarily the closest point (imagine a ray that is mostly parallel to the plane and slightly above it - the closest point on the ray would be above the triangle, not intersecting its plane).

Has anyone developed an algorithm for this, and if so, what is it?

答:
Putting together some stuff from this question's comments:

First do a regular ray-triangle intersection test. If it passes, the closest point is obviously the intersection.

<s>If the ray is facing away from the triangle (i.e. the ray's time-of-intersection with the plane defined by the triangle is negative, which most ray-triangle intersections test for), the closest point on the ray is the ray's origin. Can use that point with a standard algorithm to find the corresponding closest point on the triangle.</s>

Otherwise, the closest point will be on one of the triangle's edges. Run the closest point on ray and line segment algorithm on all 3 of the edges and take the one that's closest.

(For lines parallel to the triangle, there may not be a singular closest point, but that does not matter for my case in particular)

Title: Closest point on ray to triangle in 3D


问:
A Probability Question From Real Life
I've tried asking this question of various mathematicians, but never gotten an answer.  Perhaps because it is not well posed.  I'll present the problem, but it may be that certain simplifying assumptions must be made in order to get a handle on it.

At the Manhattan Scrabble Club four games are played by each player during an evening tournament.  Each game is played by two players.  (If there are an odd number of players present on a given night, then the moderator plays too, otherwise he doesn't play.) There is a slight advantage to the player who plays first, so it is desirable that no player should play first more times than his opponents.  For this reason before a game between two players begins, their records for previous games on that night are compared.  If they have each played first in the same number of previous games, then each of them selects a tile from the bag without looking.  The player who selects the tile earliest in alphabetical order gets to go first in the new game. (If they choose the same letter, then each of them returns his tile to the bag and they choose again until someone prevails.) If one player has played first in more previous games than the other, then his opponent gets to play first in the new game.  In actual play there is a moderator who tries to match player according to their records for that night .  For example: if, before the fourth game, there are two players each of whom has won all three of his previous games then the moderator will try to match them against each other.  Perhaps it would be best to leave out the effect of the moderator  initially when trying to analyse the setup.

Despite these measures, it seems clear that it is possible that one or more players will play first in each of his, or their games.

First question:  What is the smallest number of players who must be present at the tournament such that it is possible that at least one player plays first in all four of his games?

Second question:  Given that the number of players in the tournament is as in the answer to the first question, can we assign a probability to the occurence that on a certain night one or more of the players has played first in all four games?  If so, what is that probability?

答:
Second Question: very small (less than 0,01%)
In order to have a player from the 16 start all of his games first, things must go "ideally". That means that all those who played first in their game 1, should play against each other in game 2. From these, there will be 4 that have played first in both their games. They must play against each other in game 3. To find the actual probability we have:

Lets say that a player that has started first in his last n games has a streak of n.

1st round of games: The probability that 8 of the 16 players start first is $ P(A) = 1 $.

2nd round of games: We have 8 players with a streak of 1 that must play against each other. The first has 7 "good" opponents and 7 bad (the remaining 8 minus the one he played against in round 1). So 7/14. Once these two are paired, the next one has 5 "good" opponents and 7 "bad". So 5/12. In total:

$ P(B) = \frac{7}{14} \cdot \frac{5}{12} \cdot \frac{3}{10} \cdot \frac{1}{8} $

Notice that the probability of having 4 players with a streak of 3 in the end of the second round is $ P(A) \cdot P(B) $.

3rd round: The reasoning is the same: we have 4 people that must play each other. Each one has already played against two people from the remaining 12. So $ P(C) = \frac{3}{13} \cdot \frac{1}{11} $.

4th round: If we managed to get here with 2 people having a streak of 3 (and the remaining 14 a smaller streak) - we just have to pair these 2. That gives $ P(D) = \frac{1}{12} $.

In total your probability is $ P(A) \cdot P(B) \cdot P(C) \cdot P(D) = \dfrac{1}{73.216} $

On a sidenote - the bigger the advantage the starting player has and considering how the moderator matches players, this probability can become significantly higher. If the player who plays first is sure to win - then it is actually certain that you will have someone with a streak of 4 (but in that case you are not really playing Scrabble - you are playing an extremely convoluted coin toss game :) ).

OwnerDisplayName: David S. Newman

Title: A Probability Question From Real Life


问:
How to Evaluate $ \sum_{n=1}^{\infty} \frac{(-1)^n}{n}H_{4n-3} $
I came across the following result:

$$ \sum_{n=1}^{\infty} \frac{(-1)^n}{n}H_{4n-3} = \frac{\pi}{4} + \frac{\pi}{\sqrt{2}}-\frac{5\pi^2}{32}+\frac{\ln^2(2)}{8}-\frac{3\ln(2)}{2}+\frac{\ln^2(1+\sqrt{2})}{2}+\frac{\ln(3-2\sqrt{2})}{\sqrt{2}}$$

$H_{4n-3}$ refers to Harmonic Numbers

However Mathematica is not able to compute it as it gives an enormous result full of PolyLogs and Roots of functions.

Could someone please provide a proof for the above result?

答:
The opposite series is
$$ \sum_{n\geq 0}\frac{(-1)^n}{n+1}H_{4n+1} = \int_{0}^{1}\sum_{n\geq 0}\frac{(-1)^n}{n+1}\cdot\frac{x^{4n+1}-1}{x-1}\,dx =\int_{0}^{1}\frac{x^3\log(2)-\log(1+x^4)}{x^3(1-x)}\,dx$$
and Mathematica is able to deal with the integral, even if the simplification of dilogarithms has to be carried out by hand. By using integration by parts the RHS boils down to elementary integrals and
$$ I_1 = \int_{0}^{1}\frac{x^3}{1+x^4}\log(x)\,dx,\qquad I_2=\int_{0}^{1}\frac{x^3}{1+x^4}\log(1-x)\,dx. $$
Of course
$$ I_1 = \sum_{n\geq 0}\int_{0}^{1} (-1)^n x^{4n+3}\log(x)\,dx = \sum_{n\geq 0}\frac{(-1)^n}{(4n+4)^2}=\frac{\pi^2}{192}$$
so the whole problem is more or less equivalent to the computation of $I_2$, which can be performed by enforcing the substitution $x=1-z$, computing a partial fraction decomposition and exploiting
$$ \int_{0}^{1}\frac{\log(x)}{x-a}\,dx =\text{Li}_2\left(\frac{1}{a}\right).$$
This is strongly reminiscent of the trick I used at page $3$ here.


问:
Can two random variables $X$ and $Y$ be identically distributed while satisfying $P(X<Y)=1$?
I realise this is not possible if $X$ and $Y$ are discrete with a finite support and I think it is true in general, but I am having trouble with the continuous and discrete-with-infinite-support cases.

Any help would be appreciated.

答:
The answer is negative.

Suppose that $X$ and $Y$ has the same distribution function $F$.  Put $B_n =  \{ X + \frac{1}{n} \le Y <  X + \frac{1}{n-1} \}$, $n \ge 1$, thus $\Omega = \sqcup_{n=1} B_n$.

$$\sum_n P(X \le t, B_n) = P(X \le t) = P(Y \le t) = \sum_n P(Y \le t, B_n) \text{${}$ ${}$(1)} $$
But $P(Y \le t, B_n) \le P(X \le t, B_n)$ and it follows from (1) that  $P(Y \le t, B_n) = P(X \le t, B_n)$ for all $n$.

We have

$$ P(X \le t-\frac1n, B_n) \le P(X \le t, B_n)  = P(Y \le t, B_n) =$$
$$ = P(Y \le t, X + \frac{1}{n} \le Y <  X + \frac{1}{n-1}) \le $$
$$\le P(X + \frac1n \le t, X + \frac{1}{n} \le Y <  X + \frac{1}{n-1}) =$$
$$ =P(X + \frac1n \le t, B_n) = P(X \le t-\frac1n, B_n) \text{${}$ ${}$(2)} $$
and it follows that all values in (2) are equal. Hence
$P(X \le t-\frac1n, B_n) = P(X \le t, B_n) $ and that's why
$$P(X \in (t-\frac1n, t], B_n) = 0.$$
Fix $n$. As $t$ is arbitrary we get $P(B_n) = 0$.

As  $\Omega = \sqcup_{n=1} B_n$ we have $1 = P(\Omega ) = \sum_n 0 = 0$. We got a contradiction, q.e.d.