TITLE: New way of combining information in graphs
QUESTION [0 upvotes]: So, I am working for a social project involving graph theory. I have a dynamic dataset (weighted and undirected), I made graphs out of them ( for 10 years ). Now, I am trying to find out relations between those graphs. I basically aim to do some knowledge discovery out of those graphs that I made. I did some research and reached the following conclusion: I can compare graphs in two ways:
1.) Either I can use the similarity techniques ( Graph edit distance, or Feature extraction or iterative methods ) which basically prove if two graphs are isomorphic/subgraphs or not.
2.) I can go by the method of ego networks. I can extract a particular ego ( a node, or a group of people ) and study only their properties and their evolution about how the ego's nature changes over a period of time.
I wish to know, is there any other way of like this of doing some knowledge discovery?
PS. I sort of feel this is not the appropriate place for this question, so it will be great if you can guide me to the right forum and not actually downvote it. This problem is somewhat close to my heart as I said, I am doing it for a social cause.

REPLY [1 votes]: I'll hazard an answer.
What to do would depend on the network and what you want to look for.  Generally it's better to start with a hypothesis and test for it, rather than diving in trying to "find something interesting".  I suggest you play around with it manually, e.g. try drawing the data (or parts of it) in different ways, until you find something you might be interested in specifically researching.
E.g. I studied my Facebook social network, and found that $4$-cycles tended to have "chords".  I then compared this to other networks, and found that the $4$-cycles are important for determining the frequencies of other subgraphs.
Researchers often look at clusters in social networks (close nit communities); e.g. the famous Karate Club network.  And with a dynamic network, look at how they change over time.  (I think things like edit distance would be impractical to implement though.  But it depends on the data.)
Researchers also search for network motifs (and how these change over time).  Whether or not this is possible and worthwhile depends on the data.
Personally, I find a lot of network analysis dissatisfying: it's promoted as being a next big thing, but almost always only very broad statements can be made from the network structure (there's a dense cluster here, these few nodes are hubs, it is resistant to random edge failures, and so on).  To get a non-superficial understanding, a careful (and time-consuming) human analysis is needed.


TITLE: Trying to convert a logical expression into CNF
QUESTION [2 upvotes]: I'm trying to convert the following Boolean expression into a CNF (or DNF):
$(\neg p \vee \neg q) \rightarrow (q \rightarrow \neg p)$
I apply various laws until I get to:
$(p \wedge q) \vee (\neg p \vee \neg q)$
This doesn't fit the form of a CNF, but I'm not sure how to get that last expression into an 'and' statement, or a series of more ORs of ANDs. I can do it by making a truth table and just writing it out, but is there some law that I am supposed to apply to $(\neg p \vee \neg q)$ to make it a CNF?

REPLY [1 votes]: It might help to think by analogy with algebraic expressions formed using multiplication and addition. Multiplication distributes through addition, i.e., you have $x \times (y + z) = (x \times y) + (x \times z)$. Hence you can write any expression as a sum of products of atoms, by pushing the multiplications in through additions. But note that addition does not distribute through multiplication, so you can't write every expression as a product of sums of atoms.
Boolean algebra, however is much more symmetric: not only does conjunction distribute through disjunction, i.e., $x \land (y \lor z) = (x \land y) \lor (x \land z)$ but also disjunction distributes through conjunction, i.e., $ x \lor (y \land z) = (x \lor y) \land (x \lor z)$. Hence (also using De Morgan's laws to push in negations), you get to choose whether to push the conjunctions in, which will lead you to DNF: a disjunction of conjunctions of literals, or to push the disjunctions in, which will lead you to a CNF: a conjunction of disjunctions of literals. (Here "literal" means an atom or negated atom.) For example, your formula can be transformed into a CNF like this:
$$
\begin{array}{rcl}
[(p \land q) \lor \lnot p] \lor \lnot q &=& [(p \lor \lnot p) \land (q \lor \lnot p)] \lor \lnot q\\
 &=& (p \lor \lnot p \lor \lnot q) \land (q \lor \lnot p \lor \lnot q)
\end{array}
$$
You can now do further simplifications if you wish, e.g., to arrive at $p \lor \lnot p$ (which is both a DNF and a CNF).


TITLE: How do continuity, distance and irrationals arise from discreteness?
QUESTION [3 upvotes]: Consider a square as rendered on a computer screen: its width and height are $N$ pixels each, and its area is $N^2$ pixels. Its diagonal, when measured in pixels, is also $N$ pixels long. If you double the number of pixels, the sides and diagonals will again be $2N$ pixels long. Obviously, this will never converge to $\sqrt2$.
I know I'm supposed to measure the diagonal length in terms of pixel diagonal length, but this only pushes the question one step back: how (from which limiting geometrical process) does $\sqrt2$ as the pixel diagonal length arise? Does there exist a discrete process, akin to the one described above, that converges to $\sqrt2$ in the limit?

REPLY [2 votes]: The lenght of the diagonal is independent of the pixel grid. Moreover, the boundary of the approximating pixels after adding up has always the same length: (horizontal distance + vertical distance)*2. So "pixel distance" has little to do with "Euclidean distance".


TITLE: Rising factorial stirling numbers from the recurrence
QUESTION [0 upvotes]: I have seen a proof that the recurrence of the unsigned stirling numbers of the first kind can be derived from the rising factorial definition.
That is, $s(n,k)$ are given by the coefficients on $x^k$ in the expansion $x(x+1)...(x+n-1)$ and this definition can be used to show that $s(n,k)=(n-1)s(n-1,k)+s(n-1,k-1)$
This seems to be the general progression. Start with the rising factorial definition, and then it is fairly straightforward to show the recurrence relation.
My Question:
Is there a good way to see this in reverse? Can you start with the stirling recurrence I have listed above and show that the stirling numbers must come from the coefficients of the rising factorial polynomial?

REPLY [1 votes]: Sure, just call $$f_n(x)=\sum _{k=0}^ns(n,k)x^k,$$
use the base case to understand $f_0(x)$ and then, for $n>0$, just plug the recurrence as
$$f_n(x)=\sum _{k=0}^ns(n,k)x^k=\sum _{k=1}^{n}\left ((n-1)s(n-1,k)+s(n-1,k-1)\right )x^k,$$
split the sum and conclude that $f_n(x)=(n-1)f_{n-1}(x)+xf_{n-1}(x)=f_{n-1}(x)(x+n-1).$
Show that the rising factorials have the same recursion and you are done.


TITLE: Barbalat's Lemma
QUESTION [0 upvotes]: I have this problem to solve:
Use Barbalat’s Lemma to show that $\lim_{t\to \infty} x_1(t) = 0$
 for the system:
$\dot x_1= − x_1 + x_1 x_2 $
$\dot x_2= − \gamma x_1^2$ ,
where $\gamma > 0$. Can we you anything about $x_2(t)$ based on this analysis?
First, I defined the following function:
$V(x_1, x_2)=\frac{1}{2} (x_1^2+x_2^2)$
This is clearly lower bounded. I then proceeded to check if $\dot V\leq0$. I get:
$\dot V(x_1, x_2)=x_1 \dot x_1+x_2 \dot x_2=-x_1^2-x_1^2x_2(\gamma-1)$
Here's where I can't proceed any further. The sign of $\dot V$ depends on the quantity $(\gamma-1)$, which I'm not told if it's always positive... I only know that $\gamma >0$. What do you guys suggest?

REPLY [0 votes]: This system is a degenerate one; it has infinitely many connected poles due to degenerate linearized system.
It seems to have an attractor, but it doesn't. More precisely, if $|x_2-1|$>1 then $x_2$ starts to decrease because of increasing in $x_1$ until it traps in the region $|x_2-1|$<1 which can be easily proved by your Lyapunov candidate.
the term $\gamma-1$ can be vanished by using some multipliers like $(1-x_2)x_1$ for $x_1>0$; and $(x_2-1)x_1$ for $x_1<0$. look at Multiplier Method for Lyapunov function.


TITLE: How to convert linear programming model to standard form?
QUESTION [2 upvotes]: How do I convert this LP model to standard form?

REPLY [2 votes]: Two of possible standard form notation used by different authors (maybe there are more):
First gives 3 conditions:
1)maximalization of function
2)constraints in the form $c_1x_1+c_2x_2+\dots c_nx_n \leq b_j$
3)Non-negative variables
Second also  gives 3 conditions:
1)minimalization of function
2)equality constraints
3)Non-negative variables
 You should pick one (or maybe some other) and then transform the system of equation. Let's find the first form. To satisfy the first condition, note that the problem of minimalization of $f(X)$ is equal to maximalization of $-f(X)$. For the second condition, note that $c_1x_1+c_2x_2+\dots c_nx_n \leq b_j$ is equivalent to $-c_1x_1-c_2x_2-\dots -c_nx_n \geq -b_j$. So your problem may be expressed in (first) standard form as:
maximize $-3x_1+x_2$
subject to $-x1+3x_2\leq3$$-2x1-x_2\leq2$$2x1+x_2\leq8$$4x1-x_2\leq16$$x_1,x_2\geq0$. To obtain second type of standard form we will replace inequalities with equalities by introducing $x_3,x_4,x_5,x_6\geq 0$ and rewriting our problem as:
minimize $3x_1-x_2$
subject to $-x1+3x_2+x_3=3$$-2x1-x_2+x_4=2$$2x1+x_2+x_5=8$$4x1-x_2+x_6=16$$x_1,x_2,x_3,x_4,x_5,x_6\geq0$.

