text:
\section{Long-time behavior of the finite N model}
\label{sec-finite}

We consider a fixed finite number of peers and let time $k$ go to infinity. We prove that the distribution of peer opinions $M^N(k)$ converges almost surely (a.s.) to a random distribution $M^N(\infty)$. Note that the limiting distribution $M^N(\infty)$ depends on chance as well as on the initial condition. We prove that
$M^N(\infty)$ is a combination of at most
$\left\lceil\frac{1}{\Delta}\right\rceil$ Dirac measures at points
separated by at least $\Delta$. A key observation
here is that if $h$ is any convex function then $\cro{h,M^N(k)}$ is
non-increasing in $k$. Dittmer and Krause
\cite{dittmer2001consensus,krause2000discrete} obtained similar
results, but for a deterministic model.

\begin{definition}
\label{d-partcons}
We say that  $\nu\in \calP[0,1]$
is a \emph{partial consensus with $c$ components} if $\nu =
\sum_{m=1}^{c}\alpha_m \delta_{x_m}$ with
 $x_m \in [0,1]$, $\abs{x_m-x_{m'}}
> \Delta$ for $m \neq m'$, and $\alpha_m >0$. Necessarily
$c \leq \left\lceil\frac{1}{\Delta}\right\rceil$ and $\sum_{m= 1}^{c} \alpha_m
= 1$.
If $c=1$, \emph{i.e.}, if $\nu$ is a Dirac measure, we say that
$\nu$ is a \emph{total consensus}.
\end{definition}

If $M^N(k)$ is a partial consensus, then
peers are grouped in a number of components too far apart to interact,
and
within one component all peers have the same
value.
Thus, a partial consensus is an absorbing state for
$M^N$, and \thref{discrete_convergence}
below will show that $M^N(k)$ converges a.s., as
$k\to \infty$, to one such state.

\subsection{Convexity and Moments} We start with results about convexity and moments, which are
needed to establish the convergence result and are also of
independent interest.

\begin{proposition}For any convex function $h: [0,1] \to \Reals$,
any $x,y$ and $w$ in $[0,1]$,
 \ben
 h\lp wx+(1-w)y\rp+h\lp wy+(1-w)x\rp-h(x)-h(y)\leq 0
 \een
 with equality when $h$ is strictly convex possible only if
 $x=y$ or $w =0$ or $w=1$.\label{lem-convex}\label{prop-convex}
\end{proposition}

The following corollary is immediate from the interaction structure of the model.

\begin{corollary}
If $h: [0,1] \to \Reals$ is a convex function, then $\cro{h,M^N(k)}$ is a non-increasing function of $k$
along any sample path. \label{prop-fn-conv}
\end{corollary}

Applying this to $h(x)=x$, $h(x)=-x$ and $h(x)=x^n$ yields that in any sample path,
the first moment is constant and other moments are non-increasing with time.

\begin{corollary}
\label{cor-fin-mom}
For $n =1,2,\dots$ and $k\in\Nats$, let $\mu_n^N(k) =
\frac{1}{N}\sum_{i=1}^{N}X_i^N(k)^n$ denote the $n$-th moment
of $M^N(k)$, and let $\sigma^N(k)$ be the standard deviation given by
$\sigma^N(k)^2= \mu^N_2(k)-\mu^N_1(k)^2 $.
Then:
\begin{enumerate}
  \item The mean $\mu_1^N(k)$ is stationary in $k$, \emph{i.e.}, $\mu_1^N(k)=\mu_1^N(0)$
  for all $k$.
  \item The moments and the standard deviation are
      non-increasing in $k$: if $k \leq k'$
      then $\mu_n^N(k) \geq \mu_n^N(k')$ and $\sigma^N(k)
      \geq \sigma^N(k')$.
\end{enumerate}\label{discrete_moments}\label{discrete_variance_drop}
\end{corollary}

Moreover, stationarity of moments is equivalent to
reaching partial consensus:

\begin{proposition}
\label{pro-partcons}
If $M^N(k)$ is a partial consensus, then $\mu_n^N(k')=\mu_n^N(k)$ for all $n\ge1$ and $k'\geq k$.
Conversely, if for some $n \geq 2$ there exists a (random) instant $k$ such that $\mu_n^N(k')=\mu_n^N(k)$ for all $k'\geq k$,
then  $M^N(k')=M^N(k)$ for all $k'\geq k$
and $M^N(k)$ is a partial consensus, almost surely.
\end{proposition}

\subsection{Almost Sure Convergence to Partial Consensus}

\begin{definition}
We say that two peers $i$ and $j$ are
\emph{connected} at time $k$ if their values $x$ and $y$
satisfy
 $\abs{y-x} \leq \Delta$. We
say that $F\subset \{1,2,\dots,N\}$ is a \emph{cluster} at time
$k$ if it is a maximal connected component.
\end{definition}
In other words, a cluster is a maximal set of peers such that
every peer can pass the deviation test with one neighbour in
the cluster. The set of clusters at time $k$ is a random
partition of the set of peers.
The following proposition states that a cluster can either
split or stay constant, but cannot grow.

\begin{proposition}
\label{pro-clusters}
Let $\calC^N(k)=\{C_1, \dots ,C_{\ell}\}$
be the set of clusters at time $k$. Then either $\calC^N(k+ 1)=
\calC^N(k)$ or
  $\calC^N(k+ 1) = \lp \calC^N(k) \setminus C_{\ell_1}\rp \cup \calC'$
where $\calC'$ is a partition of $C_{\ell_1}$,
for some $\ell_1\in \{1, \dots, \ell\}$.
 \label{cluster_not_grow}
\end{proposition}
The number of clusters is thus non decreasing,
and since it is bounded by $\left\lceil
\frac{1}{\Delta} \right\rceil$ it must be
constant after some time, yielding the
following:

\begin{corollary}
\label{constant_clusters_after_time} There exists a random time $K^N$,
a.s. finite, such that
 \ben
 \calC^N(k) = \calC^N(K^N) \mfor k \geq K^N\,.
 \een
\end{corollary}

Finally, we prove that the occupancy measure
converges to a partial consensus (see \ref{sec-probab} for the
usual weak topology on $\calP[0,1]$):

\begin{theorem}
\label{thm-longtimelim}
\label{discrete_convergence} As $k$ goes to infinity,  $M^N(k)$ converges
almost surely, for the weak topology on $\calP[0,1]$, to a random probability $M^N(\infty)$,
which is a partial consensus with $L^N$ components,
where $L^N:=\textnormal{Card}(\calC^N(K^N))$ is
the \emph{final number of clusters}.
\end{theorem}

\thref{thm-longtimelim} notably implies that there is
convergence to total consensus if and only if $L^N = 1$. The
probability $p^*:=\P(L^N=1)$ of convergence to total consensus
is not necessarily $0$ or $1$, but:

\begin{enumerate}
    \item If the diameter of $M^N(0)$ is less than $\Delta$
        (\emph{i.e.}, $\max_{i,j}\abs{X^N_i(0)-X^N_j(0)}<
        \Delta$) then $p^*=1$ (obvious);
    \item If there is more than 1 cluster in $M^N(0)$ then
        $p^*=0$ (see \pref{cluster_not_grow}).

\end{enumerate}

config: arxiv


TITLE: How to check whether these elements of a cubic number field are relatively prime?
QUESTION [3 upvotes]: Let $a,b$ be odd positive integers, and let $x$ be an integer not divisible by $7$ or $13$.
In the field $K = \mathbb{Q(\theta)}$ with $\theta^3 = 7 \cdot 13^2$, we have
$$
x^3 - 7 \cdot 13^2 \cdot (7^a 13^b)^3 = (x-7^a 13^b \theta)(x^2 + 7^a 13^bx\theta + 7^{2a} 13^{2b}\theta^2).
$$
How can I check whether the two factors on the right are relatively prime in $\mathcal{O}_K$ (the ring of integers of $K$)?  Should I take norms?
I know that an integral basis for $K$ is given by $1,\theta,\theta^2/13.$

REPLY [7 votes]: Taking norms is not the best technique, since it can return false negatives.  (E.g. in $\mathbb Z[i]$, the elements $2-i $ and $2+i$ are coprime, but they both
have norm equal to $5$.)
The simplest approach is to just reduce one of them modulo the other and see
what happens.
In your case it makes sense to reduce the second factor modulo the first,
since the first is evidently simpler.  Since $x \equiv 7^a 13^b \theta \bmod$
the first factor, we find that modulo this first factor, the second factor
is equal to
$3 \cdot 7^{2 a} 13^{2 b} \theta^2.$
[This is an illustration of the general principle that if $x_0$ is
a root of $f(x)$, then $f(x) = (x - x_0)(f'(x_0) +$ terms divisible by $(x- x_0 ))$.  In your case, $f'(x_0) = 3 x_0^2$.]
So now you have to ask yourself whether $3 \cdot 7^{2a} 13^{2b}$ has any
factor in common with $x  - 7^a 13^b \theta$.  Since $x$ is coprime to $7$ and $13$ by stipulation, the only common factor could be a divisor of $3$.
Now it makes sense to consider norms, since $3$ is a rational prime, and
so it has a factor in common with $x - 7^a 13^b$ precisely if it divides the
norm of this element.  The norm is equal to $x^3 - 7^{3a+1}13^{3b+2}.$
Modulo $3$ this is equal to $x - 1$, so if $x \not\equiv 1\bmod 3$ then
your two factors are coprime, while if $x \equiv 1 \bmod 3$ then they are
not coprime.


TITLE: Permutations of cards with no adjacent pairs
QUESTION [5 upvotes]: We have a standard 52-card deck, and are looking at the possible shuffles/permutations of this deck. However, we have rubbed off the suits
  from the cards, so for every rank (aces, tens, etc.) all 4 cards are indistinguishable. Furthermore, if we can transform one permutation into another just by relabeling ranks, we regard the permutations as equal. For example, looking at the first 6 cards, A52343 and 5234A4 are to be counted as the same permutation.
Two cards of the same rank cannot be adjacent to each other, so
  AA2343... is not permissible (adjacent aces). We can assume the first and
  last card are adjacent to make the question easier.
How many distinct permutations exist of the 52-card deck?

My attempt:
Let us assume the first card is an ace of diamonds. We generally have $52!$ permutations for a deck of cards. However, since all suits are equal, we have $\frac{52!}{3!}$. All ranks are symmetrical, so we have $\frac{52!}{3!\times12!}$.
I'm not sure how to take into account the adjacent pairs rule.
P.S.
I have almost no knowledge of combinatorics, I asked because of this answer by @RobWatts.

REPLY [1 votes]: Ignoring your no neighboring pairs rule, and assuming that you have a unique starting point, there are $\frac {52!}{4!^{13}13!}=14778213400262135041705388361938994140625\approx 1.5\cdot 10^{40}$ permutations.  The $52!$ is the number of orders of a complete deck.  We divide by $4!=24$ for each rank, as we can put the four cards in any order. We divide by $13!$ for your equivalence of ranks-we can just list the ranks in the order of the first time we see each one.
I don't see an easy way to incorporate the neighboring pairs rule exactly.  I will make the incorrect but probably not far wrong assumption that the event of one pair matching is independent of any other pair matching.  The chance that one given pair matches is $\frac 3{51}=\frac 1{17}$ because having drawn the first card there are $3$ matching cards out of the remaining $51$ cards.  The chance that a given permutation has no matches is then $(\frac {16}{17})^{52}\approx 0.042746$, giving about $6.3171\cdot 10^{38}$ permutations matching your requirements.


text:
\section{Autoencoder}\label{sec:ae}

Usually, an \ac{AE} in the context of communications consists of two neural networks (encoder and decoder) with a penalty layer in between, which, in our case, is the optical channel. Its goal is to encode the input information, such that it can be decoded with minimal loss after having passed the penalty. One problem concerning this approach is that the encoding network is hard to interpret. Hence, we have designed an architecture for the \ac{AE} that follows along the lines of classic communication, meaning that it has a classic communication structure while specific parameters may be learned. Those trainable parameters are
\begin{itemize}
	\item the mapping of symbol indices $\mathbf{s}$ to \ac{IQ}-symbols $\mathbf{c}$, i.e., embedding $\mathbf{W}$, and
	\item the pulse-shaping FIR-filter, i.e., its filter-taps $\mathbf{F}$
\end{itemize}
Fig. \ref{fig:ae-tx} shows the trainable \ac{TX}-\ac{DSP}-implementation of the \ac{AE}. Akin to a conventional system, first, it maps the integer symbol indices $\mathbf{s} \in \mathcal{M}^{N_\mathrm{B}}$ to complex \ac{IQ}-symbols. This corresponds to a simple lookup in a trainable embedding matrix $\mathbf{W} \in \mathbb{R}^{M \times 2}$ where $s_m$ ($m = 1,\,\ldots,\,{N_\mathrm{B}}$) determines the row of the matrix, of which the first column is the real and the second column the imaginary part of the resulting \ac{IQ}-sample. Here, $s_m$ is the $m$-th element of $\mathbf{s}$. After normalization, these \ac{IQ}-constellation symbols $\mathbf{c}$ shall be analyzed later to compare them with a classic 256-\ac{QAM} constellation. It follows an upsampling to simulation sampling rate $f_\mathrm{sim}$. The idea behind this is that the encoding \ac{DSP} shall be able to really learn a pulse-shaping, that we can visualize easily. With this, we try to make the encoder easier to understand, knowing that this increases the complexity but not its degree of freedom. Again, equivalently to a classic scheme, it follows a trainable pulse-shaper $\mathbf{F}$ that allows jointly learning of
\begin{itemize}
	\item a bandwidth-limitation to avoid information- or \ac{SNR}-loss by the \ac{LPF},
	\item a pulse-shape that propagates with little distortions, and
	\item a simple and low-level diversity coding, such that information may be distributed over time.
\end{itemize}
At last, the filtered signal undergoes an additional \ac{LPF} and a power-normalization with power $P$ to finally obtain the \ac{TX}-signal $\mathbf{x}$. The \ac{LPF} seems to be redundant as part of the pulse-shaping (see \ac{DAC} of the channel) and hence does not affect the overall performance of the system. Nevertheless, only the block-sequence \ac{LPF} first, and normalization second prevents the \ac{AE} from intentionally wasting power in the outside-bandwidth-regime\footnote{In case the normalization comes first, the \ac{LPF} would extract only a portion of the configured input power $P$.}, thus reducing the effective input power $P$, the influence of \ac{KNL} and hence manipulating the \ac{SNR}-definition. Further, this sequence of execution is necessary to preserve the gradient flow for frequencies outside $B_\mathrm{w}$, and hence to prevent the \ac{AE} from retaining high frequencies from the filter-weight-initialization. As the \ac{DAC}'s \ac{LPF} is fixed and as we do not want to add a normalization within the channel, we were forced to add an \ac{LPF} in the \ac{TX}-\ac{DSP}.

As shown in Fig. \ref{fig:ae-rx}, on the receiver side a \ac{DNN} with layers described in Tab. \ref{tab:rx-dnn} shall demap the received samples $\mathbf{y}_\mathrm{sam} \in \mathbb{C}^{N_\mathrm{B}}$ to the estimated sent symbol indices $\mathbf{\hat{s}} \in \mathcal{M}^{N_\mathrm{B}}$, where $\mathbf{y}_\mathrm{sam}$ again is the downsampled received signal $\mathbf{y}$. Therefore, it has not only access to the corresponding single sample, but also to its temporal neighbors. As shown in Fig. \ref{fig:ae-rx}, after downsampling the received signal, a sliding window of length $2N_\mathrm{adj}+1$ parallelizes the sequentially received samples to a matrix $\mathbf{Y}_\mathrm{adj}$. Hence, the input of the \ac{DNN} is a single row of $\mathbf{Y}_\mathrm{adj}$. With parameter $N_\mathrm{adj}$ we control the number of single-side neighbors.

\begin{table}[h]
	\caption{\ac{RX}-\ac{DNN}-configuration}
	\begin{center}
		\begin{tabular}{c|c|c}
			\textbf{Layer}&\textbf{Neurons}&\textbf{Activation function} \\
			\hline
			&& \\
			1&2048&$\mathrm{elu}$ \\
			2-6&512&$\mathrm{elu}$ \\
			7&256&$\mathrm{softmax}$ \\
		\end{tabular}
		\label{tab:rx-dnn}
	\end{center}
\end{table}

Finally, the \ac{AE} is trained, such that the cross-entropy between the conditional \acp{PMF} of the labels and estimates is minimized. One can show that this optimization maximizes the spoken \ac{MI}.


TITLE: Parameterization of a curve of intersection between paraboloid and parabolic cylinder.
QUESTION [1 upvotes]: Find a parameterization of the curve of intersection of the paraboloid $z=4x^2 + y^2$ and the parabolic cylinder $y=x^2$

I understand that we need to find a map $M:\mathbb{R} \to \mathbb{R^3}$ such that $\{M(t):t \in \mathbb{R}\} = \{(x,y,z)\in \mathbb{R^3}:y=x^2 \, \wedge \, 4x^2 + y^2=z\}$
Let $x = \sqrt{t}$. Then $y=t$ and $z=4t+t^2$
The we get $$\vec{r}(t)=\begin{pmatrix}\sqrt{t} \\ t^2  \\ 4t+t^2\end{pmatrix}$$  for $\forall \,  t \in \mathbb{R}$
I would like to know if this is acceptable because I've seen similiar questions on this website with answers given in trigonometric form. I don't know how to write $\vec{r}(t)$ in terms of $\cos$ and $\sin$.

REPLY [4 votes]: Square root is not a good idea. You lose half curve
Solve
$
\left\{
\begin{array}{l}
 z=4 x^2+y^2 \\
 y=x^2 \\
\end{array}
\right.
$
$
\left\{
\begin{array}{l}
 x= t\\
 y =t^2\\
 z=4 t^2+t^4
\end{array}
\right.$
I got this nice image,


TITLE: Finding basis of quotient vector space $V/W$ not by extending a basis of $W$
QUESTION [1 upvotes]: Let $V$ be a vector space and $W$ a subspace. I want to find a basis for $V/W$ without giving first a basis of $W$, extending it to a basis of $V$ and taking the classes of the added vectors (the standard way to do it).
Suppose $\{v_1,\ldots,v_n\}$ is a basis for $V$. Is the set of distinct classes in $V/W$ of the vectors $v_i$ a basis for $V/W$?
I can see this is a set of generators of $V/W$, but I can't prove linear  independence.

REPLY [1 votes]: Consider $V=\Bbb{R}^2$ with the standard basis $\{e_1,e_2\}$ and $W=\{(v_1,v_2)\in V:\ v_1=v_2\}$. Then the two standard basis vectors map to two distinct elements of $V/W$, which is one-dimensional, so they cannot be linearly independent.
A more general and perhaps simpler example; extend a basis for $W$ to a basis for $V$. Then all basis vectors of $W$ are mapped to $0$ in $V/W$, so the resulting set cannot be linearly independent.


TITLE: Calculating $\lim_{n\to\infty}\frac{\sum\limits_{i=0}^{n}{1.5}^i}{\sum\limits_{i=0}^{n}1}$
QUESTION [1 upvotes]: Given the sequence $\displaystyle{S_n}=\frac{\sum\limits_{i=0}^{n}{1.5}^i}{\sum\limits_{i=0}^{n}1}$
How can I calculate $\displaystyle\lim_{n\to\infty}S_n$ (or prove the divergence of this sequence)?
I believe that it can be achieved by analyzing $S_n-S_{n-1}$, but I'm not quite sure how.
Thanks

REPLY [2 votes]: Recall that $$\sum_{i=0}^n x^i = \frac{x^{n+1}-1}{x-1}$$ then $S_n$ can be written as $$S_n = \frac1n\frac{(3/2)^n-1}{3/2-1}$$
Now we see that $S_n$ is ratio of a function that is going to $\infty$ exponentially and a function that is going to $\infty$ linearly. Therefore $S_n \to \infty$.

REPLY [2 votes]: $P_n=\displaystyle \sum_{i=0}^{n}1.5^i=\dfrac{1-1.5^n}{1-1.5}=-2+2\cdot1.5^n.$ See geometric series.
$Q_n=\displaystyle \sum_{i=0}^{n}1=n-0+1=n+1.$
So: $\displaystyle\lim_{n\to\infty}S_n=\lim_{n\to\infty}\dfrac{P_n}{Q_n}=\infty.$ Since $\displaystyle\lim_{n\to\infty}\dfrac{\exp(n)}{n}=\infty$.