REPLY [2 votes]: Standard form varies from author to author as @M. Stawiski noted in the comments. Nevertheless in the various texts I have seen there are generally two recurring themes. Writing the system in the form of
$$ Ax \le b, x \ge 0$$
where $x$ is a vector in $\Bbb{R}^n$ and $A,b$ are matrices and vector respectively, or
$$ Ax = b, x \ge 0 $$.
Lets cover form 1. Any inequality that is $\le$ need not be changed. Lines with a $\ge$ can be multiplied to flip the sign, and a trickier one is if someone throws at you $=$ constraints. Of which you have given none. But suppose you had a line such as
$$ 2x_1 + 3x_2 = 4 $$
Then you can just write as
$$ \begin{pmatrix} 2x_1 + 3x_2 \le 4 \\2x_1 + 3x_2 \ge 4   \end{pmatrix} $$
And then flip the bottom one to yield
$$ \begin{pmatrix} 2x_1 + 3x_2 \le 4 \\-2x_1 - 3x_2 \le -4   \end{pmatrix} $$
Lastly (now this doesn't apply in your case) suppose someone throws in a variable $x_r$ that is unconstrainted. Then we can rewrite $x_r$ as $x_j - x_k$ where $x_j,x_k \ge 0$ then make that subsitution. Eventually after doing sign flipping, breaking inequalities, and substitutions you will have only $\le$ signs, and your variables will be $\ge 0$ observe in your case:
$$ \begin{pmatrix} -x_1 + 3x_2 \le 3 \\ -2x_1 - x_2 \le 2 \\ 2x_1 + x_2 \le 8 \\ 4x_1 - x_2 \le 16 \end{pmatrix} \rightarrow \begin{pmatrix} -1 & 3 \\ -2 & -1 \\ 2 & 1  \\ 4 & -1\end{pmatrix} \begin{pmatrix} x_1 \\ x_2\end{pmatrix} \le \begin{pmatrix} 3 \\ 2 \\ 8 \\ 16 \end{pmatrix} x_1, x_2 \ge 0 $$
So here you are in standard from with $A$ that matrix, $b$ the vector on the right side and $x$ the pair of two variables which is strictly positive.


TITLE: lebesgue measurable problem
QUESTION [3 upvotes]: Let $E$ be a Lebesgue measurable subset of $[0,1]$, and suppose that $m(E)>3/4$. Prove that $(-1/2,1/2) \subseteq E-E$. We use $E-E$ to denote the set $\{x-y:x,y \subseteq E\}$

REPLY [0 votes]: Let $x\in[0,\frac12)$, then $E, E+x\subseteq[0,\frac32)$ and
$$m(E\cap(E+x))=m(E)+m(E+x)-m(E\cup(E+x))>\frac34+\frac34-\frac32=0$$
so the sets intersect and $e=e'+x\Longrightarrow x=e-e'$.
So $[0,\frac12)\subseteq E-E$ and by symmetry also $(-\frac12,0]\subseteq E-E$.


TITLE: Finding wave-fuctions of a Dirac particle for given 4-momentum and spin 4-vector
QUESTION [2 upvotes]: I've been reading through various materials on relativistic quantum mechanics, but I find the lack of simple examples disturbing.
I'm acquainted with the general form the solutions to the Dirac equations have, but I'm having trouble just practically getting any specific example solution.
Since the motion of a free Dirac particle is entirely determined with four-momentum $p^\mu$ and the spin (polarization) four-vector $s^\mu$, how exactly does one find the wave-function corresponding to some given $p^\mu,s^\mu$?
E.g. $p^\mu=m\{\sqrt{2},0,0,1\}, s^\mu=\{1,0,0,\sqrt{2}\}$

REPLY [1 votes]: Start with a plane-wave at rest with its spin pointing in the z-direction:
$\psi_L=\psi_R=\left(\begin{array}{c} 1\\ 0\end{array}\right)$

First rotate the spin to the required direction.
$\psi_L \rightarrow \exp\left(-\tfrac12 i\theta_i\,\sigma^i\right)\psi_L
~~~~~~~~~~~~
 \psi_R \rightarrow \exp\left(-\tfrac12 i\theta_i\,\sigma^i\right)\psi_R$
(Find the Euler angles $\theta_i$ by transforming the spin-vector to the rest-frame)

Now boost the rotated spinors in the right direction.
$\psi_L \rightarrow \exp\left(-\tfrac12\vartheta_i\,\sigma^i\right)\psi_L
~~~~~~~~~~~~
 \psi_R \rightarrow \exp\left(+\tfrac12\vartheta_i\,\sigma^i\right)\psi_R$
(Calculate the rapidity $\vartheta_i$ from the momentum)

Finally: Note that you can expand:
$\exp(i\phi_i\sigma^i) \longrightarrow \cos|\phi|+i  \phi_i\sigma^i  \sin|\phi|\,/\,|\phi|$
to get the matrices out of the exponent's argument

Hans


TITLE: Show that $\| \mathbf{b} - \mathbf{A} \mathbf{x} \|_{2}^{2} < \| \mathbf{b}\|_{2}^{2}$ given $|x_{i}| = 1 \quad \forall i$
QUESTION [0 upvotes]: Suppose that I solve the following optimization problem:
$$ \underset{\mathbf{x}}{\text{minimize}} \quad || \mathbf{b} - \mathbf{A} \mathbf{x} ||_{2}^{2} $$
$$ \text{subject to} \; \; |x_{i}| = 1 \quad \forall i $$
where $\mathbf{b} \in \mathbb{C}^{M \times 1}$ with $|\mathbf{b}|_{i} \in \{-1, 0, 1, N \}$, $\mathbf{A} \in \mathbb{C}^{M \times N}$ is a lower triangular Toeplitz matrix with $|\mathbf{A}|_{i,j} \leq 1$, and $\mathbf{x} \in \mathbb{C}^{N \times 1}$ and $M > N$.
Can I ever be sure that:
$$\| \mathbf{b} - \mathbf{A} \mathbf{x}_{\ast} \|_{2}^{2} < \| \mathbf{b}\|_{2}^{2}$$
where $\mathbf{x}_{\ast}$ is the optimal solution?
If so, how can I show this? Or perhaps in other words, what are the conditions that allow me to say this?

Subtracting and expanding this out, we get:
$$ \|\mathbf{b}\|_{2}^{2} - 2 \mathbf{b}^{H} \mathbf{A} \mathbf{x}_{\ast} + \mathbf{x}_{\ast}^{H} \mathbf{A}^{H} \mathbf{A} \mathbf{x}_{\ast} -  \|\mathbf{b}\|_{2}^{2} < 0 $$
ie that:
$$ \mathbf{x}_{\ast}^{H} \mathbf{A}^{H} \mathbf{A} \mathbf{x}_{\ast}  < 2 \mathbf{b}^{H} \mathbf{A} \mathbf{x}_{\ast} $$
But I don't see how that actually tells me anything.
Does anyone have any ideas?
Here is an idea. Since $|x_{i}| = 1$, if we transpose and then  take absolute values, we get:
$$ \mathbf{1}^{T} \mathbf{A}^{H} \mathbf{A} \mathbf{1} < 2 \mathbf{1}^{T} | \mathbf{A}^{H} \mathbf{b}| $$
Does that spark any ideas? Hmm...I think the restrictions on the absolute values of the elements will be important here...but I can't figure out how they fit together...

Edit:
The matrix $\mathbf{A}$ is a causal FIR filter matrix -- ie lower triangular and Toeplitz. See: https://www.dsprelated.com/freebooks/filters/Matrix_Filter_Representations.html

REPLY [2 votes]: You cannot.  For instance, consider
$$
A = \pmatrix{0&0\\0&0\\1&0}, \quad b = \pmatrix{1\\0\\0}.
$$
In this case, we find that all $\|b - Ax\|_2^2 = 2$ for all $x$ satisfying $|x_1| = 1$, but $\|b\|_2^2 = 1$.


TITLE: How to see the convergence/divergence of this integral
QUESTION [1 upvotes]: I have a question, I want to know for which values of $p\in \mathbb{R}$ this integral have finite value:
$$\int_{0}^{\infty} \frac{\sin{x}}{x^p}dx $$
I have shown that for $p=1$ the integral is finite and equals to $\frac{\pi}{2}$, so, if $p\geq1$ is easy to see that the integral converges. The intuition says that if $p<1$, it diverges. But I don't know how to prove that. Any idea?

REPLY [3 votes]: The integral converges for $0<p<2$.
Convergence for $0 < p \leq 1$.
First note that $\lim_{x\to 0}(\sin x)/x^p=\lim_{x\to 0}x^{1-p} =0$ if $p < 1$; the limit is 1 if $p=1$. So there is no problem around $x=0$. Therefore it suffices to show that the integral from $1$ to $\infty$ converges.
Partial integration gives
$$
\begin{align*}
 \int_1^\infty \frac{\sin x}{x^p}\,dx &= \int_1^\infty \frac{1}{x^{p}}\,d(-\cos x) \\
&= -\Biggl.\frac{\cos x}{x}\Biggr|_1^\infty - p\int_1^\infty \frac{\cos x}{x^{p+1}}\,dx \\
&= \cos 1 -p\int_1^\infty \frac{\cos x}{x^{p+1}}\,dx.
\end{align*}
$$
Since $|x^{-(p+1)}\cos x|\leq |x^{-(p+1)}|$ and since $p>0$ the integral in the last term converges. Therefore the whole integral
$$
  \int_0^\infty \frac{\sin x}{x^p}\,dx
$$
is convergent.
Convergence for $1 < p < 2$. Note that $\sin x \sim x$ for $x\to 0$. Therefore the integrand is asymptotically equivalent with $\frac{1}{x^{p-1}}$ around $x=0$. In order for the integral to be convergent, $p-1 < 1$, or $p < 2$.
Note that at infinity there is no problem. If you would take the integral from, say, 1 to infinity, convergence follows from the inequality $|x^{-p}\sin x|\leq |x^{-p}|$ and the fact that $p > 1$.
No convergence for $p < 0$. We write
$$
 \int_{\pi}^\infty \frac{\sin x}{x^p}\,dx = \sum_{n=1}^\infty a_n \quad
\text{ with }
\quad a_n = \int_{n\pi}^{(n+1)\pi} \frac{\sin x}{x^p}\,dx.
$$
For $n\pi \leq x \leq (n+1)\pi$,  we have $(n\pi)^{-p}\leq x^{-p}\leq((n+1)\pi)^{-p}$ since $-p > 0$. For even integers $n$, the $a_n$ are positive and we have
$$
 \int_{n\pi}^{(n+1)\pi} \frac{\sin x}{x^p}\,dx \geq (n\pi)^{-p}\int_{n\pi}^{(n+1)\pi} \sin x\,dx = 2(n\pi)^{-p}.
$$
For odd $n$, the term $a_n$ is negative and
$$
 \int_{n\pi}^{(n+1)\pi} \frac{\sin x}{x^p}\,dx \leq ((n+1)\pi)^{-p}\int_{n\pi}^{(n+1)\pi} \sin x\,dx = -2((n+1)\pi)^{-p}.
$$
This implies that the series $\sum_{n=1}^\infty a_n$ diverges, and so the integral also diverges.


TITLE: Expected value that depends on Poisson distribution
QUESTION [0 upvotes]: X = The number of customers entering a shop.
X∼Poisson(4)
P(Costumer buys 1 pair of socks) = 3/4.
decisions are not dependent.
Y random variable that equals the number of socks sold.
What is E[Y]?

Would like to get some help with this question, I got a hint that its between [3,3.5)
but not sure how to get the exact value..
Thanks in advance.

REPLY [1 votes]: We have
$$P(X=n)=\frac{4^ne^{-4}}{n!}$$
The expected number of socks bought if $n$ customers enter is $\frac34n$. Then
$$E(Y)=\sum_{n=0}^\infty\frac{4^ne^{-4}}{n!}\cdot\frac34n$$
$$=3\sum_{n=1}^\infty\frac{4^{n-1}e^{-4}}{(n-1)!}$$
$$=3\sum_{n=0}^\infty\frac{4^ne^{-4}}{n!}=3$$
The following more general property holds: if $X\sim\operatorname{Pois}(\lambda)$ and $Y$ given $X=k$ follows $\operatorname{binom}(k,p)$, then $Y\sim\operatorname{Pois}(p\lambda)$.


TITLE: Cross Variation of Ito Integral with $L^2$ bounded continuous martingale
QUESTION [2 upvotes]: I am trying to prove the identity:
$$ < I(K), N_{\cdot}>_t = \int_0^t K_s \ d < B,N_{\cdot}>_s $$
where $I(K)_t$ is by definition $ \int_0^t K_s \ d B_s $, and we take $K$ as a progressively measurable process, bounded with respect to the norm $\mathbb E[ \int_0^{\infty} (K_s)^2 \ ds]$, and we take $N$ to be a $L^2$ bounded martingale ( $\sup_{s \geq 0} \mathbb E[ (N_s)^2 ] < \infty $).

My attempt:
The problem I am facing is that I do not know how to rewrite $d < B,N>_s$  or simplify the following term:
\begin{align}
< I(K), N_{\cdot}>_t &=
< \int_0^{\cdot} K_s \ d B_s, N_{\cdot}>_t \\
&= \frac 1 4 [ < \int_0^{\cdot} K_s \ d B_s + N_{\cdot}>_t -  < \int_0^{\cdot} K_s \ d B_s - N_{\cdot}>_t] \\
&= \ ??  \\
&= \int_0^t K_s \ d < B,N_{\cdot}>_s
\end{align}
I thought about using the polarising identity: $<M-N> = <M> + <N> - 2 <M,N>$ but I am unsure about how to use it correctly in this case.
Any thoughts?

REPLY [0 votes]: After working it and using hints, here I described the steps to do the proof:
We prove for all $M,N$ local martingales: $< \int H d M, N > = \int H \ d < M,N> $

Take $M$ and $N$ $L^2$ continuous martingales first. $H$ a simple process. Then using the orthogonality of martingales:

\begin{align}
< \int H \ d M, N >_t
&= < \sum H_{t_i} ( M^{t_{i+1}} - M^{t_{i}}), N >_t \\
&= \sum H_{t_i} ( <M,N>_t^{t_{i+1}} -  <M,N>_t^{t_{i}}) \\
&= \int H \ d < M,N>
\end{align}

Replace $H$ by a progressively bounded process ( bounded in the sense: $\mathbb E[ \int^{\infty}_0 H_s^2 \ d < M >_s ]$, and use the Kunita Watanabe inequality.

Conclude with stopping times (localisation argument) and replacing $M,N$ local martingales.

There is a very nice proof of this statement (thrm 5.4) in Le Gall Brownian Motion, Martingales, and Stochastic Calculus.


TITLE: What is the probability of obtaining a total of 6 for the two cards?
QUESTION [1 upvotes]: Consider the experiment of drawing two cards from a deck in which all picture cards have been removed and adding their values (with ace = $1$).

What is the sample space?
What is the probability of obtaining a total of $5$ for the two cards?
Let A be the event “total card value is 5 or less.” Find $P ( A )$
Let A be the event “total card value is 5 or less.” Find $P (A^{\complement} )$

REPLY [0 votes]: Assuming that all face cards are removed, you are left with $52-12=40$ cards.
So, your Sample Space is $40$ cards consisting of all numbered cards (from Ace=$1$ to $10$) in all $4$ suits.
When you draw $2$ cards to obtain a total of $5$, there are following possibilities:
$$(4,1),(3,2)$$
and there are $4$ cards of each kind.
 So select $1$ of them in $^4C_1$ way, and $2$ cards can be selected from $40$ in $^{40}C_2$ ways.
$$P(\text{sum=5})=\frac{^4C_1\cdot ^4C_1+^4C_1\cdot ^4C_1}{^{40}C_2}=\frac{32}{^{40}C_2}$$
For $sum\leq5$, possible cases are: $$(1,1),(1,2),(1,3),(2,2),(1,4),(2,3)$$
There are $^4C_2$ ways to draw $2$ cards with same number, from $4$.
$$P(A)=\frac{(^4C_2)+(^4C_1\cdot ^4C_1)+(^4C_1\cdot ^4C_1)+(^4C_2)+(^4C_1\cdot ^4C_1)+(^4C_1\cdot ^4C_1)}{^{40}C_2}=\frac{76}{^{40}C_2}$$
$$P(A^C)=1-P(A)=1-\frac{76}{^{40}C_2}$$


TITLE: How can I show that $y'=\sqrt{|y|}$ has infinitely many solutions?
QUESTION [10 upvotes]: Show that the first order differential equation
$y'(x)=\sqrt{|y(x)|}$
with intial value
$y(1/2)= 1/16$
has infinitely many solutions on the interval [−1, 1].
My thought were to show that this equation has two solutions (just by ansatz, or just looking at the interval $]0, 1]$ to get $y'(x) = \sqrt{|y(x)|}$) and deduce from that that there must be infinitely many solutions since the solution set forms a vector space. I've got a nagging feeling this isn't the way to go though. Can anybody give me a hint where to look?

REPLY [16 votes]: This is a classical example of non uniqueness due to the fact that the right hand side of the equation, $\sqrt{|y|}$, is not Lipschitz at $y=0$. You show this by direct computation. The equation is in separeted variables:
$$
\frac{dy}{\sqrt{|y|}}=dt,\quad y(1/2)=1/16.
$$
Integrating, and taking into account the absolute value, we see that
$$
y(t)=\frac{t\,|t|}{4}=\begin{cases}
t^2/4 & t\ge0,\\-t^2/4 & t<0, \end{cases}
$$
is a solution. But for any $\tau\in(-1,0)$, the function
$$
y_\tau(t)=\begin{cases}
t^2/4 & t\ge0,\\0 & \tau<t<0\\-(t-\tau)^2/4 & t<\tau, \end{cases}
$$
is also a solution. Below is the graph of $y_{-1/2}$.

By the way, the set of solutions is not a vector space.


text:
\begin{document}
Graph matrices are a type of matrix which appears naturally when analyzing the sum of squares hierarchy and other methods which analyze higher moments. In the paper ``Graph Matrices: Norm Bounds and Applications'' \cite{AMP20}, Ahn, Medarametla, and Potechin proved rough norm bounds on all graph matrices and described several applications of graph matrices in analyzing random subspaces and analyzing tensor decomposition. However, beyond these rough norm bounds, little is known about graph matrices.

A natural question is whether we can analyze graph matrices more carefully. Can we make the norm bounds on graph matrices tight up to a factor of $(1 \pm o(1))$ rather than $\polylog(n)$? More ambitiously, can we determine the spectrum of graph matrices? In other words, can we find analogues of Wigner's semicircle law \cite{wigner1958distribution,wigner1993characteristic} and Girko's Circular Law \cite{girko} for graph matrices?

In this paper, we take a step towards this goal by analyzing the spectrum of the singular values of Z-shaped and multi-Z-shaped graph matrices.

\subsection{Definitions}
In order to state our results, we need a few definitions.

\begin{defn}[Fourier Characters]
Given a graph $G=\(V(G),E(G)\)$ and a multi-set of possible edges $\displaystyle{E \subseteq {V(G)\choose 2}}$, define $\chi_{E}(G) = \prod_{e \in E} e(G)$ where the \textit{edge variable} $e(G)$ is $e(G)=1$ if $e \in E(G)$ and $-1$ otherwise.
\end{defn}

\begin{defn}[Shapes]
We define a \emph{shape} $\alpha$ to be a graph with vertices $V(\alpha)$, edges $E(\alpha)$, and distinguished tuples of vertices $U_{\alpha} = \(u_1,\ldots,u_{|U_{\alpha}|}\)$ and $V_{\alpha} = \(v_1,\ldots,v_{|V_{\alpha}|}\)$.
\end{defn}

\begin{defn}[Bipartite Shapes]
We say that a shape $\alpha$ is \emph{bipartite} if $U_{\alpha} \cap V_{\alpha} = \emptyset$, $V(\alpha) = U_{\alpha} \cup V_{\alpha}$, and all edges in $E(\alpha)$ are between $U_{\alpha}$ and $V_{\alpha}$.
\end{defn}

\begin{defn}[Graph Matrices]\label{defn:graph matrix}
Given a shape $\alpha$, we define the \emph{graph matrix} $M_{\alpha}$ (which depends on the input graph $G$) to be the $\frac{n!}{\(n-|U_{\alpha}|\)!}\times\frac{n!}{\(n-|V_{\alpha}|\)!}$ matrix with rows indexed by tuples of $|U_{\alpha}|$ distinct vertices, columns indexed by tuples of $|V_{\alpha}|$ distinct vertices, and entries
\begin{equation*}
    M_{\alpha}(A,B) = \sum_{\sigma: V(\alpha) \to V(G): \sigma \text{ is injective}, \atop \sigma(U_{\alpha}) = A, \sigma(V_{\alpha}) = B}{\chi_{\sigma(E(\alpha))}(G)}.
\end{equation*}
\end{defn}

\subsection{Our Results}
Our main result is determining the spectrum of the singular values of the Z-shaped graph matrix.
\begin{defn}\label{defn:z-shape}
    Let $\a_{Z}$ be the bipartite shape with vertices $V(\a_{Z})=\{u_1,u_2,v_1,v_2\}$ and edges $E(\a_{Z})=\left\{\{u_1,v_1\},\{u_2,v_1\},\{u_2,v_2\}\right\}$ with distinguished tuples of vertices $U_{\a_{Z}}=(u_1,u_2)$ and $V_{\a_{Z}}=(v_1,v_2)$. See Figure \ref{fig:graph H} for an illustration. We call $\a_{Z}$ the \emph{Z-shape}.
\end{defn}

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.35]{z-shape.png}
    \caption{Z-shape $\a_Z$}
    \label{fig:graph H}
\end{figure}

\begin{defn}
Let $a = \dfrac{3\sqrt{3}}{2}$ and define $g_{\alpha_Z}: (0,\infty) \to \mathbb{R}$ be the function such that
\begin{equation*}
g_{\alpha_Z}(x) = \dfrac{i}{\pi}\cdot \(\sqrt{3}\cdot \sin\(\dfrac{1}{3}\cdot\arctan\(\dfrac{3}{\sqrt{4x^2/3-9}}\)\)+ \cos\(\dfrac{1}{3}\cdot\arctan\(\dfrac{3}{\sqrt{4x^2/3-9}}\)\)\)
\end{equation*}
if $x \in (0,a]$ and $g_{\alpha_Z}(x) = 0$ if $x > a$. See Figure \ref{introspectrumfigure} for an illustration.
\end{defn}
    \begin{figure}[h]
      \centering
      \includegraphics[scale = 0.5]{Z-shape-spec.png}
      \caption{The limiting distribution of the singular values of $\frac{1}{n}M_{\alpha_Z}$ as $n \to \infty$}
      \label{introspectrumfigure}
    \end{figure}
\begin{thm}
As $n \to \infty$, the spectrum of the singular values of $\frac{1}{n}M_{\alpha_Z}$ approaches $g_{\alpha_Z}$.
\end{thm}
After proving this result, we apply our techniques to give a partial analysis of the spectrum of the singular values of multi-Z-shaped graph matrices.
\subsection{Paper Outline}
The remainder of the paper is organized as follows. In section 2, we describe the main techniques we use to prove our results. In section 3, we calculate the trace powers for the Z-shaped graph matrix. In section 4, we use these calculations to determine the limiting distribution of the singular values of $\frac{1}{n}M_{\alpha_Z}$ as $n$ goes to infinity. In section 5, we generalize the results in Section 3 to calculate the trace powers for multi-Z shaped graph matrices. In section 6, we use these calculations to determine a differential equation for the limiting distribution of the singular values of one multi-Z shaped graph matrix.
\end{document}

config: arxiv


TITLE: Supremum and Infimum using Archemedian Property
QUESTION [2 upvotes]: I'm having trouble understanding where the Archemedian Property can be applied when evaluating the supremum and infimum of a set S.
For example:
Suppose $S = \{\frac{1}{n} - \frac{1}{m} : n,m \in \mathbb N\} $ Find $sup(S)$ and $inf(S)$
I want to show that $sup(S) = 1$ and $inf(S) = - 1$
$sup(S) = 1 $ :
First note that $\frac{1}{n} - \frac{1}{m} \leq 1 - \frac{1}{m} < 1$
Then 1 is an upper bound for $\frac{1}{n} - \frac{1}{m}$.
At this point I believe I need to apply the Archemedian Property but I'm not sure how.
I think I need to use the corollary that states : For any arbitrary $\epsilon > 0$, there exists $n_\epsilon \in \mathbb{N}$ such that $ 0 < \frac{1}{n_\epsilon} <\epsilon $
Could anyone give me a hint?

REPLY [0 votes]: $N=\left\{\dfrac{1}{n} \mid n\in \mathbb{N}\right\}$
$(-M)=\left\{-\dfrac{1}{m} \mid m\in \mathbb{N}\right\}$
$(N-M)=\left\{\dfrac{1}{n}-\dfrac{1}{m} \mid n,m\in \mathbb{N}\right\}$
$\sup (N-M)=\sup N+\sup(-M)=\sup N-\inf M=1$
$\inf (N-M)=\inf N+\inf(-M)=\inf N-\sup M=-1$


TITLE: Does the earth's gravity affect horizontal movement?
QUESTION [0 upvotes]: In a frictionless environment, would the weight of an object affect how hard it is to move it horizontally? Since without friction, there is no horizontal force resisting your applied force, would the object be easy to move?
I am aware of inertia but don't see any reason for it to play a role considering there is no opposing force to your applied force.

REPLY [3 votes]: In an ideal frictionless environment on a massive body (such as Earth), no force would oppose horizontal motion. Things are never that ideal, but your point is taken. But inertia still affects how much something will accelerate for a given amount of force applied. This will, in turn, affect how fast it ends up moving. So, even the gentlest force will start the object moving, but the final velocity when you stop pushing is dependent on how massive it is.


TITLE: Proving $P[\{X_n ≤ x\} ∩ \{|X_n − X| < \epsilon\}] \leq P[X ≤ x + \epsilon]$
QUESTION [1 upvotes]: I'm studying Theorem 5.2.1 from Hogg, Craig Introduction to Mathematical Statistics 8th Edition. I'm adding a few intermediate steps to the proof for clarity and want to know if I'm doing it correctly. Thanks in advance!
My goal is to prove:
$P[\{X_n ≤ x\} ∩ \{|X_n − X| < \epsilon\}] \leq P[X ≤ x + \epsilon]$
where $X_n$ is a sequence of random variables.
My attempt:
$P[\{X_n ≤ x\} ∩ \{|X_n − X| < \epsilon\}]$
 $= P[\{X_n ≤ x\} \cap (\{X_n − X < \epsilon\} \cup \{X \lt X_n + \epsilon\} )]$
 $= P[(\{X_n ≤ x\} \cap (\{X_n − X < \epsilon\}) \cup (\{X_n ≤ x\} \cap \{X \lt X_n + \epsilon\})]$
 $\leq P[\{X_n ≤ x\} \cap \{X \lt X_n + \epsilon\}]$
 $=P[X \lt x + \epsilon]$
 $\leq P[X \leq x + \epsilon]$

REPLY [0 votes]: Note that
$$
X_n\leqslant x\implies X_n+\epsilon \leqslant x+\epsilon \implies X_n+|X-X_n|\leqslant x+\epsilon \implies X\leqslant x+\epsilon
$$
Now, as a probability measure is an increasing function, we have that
$$
\{X_n\leqslant x\}\subset \{X\leqslant x+\epsilon \}\implies P(X_n\leqslant x)\leqslant P(X\leqslant x+\epsilon )
$$
∎


TITLE: Prove that $2^n \ge n^3 \ \forall n\ge 1$
QUESTION [0 upvotes]: $$2^n \ge n^3  \ \forall n\ge 1$$
My effort:

Check the base case: $P(1): 2\ge1 \ \text{(true)}$
supposing that $P(n) \Rightarrow  P(n+1):$ $2^{n+1} \ge (n+1)^3$
I'll try the induction step:
$$2^{n+1} = 2^n \cdot 2 \ge 2n^3 = n^3 \cdot 2 \ge n^3 \cdot \frac{1}{(n+1)^3}$$
I'm not sure about the last step, but in any case, I can't find any way to get to $(n+1)^3$ and prove the induction step.

How can I do?

REPLY [5 votes]: You cannot prove that since it is false when $n=2$. It is true when $n\geqslant10$ though. Indeed, $2^{10}=1024>1000=10^3$, and, if $2^n\geqslant n^3$, then, as you have proved, $2^{n+1}\geqslant2n^3$. And $2n^3\geqslant(n+1)^3$, since$$2n^3\geqslant(n+1)^3\iff2\geqslant\left(1+\frac1n\right)^3,$$which is true, since $n\geqslant10$, and therefore$$\left(1+\frac1n\right)^3\leqslant\left(\frac{11}{10}\right)^2<2.$$


TITLE: successive doubling the stake until head appears
QUESTION [3 upvotes]: I consider the following gaming system: Start with 1 dollar and always bet on head (coin tossing). You always double your stake until the first head appears. Maximum rounds: $n$
I formulated it as a random walk: $S_n=\sum_{k=1}^{n}X_k$ with $\mathbb P(X_k=1)=\mathbb P(X_k=-1)=1/2$ and stopping time $T:=\min\{1\le k\le n : X_k=+1\}$
First I would like to rewrite $V_k$ (=stake in round $k$) with an indicator function as a function of the stopping time $T$, I would guess it is $2^T \mathbb {1}_{\{k\in T\}}$
In the second step I want to calculate the distribution of the gains $(V*S)_n=\sum_{k=1}^{n}V_k X_k$ of the gaming system: What is the probability to lose money?

REPLY [2 votes]: For every $k\geqslant 1$, the stake at round $k$ is $V_k=2^{k-1}\mathbf 1_{T\geqslant k}$. To wit, one bets at round $k$ if and only if $T\geqslant k$ and, if one bets, the bet is $2^{k-1}$.
The (algebraic) gain $G_n$ after round $n$ is $+1$ if $T\leqslant n$ and $-(2^n-1)$ if $T\gt n$. To wit, if $T\leqslant n$, one recovered all one's stakes $+1$ at time $T$ then one stopped betting, while if $T\gt n$, one lost $n$ times, betting $1$, $2$, $4$, ..., $2^{n-1}$, hence one lost a total of $2^n-1$. Thus, $G_n=1-2^n\mathbf 1_{T\gt n}=1-V_{n+1}$.
Since $[G_n\lt0]=[T\gt n]=[X_1=\cdots=X_n=-1]$ and the random variables $(X_k)$ are i.i.d., one loses money at time $n$ with probability $P[G_n\lt0]=P[X_1=-1]^n=(1/2)^n$.
Thus, the distribution of $G_n$ is characterized by $P[G_n=1]=1-(1/2)^n$ and $P[G_n=1-2^n]=(1/2)^n$.


TITLE: Are these two definitions of the Riemann mapping theorem equivalent?
QUESTION [0 upvotes]: I have two definitions of the Riemann mapping theorem
1.Suppose that $G$ is a simply connected domain in the complex plane, $G\neq \mathbb{C}$, and that $z_0$ is a point of $G$. There exists a unique conformal mapping f of $G$ onto the open unit disk $\mathbb{D}$ satisfying the conditions $f(z_0)=0$ and $f'(z_0)>0$.
2.$G$ is a non-empty simply connected Domain of the complex number plane $\mathbb{C}$ which is not all of $\mathbb{C}$, then there exists a biholomorphic mapping $f$ from $G$ onto the open unit disk $\mathbb{D}$.
Regarding that $conformal \Leftrightarrow biholomorphic$ it follows: $1 \Rightarrow 2$. Is $2 \Rightarrow 1$ also true ?

REPLY [2 votes]: The answer is yes.
So let $f: G\to \mathbb{D}$ be the biholomorphic map you're given. Let $w=f(z_0)$.
Then, $T_w(z)=\frac{z-w}{1-\overline{w}z}$ is a conformal equivalence of the unit disk onto itself mapping $w$ to $0$.
Hence, $g=\frac{1}{f'(z_0)T_w'(w))}T_w\circ f$ is a conformal equivalence with the desired property. This gives you existence.
Must it be unique?
Well, assume $g$ and $\tilde{g}$ are both biholomoprhic maps onto $\mathbb{D}$ mapping $z_0$ to $0$ and such that their derivatives at $z_0$ are positive. Assume without loss of generality that $g'(z_0)\geq \tilde{g}'(z_0)$. Then,
$$
(g\circ \tilde{g}^{-1})'(0)=\frac{g'(z_0)}{\tilde{g}'(z_0)}\geq 1
$$
but by the Schwarz lemma, $|(g\circ \tilde{g}^{-1})'(0)|\leq 1$ so, in fact it must be equal to 1. Thus, by the second part of the Schwarz lemma, $g\circ \tilde{g}^{-1}$ must be a rotation and, since it's derivative is positive, it must be the identity. Hence, $g=\tilde{g}$.


TITLE: What else is a neighbourhood?
QUESTION [1 upvotes]: I need to settle an argument.
Yes or no:
If $(X,\tau)$ is a topological space ($X$ is an arbitrary - and I mean arbitrary - set, $\tau\subseteq\mathcal P(X)$ is the collection of open sets), then a set $N$ is a neighbourhood of a point $x\in X$ iff there exists an open set $U\in\tau$ such that $x\in U$ and $U\subseteq N$.
In short: a neighbourhood is a superset of an open set.
If no, then what am I missing? My friend seems to think that there is something special about neighbourhoods that cannot be explained in such basic terms. I think that my friend is still holding onto the idea that "topology" means "metric topology."

REPLY [1 votes]: Your definition is certainly very common and well-established.
But some authors insist that a neighbourhood of $x$ is an open set that contains $x$. I usually call that "open neighbourhood" instead. IMO a less useful definition.
In a metric space $(X,d)$ (in the induced topology) your definition (which I also prefer, because it allows me to talk about closed and compact neighbourhoods as well, without being restricted by openness requirements) is just equivalent to saying that $N$ is a neighbourhood of $x$ iff there is some $r>0$ so that $B_d(x,r) \subseteq N$ and this is a very common first definition in many analysis courses, I believe. But a metric space is just a very special topological space anyway (maybe not as your friend sees it, but it is.). The metric definition is just a special case of the definition you gave.
As long as it's clear if you're working in a general (topological) space or a metric space, you and your friend will have no need to quarrel.


TITLE: If monotone decreasing and $\int_0^\infty f(x)dx <\infty$ then $\lim\limits_{x\to\infty} xf(x)=0.$
QUESTION [9 upvotes]: Let $f:\mathbb{R}_+ \to \mathbb{R}_+$ be a monotone decreasing function defined on the positive real numbers with $$\int_0^\infty f(x)dx <\infty.$$ Show that $$\lim_{x\to\infty} xf(x)=0.$$

This is my proof: Suppose not. Then there is $\varepsilon$  such that for any $M>0$ there exists $x\geq M$ such that $xf(x)\geq \varepsilon$. So we can construct a sequence $(x_n)$ such that $x_n \to \infty $ and $x_n f(x_n ) \geq \varepsilon$. So $$\frac{\varepsilon}{x_n}\leq f(x_n) \implies \sum_{n\in\mathbb{N}}\frac{\varepsilon}{x_n} \leq  \sum_{n\in\mathbb{N}} f(x_n) \leq \int_0^1 f(x)dx.$$ So we get a contradiction.  I feal like I have the correct idea but some details are wrong.  Any help would be appreciated.

REPLY [0 votes]: You can solve this using BCT. First, note that for the integral to exist, we must have
$$\lim_{x \rightarrow \infty} f(x) = 0$$
Now we know that the original limit is of indeterminate form. Now from here, since the improper integral converges, we know for sure that $f(x) < \frac{1}{x^a}$ where $a > 1$. This is by BCT since the improper integral of $\frac{1}{x}$ doesn't converge. Thus we know that $xf(x) < x(\frac{1}{x^a})$


TITLE: Find the kernel of a ring homomorphism $f(x)\to f(\sqrt 2)$
QUESTION [1 upvotes]: Let $$\phi:\mathbb Z[x]\longrightarrow \mathbb R$$, where $$\phi(f(x))=f(\sqrt 2)$$
find $$\operatorname{Ker}(\phi)=\{f(x)\in \mathbb Z[x]\mid f(\sqrt2)=0\}$$
1st) I wanted to use isomorphism theorem since we have $\mathbb R$-field so $Z[x]/\ker\phi\simeq \mathbb R$ so we find that $\ker\phi$ maximal ideal so it must be irreducible minimal polynomial which has root $\sqrt2$ that is $x^2-2$ but $\phi$ is not surjective.
2nd) Let $f=f_0+f_1x+f_2x^2+f_3x^3+f_4x^4+..$
since $\\f(\sqrt2)=0$ we have $$\\f_0+2f_2+4f_4+8f_6+...=0\\ f_1+2f_3+4f_5+...=0$$but how to show $x^2-2\mid f(x)$

REPLY [3 votes]: $\newcommand\Ker{\operatorname{Ker}}$First note that $x^2-2\in\Ker\varphi$.
Conversely, if $f\in\Ker\varphi$, write $f(x)=(x^2-2)q(x)+r(x)$ with $r(x)=0$ or $\deg r(x)<2$.
Since $f(\sqrt 2)=0$ you get $r(\sqrt 2)=0$, but since $\sqrt 2$ is irrational and $\deg r<2$ we get $r=0$.
This proves $(x^2-2)|f(x)$.
Consequently, $\Ker\varphi=(x^2-2)\Bbb Z[x]$.

REPLY [1 votes]: Let $p(x) \in \ker(\varphi)$. Since $x^2-2$ is a monic polynomial, we use the division in $\Bbb{Z}[x]$ to write
$$p(x)=(x^2-2)q(x)+(ax+b), \qquad \text{ where } a,b \in \Bbb{Z}.$$
Now $\varphi(p(x))=0$ implies that $\varphi(ax+b)=a\sqrt{2}+b=0$. If $a,b \neq 0$, then this is a contradiction because this would imply that $\sqrt{2} \in \Bbb{Q}$. Thus $p(x)=(x^2-2)q(x)$.

REPLY [1 votes]: The first isomorphism theorem tells you that $\Bbb{Z}[x]/\ker\phi\cong\operatorname{im}\phi$. This is not isomorphic to $\Bbb{R}$, because as you say $\phi$ is not surjective. The rest of your argument is on the right track, though.
What is true is that $\operatorname{im}\phi$ is isomorphic to a subring of $\Bbb{R}$, so in particular it is an integral domain. This means $\ker\phi\subset\Bbb{Z}[x]$ is a prime ideal (note that it is not maximal), and so $\ker\phi$ contains an irreducible polynomial.
There are still a lot of details missing from your solution; why does $\ker\phi$ contain an irreducible polynomial? Why is $\ker\phi$ generated by this irreducible polynomial? And why must it be $x^2-2$? Most of these are simple details to mention, but depending on the context, should be mentioned.


TITLE: Is gravitational force affected by intervening medium?
QUESTION [1 upvotes]: If we leave a iron ball and feather into the water, feather returns to the surface and floats or moves into the water slowly. On the other hand, iron ball (of certain mass greater than mass of feather) moves into the water directly. Here, both iron ball and feather are accelerated towards the earth to the same extent. Then why does feather moves slowly into the water than iron ball? Shouldn't they reach the earth at the same time.
If we assume that water medium is making the feather to accelerate to lesser extent than iron ball, then doesn't it mean gravitational force is affected by intervening medium?
Similarly if we consider a feather and iron ball to be left from certain height, I hope iron ball reaches the earth first and then feather. The reason I think is because of air resistance, doesn't this mean air medium or intervening medium is affecting gravitational force?
We know that gravitational force is not affected by intervening medium, but it is contrary to the above situations. Is it that gravitational force is affected by intervening medium?
I might have misunderstood sometimes, if so, pardon me and explain.

REPLY [0 votes]: Let's use a spring scale in water s.t the spring scale is sealed in a air tight glass box containing only vacuum so as to remove the buoyancy. Putting both the feather and the iron ball of same masses on the scale we notice that the spring shows the same reading(say $a_0$) for both feather and iron ball. Hence the gravitational force on both the feather and iron are same.
Now let's repeat this experiment by putting the spring scale enclosed in the box in the air(or oil or some other material). We notice that the spring scale again gives the reading $a_0$ for both feather and iron ball.
Hence we conclude that the medium does not affect gravitational force.


TITLE: How does radiation from a nuclear accident "infect" clothing and people?
QUESTION [0 upvotes]: In the mini series "Chernobyl" first responders who were exposed to radiation at the scene had to be quarantined.  Why?  My understanding is that when Uranium 235 fissions it releases nuetrons and gamma energy.  The gamma enery can penetrate the skin and 'ionize' compounds in our bodies (bad) as well as break checmical bonds in our dna (also, bad and maybe not a different thing).  So that explains why direct exposure is bad, but what is the mechanism for them continuing to be dangerous to others around them?  Is fissioning Uranium somehow in their body?

REPLY [0 votes]: Used nuclear fuel contains fission products like cesium-137 and iodine-131. When that escapes from the core of the reactor surfaces, clothes, food, dust etc will get "contaminated" with radioactive isotopes. People will ingest and inhale these. Unhealthy.
But there is no infection. After a shower and clean clothes, such people are not a danger to others. However, it seems that people from Hiroshima and Fukushima were shunned like bearers of contagious diseases. Very strange, but possibly due to unfortunate jargon like "contamination".


TITLE: Minoration of an expectation
QUESTION [1 upvotes]: I'm working on the next exercise, it's an excerpt from an Oral HEC
$X$ is a random variable defined on a probabilistic space $(Ω, A, P)$ that follows the uniform law on $[a, b]$
with $1≤a <b$     prove that   $E(X+\frac{1}{X})\ge a+\dfrac{1}{a}$
to show that :
$E(X+\frac{1}{X}) \ge a+\dfrac{1}{a}$
Indeed
$$E\left(X+\frac{1}{X}\right)= \int_a^b \left(x+\frac{1}{x}\right)\left(\frac{1}{b-a}\right)\,dx = \frac{a+b}2 + \frac{\ln(b)-\ln(a)}{b-a}$$
as $(a+b)/2 >a$  a and $\frac{\ln (b) -\ln (a)}{b-a} = 1 / c$ by the theorem of finite increments
it is larger than $a$, so $1/c$ is smaller than $a.$ I get an inequality that is not in the right direction there may be another way to achieve good inequality.

REPLY [2 votes]: Define $f(x):=x+1/x$. Then $f'(x)=1-1/x^2$. So on $[a,b]$ with $a\geq 1$, $f$ is monotonically increasing, hence $f\geq f(a)=a+1/a$. It follows that $E[X+1/X]\geq E[a+1/a]=a+1/a$.


TITLE: Why is this process a certain density process?
QUESTION [4 upvotes]: We are given a stochastic process $X$ and denote by $\mathbb{P}$ the set of all equivalent local martingale measure, that is the set of all equivalent measures $Q\approx P$, such that $X$ is a local $Q$ martingale. We can assume $\mathbb{P}\not=\emptyset$ and $\mathcal{F}_0$ is trivial.
For $t\in \mathbb{R}_+$, $Q\in\mathbb{P} $ let $$A_t:=\{Z|Z \mbox{ is a density process with respect to } Q \mbox{ of some }R\in\mathbb{P}, Z_s=1,s\le t\}$$ Suppose we have $Z^1,Z^2\in A_t$ given and a set $F\in\mathcal{F}_t$. We define $Z^3:=\mathbf1_FZ^1+\mathbf1_{F^c}Z^2$. The claim is, that $Z^3$ is again an element of $A_t$. Clearly $Z^3_s=1$ for $s\le t$. However I'm unsure with other properties. How can I define such a $R$ with the desired properties?
$\mathbf{motivation:}$ The question arises when studying the so called hedging duality in mathemtical finance. There $X$ is a semimartingale and should model a risky asset. For a $H\in L_+^0(\mathcal{F}_T)$ we want to study the process
$$Y_t:=\underset{Q \in \mathbb{P}}{\text{esssup}} \  E_Q \left[ H | \mathcal{F}_t \right]$$
and prove that $(Y_t)$ is a supermartingale for every $Q\in\mathbb{P}$. The question is a part of the proof of this statement.

REPLY [1 votes]: Let $Z$ in $A_t$ denote the density process with respect to $Q$ of some $R$ in $\mathbb P$. Let $G$ and $H$ in $\mathcal F_t$. Assume to simplify things that $X$ is a martingale for $Q$ and $R$ (and not only a local martingale).
Let $s\geqslant t$.
Then, $E^Q[X_sZ_s\mathbf 1_G\mid\mathcal F_t]=\mathbf 1_GE^Q[X_sZ_s\mid\mathcal F_t]$. Furthermore,
$$E^Q[X_sZ_s\mathbf 1_H]=E^R[X_s\mathbf 1_H]=E^R[E^R[X_s\mid \mathcal F_t]\mathbf 1_H]=E^R[X_t\mathbf 1_H]=E^Q[X_tZ_t\mathbf 1_H].
$$
This holds for every $H$ in $\mathcal F_t$  hence $E^Q[X_sZ_s\mid\mathcal F_t]=X_tZ_t$ and finally,
$$
E^Q[X_sZ_s\mathbf 1_G\mid\mathcal F_t]=\mathbf 1_GX_tZ_t.
$$
Applying this to $(G,Z)=(F,Z^1)$ and to $(G,Z)=(F^c,Z^2)$ for $Z^1$ and $Z^2$ in $A_t$ and summing the results, one sees that $Z^3=Z^1\mathbf 1_F+Z^2\mathbf 1_{F^c}$ is such that $E^Q[X_sZ^3_s\mid\mathcal F_t]=X_tZ^3_t$ for every $s\geqslant t$, hence $Z^3$ is in $A_t$.


TITLE: Position operator explicit form & definition
QUESTION [0 upvotes]: I've got a question regarding the position operator.
As far as I learned it, the position operator simply gets defined by saying:
$\hat{x} \ \psi(x,t) = x \ \psi(x,t)$
And I also learned that the momentum representation of the position operator is defined as ($p,k$ used interchangeably):
$(\hat{x})_p = i \frac{\partial}{\partial k}$
I'm a bit confused about that. Why is this the "momentum" representation? Let's say I have a plane wave
$\psi(x,t)=e^{i(kx-\omega t)}$
If I wanted to define the position operator, I would just do it like that:
$\hat{x} e^{i(kx-\omega t)} = -i \frac{\partial}{\partial k} e^{i(kx-\omega t)} = x e^{i(kx-\omega t)}$
So why does this look like the momentum representation of the position operator (except for the sign)?
I was just wondering since I never learned the "explicit form" of the position operator. I just learned what it does, namely:
$\hat{x} \ \psi(x,t) = x \ \psi(x,t)$
But my question is, what does $\hat{x} = \cdots$ look like specifically? Does the explicit form of $\hat{x} = \cdots$ depend on the function I'm using it on?

REPLY [5 votes]: Let us first clarify that things like $\hat{x}\,\psi(x)$ in fact mean
$$ (\hat{x}\psi)(x) \equiv \langle x| \hat{x} |\psi\rangle \quad .$$
We further define the wave function as
$$ \psi(x) \equiv \langle x|\psi\rangle \quad. $$
Similar equations hold for the case of the momentum operator / basis.
In the following we set $\hbar=1$.

The position representation of the position and momentum operator is (very nicely explained here):
\begin{align}
\langle x|\hat{x} &= \langle x| \,x \\
\langle x| \hat{p}  &= - i \,\frac{\mathrm{d}}{\mathrm{d}x} \langle x| \quad .
\end{align}
This should look familiar to you: Evaluated in the position basis, the position operator acts as a multiplicative operator while the momentum operator acts as a derivative. Using the conventions from the beginning we then find
\begin{align}
(\hat{x}\psi)(x) &= x\, \psi(x) \\
(\hat{p}\psi)(x) &= - i \,\frac{\mathrm{d}}{\mathrm{d}x} \psi(x) \quad ,
\end{align}
which means for example that the projection of the vector $\hat{x}|\psi\rangle$ onto a state of the position basis is the number $ x\, \psi(x)$.
However, this does not mean that the momentum operator is a derivative; in the same sense, the position operator is not an operator multiplying 'everything' it acts on with $x$. Indeed, evaluated in the momentum basis, we find that the momentum operator is multiplicative and the position operator acts as a derivative:
\begin{align}
\langle p | \hat{x} &= i\, \frac{\mathrm{d}}{\mathrm{d}p} \langle p|\\
 \langle p | \hat{p } &=   \langle p |\,p \quad .
\end{align}
See also this question and the links therein. This tells us that e.g. the projection of the vector $\hat{x}|\psi\rangle$ onto an element of the momentum basis is the number $i\, \frac{\mathrm{d}}{\mathrm{d}p} \psi(p)$.
Finally, by making use of the completeness relations $\displaystyle \mathbb I = \int \mathrm dx \, |x\rangle \langle x| = \int \mathrm dp \, |p\rangle\langle p|$, we can express the action of the position operator $\hat{x}$ on a state $|\psi\rangle$ either as
$$ \hat{x}|\psi\rangle = \int \mathrm{d}x\, x\, |x\rangle \langle x|\psi\rangle$$
or
$$\hat{x}|\psi\rangle = i\,\int \mathrm{d}p \, |p\rangle \frac{\mathrm{d}}{\mathrm{d}p}\langle p|\psi\rangle \quad .$$

Regarding your example: We know that $\langle x |p\rangle = e^{ipx}$ (up to some constant factor which I'll omit) and let's say we want to calculate $ \langle x |\hat{x}|p\rangle$, which is I think you meant by $\hat{x}\, e^{ipx}$.
Using the position representation of the position operator, we easily find
$$\langle x |\hat{x}|p\rangle  = x \, \langle x|p\rangle = x \,e^{ipx} \quad . $$
Performing the calculation within the momentum representation of the position operator yields:
$$\langle x |\hat{x}|p\rangle  = \left({\langle p |\hat{x}^\dagger|x\rangle }\right)^* = \left({\langle p |\hat{x}|x\rangle }\right)^* = \left(i \frac{\mathrm{d}}{\mathrm{d}p} e^{-ipx}\right)^* = x \, e^{ipx} \quad ,$$
as expected.


TITLE: How many directed graphs with N nodes contain a given directed cycle of length L?
QUESTION [1 upvotes]: Given a directed graph $C$ that only contains a directed cycle of length $L$ (and all resulting sub-cycles), that visits each node at least once,
$$C=(V, D)$$
where $V$ is a fixed set of vertices and $D$ is a set of directed edges, and:
$$|V| = N$$
$$|D| = L$$
$$ 1 \leq \deg^+(v) \leq 2,  v \in V$$
How many directed graphs $G=(V,E)$, where $E$ is a set of directed edges and,
$$ \deg^+(v) = 2,  v \in V$$
contain $C$? I am not considering $G$ that contains a graph isomorphic to $C$, I am only interested in $G$ that contain exactly $C$.
That is, if F is the set of all G that contain exactly C as a subgraph, and
$$ n = |F| $$
what is n?

REPLY [1 votes]: Let $a_0,a_1,a_2$ be the vertices with out-degree $0,1,2$ in $C$; so $a_0+a_1+a_2=N$. Following David's advice, it seems that since you're (for now) ignoring the in-degree, the number of graphs is exactly
$$ \binom{N+1}{2}^{a_0} N^{a_1}. $$
Now according to your (current) spec, in fact $a_0 = 0$, and moreover $a_1 + 2a_2 = L$. Since $a_2 = N-a_1$, we get that $a_1 + 2(N-a_1) = L$ and so $a_1 = 2N-L$. Therefore
$$ n = N^{2N-L}. $$


text:
\begin{document}

\begin{abstract}
Let $G$ be a connected semisimple Lie group with finite center and without compact factors, $P$ a minimal parabolic subgroup of $G$,
and $\Gamma$ a lattice in $G$. We prove that every $\Gamma$-orbits in the Furstenberg boundary $G/P$
is equidistributed for the averages over Riemannian balls. The proof is based on the proximality of the action of $\Gamma$ on $G/P$.
\end{abstract}

\maketitle

\section{Introduction}

Let $G$ be a connected semisimple Lie group with finite center and without compact factor, and $\Gamma$ a lattice in $G$,
that is, a discrete subgroup of $G$ such that $\Gamma\backslash G$ has finite volume.
In this article we investigate the distribution of orbits of $\Gamma$ acting
on the Furstenberg boundary of $G$. Recall that the Furstenberg boundary can
be identified with the factor space $G/P$, where $P$ is a minimal parabolic subgroup of $G$.
It is known that every orbit of $\Gamma$ in $G/P$ is dense (see \cite{most}).
We show that orbits of $\Gamma$ are equidistributed with respect to the averages over Riemannian balls.

Since we study the action of a nonamenable group on a space without a finite invariant measure,
our result lies outside the scope of the classical ergodic theory.
The published results about distribution of dense orbits of nonamenable groups are limited to a few special examples.
Arnold and Krylov showed in \cite{ak} that dense orbits of groups generated by two rotations acting
on the $2$-dimensional sphere are equidistributed.
A similar problem was considered by Kazhdan in \cite{ka} where he studied the action of a group
generated by two affine isometries on the plane $\mathbb{R}^2$.
Distribution of dense orbits of a lattice in $\hbox{\rm SL}(2,\mathbb{R})$
acting on $\mathbb{R}^2$ was investigated by Ledrappier \cite{l} and Nogueira \cite{no}.

Let $X$ be the symmetric space of $G$ equipped with a right invariant Riemannian metric $d$.
Note that $X$ can be identified with $L\backslash G$ for a maximal compact subgroup $L$ of $G$.

Fix $x,\tilde x\in X$ and denote by $K$ and $\tilde K$ the stabilizers of $x$ and $\tilde x$ respectively. Let $\nu$ and $\tilde\nu$ be the probability Haar measures on $K$ and $\tilde K$
and $m_{\tilde x}$ the harmonic measures at $\tilde x$ on $G/P$, that is, the unique $\tilde{K}$-invariant
probability measure on $G/P$.

For $S\subset G$ and  $T>0$, define
\begin{eqnarray*}
S_T(\tilde x)&=&\{s\in S: d(x,\tilde xs)<T\},\\
S_T&=& S_T(x).
\end{eqnarray*}

Our main result is the following theorem.

\begin{thm}\label{th_main}
For every $f\in C(G/P)$, $\tilde x\in X$, and $y\in G/P$,
$$
\lim_{T\to\infty}\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma y)= \int_{G/P} f dm_{\tilde x},
$$
Moreover, the convergence is uniform for $y\in G/P$.
\end{thm}

We remark that it was shown in \cite{em} (see also \cite{drs}) that
\begin{equation}\label{eq_eskin}
|\Gamma_T(\tilde x)|\sim_{T\to\infty} \frac{\textrm{Vol}(G_T(\tilde x))}
{\textrm{Vol}(\Gamma\backslash G)},
\end{equation}
and the exact asymptotics of the volume $\textrm{Vol}(G_T(\tilde x))=\textrm{Vol}(G_T)$ as $T\to\infty$
was computed in \cite{kni}.

The first result in the direction of Theorem \ref{th_main} was established in \cite{mau},
where the case of the real hyperbolic spaces was considered.
A different proof of Theorem \ref{th_main} is given in \cite{g_o}.
An advantage of the approach presented here is that it shows that the convergence is uniform.
While the proof in \cite{g_o} uses equidistribution of solvable flows on $\Gamma\backslash G$,
our proof is based on the strong proximality of the action of $G$ on $G/P$
(see Theorem \ref{th_proxy} below). This result is of independent interest, and
it might be useful for other applications.

Recall that an action of a group $H$ on a compact metric space $(Y,d)$ is called {\it proximal} if
for every $u,v\in Y$ there exists a sequence $\{h_n\}\subset H$ such that
$d(h_nu,h_nv)\to 0$ as $n\to\infty$. The fact that the action of $G$ on $G/P$ is proximal plays
important role in the study of random walks on $G$ (see, for example, \cite{furst}). It turns out that a typical sequence in $G$ acts on $G/P$ in proximal fashion.

\begin{thm}[\bf Strong proximality]\label{th_proxy}
Let $\mathcal{O}$ be neighborhood of the diagonal in $G/P\times G/P$ and $u,v\in G/P$. Then
$$
\lim_{T\to\infty}\frac{\hbox{\rm Vol}(\{g\in G_T(\tilde x): (gu,gv)\notin \mathcal{O}\})}{\hbox{\rm Vol}(G_T(\tilde x))}= 0
$$
and
$$
\lim_{T\to\infty}\frac{|\{\gamma\in \Gamma_T(\tilde x): (\gamma u,\gamma v)\notin \mathcal{O}\}|}{|\Gamma_T(\tilde x)|}= 0
$$
uniformly on $u,v$.
\end{thm}

In the case of the real hyperbolic space, Theorem \ref{th_proxy} was proved in \cite{mau}
using geometric methods.

\section{Proof of Theorem \ref{th_proxy}}

\subsection{Cartan decomposition}
Let $G=K_0\exp(\mathfrak{p})$ be the Cartan decomposition of $G$ and $A\subset \exp(\mathfrak{p})$
a split Cartan subgroup of $G$, that is, a maximal connected abelian subgroup in $\exp(\mathfrak{p})$.
We fix a system of positive roots $\Sigma^+$ on $\mathfrak{a}=\hbox{Lie}(A)$, and let
$$
A^+=\{a\in A: \alpha(\log a)\ge 0\hbox{ for all }\alpha\in\Sigma^+\}
$$
denote the closed positive Weyl chamber in $A$. Then $G=KA^+K$, and
a Haar measure on $G$ can be given by
\begin{equation}\label{eq_cartan}
\int_{G}\psi(g)dg=\int_{K}\int_{A^+}\int_{K} \psi(k_1ak_2)\xi(\log a)d\nu(k_1)dad\nu(k_2),\quad \psi\in C_c(G),
\end{equation}
where $da$ denotes the Lebesgue measure on $A$,
$$
\xi(s)=\prod_{\alpha\in\Sigma^+} \sinh(\alpha(s))^{m_\alpha},\;\;\; s\in\mathfrak{a},
$$
and $m_\alpha$ denotes the dimension of the root space for the root $\alpha\in\Sigma^+$.

Let $\tilde g\in G$ be such that $x\tilde g=\tilde x$. Then $G=\tilde g^{-1} KA^+K$, $G_T(\tilde x)=\tilde g^{-1} KA^+_TK$, and
\begin{equation}\label{eq_cartan2}
\int_{G}\psi(g)dg=\int_{K}\int_{A^+}\int_{K} \psi(\tilde g^{-1}k_1ak_2)\xi(\log a)d\nu(k_1)dad\nu(k_2),\quad \psi\in C_c(G).
\end{equation}
In particular, it follows that
\begin{equation}\label{eq_gt}
\hbox{Vol}(G_T(\tilde x))=\hbox{Vol}(G_T)=\int_{A^+_T} \xi(\log a)da.
\end{equation}

\subsection{Reduction to maximal parabolics}
Fix a system of simple roots $$\Pi=\{\alpha_1,\ldots,\alpha_r\}\subset\Sigma^+.$$
Here $r=\dim A$ is the $\mathbb{R}$-rank of $G$.
It is well-known that the closed subgroups of $G$ that contain $P$ are in
one-to-one correspondence with the subsets of $\Pi$ (see \cite[Sec.~1.2]{wa}). In particular, $P_i=P_{\{\alpha_i\}}$, $i=1,\ldots,r$,
are the maximal parabolic subgroups of $G$ and $$P=\bigcap_{i=1}^r P_i.$$
We consider the projection maps
$$\pi_i : G/P\times G/P \rightarrow G/P_i\times G/P_i,\quad i=1,\ldots,r.$$
Let $\Delta$ and $\Delta_i$ denote the diagonals in $G/P\times G/P$ and $G/P_i\times G/P_i$ respectively.
Then $$\Delta=\bigcap_{i=1}^r \pi_i^{-1}(\Delta_i).$$ Since
$$\prod_{i=1}^r\pi_i :\; G/P\times G/P \rightarrow \prod_{i=1}^r G/P_i\times G/P_i$$
is a continuous injective map from a compact space to a Hausdorff space, it is a homeomorphism onto its image.
It follows that for any neighborhood $\mathcal{O}$ of $\Delta$ in $G/P\times G/P$, there exist
neighborhoods $\mathcal{O}_i$ of $\Delta_i$ in $G/P_i\times G/P_i$ such that
$$
\mathcal{O}\supset \bigcap_{i=1}^r \pi_i^{-1}(\mathcal{O}_i).
$$
Then for every $(u,v)\in G/P\times G/P$,
$$
\{g\in G: g\cdot (u,v)\notin\mathcal{O}\}\subset \bigcup_{i=1}^r \{g\in G: g\cdot \pi_i(u,v)\notin\mathcal{O}_i\}.
$$
This inclusion shows that it suffices to prove Theorem \ref{th_proxy} under the assumption
that $P$ is a maximal parabolic subgroup of $G$. We keep this assumption until the end of this section.

\subsection{Dynamics on projective space}
By a result from \cite{Tits}, there is an irreducible representation $G\to\hbox{GL}(V)$ such that
the highest weight space is one-dimensional, and the stabilizer of this space is $P$.
We consider the induced action of $G$ on the projective space $\mathbb{P}(V)$, and let $w^+\in \mathbb{P}(V)$
be the direction of the highest weight space. The map $g\mapsto gw^+$ defines an embedding of $G/P$ in $\mathbb{P}(V)$.
Note that if $\lambda$ is the highest weight, the other weights of the representation are of the form
$\lambda-\sum_{\alpha\in\Sigma^+} n_\alpha \alpha$ for integers $n_\alpha\ge 0$.
We denote by $V^<$ the sum of all root spaces with weights other than $\lambda$.
We fix a $K$-invariant scalar product on $V$,  which gives rise to a metric $d$ on $\mathbb{P}(V)$, which is $K$-invariant. Put $\tilde d(w_1,w_2)= d(\tilde gw_1,\tilde gw_2)$.
Let $V^<_\varepsilon$ be the open $\varepsilon$-neighborhood of $V^<$ in $\mathbb{P}(V)$ with respect to the
metric $\tilde d$.

For $w \in  \mathbb{P}(V)$ and $\tau>0$, define
$$
K_{\tau}(w)=\{ k \in K : kw \notin V^<_\tau\}.
$$
   \begin{lem}\label{l_k_e}
   For every $w\in G\cdot w^+$,
   $$\lim_{\tau \rightarrow 0^+} \nu(K-K_{\tau}(w)) =0.$$
   \end{lem}
   \begin{proof}
   It follows from the Iwasawa decomposition that $G\cdot w^+=K\cdot w^+$.
   Thus, without loss  of generality, we may assume that $w=w^+$.
   By the continuity of the measure, it suffices to prove that
   $$
   \nu(\{k\in K: kw^+\in V^<\})=0.
   $$
   Suppose that this is false. For a subspace $W$ of $V$, define
   $$
   K_W=\{k\in K: kw^+\in W\}.
   $$
   Let $W$ be a minimal subspace of $V^<$ such that $\nu(K_W)>0$. We claim that $\hbox{Stab}_{K}(W)=K$.
   If $\hbox{Stab}_{K}(W)$ has infinite index in $K$, then there exist $k_i\in K$, $i\ge 1$, such that
   $k_iW\ne k_j W$ for $i\ne j$. Since all sets $k_iK_W\subset K$, $i\ge 1$, have the same positive measure,
   it follows that for some $i\ne j$, $k_iK_W\cap k_jK_W$ has positive measure.
   Then $k_j^{-1}k_iK_W\cap K_W$ has positive measure too, and for $k\in k_j^{-1}k_iK_W\cap K_W$, $$kw^+\in k_j^{-1}k_iW\cap W.$$
   Since $k_j^{-1}k_iW\cap W$ is a proper subspace of $W$, this contradicts the choice of $W$. Thus,
   $\hbox{Stab}_{K}(W)$ is a closed subgroup of finite index in $K$. Since $K$ is connected,
   it follows that $K=\hbox{Stab}_{K}(W)$. Then $w^+\in K_W^{-1}W\subset V^<$. This contradiction proves the lemma.
    \end{proof}

 We consider the sets
 \begin{eqnarray}
 A_T^\eta&=&\{a\in A_T: \alpha(\log a)\ge \eta\hbox{ for all }\alpha\in\Sigma^+\},\nonumber\\
 G_{T,\varepsilon}(u,v)&=&\{g \in G_T(\tilde x) : \tilde d(gu,gv)>\varepsilon\},\label{eq_ate}\\
 \Omega^\eta_{T,\tau}(u,v)&=&\tilde g^{-1}K A^\eta_{T} (K_{\tau}(u)\cap K_{\tau}(v))\nonumber
 \end{eqnarray}
 defined for $T,\eta,\tau,\varepsilon>0$ and $u,v\in\mathbb{P}(V)$.

   \begin{lem}\label{l_last}
   For every $\varepsilon>0$ and $\tau>0$, there exists $\eta>0$ such that for every $T>0$
     and $u,v \in G\cdot w^+$,
     \begin{equation}\label{eq_empty}
     \Omega^\eta_{T,\tau}(u,v) \cap G_{T,\varepsilon}(u,v) = \emptyset.
     \end{equation}
   \end{lem}
   \begin{proof}
     Note that an element $a \in A^\eta_{T}$ acts by diagonal transformations
     on $V$ with respect to some fixed basis, and the eigenvalue associated to the vector $w^+$
     is at least $e^\eta$ times greater than the other eigenvalues. Therefore, for all $w\notin V_\tau^<$ and
     sufficiently large $\eta$ (depending only on $\tau$ and $\varepsilon$), we have $d(aw,w^+)<\varepsilon/2$ when $a \in A^\eta_{T}$.
     Thus, for
     $$\tilde g^{-1}k_1 a k_2 \in \Omega^\eta_{T, \tau}(u,v)=\tilde g^{-1}K A^\eta_{T} (K_{\tau}(u)\cap K_{\tau}(v)),$$
     we have
     $$\tilde d(\tilde g^{-1} k_1a k_2 u,\tilde g^{-1} k_1a k_2 v)=d(a k_2 u, a k_2v)\leq d(a k_2 u ,w^+)+d(a k_2 v ,w^+)<\varepsilon,$$
     This proves the lemma.
   \end{proof}

\subsection{Completion of the proof}
By (\ref{eq_cartan2}),
\begin{equation}\label{eq_Ht}
\hbox{Vol}(\Omega^\eta_{T,\tau}(u,v))=\left(\int_{A^\eta_{T}}\xi (\log a) da\right)\cdot \nu(K_{\tau}(u)\cap K_{\tau}(v)).
\end{equation}
Let $\varepsilon,\delta\in (0,1)$. Using Lemma \ref{l_k_e}, we choose $\tau>0$ such that
$$
\nu(K_{\tau}(u)\cap K_{\tau}(v))> 1-\delta.
$$
Let $\eta>0$ be as Lemma \ref{l_last}. By Lemma \ref{l_a_eta}(a), for sufficiently large $T$,
$$
\int_{A^\eta_{T}}\xi (a) da\ge (1-\delta) \int_{A^+_{T}}\xi (\log a) da.
$$
Thus, it follows from (\ref{eq_gt}) and (\ref{eq_Ht}) that
$$
\hbox{Vol}(\Omega^\eta_{T,\tau}(u,v))\ge (1-\delta)^2\hbox{Vol}(G_T(\tilde x)).
$$
for sufficiently large $T>0$. Therefore, by (\ref{eq_empty}),
$$
\hbox{Vol}(G_{T,\varepsilon}(u,v))\le (1-(1-\delta)^2)\hbox{Vol}(G_T(\tilde x))
$$
for all $\delta \in (0,1)$ and sufficiently large $T>0$.
Since the sets $$\{(g_1P,g_2P): \tilde d(g_1w^+,g_2w^+)<\varepsilon\},\quad \varepsilon >0,$$ form a base of
the neighborhoods of the diagonal in $G/P\times G/P$,
this proves the first part of Theorem \ref{th_proxy}.

To prove the second part of Theorem \ref{th_proxy}, we choose a neighborhood $\mathcal{P}$
of $e$ in $G$ and a neighborhood $\mathcal{Q}$ of the diagonal in $G/P\times G/P$ such that
\begin{eqnarray}
\mathcal{P}^{-1}\mathcal{P}\cap \Gamma&=&\{e\},\label{eq_1}\\
\mathcal{P}^{-1}\cdot\mathcal{Q}&\subset& \mathcal{O},\label{eq_2}\\
\mathcal{P}\cdot G_T(\tilde x)&\subset& G_{T+c}(\tilde x).\label{eq_3}
\end{eqnarray}
for fixed $c>0$ and all $T>0$.
Here we use that $\Gamma$ is discrete, the space $G/P$ is compact, and the metric
on the symmetric space is uniformly continuous.
By (\ref{eq_2}), for every $\gamma\in\Gamma$ such that $\gamma\cdot (u, v)\notin \mathcal{O}$,
we have $\mathcal{P}\gamma\cdot (u,v)\cap \mathcal{Q}=\emptyset$.
Thus, using (\ref{eq_3}), we deduce that
$$
\mathcal{P}\cdot \{\gamma\in\Gamma_T(\tilde x):\gamma\cdot (u, v)\notin \mathcal{O}\}
\subset \{g\in G_{T+c}(\tilde x): g\cdot (u, v)\notin \mathcal{Q}\}.
$$
Then by (\ref{eq_1}), $\mathcal{P}\gamma_1\cap \mathcal{P}\gamma_2=\emptyset$ for $\gamma_1,\gamma_2\in\Gamma$, $\gamma_1\ne \gamma_2$, and
\begin{eqnarray*}
|\{\gamma\in\Gamma_T(\tilde x):\gamma\cdot (u, v)\notin \mathcal{O}\}|&\le&
\frac{1}{\hbox{Vol}(\mathcal{P})}\hbox{Vol}(\{g\in G_{T+c}(\tilde x): g\cdot (u, v)\notin \mathcal{Q}\})\\
&=& o(\hbox{Vol}(G_{T+c}(\tilde x)))
\end{eqnarray*}
as $T\to\infty$. Now the second statement of Theorem \ref{th_proxy} follows from Lemma \ref{l_a_eta}(d) and (\ref{eq_eskin}).

\section{Equidistribution on $\Gamma\backslash G$}

Recall that $K$ is a maximal compact subgroups of $G$, and $\nu$
is the probability Haar measure on $K$.

Denote by $\varrho$ a right Haar measure on the minimal parabolic subgroup $P$. For a suitable normalization of $\varrho$,
the Haar measure on $G$ is given by
\begin{equation}\label{eq_iwasawa}
\int_G \psi(g) dg=\int_{K}\int_P \psi(kp)d\varrho(p)d\nu(k),\quad \psi\in C_c(G).
\end{equation}
We also define a measure $\mu$ on $G$ by
\begin{equation}\label{eq_mu}
\int_G \psi(g) d\mu(g)=\int_{K}\int_P \psi(kp^{-1})d\varrho(p)d\nu(k),\quad \psi\in C_c(G).
\end{equation}
Note that $\mu$ is left $K$-invariant.

The first step in the proof of Theorem \ref{th_main} is the following result.
\begin{pro} \label{p_gg}
For every $\Psi\in C_c(\Gamma\backslash G)$ and $z\in \Gamma\backslash G$,
$$
\lim_{T\to\infty}\frac{1}{\mu(G_T)}\int_{G_T} \Psi(zg)d\mu(g)=\frac{1}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg
$$
where $G_T=\{g\in G: d(x,xg)<T$\}.
\end{pro}
Proposition \ref{p_gg} is a consequence of the equidistribution of translates of $K$ in
$\Gamma\backslash G$ proved by Eskin and McMullen in \cite{em} (see also \cite{sh} for a more general result).
They showed that for every strongly divergent sequence $\{g_n\}\subset G$,
\begin{equation}\label{eq_K}
\lim_{n\to\infty} \int_{K} \Psi(zkg_n)d\nu(k)=\frac{1}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg.
\end{equation}
Recall that a sequence $\{g_n\}\subset G$ is {\it strongly divergent} if the projection of $\{g_n\}$
on every noncompact simple factor of $G$ is divergent.
Note that (\ref{eq_K}) was proved in \cite{em} under the condition that the lattice $\Gamma$ is irreducible.
Since the proof of (\ref{eq_K}) is based on mixing properties of the action of $G$ on $\Gamma\backslash G$,
it is applicable to the case of a reducible lattice $\Gamma$ provided that the sequence $\{g_n\}$  is strongly divergent.

Denote by $\pi_i:G\to G_i$, $i=1,\ldots,s$, the projections of $G$ onto its simple factors.
Let $C_{i,j}\subset G_i$, $j\ge 1$, be an increasing sequence of compact subsets such that $G_i=\cup_{j\ge 1} C_{i,j}$.
Define
\begin{equation}\label{eq_gtn}
G_{T,n}=G_T- \bigcup_{1\le i \le s} \pi_i^{-1}(C_{i,n}).
\end{equation}

\begin{lem}\label{l_gtn}
For every $n\ge 1$, $\mu(G_{T,n})\sim \mu(G_T)$ as $T\to\infty$.
\end{lem}

\begin{proof}
It suffices to show that for every $i=1,\ldots,s$ and $n\ge 1$,
$$
\mu(G_T\cap \pi_i^{-1}(C_{i,n}))=o(\mu(G_T))\quad\hbox{as}\quad T\to\infty.
$$
Fix $i=1,\ldots,s$ and $n\ge 1$.
Note that $G=DH$, where $D$ and $H=\hbox{ker}(\pi_i)$ are normal connected
semisimple Lie subgroups with finite centers, and $D$ and $H$ commute.
We have $\pi_i^{-1}(C_{i,n})=D_{i,n}H$ for some compact set $D_{i,n}\subset D$.
There is a constant $\delta>0$ such that
\begin{equation}\label{eq_DH}
D_{i,n}H_{T-\delta}\subset (D_{i,n}H)_T\subset D_{i,n}H_{T+\delta}\;\;\hbox{ for all $T>0$.}
\end{equation}
We define measures $\mu_D$ and $\mu_H$ for the groups $D$ and $H$ respectively as in (\ref{eq_mu}).
With appropriate normalization, $\mu=\mu_D\otimes\mu_H$. Thus, it follows from (\ref{eq_DH}) that
\begin{equation}\label{eq_Ha}
\mu(G_T\cap \pi_i^{-1}(C_{i,n}))=\mu((D_{i,n}H)_T)\ll \mu_H(H_{T+\delta}).
\end{equation}
Since $G_T=KP_T$ and $P_T^{-1}=P_T$, using (\ref{eq_iwasawa}) and (\ref{eq_mu}), we conclude that
\begin{equation}\label{eq_mu_vol}
\mu(G_T)=\varrho(P_T^{-1})=\varrho(P_T)=\hbox{Vol}(G_T).
\end{equation}
Similarly, $H=LQ_T$ where $L$ is a maximal compact subgroup of $H$ contained in $K$, and $Q$ is a minimal
parabolic subgroup of $H$. As in (\ref{eq_mu_vol}), we deduce that $\mu_H(H_T)=\hbox{Vol}_H(H_T)$.
By (\ref{eq_Ha}), it is sufficient to show that
\begin{equation}\label{eq_HTa}
\hbox{Vol}_H(H_{T+\delta})=o(\hbox{Vol}(G_{T}))\quad\hbox{as}\quad T\to\infty.
\end{equation}
Note that with appropriate normalization the Haar measure on $G$ is the product of Haar measures on $D$ and $H$.
Without loss of generality, $\hbox{Vol}_D(D_{i,n})>0$. Then by (\ref{eq_DH}),
$$
\hbox{Vol}_H(H_{T+\delta})\ll \hbox{Vol}(D_{i,n}H_{T+\delta})\le \hbox{Vol}((D_{i,n}H)_{T+2\delta}).
$$
Let $G_T^\eta$ be defined as in (\ref{eq_last}). Since the set $D_{i,n}$ is compact, there
exists $\eta>0$ such that
$$
(D_{i,n}H)_{T+2\delta}\subset G_{T+2\delta}- G^\eta_{T+2\delta}.
$$
Thus, (\ref{eq_HTa}) follows from Lemma \ref{l_a_eta}(b).
\end{proof}

\begin{proof}[Proof of Proposition \ref{p_gg}]
The map $K\times A^+\times K\to G$ is a diffeomorphism on an open set of full measure.
Since the measure $\mu$ is left $K$-invariant and smooth, for some $\sigma\in C(A^+\times K)$,
$$
\int_G \psi (g)d\mu(g)=\int_{K}\int_{A^+}\int_{K} \psi (k_1ak_2)\sigma(a,k_2) d\nu(k_1)dad\nu(k_2),\quad \psi\in C_c(G).
$$

Let $G_{T,n}$ be defined as in (\ref{eq_gtn}), and it is $K$-bi-invariant (equivalently,
all $C_{i,j}$ are $\pi_i(K)$-bi-invariant). Then
$$
G_{T,n}=KA^+_{T,n}K\;\;\hbox{and}\;\;
\mu(G_{T,n})=\int_{K}\int_{A^+_{T,n}}\sigma(a,k_2)dad\nu(k_2),
$$
where $A^+_{T,n}=G_{T,n}\cap A^+$.

Let $\varepsilon>0$. By (\ref{eq_K}),
$$
\left|\int_{K} \Psi(zk_1ak_2)d\nu(k_1)-\frac{1}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg \right|<\varepsilon
$$
for $a\in A^+_{T,n}$ and $k_2\in K$ when $n>n_0(\varepsilon)$. Thus, for $n>n_0(\varepsilon)$,
\begin{eqnarray}\label{eq_g_gt}
&&\left|\int_{G_{T,n}} \Psi(zg)d\mu(g)-\frac{\mu(G_{T,n})}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg \right|\\
&=&\left|\int_{K}\int_{A^+_{T,n}}\int_{K} \Psi(zk_1ak_2)d\nu(k_1)\sigma(a,k_2)dad\nu(k_2)\right.\nonumber \\
&-&\left.\frac{\mu(G_{T,n})}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg \right|
\le \int_{K}\int_{A^+_{T,n}}\left|\int_{K}\Psi(zk_1ak_2)d\nu(k_1)\right.\nonumber \\
&-& \left. \frac{1}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg\right|\sigma(a,k_2)dad\nu(k_2)<\varepsilon \mu(G_{T,n}).\nonumber
\end{eqnarray}
By Lemma \ref{l_gtn}, for every $n\ge 1$,
$$
\int_{G_{T}} \Psi(zg)d\mu(g)=\int_{G_{T,n}} \Psi(zg)d\mu(g)+o(\mu(G_{T,n}))
$$
as $T\to\infty$. Thus, it follows from (\ref{eq_g_gt}) that
$$
\limsup_{T\to\infty}\left|\frac{1}{\mu(G_T)}\int_{G_{T}} \Psi(zg)d\mu(g)-\frac{1}{\hbox{\rm Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi\;dg \right|<\varepsilon
$$
for every $\varepsilon>0$. This proves the proposition.
\end{proof}

\section{Equidistribution on average}

In this section we prove that Theorem \ref{th_main} holds ``on average''.
In the case of hyperbolic spaces, the following proposition is a consequence
 of the work
 of Roblin \cite{ro}.
\begin{pro}\label{p_average}
For every $f\in C(G/P)$ and $y\in G/P$,
$$
\lim_{T\to\infty}\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in\Gamma_T(\tilde x)} \int_{K} f(\gamma k y)d\nu(k)=\int_{G/P} f dm_{\tilde x}
$$
where $\Gamma_T(\tilde x)=\{\gamma\in \Gamma: d(x,\tilde x\gamma)<T\}$.
\end{pro}
\begin{proof}
There exists $\tilde p\in P$ such that $\tilde x=x\tilde p$. Then $\tilde K=\tilde p^{-1}K\tilde p$, and
it follows from (\ref{eq_iwasawa}) that
\begin{equation}\label{eq_iwasawa2}
\int_G \psi(g) dg=\int_{\tilde K}\int_P \psi(k\tilde p^{-1}p)d\varrho(p)d\tilde \nu(k),\quad \psi\in C_c(G).
\end{equation}

Without loss of generality, $f\ge 0$, and since $G=KP$, we may assume that $y=eP$.

Let $\varepsilon>0$, $\mathcal{O}_\varepsilon=\{z\in X: d(x,z)<\varepsilon\}$, and $\phi_\varepsilon\in C_c(X)$ such that
$$
\phi_\varepsilon\ge 0,\quad \hbox{supp}(\phi_\varepsilon)\subset \mathcal{O}_\varepsilon, \quad \int_P \phi_\varepsilon(xp^{-1}) d\varrho(p)=1.
$$
Since $X=\tilde xP$ and $\varrho$ is right invariant, it follows that
\begin{equation}\label{eq_int_P}

\int_P \phi_\varepsilon(zp^{-1}) d\varrho(p)=1\quad\hbox{ for every $z\in X$.}
\end{equation}
Let $$\psi_\varepsilon(g)=f(gP)\phi_\varepsilon(\tilde xg),\quad g\in G.$$
Clearly, $\psi_\varepsilon\in C_c(G)$ and
$$
\Psi_\varepsilon(\Gamma g)\stackrel{def}{=}\sum_{\gamma\in\Gamma} \psi_\varepsilon(\gamma g)\in C_c(\Gamma\backslash G).
$$
By Proposition \ref{p_gg},
\begin{equation}\label{eq_mu_lim0}
\lim_{T\to\infty}\frac{1}{\mu(G_T)}\sum_{\gamma\in \Gamma} \int_{G_T} \psi_\varepsilon(\gamma g)d\mu(g)=\frac{1}{\hbox{Vol}(\Gamma\backslash G)}\int_{\Gamma\backslash G} \Psi_\varepsilon(\Gamma g) dg
\end{equation}
and by (\ref{eq_iwasawa2}),
\begin{eqnarray*}
\hbox{Vol}(\Gamma\backslash G)\int_{\Gamma\backslash G} \Psi_\varepsilon(\Gamma g) dg &=& \int_G \psi_\varepsilon(g)dg
=\int_{\tilde K} f(kP)d\tilde\nu(k)\cdot\int_P \phi_\varepsilon(\tilde x\tilde p^{-1}p)d\varrho(p)\\
&=&\int_{G/P} f dm_{\tilde x}\cdot\int_P \phi_\varepsilon(xp)d\varrho(p).\nonumber
\end{eqnarray*}
Denote by $\delta$ the modular function of $P$. By (\ref{eq_int_P}),
\begin{eqnarray*}
\left| \int_P \phi_\varepsilon(xp)d\varrho(p)-1\right|&=&\left| \int_P \phi_\varepsilon(xp^{-1})(\delta(p)-1)d\varrho(p)\right|\\
&\le&\max\{|\delta(p)-1|: xp^{-1}\in\mathcal{O}_\varepsilon\}.
\end{eqnarray*}
The sets $\{p\in P: xp^{-1}\in\mathcal{O}_\varepsilon\}$, $\varepsilon>0$, form a base of neighborhoods of $P\cap K$ in $P$.
Since $\delta|_{P\cap K}=1$ and $P\cap K$ is compact,
$$
\max\{|\delta(p)-1|: xp^{-1}\in\mathcal{O}_\varepsilon\}\to 0\quad\hbox{ as $\varepsilon\to 0^+$.}
$$
Thus, it follows from (\ref{eq_mu_lim0}) that
\begin{equation}\label{eq_mu_lim}
\lim_{\varepsilon\to 0^+}\lim_{T\to\infty}\frac{1}{\mu(G_T)}\sum_{\gamma\in \Gamma} \int_{G_T} \psi_\varepsilon(\gamma g)d\mu(g)=\int_{G/P} f dm_{\tilde x}.
\end{equation}
Since $G_T=KP_T$,
\begin{eqnarray*}
&&\sum_{\gamma\in \Gamma} \int_{G_T} \psi_\varepsilon(\gamma g)d\mu(g)\\
&\stackrel{(\ref{eq_mu})}{=}&\sum_{\gamma\in \Gamma}\int_{K\times P_T^{-1}} \psi_\varepsilon(\gamma kp^{-1})d\nu(k)d\varrho(p)\\
&=&\sum_{\gamma\in \Gamma} \int_{K} f(\gamma kP)
\left(\int_{P_T^{-1}} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)\right)d\nu(k).
\end{eqnarray*}
For $\gamma\in \Gamma-\Gamma_{T+\varepsilon}(\tilde x)$, $k\in K$, and $p\in P_T^{-1}$,
$$
d(x,\tilde x\gamma kp^{-1})=d(xpk^{-1},\tilde x\gamma)\ge d(x,\tilde x\gamma)-d(x, xpk^{-1})\ge \varepsilon.
$$
This implies that $\int_{P_T^{-1}} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)=0$ for $\gamma\in \Gamma-\Gamma_{T+\varepsilon}(\tilde x)$. Thus,
\begin{eqnarray*}
&&\sum_{\gamma\in \Gamma} \int_{G_T} \psi_\varepsilon(\gamma g)d\mu(g)\\
&=&\sum_{\gamma\in \Gamma_{T+\varepsilon}(\tilde x)} \int_{K} f(\gamma kP)
\left(\int_{P_T^{-1}} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)\right)d\nu(k)\\
&\le&
\sum_{\gamma\in \Gamma_{T+\varepsilon}(\tilde x)} \int_{K} f(\gamma kP)
\left(\int_{P} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)\right)d\nu(k)\\
&\stackrel{(\ref{eq_int_P})}{=}&\sum_{\gamma\in \Gamma_{T+\varepsilon}(\tilde x)} \int_{K} f(\gamma kP)d\nu(k).
\end{eqnarray*}
Combining (\ref{eq_mu_lim}), (\ref{eq_mu_vol}), (\ref{eq_eskin}) and Lemma \ref{l_a_eta}(c), we deduce that
$$
\liminf_{T\to\infty}\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in \Gamma_{T}(\tilde x)} \int_{K} f(\gamma kP)d\nu(k)\ge \int_{G/P} f dm_{\tilde x}.
$$

On the other hand, for $\gamma\in \Gamma_{T-\varepsilon}(\tilde x)$, $k\in K$, and $p\in P$ such that
$d(x,\tilde x\gamma kp^{-1})<\varepsilon$,
$$
d(x,xp^{-1})\le d(x,\tilde x\gamma kp^{-1})+ d(xp^{-1},\tilde x\gamma k p^{-1})<T.
$$
This shows that for $\gamma\in \Gamma_{T-\varepsilon}(\tilde x)$,
$$
\int_{P^{-1}_T} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)=\int_{P} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)\stackrel{(\ref{eq_int_P})}{=}1.
$$
Hence,
\begin{eqnarray*}
&&\sum_{\gamma\in \Gamma} \int_{G_T} \psi_\varepsilon(\gamma g)d\mu(g)\\
&\ge&
\sum_{\gamma\in \Gamma_{T-\varepsilon}(\tilde x)} \int_{K} f(\gamma kP)
\left(\int_{P_T^{-1}} \phi_\varepsilon(\tilde x\gamma kp^{-1})d\varrho(p)\right)d\nu(k)\\
&=&\sum_{\gamma\in \Gamma_{T-\varepsilon}(\tilde x)} \int_{K} f(\gamma kP)d\nu(k).
\end{eqnarray*}
By (\ref{eq_mu_lim}), (\ref{eq_mu_vol}), (\ref{eq_eskin}), and Lemma \ref{l_a_eta}(c),
$$
\limsup_{T\to\infty}\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in \Gamma_{T}(\tilde x)} \int_{K} f(\gamma kP)d\nu(k)\le \int_{G/P} f dm_{\tilde x}.
$$
This proves the proposition.
\end{proof}

\section{Proof of Theorem \ref{th_main}}

Now the proof can be completed using the argument from \cite{mau}.
Let $\varepsilon>0$. Since the space $G/P\times G/P$ is compact, there exists a neighborhood $\mathcal{O}$
of the diagonal in $G/P\times G/P$ such that for every $(z_1,z_2)\in \mathcal{O}$, we have
$|f(z_1)-f(z_2)|<\varepsilon$. Then for every $k\in K$,
\begin{eqnarray*}
&&\left|\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma y)-\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma k y)\right|\\
&\le& \sum_{\gamma\in\Gamma_T(\tilde x): (\gamma y,\gamma ky)\in\mathcal{O}} |f(\gamma y)-f(\gamma ky)|
+ \sum_{\gamma\in\Gamma_T(\tilde x): (\gamma y,\gamma ky)\notin\mathcal{O}} |f(\gamma y)-f(\gamma ky)|\\
&\le& \varepsilon |\Gamma_T(\tilde x)|+ 2 \sup |f|\cdot
|\{\gamma\in\Gamma_T(\tilde x): (\gamma y,\gamma ky)\notin\mathcal{O}\}|.
\end{eqnarray*}
Thus, it follows from Theorem \ref{th_proxy} that
$$
\lim_{T\to\infty} \frac{1}{|\Gamma_T(\tilde x)|}\left|\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma y)-\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma k y)\right|=0
$$
for all $k\in K$. Hence, by the dominated convergence theorem,
$$
\lim_{T\to\infty} \left|\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in\Gamma_T(\tilde x)} f(\gamma y)-\frac{1}{|\Gamma_T(\tilde x)|}\sum_{\gamma\in\Gamma_T(\tilde x)}\int_{K} f(\gamma k y)d\nu(k)\right|=0.
$$
Finally, Theorem \ref{th_main} follows from Proposition \ref{p_average}.

\section{Appendix: volume estimates}

In this section, we give proofs of volume estimates, which are used in Theorems \ref{th_main} and \ref{th_proxy}.
There are other ways to establish these volume estimates. For example, one can use the exact asymptotics of
the volume of Riemannian balls from \cite{kni} (see also \cite{g_o}).
We present a straightforward proof that does not use asymptotics.

Let $\mathfrak{a}$ be the Lie algebra of the Cartan subgroup $A$ and $\mathfrak{a}^+$
the positive Weyl chamber with respect to the root system $\Sigma^+$.
The Riemannian metric defines a scalar product on $\mathfrak{a}$ and, by duality, on the dual space of $\mathfrak{a}$.
For $\alpha\in\Sigma^+$, we denote by $m_\alpha$
the dimension of the corresponding root space and put $\rho=\frac{1}{2}\sum_{\beta \in \Sigma^+} m_\beta \beta$.

   \begin{lem}\label{l_max}
   The maximum of $\rho$ on $\{a\in\mathfrak{a}:\|a\|\le 1\}$
   is achieved at a unique point in the interior of $\mathfrak{a}^+$.
   \end{lem}
   \begin{proof}
   Since the set $\{a\in\mathfrak{a}:\|a\|=1\}$ is strictly convex, it is clear that
   the point of maximum is unique.
   It is sufficient to show that $(\rho,\alpha)>0$ for every $\alpha\in\Sigma^+$.
   Denote by $\sigma_\alpha$ the reflection with respect to the hyperplane $\{\alpha=0\}$.
   The map $\sigma_\alpha$ permutes the elements of the set $\Sigma^+-\{\alpha,2\alpha\}$ and
   $\sigma_\alpha(\alpha)=-\alpha$. Since $m_{\sigma_\alpha(\beta)}=m_\beta$, we have
    $$\sigma_\alpha(\rho)=\rho-2m_\alpha \alpha-4m_{2\alpha}\alpha.$$
   Thus,
$$(\rho,\alpha)=(\sigma_\alpha(\rho),\sigma_\alpha(\alpha))=2m_\alpha(\alpha,\alpha)+4m_{2\alpha}(\alpha,\alpha)-(\rho,\alpha)$$
    and $(\rho,\alpha)=(m_\alpha+2m_{2\alpha})(\alpha,\alpha)$ is positive.
    \end{proof}

For $T,\eta>0$, define
\begin{eqnarray}
A_{T}^{\eta}&=&\{a \in A_T \, : \alpha(\log a)\ge \eta\hbox{ for all } \alpha\in\Sigma^+ \}\nonumber\\
&=& \{a \in A \, : \|\log a\|<T,\,\alpha(\log a)\ge \eta\hbox{ for all } \alpha\in\Sigma^+ \},\label{eq_last}\\
G_T^{\eta}&=&K A_{T}^{\eta}K.\nonumber
\end{eqnarray}

  \begin{lem}\label{l_a_eta} For every $\eta>0$,
\begin{enumerate}
\item[(a)]
    $$\int_{A_{T}^{\eta}} \xi(\log a)da \sim_{T\to\infty} \int_{A^+_T} \xi(\log a)da,$$
\item[(b)]
$$\hbox{\rm Vol}(G^\eta_T)\sim_{T\to\infty} \hbox{\rm Vol}(G_T),$$
\item[(c)]
$$
\liminf_{\varepsilon\to 0^+}\left( \limsup_{T\to\infty} \frac{\hbox{\rm Vol}(G_{T+\varepsilon})}{\hbox{\rm Vol}(G_{T})}\right)=1,
$$
\item[(d)]
$$
\hbox{\rm Vol}(G_{T+\eta})\ll \hbox{\rm Vol}(G_T).
$$
\end{enumerate}
   \end{lem}
   \begin{proof}
We have
\begin{equation}\label{eq_sum}
\int_{\mathfrak{a}^+_T} \xi(a)da=2^{-|\Sigma^+|}\sum_{i\in I} \int_{\mathfrak{a}_T^+} e^{\lambda_i(a)}da
\end{equation}
where $\lambda_i$'s the characters of the form $2\rho-\sum_{\alpha\in\Sigma^+} n_\alpha\alpha$ for some $n_\alpha\ge 0$.
Let
\begin{eqnarray*}
\delta&=&\max\{2\rho(a): a\in\mathfrak{a}^+_1\},\\
\delta_i&=&\max\{\lambda_i(a): a\in\mathfrak{a}^+_1\},\;\;\; i\in I,\\
\delta_\alpha&=&\max\{2\rho(a): a\in\mathfrak{a}^+_1,\alpha(a)=0\},\;\;\;\alpha\in\Sigma^+.
\end{eqnarray*}
It follows from Lemma \ref{l_max} that for $\lambda_i\ne 2\rho$ and $\alpha\in\Sigma^+$,
$\delta>\max\{\delta_i,\delta_\alpha\}$.
Thus,
\begin{equation}\label{eq_lambda}
\int_{\mathfrak{a}^+_T} e^{\lambda_i(a)}da\le \hbox{Vol}(\mathfrak{a}_T^+) e^{\delta_i T}\ll T^{r} e^{\delta_i T}
\end{equation}
where $r=\dim \mathfrak{a}$.
Let $\varepsilon>0$ be such that
$$
\delta-\varepsilon>\max\{\delta_i,\delta_\alpha: i\in I,\alpha\in\Sigma^+\}.
$$
Then
\begin{eqnarray}
\int_{\mathfrak{a}^+_T} e^{2\rho(a)}da &=& T^r\int_{\mathfrak{a}_1^+} e^{2T\rho(a)}da\label{eq_up}\\
&\ge& T^r e^{(\delta-\varepsilon)T}\hbox{Vol}(\{a\in \mathfrak{a}_1^+: 2\rho(a)\ge \delta-\varepsilon\})\gg T^r e^{(\delta-\varepsilon)T}.\nonumber
\end{eqnarray}
Combining (\ref{eq_sum}), (\ref{eq_lambda}), and (\ref{eq_up}), we deduce that
\begin{equation}\label{eq_low}
\int_{\mathfrak{a}^+_T} \xi(a)da\gg T^r e^{(\delta-\varepsilon)T}.
\end{equation}
On the other hand, for $\alpha\in\Sigma^+$,
\begin{eqnarray*}
\int_{\mathfrak{a}^+_T\cap\{\alpha<\eta\}} \xi(a)da&\le& \int_{\mathfrak{a}^+_T\cap\{\alpha<\eta\}} e^{2\rho(a)}da
\ll \int_{\mathfrak{a}^+_T\cap\{\alpha=0\}} e^{2\rho(a)}da\\
&=&T^{r-1}\int_{\mathfrak{a}^+_1\cap\{\alpha=0\}} e^{2T\rho(a)}da\ll T^{r-1}e^{\delta_\alpha T}=o(e^{(\delta-\varepsilon)T}).
\end{eqnarray*}
Since
$$
\mathfrak{a}^+_T-\mathfrak{a}^\eta_T\subset \bigcup_{\alpha\in\Sigma^+} \mathfrak{a}^+_T\cap\{\alpha<\eta\}.
$$
This proves part (a) of the lemma. Part (b) follows from (\ref{eq_cartan}).

To prove part (c), we note that
$$
\hbox{\rm Vol}(G_{T+\varepsilon})=\int_{\mathfrak{a}^+_{T+\varepsilon}}\xi(a)da=(T+\varepsilon)^r\int_{\mathfrak{a}^+_{1}}\xi((T+\varepsilon)a)da
$$
It is easy to check that there exist $b>0$ such that $\sinh(t+\varepsilon)\le e^\varepsilon\sinh (t)+b$ for every $\varepsilon\in (0,1)$ and $t\ge 0$.  Thus, for $a\in\mathfrak{a}^+_1$ and sufficiently small $\varepsilon>0$,
$$
\xi((T+\varepsilon)a)\le \prod_{\alpha\in\Sigma^+} (a_\varepsilon\sinh(\alpha(Ta))+b)^{m_\alpha}\le d_\varepsilon\xi(Ta)+C\sum_{i\in I} e^{\lambda_i(a)}
$$
where $d_\varepsilon\to 1$ as $\varepsilon\to 0^+$, $C>0$, and $\lambda_i$'s are characters such that $2\rho-\lambda_i<0$ in the interior of $\mathfrak{a}^+$.
Thus, it follows from (\ref{eq_lambda}) that
$$
\int_{\mathfrak{a}_T^+} \xi((T+\varepsilon)a)da\le  d_\varepsilon \int_{\mathfrak{a}_T^+} \xi(Ta)da +o(e^{(\delta-\varepsilon)T}).
$$
Using (\ref{eq_gt}) and (\ref{eq_low}), we deduce that
$$
\limsup_{T\to\infty}\frac{\hbox{\rm Vol}(G_{T+\varepsilon})}{\hbox{\rm Vol}(G_{T})}\le d_\varepsilon,
$$
and part (c) of the lemma follows. The last part of lemma can be proved similarly.
\end{proof}

\section{Acknowledgements}

The main ideas of this paper were developed during the workshop ``Ergodic properties of geometric group actions'' in Summer 2003.
The authors would like to express deep appreciation to the organizers of this workshop and to the Max Planck Institute of
Mathematics for its support. We also would like to thank to R.~Spatzier for raising the problem solved in this paper during the workshop
and to Y.~Guivarc'h for bringing the paper of Arnold and Krylov to out attention.


TITLE: Confusion about sum of random variables conditional probabilities
QUESTION [1 upvotes]: Let $X,Y$ be independent random variables, and $Z = X+Y.$
Then I want to calculate $Pr[X = x \mid Z = z].$ My confusion is on evaluating this expression.
On the one hand, I have $Pr[X = x \mid Z = z] = Pr[Z - Y = x \mid Z = z] = Pr[z - Y = x] = Pr[Y = z - x].$
But also, $Pr[Z = z \mid X = x] = Pr[X+Y = z \mid X = x] = Pr[Y = z - x].$ So these two probabilities are equal? But $Pr[Z = z \mid X = x] Pr[X = x] = Pr[X = x \mid Z = z] Pr[Z = z]$ and in general $Pr[X = x]$ and $Pr[Z = z]$ are not equal. I believe it should be $Pr[X = x \mid Z = z] = Pr[Y = z - x \mid Z = z]$ but I don't think the conditional $Z = z$ can be removed since $Y$ and $Z$ are not independent?
I'm not sure whether the first equation holds either. For example, if I roll a fair six sided die $X$ (numbered 1 to 6) and roll a fair ten sided die $Y$ and take the sum, then $Pr[X = 1 \mid Z = 2] = 1$ since the only possible outcome is $(x,y) = (1,1),$ and this is not equal to $Pr[Y = (2-1)] = 1/10.$ On the other hand it is equal to $Pr[Y = (2-1) \mid Z = 2] = 1.$ I think I'm making a mistake in one of these but it's not clear to me in which step.
(The context of this was that $X$ is a random variable with given distribution representing some unknown parameter and $Y$ is a standard normal error. Then you observe $z = x + y$ and want to estimate the $X.$)

REPLY [0 votes]: The mistake lies in this step:

$$Pr[Z−Y=x∣Z=z]=Pr[z−Y=x]$$

Note that $P(A|B)=\frac{P(B|A)\cdot P(A)}{P(B)}$. The actual evaluation is instead
$$P(Z-Y=x|Z=z)=\frac{P(Z=z|Z-Y=x)\cdot P(Z-Y=x)}{P(Z=z)}=\frac{P(Z=z|X=x)\cdot P(X=x)}{P(Z=z)}$$
If we are given $X=x$, $Z=z$ only when $Y=z-x $. Thus, $P(Z=z|X=x)=P(Y=z-x)$. The above formulation should make it clear that this is not true for $P(X=x|Z=z).$We now have
$$P(Z-Y=x|Z=z)=P(Y=z-x)\cdot\frac{ P(X=x)}{P(Z=z)}$$

In your dice example, this evaluates as
$$P(X=1|Z=2)=P(Y=1)\cdot\frac{ P(X=1)}{P(Z=2)}=\frac{1}{10}\cdot\frac{\frac1 6}{\frac1 {60}}=1$$
as expected.

I shall take another example, to make it clearer. Let us calculate the probability $P(X=2|Z=5)$. We see that $Z=5$ is achieved by the following pairs : $$(X,Y)=\{(1,4),(2,3),(3,2),(4,1)\}\implies P(X=2|Z=5)=\frac14$$
Using the formula, we can calculate the same as $$P(X=2|Z=5)=P(Y=3)\cdot \frac{P(X=2)}{P(Z=5)}=\frac1{10}\cdot \frac{\frac16}{\frac4{60}}=\frac14$$
which is the same as before.
[$P(Z=5)=\frac{4}{60}$ as there are $60$ possible $(X,Y)$ and $Z=5$ is only achieved by $4$]


TITLE: Geometrical Significance of determinant of Jacobian matrix
QUESTION [0 upvotes]: Geometrical Significance of determinant of the Jacobian matrix

I know that determinent of the matrix is geometrically thought as the volume of parallelopiped span by the vector.
Is there any geometrical significance of determinant of Jacobian matrix?
Any HElp will be appreciable

REPLY [4 votes]: Calculus is all about functions which, at very small scales, appear linear. This is why in Calculus I you learn how to find the line tangent to a function by using the derivative at a point. You are finding a linear approximation of your function at a point.
In higher dimensions, a linear map is represented by a matrix, and the Jacobian is that matrix! If you have a differentiable function, no matter how complicated it is, it looks like a linear transformation if you zoom in far enough. If you pick a point $p$, then the Jacobian $J_f(p)$ tells you what that linear transformation is (around $p$). This is analogous to the line approximating your function around a point in calculus I.
What, then, is the determinant of the Jacobian? As you mention, the determinant measures how a linear transformation affects the volume of space. If you look at the cube spanned by the standard basis vectors, we say it has volume 1. After applying our linear transformation $T$, our basis vectors were sent to the edges of a parallelopiped, and the new volume tells you how volumes changed after applying $T$.
In one dimension, if the derivative at a point is $3$, that means it is changing faster than if the derivative were $2$. The determinant of the Jacobian measures the same thing. If $|J_f(p)| = 3$, that means if $C$ is a (very small) cube near $p$, we can expect $f(C)$ to be a parallelopiped with about $3$ times the area of $C$!
This is why, when we change coordinates to take an integral, we need to multiply by a factor of the determinant of the Jacobian of the transformation. We integrate to measure the size of some object, but when we change coordinates the size of that object changes! How does the size change? The determinant of the Jacobian tells us exactly how the size changes at any point.
As an excellent visual example, this is a youtube video showcasing how (at small scales) a differentiable transformation looks linear.

I hope this helps ^_^


TITLE: Establishing a bijection between permutations and permutation matrices.
QUESTION [2 upvotes]: I am trying to prove the following:
Given $\sigma \in S_n$ let $P(\sigma)$ be the matrix with $(P(\sigma))_{i,j} = \delta_{i,\sigma(j)}$. Show that $P$ is a bijection between $S_n$ and the set of permutation matrices of size $n$ $-$ where $\delta_{i,j}$ is the Kronecker delta which equals 1 if $i=j$ and 0 otherwise.
As I understand the question, the question is saying that for each row $i$ and column $j$ we have that position $i,j$ equals 1 iff $\sigma(j) = i$.
So then it seems then that for any $\sigma$ such that $\sigma(i) = i$, we would have $P(\sigma)$ as the identity matrix with strictly 1's from the top-left to the bottom-right and zeros everywhere else.
On the other hand, suppose that we have $\sigma(1) = 2$, $\sigma(2) = 3$, $\sigma(3) = 4$, $\sigma(4) = 1$; then we'd have the following matrix
\begin{bmatrix}0 & 0 & 0& 1\\1 & 0 & 0 & 0\\0 & 1  & 0 & 0 \\ 0 & 0 & 1 & 0\end{bmatrix}
Is this a correct understanding?
If so, then here is my attempted proof of the question mentioned above:
$\bf{Injectivity}$: Assuming $\sigma, \tau \in S_n$ and $P(\sigma) = P(\tau)$ then whenever $\sigma(j) = i$ we have the jth-column and i-th row of the matrix $p$ as a 1 and similarly for $\tau(j) = i$. So $\tau = \sigma$ and we are done.
$\bf{Surjectivity}$: Let $P$ be some $n \times n$ permutation matrix. Then each row and column will have exactly one 1 with zeros everywhere else. Then for every i,j position which has a 1 in it, we can choose a permutation $\sigma$ such that $\sigma(j) = i$ for some $\sigma$ which is an n-cycle and we are done.
Is this proof sound? Thank you in advance.

REPLY [0 votes]: It can also be shown that the map $\Phi: \mathcal{S}_n \longrightarrow \mathcal{P}_n$ defined by $\sigma \in \mathcal{S}_n \longmapsto P_\sigma \in \mathcal{P}_n$ is a homomorphism and hence an isomorphism.
If $\sigma$, $\gamma \in \mathcal{S}_n$ and $1 \le i,j \le n$, then
$$
\left[ P_\sigma P_\gamma\right]_{ij}
= \sum_{k=1}^n \delta_{i,\sigma(k)} \delta_{k, \gamma(j)}
= \delta_{i, \sigma(\gamma(j))}
= \left[ P_{\sigma \circ \gamma}\right]_{ij},
$$
i.e., $P_{\sigma} P_{\gamma} = P_{\sigma \circ \gamma}$.
Thus,
\begin{align}
\Phi(\sigma\circ\gamma) = P_{\sigma \circ \gamma} = P_\sigma P_\gamma = \Phi(\sigma)\Phi(\gamma)
\end{align}
as desired.


TITLE: A department store is holding a drawing to give free shopping sprees- Probability
QUESTION [0 upvotes]: A department store is holding a drawing to give free shopping sprees to two lucky customers. There are $18$ customers who have entered the drawing: $4$ live in the town of Gaston, $8$ live in Pike, and $6$ live in Wells. In the drawing, the first customer will be selected at random, and then the second customer will be selected at random from the remaining customers. What is the probability that both customers selected are Pike residents?
Report your answer as an exact fraction.
My answer
The probability that the first customer lives in Pike is
P1=8/18=4/9
The probability that the second customer lives in Pike is
P2=7/17
The probability that both customers selected are Pike residents is
P1*P2=(4/9)*(7/17)=28/153
Am I Correct?

REPLY [0 votes]: This is a way to formalize your answer.
For $i=1,2$ let $E_i$ be the event that the $i$-th customer lives in Pike.
Then:$$P(E_1\cap E_2)=P(E_1)P(E_2\mid E_1)=\frac8{18}\frac7{17}$$
As you were told in the comments on your question we have $P(E_1)=P(E_2)=\frac8{18}$ but $P(E_2\mid E_1)=\frac7{17}$.


TITLE: What are arithmetical logarithms?
QUESTION [3 upvotes]: According to the YouTube video "Evariste Galois a documentary" by
MsrEvaristeGalois, when the young Evariste Galois was taking his entrance exam for the Ecole Polytechnique, his examinateurs asked Galois to explain the theory of arithmetical logarithms.  According to the video, Galois refused, claiming there is no such thing as arithmetical logarithm, apparently angering the examining professors.
Does anyone know what arithmetical logarithms supposedly are?

REPLY [0 votes]: According to the Encyclopédie (mid-eighteenth century), real logarithms belong to arithmetic, while logarithms of negative or complex numbers belong to analysis. "la première partie de l’article Logarithme, considérée comme élémentaire, est classée en Arithmétique ; c’est la seconde partie, consacrée au problème des logarithmes des nombres négatifs et aux développements en séries entières, qui est classée en Analyse." (https://journals.openedition.org/rde/4728?lang=en, paragraph 105). English translation by Google-translate: "the first part of the article Logarithm, considered as elementary, is classified in Arithmetic; it is the second part, devoted to the problem of the logarithms of negative numbers and to expansions in whole series, which is classified in Analysis."


TITLE: Define the open balls of this metric
QUESTION [1 upvotes]: The post office metric space, $P$ has the distance function defined as follows:
$$
d_P (\mathbf{x},\mathbf{y}) := \begin{cases}
0 & \mathbf{x} = \mathbf{y}\\
\Vert \mathbf{x-y}\Vert_2 & \mathbf{x}, \mathbf{y}, \mathbf{0} \mathbf{ \ are \ aligned } \\
\Vert \mathbf{x}\Vert_2+\Vert \mathbf{y}\Vert_2 & \mathbf{x}\neq \mathbf{y}
\end{cases}
$$
Where $\Vert \mathbf{x}\Vert_2 = \sqrt{x_1^2+x_2^2}$ is the Euclidean distance from $\mathbf{x}=(x_1,x_2) \in \mathbb{R}^2$ to the origin.
I am interested in drawing the balls of this metric centered at point $\mathbf{p}$, having a radius $r$:
$$B_r(\mathbf{p}) \triangleq  \{\mathbf{x} \in P\vert\ d(\mathbf{x},\mathbf{p})<r  \}$$
Does anyone have any tips on how to do this?

REPLY [2 votes]: The definition for the $\textit{post office metric}$ I know is slightly different than yours, namely:
$$d_P(\textbf{x}, \textbf{y}) =
\begin{cases}
0 & \textbf{x} = \textbf{y} \\
\|\textbf{x}\|_2 + \|\textbf{y}\|_2 & \textbf{x} \neq \textbf{y}
\end{cases}
$$
The way I've been told to think about this metric is, that a letter has to pass through the post office (the origin) in all cases, even if the house i want to send my letter to lies in a straight line with my own house. (In fact, when I learned about this metric it was called the 'French Railway Metric', since every train has to go through Paris, but that's the same concept...).
But nonetheless we can figure out how open balls in your metric look like! First the easy case, if $\textbf{p} = 0$ then the open ball around $\textbf{p}$ with radius $r$ is the same as the open ball in the euclidean metric, because any point is aligned with just 0.
Let's now look at $\textbf{p} \neq 0$. We have two cases, either $\|\textbf{p}\| \leq r$, or $\|\textbf{p}\| > r$. In the first case, we never reach the origin, so the open ball is just the straight line from $p$ in direction of the origin of length $r$, and also in the opposite direction (away from the origin, also of length $r$) not including the endpoints. So geometrically this open ball is just a straight line. If $\|\textbf{p}\|<r$, the open ball is the union of the line segment from $p$ to the origin, and the open disc centered at the origin of radius $r-\|\textbf{p}\|$ (with respect to the usual euclidean metric).


TITLE: Using the Sum Rule to determine N in this counting problem
QUESTION [0 upvotes]: I'm having trouble with this problem. How would I be able to determine N with the sum rule? I'm following my textbook but it doesn't cover a problem like this one, and there's no answers included either so no way to know what I'm doing.
Any help would be appreciated, thank you!
Let $n ≥ 4$ be an integer and consider the set $S = \{1, 2, . . . , n\}$. Let $k$ be an integer with $2 \leq k \leq n − 2$.
In this question, we consider subsets $A$ of $S$ for which $|A| = k$
and $\{1, 2\} \subseteq A$.
Let $N$ denote the number of such subsets.
Use Sum Rule to determine $N$:

REPLY [0 votes]: The set $A$ has cardinality $k$ and must contain $1$ and $ 2$ , so the other $k-2$ elements must be chosen form the last $n-2$ This can be done in $\binom{?}{?}$ ways & $k$ can range from ? to ?
\begin{eqnarray*}
\sum_{k=?}^{?} \binom{?}{?}
\end{eqnarray*}
Now change the index of the sum then the sum is easily evaluated using the binomial theorem and we have

$2^{n-4}$