text:
\begin{document}
\maketitle

\begin{abstract}
We investigate properties of random mappings whose core is composed of derangements as opposed to permutations. Such mappings arise as the natural framework to study the Screaming Toes game described, for example, by Peter Cameron. This mapping differs from the classical case primarily in the behaviour of the small components, and a number of explicit results are provided to illustrate these differences.
\end{abstract}

\noindent {\bf Keywords: } Random  mappings, derangements,  Poisson approximation, Poisson-Dirichlet distribution, probabilistic combinatorics, simulation, component sizes, cycle sizes

\noindent {\bf MSC:} 60C05,60J10,65C05, 65C40

\section{Introduction}
The following problem comes from Peter Cameron's book, \cite[p. 154]{cameron_notes_2017}.
\begin{quotation}
\noindent \emph{$n$ people stand in a circle. Each player looks down at someone else's feet (i.e., not at their own feet). At a given signal, everyone looks up from the feet to the eyes of the person they were looking at. If two people make eye contact, they scream. What is the probability $q_n$, say, of at least one pair screaming?}
\end{quotation}
The purpose of this note is to put this problem in its natural probabilistic setting, namely that of a random mapping whose core is a derangement, for which many properties can be calculated simply. We focus primarily on the small components, but comment on other limiting regimes in the discussion.

We begin by describing the usual model for a random mapping. Let $B_1,B_2,\ldots,B_n$ be independent and identically distributed random variables satisfying
\begin{equation}\label{Bdef}
\mathbb{P}(B_i = j) = 1/n, \quad j \in [n],
\end{equation}
where $[n] = \{1,2,\ldots,n\}$. The mapping $f: [n] \to [n]$ is given by $f(i) = B_i$.
Components of the mapping are formed by iteration: $i$ and $j$ are in the same component if some iterate of $i$ equals some iterate of $j$; each component is a directed cycle of rooted, labeled trees. An example with $n = 20$, displayed in  Fig.~\ref{fig1}, is given by \\

\hskip -0.25in
\begin{tabular}{c|cccccccccccccccccccc}
$i$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\
$B_i$ & 2 & 14 & 7 & 1 & 7 & 19 & 17 & 11 & 10 & 13 & 2 & 14 & 9 & 8 & 19 & 10 & 6 & 16 & 6 & 19\\
\end{tabular}

\begin{figure}[htbp]
\centering
\includegraphics[width=0.6\textwidth]{rm20.eps}
\vskip -0.9in
\caption{A mapping graph on $n = 20$ vertices with no singleton cycles. This one has 3 components, of sizes 5, 7 and 8. There are 9 elements in cycles, which have length 3, 4 and 2 respectively. Figure produced by the {\sf R} igraph package~\cite{csardi2006}. }\label{fig1}
\end{figure}

\subsection{The components of a random mapping}
Denoting the number of components of size $j$ by $C_j(n), j=1,2, \ldots, n$, Harris~\cite{bh60} showed that the  probability that a random mapping  has $a_j$
components of size $j$ is
\begin{equation}\label{hsf}
\BP(C_j(n) = a_j, j=1,\ldots,n) = \bbbone\left\{\sum_{j=1}^n j a_j = n\right\}\, \frac{n!e^n}{n^n} \prod_{j=1}^n
\frac{\lambda_j^{a_j}}{a_j!},
\end{equation}
where
\begin{equation}\label{lambdaj}
\lambda_j = \frac{e^{-j}}{j} \sum_{i=0}^{j-1}\frac{j^i}{i!} = \frac{1}{j}\,\bbbp(\textrm{Po}(j) < j),
\end{equation}
 $\textrm{Po}(\mu)$ denoting a Poisson random variable with mean $\mu$. In particular, the probability that a mapping of size $n$ has a single component is
 $$
 s_n := \bbbp(C_n(n) = 1) = \frac{n! e^n}{n^n} \, \lambda_n.
$$
 It follows readily from (\ref{hsf}) that
\begin{eqnarray}\label{hsfmeans}
\BE C_j(n) & = & \frac{n!}{n^n} \frac{(n-j)^{n-j}}{(n-j)!}
e^j \lambda_j, \nonumber \\
& = & s_j \,\binom{n}{j} \left(\frac{j}{n}\right)^j \left( 1 - \frac{j}{n}\right)^{n-j}\quad j=1,2,\ldots,n.
\end{eqnarray}
A probabilistic interpretation of (\ref{hsfmeans}) is given in \cite{dep91}. Kolchin~\cite{kolchin1976} established that
$(C_1(n),C_2(n),\ldots) \Rightarrow (Z_1,Z_2,\ldots),$ where the $Z_i$ are independent Poisson random variables with means $\BE Z_i = \lambda_i.$
Many other properties of random mappings may be found, for example, in ~\cite{dep91}.

\subsection{The core of a random mapping}

Here we record some properties of the core of a random mapping, the set of elements that are in cycles.  Results (\ref{corenumber}) through (\ref{core1}) are classical; see, for
example,~\cite[p. 366]{bb85}. The number $N_n $ of elements in the core has  distribution
given by
\eq\label{corenumber}
\BP(N_n = r) = \frac{r}{n}\prod_{l=0}^{r-1}
\left(1 - \frac{l}{n}\right) = \frac{r}{n} \frac{n_{[r]}}{n^r}, \quad r=1,\ldots,n,
\en
where $n_{[j]} = n(n-1)\cdots (n-j+1).$ The mean of $N_n$ is
$$
\bbbe N_n   = \sum_{l=0}^{n-1} \frac{(n-1)_{[l]}}{n^l},

$$
and it follows directly from (\ref{corenumber}) that $N_n/\sqrt{n}$ converges
in distribution to a random variable with density function
$x e^{-x^2/2}, x >0$. We write $C_j^*(n)$ for the number of
cycles of size $j$ in the core of a random mapping, and let $C'_j(r)$
be the number of cycles of size $j$ in a  {\em uniform} random permutation
of $r$ objects. The joint law of the ${\cal L}(C_j^*(n))$ is given by
$$
{\cal L}(C_j^*(n)) = \sum_{r=1}^n \BP(N_n = r) {\cal L} (C'_j(r)),
$$
since, conditional on $N_n = r$ the random mapping restricted to its
core is a uniformly distributed permutation on those $r$ elements.
It follows that
\eq\label{blurb}
\BE C_j^*(n) = \frac{1}{j} \frac{n_{[j]}}{n^j}, \quad j=1,\ldots,n.

\en
For fixed $j$, $\BE C_j^*(n) \to 1/j$, and
\eq\label{core1}
(C_1^*(n),C_2^*(n),\ldots) \Rightarrow (Z_1^*,Z_2^*,\ldots)
\en
where $Z_j^*$ are independent Poisson random variables with mean $\BE Z^*_j =
1/j$.

\section{The Screaming Toes random mapping}

We return now to Cameron's setting. Label the players $1, 2, \ldots, n$, and form components by iteration: $i$ and $j$ are in the same component if some iterate of $i$ equals some iterate of $j$; components now describe how the players are looking at each other. The cycles in the core of the mapping indicate sets of players, say $i_1, \ldots,i_r$ for which $i_1 \to i_2 \to \cdots \to i_r \to i_1$ (where $\to$ denotes `looks at the feet of'), and the trees attached to any of the cyclic elements describe the sets of players who look from one to another, and finally to someone in a cycle. Each component has a single cycle, so that the number of components is the number of cycles in the core, and each cycle must have length at least two.
Fig.~\ref{fig1} provides an illustration.

We study the cycles in the core and the structure of the components of the mapping for the screaming toes game. We find the probability that there are $k$ screaming pairs (for $k = 1, 2, \ldots, \lfloor n/2 \rfloor)$ (see (\ref{c2n*law})), identify the structure of the random mapping itself, and derive some basic properties of the component sizes.  In the setting of (\ref{Bdef}), the $B_i$ are independent, but no longer identically distributed; we let
\begin{equation}\label{Bdef1}
\mathbb{P}(B_i = j) = 1/(n-1), \quad j \in [n]\setminus \{i\}.
\end{equation}

The $B_i$ may be used simulate the modified mapping, which can be decomposed into components by iteration (as before), each of which is a directed cycle of rooted, labeled trees. In this case, though, the core of the mapping can have no cycles of length 1 and there are $p(n) = (n-1)^n$ such mappings. Note that the resulting combinatorial structure is not the same as a random mapping conditioned on having no singleton components, because such a conditioned structure may still have  singleton cycles in its core. We define $\tC_j(n)$ as the number of components of size $j$, and $\tC_j^*(n)$  the number of cycles of length $j$ in the core.

\subsection{The distribution of the component sizes}

We adopt the general approach from~\cite[Chapter 2]{arratia_logarithmic_2003}. A component of size $i \geq 2$ has $j = 2, 3, \ldots, i$ elements in its core. A modification of the counting argument that leads to (\ref{lambdaj}) then shows that the number of components of size $i$ is given by
$$
\tm_i := \sum_{j=2}^i \genfrac(){0pt}{}{i}{j}\, (j-1)! \, j i^{i-j-1} = (i-1)! \sum_{j = 2}^i \frac{i^{i-j}}{(i-j)!}
$$
It follows that for $i \geq 2$,
$$
\tm_i = (i-1)! \, e^i \, \sum_{l=0}^{i-2} \frac{e^{-i} i^l}{l!} = (i-1)! \, e^i \, \mathbb{P}({\rm Po}(i) < i-1).
$$
The joint law of $(\tC_2(n),\ldots,\tC_n(n))$ is therefore given by
\eq\label{jointlaw}
\BP(\tC_j(n) = a_j, j=2,\ldots,n) = \bbbone\left\{\sum_{j=2}^n j a_j = n\right\}\,
\frac{x^{-n} n!}{(n-1)^n}\,\prod_{j=2}^n \left(\frac{\tm_j x^j}{j!}\right)^{a_j} \frac{1}{a_j!},
\en
for any $x > 0$. Since the distribution in (\ref{jointlaw}) is independent of $x$, we are free to choose it and we make the choice $x = e^{-1}$, which results in the structure being \emph{logarithmic} in the terminology of \cite[p. 51]{arratia_logarithmic_2003}. We therefore define
\eq\label{lambdajhat}
\tlam_j = \frac{\tm_j e^{-j}}{j!} = \frac{1}{j}\,\bbbp(\textrm{Po}(j) < j-1), \quad j=2,3,\ldots
\en
which should be compared to that in (\ref{lambdaj}). The probability that a mapping of size $n$ has a single component is
\eq\label{singledeftoes}
\ts_n = \bbbp(\tC_n(n) = 1) = \frac{e^n n!}{(n-1)^n}\,\tlam_n,
\en
and
$$
\ts_n \sim e \sqrt\frac{\pi}{2}\,n^{-1/2} \approx 3.4069\, n^{-1/2}, \quad n \to \infty.
$$
\subsubsection{Moments}

The falling factorial moments of the component counts are readily calculated from (\ref{jointlaw}), to obtain
\eq\label{jointmeans}
\mathbb{E}(\tC_2^{[r_2]} \cdots \tC_b^{[r_b]}) = \tlam_2^{r_2} \cdots \tlam_b^{r_b} \,
e^m n_{[m]} \frac{(n-m-1)^{n-m}}{(n-1)^n},
\en

for $r_2, \ldots,r_b \geq 0$ satisfying $m = 2r_2 + \cdots + $ $b r_b \leq n$. It follows that, for $ j = 2,3,\ldots,n$,
\begin{eqnarray}
\mathbb{E} \tC_j(n) &  = & \tlam_j\, e^j\, n_{[j]} \frac{(n-j-1)^{n-j}}{(n-1)^n} \nonumber \\
& = & \ts_j \binom{n}{j} \left(\frac{j-1}{n-1}\right)^j\, \left( 1 - \frac{j}{n-1}\right)^{n-j}, \label{cjmeans}
\end{eqnarray}
which also admits a simple probabilistic justification. A numerical example is given in Table~\ref{tab2}. The covariances may be found from (\ref{jointmeans}): for $i+j \leq n$,
\eq\label{ecicj}
\bbbe \tC_i(n) \tC_j(n) = \ts_i \ts_j \binom{n}{i,j} \left(\frac{i-1}{n-1}\right)^i \left(\frac{j-1}{n-1}\right)^j \left(1 - \frac{i+j}{n-1}\right)^{n-i-j},
\en
the value being 0 when $i+j > n$. The expected value of the number of components $\tK_n = \tC_2(n) + \cdots + \tC_n(n)$ is
\eq\label{ekn}
 \bbbe \tK_n = \sum_{j=2}^n \tlam_j\, e^j \, n_{[j]} \frac{(n-j-1)^{n-j}}{(n-1)^n}.
\en

\subsubsection{Limit distributions}

Following \cite[p.48]{arratia_logarithmic_2003}, the joint law of an assembly such as the screaming toes mapping $(\tC_2(n),\ldots,\tC_n(n))$ may also be represented as that of $(\tZ_2,\ldots,\tZ_n)$ conditional on
\eq\label{t1ndef}
T_{1n} := 2\tZ_2 + 3 \tZ_3 + \cdots + n\tZ_n = n,
\en
where the $\tZ_i$ are independent Poisson random variables with $\bbbe \tZ_j = \tlam_j, j \geq 2,$ given in (\ref{lambdajhat}) and it follows from~\cite[Chapter 3]{arratia_logarithmic_2003}, or directly from (\ref{jointmeans}), that the counts of small components have, asymptotically,  independent Poisson distributions with means $\bbbe \tZ_j$ given above.

\section{The core of the Screaming Toes mapping}
The core of our mapping is composed of derangements, permutations with no fixed points. We use $^*$ to denote derangements, so that $C_j^*(n)$ is the number of cycles of length $j$ in a random uniform derangement of size $n$. We write
$$
D_n := n! \sum_{j=0}^n \frac{(-1)^j}{j!}
$$
to denote the number of derangements of $n$ objects; the probability that a random permutation is a derangement is $D_n / n!$.

\ignore{
\begin{remark}
By counting permutations by their number of fixed points, we recover the fact that
$$
n! = \sum_{i=0}^n {n \choose i} D_{n-i}, \quad n=1,2,3,\ldots
$$
\end{remark}
\note{Reminder: it is clear that
$$
\sum_{n \geq 0} \frac{D_n}{n!} x^n = \frac{e^{-x}}{1 - x}.
$$}
}

We record two results for future use:
\eq\label{ecjn*}
\BE C_j^*(n) = \frac{1}{j} \frac{n!}{D_n} \frac{D_{n-j}}{(n-j)!}, j = 2,3,\ldots,n.
\en
and, for a random permutation,
\eq\label{prob0k}
\bbbp(C_1(n) = 0, C_2(n) = k)

 =  \left(\frac{1}{2}\right)^k \frac{1}{k!} \sum_{l = 0}^{\lfloor n/2 \rfloor - k} (-1)^{l}
    \left(\frac{1}{2}\right)^{l}\frac{1}{l!} \frac{D_{n - 2 l -2k}}{(n - 2 l-2k)!}
\en
\ignore{
When $k = 0$, this reduces to
\eq\label{prob00}
\mathbb{P}(C_1(n) = 0, C_2(n) = 0) =  \sum_{l = 0}^{\lfloor n/2 \rfloor} (-1)^{l}
    \left(\frac{1}{2}\right)^{l}\frac{1}{l!}\, \frac{D_{n - 2 l}}{(n - 2 l)!}
\en
}
(\ref{prob0k}) follows from \cite[Eq. (1.9)]{arratia_logarithmic_2003}, and the well-known (\ref{ecjn*}) is derived in the context of $\theta$-biased random derangements (with $\theta = 1$) in \cite{dasilva2020}.

\subsection{The number of 2-cycles in the core}
In this section, we look in more detail at the cycles in the core of the mapping.
We begin with  some properties of the number $N_n$ of elements in the core of a standard random mapping. If we define
$\pi_k = \prod_{l=0}^{k} \left( 1-\frac{l}{n}\right) = (n-1)_{[k]}/n^k$
then $n \pi_k = (n-k) \pi_{k-1}$ for $k = 1, 2, \ldots, n-1.$ Hence
$\pi_{k-1} - \pi_k = k\pi_{k-1}/n$, and it follows from (\ref{corenumber}) that, for $j = 1, 2, \ldots, n,$
\begin{equation}\label{identity}
\mathbb{P}(N_n \geq j) = \sum_{k=j}^n \frac{k \pi_{k-1}}{n} = \sum_{k=j}^n (\pi_{k-1} - \pi_k) = \pi_{j-1} - \pi_n = \pi_{j-1}.
\end{equation}
\ignore{
As a consequence, we recover the well-known fact that
$$
\bbbe N_n  =  \sum_{l=1}^{n} \BP(N_n \geq l) =  \sum_{l=1}^{n} \pi_{l-1} =
\sum_{l=0}^{n-1} \prod_{j=0}^l \left(1 -\frac{j}{n}\right) = \sum_{l=0}^{n-1} \frac{(n-1)_{[l]}}{n^l}.
$$
}

To find the distribution of the number $\tC_2^*(n)$ of 2-cycles in the core, we make use of the following result.
\begin{lemma}\label{lem1}
For any $n \geq 2$ and $m = 1,2,\ldots,n$ we have
\eq\label{needtoshow}
\left(\frac{n}{n-1}\right)^n \,\sum_{r = m}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_{r - m}}{(r - m)!} = \frac{n_{[m]}}{ (n-1)^{m}}
\en
\end{lemma}

\begin{proof}
We have
\begin{eqnarray*}
\sum_{r = m}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_{r-m}}{(r-m)!} & = & \sum_{r = m}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \sum_{j = 0}^{r-m} \frac{(-1)^j}{j!}\\
& = & \sum_{j=0}^{n-m} \frac{(-1)^j}{j!} \, \sum_{r = m+j}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \\
& = & \sum_{j=0}^{n-m} \frac{(-1)^j}{j!} \,\BP(N_n \geq m+j) \qquad \textrm{ from }(\ref{corenumber}) \\
& = & \sum_{j=0}^{n-m} \frac{(-1)^j}{j!} \,\frac{n_{[m+j]}}{n^{m+j}} \qquad \textrm{ from }(\ref{identity}) \\
& = & \frac{n_{[m]}}{n^m} \, \sum_{j=0}^{n-m} \frac{(-1)^j}{j!}\,\frac{(n-m)!}{(n-m-j)!}\frac{1}{n^j} \\
& = & \frac{n_{[m]}}{n^m} \,\sum_{j=0}^{n-m} \genfrac(){0pt}{}{n-m}{n-m-j} \left(-\frac{1}{n}\right)^j \\
& = & \frac{n_{[m]}}{n^m} \left(1 - \frac{1}{n}\right)^{n-m}
\end{eqnarray*}

It follows that the left side of (\ref{needtoshow}) is
$$
\left(\frac{n}{n-1}\right)^n \, \frac{n_{[m]}}{n^m} \left(\frac{n-1}{n}\right)^{n-m} = \frac{n_{[m]}}{(n-1)^m},
$$
which establishes Lemma~\ref{lem1}.
\end{proof}

\begin{lemma}\label{lem2}
For $k=0,1,\ldots,\lfloor n/2 \rfloor,$
\eq\label{c2n*law}
\BP(\tC_2^*(n) = k) = \left(\frac{1}{2}\right)^k \frac{1}{k!} \sum_{l = 0}^{\lfloor n/2\rfloor - k} (-1)^l  \left(\frac{1}{2}\right)^l \frac{1}{l!}\,\frac{n_{[2l+2k]}}{(n-1)^{2l + 2k}}.
\en
\end{lemma}
\begin{proof}
 It follows by conditioning that the number $\tN_n$ in the core of the mapping with no singleton cycles has distribution
\begin{eqnarray}
\BP(\tN_n = r)&  = & \BP(N_n = r) \frac{D_r}{r!} \big/ \left( \frac{n-1}{n}\right)^n
\nonumber \\
& = & \left(\frac{n}{n-1}\right)^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_r}{r!}, r = 2, 3, \ldots,n. \label{toescore}
\end{eqnarray}
The law of the number of 2-cycles in the core is therefore given by
$$
\BP(\tC_2^*(n) = k) =\sum_{r=2k}^n \BP(\tN_n = r)
 \times \bbbp(\textrm{random derangement of size }r\textrm{ has }k \textrm{ 2-cycles}),
$$
and the latter probability can be found via (\ref{prob0k}) with $n$ there replaced by $r$. We obtain, after some simplification,
\begin{eqnarray*}
\BP(\tC_2^*(n) = k) & = & \left(\frac{n}{n-1}\right)^n  \frac{2^{-k}}{k!}\, \sum_{r=2 k}^n \frac{r}{n} \frac{n_{[r]}}{n^r}
\,  \sum_{l = 0}^{\lfloor r/2 \rfloor - k} (-1)^{l} \left(\frac{1}{2}\right)^{l}\frac{1}{l!}\, \frac{D_{r - 2 l -2k}}{(r - 2 l-2k)!}  \\
& = &  \frac{2^{-k}}{k!}\,\sum_{l = 0}^{\lfloor n/2 \rfloor - k} (-1)^{l} \left(\frac{1}{2}\right)^{l}\frac{1}{l!} \left(\frac{n}{n-1}\right)^n \sum_{r=2l+2k}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_{r - 2 l -2k}}{(r - 2 l-2k)!}.
\end{eqnarray*}
The term on the last line reduces to $n_{[2l+2k]}/(n-1)^{2l + 2k}$ by
using the identity in (\ref{needtoshow}), and completing the proof.
\end{proof}
A numerical example is given in Table~\ref{tab3}.

\subsubsection{Expected number of cycles of length $j$}
It is well known that the expected number of cycles of length $j$ in a standard random mapping core is
\eq\label{rmecjn*}
\bbbe C_j^*(n) = \sum_{r = j}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{1}{j} = \frac{1}{j} \BP(N_n \geq j) = \frac{1}{j} \frac{n_{[j]}}{n^j}, \quad j=1,\ldots,n;
\en
see (\ref{identity}) for the last step. For the screaming toes mapping, the expected number of cycles of length $j$ is, from (\ref{ecjn*}) and (\ref{toescore}),
\begin{eqnarray}
\BE \tC_j^*(n) & = & \left(\frac{n}{n-1}\right)^n\, \sum_{r  = j}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_r}{r!}\, \frac{1}{j} \frac{r!}{D_r}\frac{D_{r-j}}{(r-j)!} \nonumber \\
& = & \left(\frac{n}{n-1}\right)^n\, \frac{1}{j} \sum_{r = j}^n \frac{r}{n} \frac{n_{[r]}}{n^r} \frac{D_{r-j}}{(r-j)!} \nonumber \\
& = & \frac{1}{j} \frac{n_{[j]}}{(n-1)^j}, \label{ecjn*toes}
\end{eqnarray}
the final equality coming from (\ref{needtoshow}). Some numerical values are given in Table~\ref{tab1a}.

\begin{remark}
Since the number of components is equal to the number of cycles in the core, $\bbbe \tK_n$ may also be computed from (\ref{ecjn*toes}), to obtain
\eq\label{ekn2}
\bbbe \tK_n = \sum_{j=2}^n \frac{1}{j} \frac{n_{[j]}}{(n-1)^j},
\en
which should be compared to (\ref{ekn}). The equivalence of (\ref{ekn}) and (\ref{ekn2}) is illustrated for the case of $n = 10$ in Tables~\ref{tab2} and \ref{tab1a}.
\end{remark}

\subsection{Did anyone scream?}

Cameron's original problem was to show that the  probability that someone screams~is
\begin{equation}\label{pcresult}
q_n := \sum_{l = 1} ^ {\lfloor n/2 \rfloor} \frac{(-1)^{l-1} n_{[2l]}}{2^l l! (n-1)^{2l}},
\end{equation}
 and to find the limiting behavior of $q_n$ as $n \to \infty$.

We can identify $q_n$ because $\BP({\rm someone\ screams}) =  1 - \BP(\tC_2^*(n) = 0),$
so from Lemma~\ref{lem2},
$$
q_n = \BP(\tC_2^*(n) > 0) =  \sum_{l = 0}^{\lfloor n/2\rfloor} (-1)^{l-1} \left(\frac{1}{2}\right)^l \frac{1}{l!} \,\frac{n_{[2l]}}{(n-1)^{2l}},
$$
recovering (\ref{pcresult}). Representative values of $q_n$ are given in Table \ref{tab1}.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c||c | c |}
\hline
$n$ & $q_n$ & $n$ & $q_n$ \\
\hline
5 & 0.5664 & 60 & 0.4039 \\
10 & 0.4654 & 70 & 0.4023 \\
15 & 0.4386 & 80 & 0.4012 \\
20 & 0.4264 & 90 & 0.4003\\
30 & 0.4148 & 100 & 0.3996 \\
40 & 0.4093 & 1,000 & 0.3941\\
50 & 0.4060 & 10,000 & 0.3935\\
\hline
\end{tabular}
\caption{The probability $q_n$ from (\ref{pcresult}) of at least one screaming pair for various values  of $n$.}\label{tab1}
\end{center}
\end{table}

Finally, a word about the limiting value of $q_n$. It is straightforward to show that the joint law of $(\tC^*_2(n),\tC^*_3(n),\ldots)$ converges to that of independent Poisson random variables, the $j$th of which has mean $1/j$, just as in the standard mapping case.
In particular,
$$
\lim_{n \to \infty} q_n = 1 - \bbbp({\rm Po}(1/2) = 0) = 1 - e^{-1/2} \approx 0.3935.
$$

\ignore{
To establish the asymptotics of (\ref{pcresult}), we can use () and (\ref{toescore}) to see that for any fixed $b \leq n$, and $r_2, r_3, \ldots, r_b \geq 0$ satisfying $2 r_2+\cdots + br_b = m \leq n$,
\eq\label{mapcoremeans}
\mathbb{E}(C^*_2(n)^{[r_2]} \cdots C^*_b(n)^{[r_b]}) = \prod_{j=2}^b \left(\frac{1}{j}\right)^{r_j}\, \frac{n_{(m)}}{(n-1)^m},
\en
so that $C_2^*(n),\ldots,C_b^*(n))$ converges in distribution to independent Poisson components $(Z_2,\ldots,Z_n)$ where $\BE Z_i = 1/i$. (This result also follows directly from () $N_n^* \to \infty$ in probability.) Hence $q_n = \BP(C_2^*(n) > 0) \to 1 - e^{-1/2}$, as claimed in (\ref{qnlim}).
}

\section{Simulating the component counts}

It is often useful to be able to simulate combinatorial objects, for example to study the distributions of cycle lengths and component sizes for moderate values of $n$, where the asymptotics might not be good, or when asking more detailed questions where explicit answers are hard to come by. In our setting, there are (at least) two approaches to this.

\subsection{A rejection method}\label{rejmethod}

The first is useful for studying the component counting process $(\tC_2(n),\tC_2(n),\ldots)$, by exploiting a modification of the simulation approach in~\cite[Section 4]{arratia_simulating_2018}. For any $\theta > 0$, (\ref{jointlaw}) gives the distribution of $(\tC_2(n),\ldots,\tC_n(n))$  as
\begin{eqnarray*}
\bbbp(\tC_j(n) = a_j, j=2,\ldots,n) & \propto & \bbbone\left\{ \sum_{j=2}^n j a_j = n\right\}\, \prod_{j=2}^n \left(\frac{\omega_j}{j}\right) ^{a_j} \frac{1}{a_j!} \nonumber \\
& = & \bbbone\left\{ \sum_{j=2}^n j a_j = n\right\}\, \prod_{j=2}^n \left(
\frac{\omega_j}{\theta}\right)^{a_j}\, \prod_{j=2}^n  \left(
\frac{\theta}{j}\right)^{a_j} \frac{1}{a_j!} \nonumber \\
& = &  \prod_{j=2}^n \left(
\frac{\omega_j}{\theta}\right)^{a_j}\, \bbbone\left\{ \sum_{j=2}^n j a_j = n\right\}\,\prod_{j=2}^n  \left(
\frac{\theta}{j}\right)^{a_j} \frac{1}{a_j!},
\end{eqnarray*}
where $\omega_j = j \tlam_j = \bbbp({\rm Po}(j) < j-1)$ is given by (\ref{lambdajhat}). The last factorization shows that we can simulate $(a_2,\ldots,a_n)$ from the distribution
\eq\label{esfcondlaw}
\BP_\theta(a_2,\ldots,a_n) \propto \bbbone\left\{ \sum_{j=2}^n j a_j = n\right\}\,\prod_{j=2}^n  \left(
\frac{\theta}{j}\right)^{a_j} \frac{1}{a_j!}
\en
and, assuming $\theta$ can be chosen to make $\omega_j \leq \theta$ for $j = 2, 3, \ldots,n$,
we accept $(a_2,a_3,\ldots,a_n)$ as an observation from the required distribution with probability
$$
h(a_2,\ldots, a_n) = \prod_{j=2}^n \left( \frac{\omega_j}{\theta} \right)^{a_j}.
$$
The method relies on efficient simulation from (\ref{esfcondlaw}), which is precisely that of the counts $(C_1(n),\ldots,C_n(n))$ with the Ewens Sampling Formula with parameter $\theta$, conditional on $C_1(n) = 0$. For more information on this law in the context of $\theta$-biased derangements, see ~\cite{dasilva2020}.

From (\ref{lambdajhat}) we note that we may take $\theta = 1/2$. We implement the algorithm in a slightly different way, by simulating $(a_1,\ldots,a_n)$ from the regular Ewens Sampling Formula with parameter $\theta = 1/2$, and accepting $(a_2,\ldots,a_n)$ with probability
\eq\label{accrate}
h(a_1, a_2,\ldots, a_n) = \bbbone(a_1 = 0) \prod_{j=2}^n \left( \frac{\omega_j}{\theta} \right)^{a_j}.
\en

There are many ways to generate observations from the Ewens Sampling Formula with an arbitrary parameter $\theta$, for example by using the Chinese Restaurant Process or the Feller Coupling; we exploit the latter, and point the reader to the discussion in \cite{arratia_simulating_2018} about the efficiency of these methods.

\subsection{Estimating the acceptance probability}

To compute the asymptotic acceptance probability, we note that
$$
\mathbb{P}(\mbox{accept an observation}) = \mathbb{E} \left( \bbbone(C_1(n) = 0)\,  \prod_{j=2}^n ( 2 \omega_j)^{C_j(n)} \right),
$$
where  $(C_1(n),\ldots,C_n(n))$ has the Ewens Sampling Formula with parameter $\theta = 1/2$. The Poisson limit heuristic shows that this is asymptotically
\begin{eqnarray}
e^{-1/2}\,\prod_{j=2}^\infty \mathbb{E} (2\omega_j)^{Z_j}
& = &  e^{-1/2}\, \prod_{j=2}^\infty \exp\left( - \frac{1}{2j} \left( 1 - 2\omega_j \right) \right) \nonumber \\
& = & e^{- 1/2}\, \exp \left( - \sum_{j = 2}^\infty \frac{1}{j} \left(\frac{1}{2} -  \bbbp({\rm Po}(j) < j-1)\right)\right)  \nonumber \\
& = & \frac{1}{e} \,\frac{1}{\sqrt{2}}, \label{accrate1}
\end{eqnarray}
the last result following because the algorithm is effectively generating a standard random mapping, and accepting that mapping if its core is a derangement; from (\ref{toescore}), this has asymptotically probability $1/e$. In $10^6$ simulations of the case $n = 10$ the acceptance rate was estimated to be 0.247, in reasonable agreement with the limiting value of $\approx 0.260$ from (\ref{accrate}).

\begin{remark}
There is an appealing connection between the exponent in the right-hand term in (\ref{accrate1}),
\eq\label{rhterm}
\sum_{j = 2}^\infty \frac{1}{j} \left(\frac{1}{2} -  \bbbp({\rm Po}(j) < j-1)\right)
\en
and Spitzer's Theorem~\cite{fs1956}, which is described in detail in \cite[Theorem 1, p.612]{feller1970}. This may be used to evaluate the corresponding value for a \emph{standard} mapping,
$$
\sum_{j = 1}^\infty \frac{1}{j} \left(\frac{1}{2} -  \bbbp({\rm Po}(j) < j)\right) = \frac{1}{2} \log 2,
$$
as given for example in \cite[Eqn. (19)]{arratia_simulating_2018} and \cite{dep91}.
It follows that (\ref{rhterm}) is
\begin{eqnarray}
\lefteqn{
\frac{1}{2} \log 2 -\left(\frac{1}{2} - \frac{1}{e}\right) + \sum_{j=2}^\infty \frac{1}{j} \bbbp({\rm Po}(j)=j-1) }&& \nonumber \\
&= &  \frac{1}{2} \log 2 -\left(\frac{1}{2} - \frac{1}{e}\right) + 1 - \frac{1}{e} = \frac{1}{2} (1 + \log 2), \label{jfck}
\end{eqnarray}
the sum being the probability that a Borel distribution with parameter 1 is at least 2.
This provides the formal justification of (\ref{accrate1}).

\end{remark}

\subsection{Simulating component and core sizes}\label{jointmethod}

A rejection method can be used to study details of the cycle sizes in the core of a  mapping, by generating an observation $r$ from the distribution of $\tN_n$ in (\ref{toescore}), and then generating a random derangement of size $r$. While we do not illustrate this approach here, see~\cite{dasilva2020} for efficient methods for generating $\theta$-biased derangements.

The second approach simulates a random mapping with no singleton cycles in its core, as determined by the random variables in (\ref{Bdef1}), and processes the output using (for example) the {\sf R} igraph package \cite{csardi2006} to compute the component and core sizes. This provides a computationally cheap way to check the first approach, and provides a way to study aspects of the joint law of component and cycle sizes.

\subsection{Examples}
Here we illustrate some of the explicit results obtained above, and their corresponding simulated values, all in the setting of $n = 10$. Table~\ref{tab2} compares the mean number of components for the screaming toes mapping with the corresponding values for the regular mapping. The mean number of components is 1.251 for the screaming toes mapping, and 1.913 for the standard mapping.

\begin{table}[hbtp]
\begin{center}
\begin{tabular}{|c|cc||c|}
\hline
  & $\bbbe \tC_j(10)$  & Simulation &  $\bbbe C_j(10)$\\
$j$ & (\ref{cjmeans}) & &  (\ref{hsfmeans}) \\
\hline
  1 &         &        & 0.3874 \\
  2 &  0.0744 & 0.0745 & 0.2265 \\
  3 &  0.0771 & 0.0764 & 0.1680 \\
  4 &  0.0734 & 0.0734 & 0.1391 \\
  5 &  0.0699 & 0.0699 & 0.1235 \\
  6 &  0.0673 & 0.0676 & 0.1160 \\
  7 &  0.0654 & 0.0650 & 0.1150 \\
  8 &  0.0608 & 0.0607 & 0.1225 \\
  9 &  0.0000 & 0.0000 & 0.1489 \\
 10 &  0.7629 & 0.7633 & 0.3660 \\
 \hline

\end{tabular}
\caption{Mean number of components of sizes 1(1)10 for $n = 10$ for the screaming toes mapping, simulated values from $10^6$  realizations using the method in Section~\ref{rejmethod}, and the corresponding means for a standard mapping. }\label{tab2}
\end{center}
\end{table}

Table~\ref{tab3} illustrates the distribution of the number of screaming pairs, while Table~\ref{tab1a} compares the mean cycle counts for the screaming toes core, and the corresponding values for the standard core.
The mean number of cycles is 1.251 for the screaming toes mapping, and 1.913 for the standard mapping, the former in agreement with the results in (\ref{ekn}) and (\ref{ekn2}). Table~\ref{tab5} illustrates the distribution of the number of elements in the core.

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
 & $\BP(\tC_2^*(10) = k)$ & Simulation \\
$k$ &  (\ref{c2n*law}) & \\
\hline
  0 &  0.5346 &  0.5352 \\
  1 &  0.3809 &  0.3800 \\
  2 &  0.0789 &  0.0791 \\
  3 &  0.0055 &  0.0056 \\
  4 &  0.0001 &  0.0001 \\
  5 &  0.0000 &  0.0000 \\
 \hline
\end{tabular}
\caption{Distribution of the number of screaming pairs, from (\ref{c2n*law}), for $n = 10$. Simulated values from $10^6$  realizations of the method in Section~\ref{jointmethod}.}\label{tab3}
\end{center}
\end{table}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|cc||c|}
\hline
 & $\bbbe \tC_j^*(10)$  & Simulation & $\bbbe C_j^*(10)$\\
 $j$ &(\ref{ecjn*toes}) & &  (\ref{rmecjn*})\\
\hline
  1 &         &        &  1.0000\\
  2 &  0.5555 & 0.5555 &  0.4500\\
  3 &  0.3292 & 0.3292 &  0.2400\\
  4 &  0.1923 & 0.1920 &  0.1260\\
  5 &  0.1029 & 0.1024 &  0.0605\\
  6 &  0.0472 & 0.0474 &  0.0252\\
  7 &  0.0182 & 0.0181 &  0.0086\\
  8 &  0.0054 & 0.0053 &  0.0023\\
  9 &  0.0010 & 0.0010 &  0.0004\\
 10 &  0.0001 & 0.0001 &  0.0000\\
 \hline

\end{tabular}
\caption{Mean number of cycles of sizes 1(1)10 in the core for $n = 10$ for the screaming toes mapping, simulated values from $10^6$  realizations of the method in Section~\ref{jointmethod}, and the corresponding means for a typical random mapping. }\label{tab1a}
\end{center}
\end{table}

\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c|cc||c|}
\hline
 & $\bbbp(\tN_{10} = r)$  & Simulation & $\bbbp(N_{10} = r)$\\
 $r$ &(\ref{toescore}) & &  (\ref{corenumber})\\
\hline
  1 &         &        &  1.0000\\
  2 &  0.2581 & 0.257 &  0.1000\\
  3 &  0.2065 & 0.206 &  0.1800\\
  4 &  0.2168 & 0.217 &  0.2016\\
  5 &  0.1590 & 0.159 &  0.1512\\
  6 &  0.0958 & 0.096 &  0.0907\\
  7 &  0.0447 & 0.045 &  0.0423\\
  8 &  0.0153 & 0.015 &  0.0145\\
  9 &  0.0034 & 0.003 &  0.0033\\
 10 &  0.0004 & 0.0003 &  0.0004\\
 \hline
\end{tabular}
\caption{Probability distribution of the number of elements in the core for $n = 10$ for the screaming toes mapping, simulated values from $10^6$  realizations of the method in Section~\ref{jointmethod}, and the corresponding probabilities for a typical random mapping. }\label{tab5}
\end{center}
\end{table}

As a final example, we estimate, from  $10^6$ realizations of the simulation method in Section~\ref{jointmethod}, the probability that the screaming toes mapping with $n  10$ has no repeated component sizes  to be 0.959, no repeated cycle sizes to be 0.898, and no repeated component or cycle sizes to be 0.879.

\section{Discussion}
This paper has focused on the small components and cycles of the screaming toes mapping because that is where the main difference with the standard case emerge. We noted before
(\ref{lambdajhat}) that the screaming toes mapping is logarithmic, in that the Poisson random variables in (\ref{t1ndef}) satisfy
$$
i \bbbp(Z_i = 1) \to 1/2, \textrm{ and } i \bbbe Z_i \to 1/2 \textrm{ as } i \to \infty,
$$
this following from (\ref{lambdajhat}). As a consequence (\cite[Chapter 6]{arratia_logarithmic_2003}) the largest component sizes, when scaled by $n$, have asymptotically the Poisson-Dirichlet law with parameter $\theta = 1/2$, just as in a standard mapping. In a similar vein, the largest cycle lengths, when scaled by $\tN_n$, have asymptotically the Poisson-Dirichlet distribution with parameter $\theta = 1$, once more just as for the standard mapping core.

\ignore{
\begin{itemize}
\item I have tried to motivate the approach through its inherently probabilistic nature, rather than by ``counting" methods. It's a choice!
\item Could add central limit results, e.g. for number of components, if add things about total variation estimates to the independent Poisson limits. Probably a coupling proof of this with a regular r.m.?
\item It would be worth a look at joint laws of the component size counts and the cycle counts. Perhaps worth a separate look, even in the standard case?
\item It would be simple to add things about big components and the Poisson-Dirichlet laws.
\end{itemize}
}

\bibliography{amsrefs1}
\bibliographystyle{APT}

\noindent {\bf Acknowledgements: } I thank John Kingman for comments that led to the evaluation in (\ref{jfck}).
{\sf R} code for performing the computations described in the paper may be obtained from the author.

\end{document}


TITLE: What does it mean "Range"?
QUESTION [0 upvotes]: $c = 2 , x = Range[1,3,1] , y = c*x^2$
What is the answer?
I don't know how to solve. can anybody help me to solve?
Thanks.
EDIT
this's the result :
http://bit.ly/11PHGqG how this happen?

REPLY [2 votes]: The $x$, $y$, and $z$ in Range[x, y, z] are called the min, max, and step respectively.  It specifies the sequence of numbers
$$x, x + z, x + 2z, \ldots$$
which starts at $x$, increases by $z$ each time, and stops after reaching $y$.

REPLY [1 votes]: There really is no mathematical problem here.  I believe that the term Range in this context means that x ranges from 1 to 3 in steps of 1.  That is why Wolfram returned the values of 1, 2 and 3 for x. If you are supposed to find values for y, then y = 2, 8, and 18, respectively when x = 1, 2 and 3.


TITLE: Function that got positive derivative for all $x\neq 0$ And zero derivative for $x=0$ must be increasing on $\mathbb{R}$
QUESTION [1 upvotes]: I got this statement that I am trying to prove
Let $f:\mathbb{R}\to\mathbb{R}$ be a differentiable function such that for all $x\neq 0$, $f'(x)>0$ and for $x=0$, $f'(x)=0$, how do I prove that $f$ is increasing on $\mathbb{R}$ by the definition of increasing function.
My try: I showed that $f$ is increasing on $\mathbb{R}-\{0\}$ using the theorem on increasing functions and their derivatives, but at $x=0$ I came into difficulty and wasn't able to proceed that much (do I miss something, maybe MVT or Rolle's theorem ).
Some hints will be appreciated.

REPLY [3 votes]: There's a small trick. You've proved that for all $x,y$, if both are either positive or negative, then $x < y \implies f(x) < f(y)$. By the MVT you can also prove the claim if either $x$ or $y$ is zero. To conclude, you're left with the case $x < 0 < y$. But then you can apply the MVT on $[x,0]$ and $[0,y]$...
Small nitpick: you probably haven't shown that $f$ is increasing on $\mathbb{R} \setminus 0$. You have shown that it's increasing on $(-\infty, 0)$ and $(0, +\infty)$. This is different! Consider for example $f(x) = \dfrac{-1}{x}$.


TITLE: How to approximate a double integral numerically using the Simpson's Rule
QUESTION [2 upvotes]: .I'm trying to approximate the integral :
$$\int_{0}^{1} \int_{0}^{1} \ln(e^x+e^y+x+y)\, dx\,dy$$ with an error $\leq 10^{-4}$.
I tried to use the Simpson's rule, and trapezoidal rule.
But I had difficulty with this, since in these rules I have to find $n$ where $h=\frac{b-a}{n}$.
In these two rules we have a formula for the error, that includes a derivative of $f$ in a point (that belongs to $[a,b]$). But I could manage to how calculate $n$.
It is the first time for me to calculate this, so I apologize if I was not accurate.

REPLY [1 votes]: The double integral Composite Simpson's error term is given by
$$E = \dfrac{-(d-c)(b-a)}{180}\left[h^4 ~\mbox{max} \left(\dfrac{\partial^4f}{\partial x^4}\right) + k^4 ~\mbox{max} \left(\dfrac{\partial^4f}{\partial y^4}\right) \right]$$
For this particular problem, we will assume that we use an equal step size, that is $h = k = \frac{b-a}{n} = \frac{1-0}{n} = \frac{1}{n}$, which makes the error
$$E = \dfrac{-(d-c)(b-a)}{180 ~n^4}\left[~\mbox{max} \left(\dfrac{\partial^4f}{\partial x^4}\right) +  ~\mbox{max} \left(\dfrac{\partial^4f}{\partial y^4}\right) \right]$$
Our function is $f(x, y) = \ln(e^x+e^y+x+y)$, so we have
$\dfrac{\partial^4f}{\partial x^4} = -\dfrac{6 \left(e^x+1\right)^4}{\left(x+e^x+e^y+y\right)^4}+\dfrac{12 e^x \left(e^x+1\right)^2}{\left(x+e^x+e^y+y\right)^3}-\dfrac{4 e^x \left(e^x+1\right)}{\left(x+e^x+e^y+y\right)^2}+\dfrac{e^x}{x+e^x+e^y+y}-\dfrac{3 e^{2 x}}{\left(x+e^x+e^y+y\right)^2}$
$\dfrac{\partial^4f}{\partial y^4} = -\dfrac{6 \left(e^y+1\right)^4}{\left(x+e^x+e^y+y\right)^4}+\dfrac{12 e^y \left(e^y+1\right)^2}{\left(x+e^x+e^y+y\right)^3}-\dfrac{4 e^y \left(e^y+1\right)}{\left(x+e^x+e^y+y\right)^2}+\dfrac{e^y}{x+e^x+e^y+y}-\dfrac{3 e^{2 y}}{\left(x+e^x+e^y+y\right)^2}$
Using a numerical solver, the max of $\dfrac{\partial^4f}{\partial x^4}$ and $\dfrac{\partial^4f}{\partial y^4}$ over the region $0 \le x \le 1, 0 \le y \le 1$ is $-0.0186659$.
We want an $E \le 10^{-4}$, and have
$$E = -\dfrac{1}{180~ n^4}\left(-0.0186659 -0.0186659\right) = \frac{0.000207399}{n^4} \le 10^{-4}$$
This results in $n \ge 1.2$, and because we need an integer $n$, we choose $n = 2$, but this is not very satisfying as maybe we need to choose $n = 3$ or more.
Let's check this result, using Composite Simpson with $n = 2$, we get an error of $$|1.4562429599654196 - 1.4573986597429938| = 0.0011557 = 1.1157 \times 10^{-3}$$
That was pretty close, but if we had chosen $n = 3$, we have $E = 4.63677 \times 10^{-4}$, which aligns with the ask much better.
I think what this question is asking is for you to use $n = 2, 3, \ldots$ until you get a result that has a smaller error than required.
Update
This is the 2D-Simpson Formula I used above for the case $n = m = 2$
$h=\frac{b-a}{2 m}$
$k=\frac{b-a}{2 n}$
$X_{\text{i$\_$}}=a+h i$
$Y_{\text{j$\_$}}=a+j k$
$\int_{a}^{b} \int_{c}^{d} f(x, y)\, dx\,dy = \frac{1}{9} h k \left(4 \sum _{j=1}^n f\left(a,Y_{2 j-1}\right)+2 \sum _{j=1}^{n-1} f\left(a,Y_{2 j}\right)+4 \sum _{j=1}^n f\left(b,Y_{2 j-1}\right)+2 \sum _{j=1}^{n-1} f\left(b,Y_{2 j}\right)+4 \sum _{i=1}^m f\left(X_{2 i-1},c\right)+2 \sum _{i=1}^{m-1} f\left(X_{2 i},c\right)+4 \sum _{i=1}^m f\left(X_{2 i-1},d\right)+2 \sum _{i=1}^{m-1} f\left(X_{2 i},d\right)+16 \sum _{j=1}^n \left(\sum _{i=1}^m f\left(X_{2 i-1},Y_{2 j-1}\right)\right)+8 \sum _{j=1}^{n-1} \left(\sum _{i=1}^m f\left(X_{2 i-1},Y_{2 j}\right)\right)+8 \sum _{j=1}^n \left(\sum _{i=1}^{m-1} f\left(X_{2 i},Y_{2 j-1}\right)\right)+4 \sum _{j=1}^{n-1} \left(\sum _{i=1}^{m-1} f\left(X_{2 i},Y_{2 j}\right)\right)+f(a,c)+f(a,d)+f(b,c)+f(b,d)\right).$


TITLE: Why doesn't a hot air balloon burst even if we keep heating the air in balloon for a long time , shouldn't the air pressure become so high to resist?
QUESTION [1 upvotes]: I don't get one thing: we say a hot air balloon rises as hot air is less dense than  cooler air.
However, if the heat source continues to add heat to the air in the balloon, doesn't the hot air become so hot that pressure will be too high for the balloon to resist and burst? But it doesn't burst even if we continue to heat the air in balloon even for a long time?

REPLY [9 votes]: doesn't the hot air become so hot that pressure will be too high for the balloon to resist and burst?

If you have a sealed balloon, and you heat it enough, then yes.
Hot air balloons aren't sealed though. If the pressure gets too great, they can vent out of the opening where the flame goes.
Even with that though, you'd need to heat the air to the point where the balloon bursts.  There's a lot of air in a balloon, and a large surface area.  However much heat you put in, there's going to be an equilibrium point where you can't heat the balloon any more because all the heat you're putting in is dissipated into the surrounding (cooler) air.  You can (in principle) do the sums to find where that equilibrium point is, but the main thing to note is that if that equilibrium point is less than the pressure which would explode the balloon, then the balloon stays intact.

REPLY [3 votes]: The ideal gas law states that $PV=nRT$. In many cases you apply this to a closed system with a fixed quantity and volume of gas, so you often see that as temperature ($T$) increases, so does pressure ($P$). A hot air balloon is not sealed or pressurized, however - as the temperature increases, air escapes the balloon. If you consider just the air in the balloon, as $T$ increases, the number of air molecules in the balloon ($n$) decreases, resulting in a system of constant pressure and volume.
Air is forced out by a slight and transient pressure differential. Anytime the pressure in the balloon is higher than outside, air will flow through an opening in the balloon to equalize the pressure. The bigger the pressure differential, the faster air will flow to equalize the pressure, so the internal pressure is always close to (but perhaps slightly higher than) the external pressure, and in an equilibrium state, they are identical.


TITLE: Quadratic Variation of a square-integrable Lévy process
QUESTION [4 upvotes]: I am having a problem with the following question. I have tried using the definition of square integrable martingales and quadratic variation, but just can't seem to get anywhere. Can anybody offer me any assistance?

Let $(X_t)_{t \geq 0}$ be a square-integrable Lévy process. Show that $\langle X \rangle_t = t E(X_1^2)$ if $(X_t)_{t \geq 0}$ is a martingale.

I'm not sure how to proceed. If anyone can start me off, that'll be great.

REPLY [4 votes]: Hints:

Since $(X_t)_{t \geq 0}$ is a martingale and $X_0=0$, we have $\mathbb{E}(X_t)=0$ for all $t \geq 0$.
If a random variable $Y$ has finite second moment, then $$\mathbb{E}(Y) = \frac{1}{\imath} \frac{d}{d\xi} \chi(\xi) \bigg|_{\xi=0} \qquad \quad \mathbb{E}(Y^2) = -  \frac{d^2}{d\xi^2} \chi(\xi) \bigg|_{\xi=0}$$ where $\chi$ denotes the characteristic function of $Y$. Set $$\chi_t(\xi) := \mathbb{E}e^{\imath \, \xi X_t}.$$ Conclude from the Lévy-Khintchine formula that $$\chi_t(\xi) = (\chi_1(\xi))^t$$ and, by differentiating this expression, that $$\mathbb{E}(X_t^2) = t \mathbb{E}(X_1^2).$$
By the definition of $\langle X \rangle_t$, it suffices to show that $$M_t := X_t^2 - t \mathbb{E}(X_1^2)$$ is a martingale. To this end, fix $s \leq t$ and write $$\begin{align*} \mathbb{E}(M_t \mid \mathcal{F}_s) &= \mathbb{E}\big( ((X_t-X_s)+X_s)^2 \mid \mathcal{F}_s \big) - t \mathbb{E}(X_1^2)  \\ &= \mathbb{E}((X_t-X_s)^2 \mid \mathcal{F}_s) + 2  \mathbb{E}(X_s (X_t-X_s) \mid \mathcal{F}_s) + \mathbb{E}(X_s^2 \mid \mathcal{F}_s)- t \mathbb{E}(X_1^2). \end{align*}$$ Now use that $(X_t)_{t \geq 0}$ has independent increments (i.e. $X_t-X_s$ and $\mathcal{F}_s$ are independent), the stationarity (i.e. $X_t-X_s \sim X_{t-s}$) and step 2.


TITLE: How many injective functions are there from {1 2 3} to {4 5 6 7 8)?
QUESTION [3 upvotes]: My thoughts are that to find the number of injective functions, just multiply 3 and 5 together since there are 3 elements in the first set and 5 elements in the second. Is this the right way to approach this problem?

REPLY [4 votes]: This is called a Permutation of $n$ things taken $k$ at a time:
$$
P(n,k)=\underbrace{n(n-1)(n-2)\cdots(n-k+1)}_{k\text{ terms}}
$$
This says that there are $n$ ways of placing the first of $k$ items, $n-1$ to place the second, $n-2$ to place the third, and so on, until there are $n-k+1$ ways to place the $k^\text{th}$.
In your case, $n=5$ and $k=3$.

As commented by anorton, and mentioned in the link above, $P(n,k)$ is also commonly denoted by the Pochhammer symbol, $(n)_k$, and sometimes by the $k^\text{th}$ falling factorial, $n^{\underline{k}}$.


TITLE: Which textbook should I study?
QUESTION [0 upvotes]: I want to study calculus, but I should study highschool math first. Chepters like functions and inequalities. Wording, expression and description in Thomas' calculus and Anton Bivens Davis' early trascendentals books are very good. Could you recommend a high school math textbook as good as above mentioned books. Thanx.

REPLY [0 votes]: Larson Calculus is also a very good textbook. There is even a version of it that includes precalculus (Calculus I with Precalculus). I used Larson Calculus for both Calculus AB and BC. The examples are well explained, and the exercises are good practice problems, especially for tests. It is helpful for both the high school and college level calculus courses.


TITLE: Find $P(1 \le x < 3)$ if $X$ ~ $Binomial (100, 0.01)$
QUESTION [0 upvotes]: Here's my approach:
$n = 100 , $ p = 0.01
To find $P(1 \le x < 3)$, do I just find $P(X < 3) - P(1 \le X)$?

REPLY [0 votes]: To find $P(1 \le x < 3)$, you do $P(X < 3) - P(X<1)$ not $P(X < 3) - P(1 \le X)$ because
$$P(X<3) = P(X=0) + P(X=1) + P(X=2)$$
$$P(X<1) = P(X=0)$$
$$P(1 \le X) = P(X=1) + P(X=2) + P(X=3) + P(X=4) + ... + P(X=100)$$
$$\therefore, P(X < 3) - P(X<1) = P(X=1) + P(X=2)$$
and $P(X < 3) - P(1 \le X) < 0$ which is impossible if $P(X < 3) - P(1 \le X)$ is equal to the probability of some event which you guessed is $P(1 \le X < 3) = P(X < 3) - P(1 \le X)$


TITLE: Representing the cyclic differentiation pattern of $\frac{d^n}{dx^n}(\sin(x))$ using linear algebra.
QUESTION [2 upvotes]: It is known that the derivatives of $\sin(x)$ and $\cos(x)$ follow this pattern:
$$\frac{d^1}{dx^1}(\sin(x))=\cos(x)$$
$$\frac{d^2}{dx^2}(\sin(x))=-\sin(x)$$
$$\frac{d^3}{dx^3}(\sin(x))=-\cos(x)$$
$$\frac{d^4}{dx^4}(\sin(x))=\sin(x)$$
Motivated by the matrix representation of complex numbers. I thought one could interpret this pattern in the context of a coordinate plane and 90-degree rotations ($\sin$ rotates around to cosine, rotates around again to negative $\sin$, and so on for each derrivative). One can assign the following basis vectors for the space:
$$\mathbf{e}_{1}=\sin(x);\quad\mathbf{e}_{2}=\cos(x)$$
Thus a linear combination of a sine and cosine function relates to a vector in the following way:
$$C_1\sin(x)+C_2\cos(x)\equiv\begin{pmatrix} C_1 \\ C_2 \end{pmatrix}$$
The n'th derivative can be interpreted as the following matrix-vector product
$$\frac{d^n}{dx^n}(C_1\sin(x)+C_2\cos(x))\equiv\begin{pmatrix} \cos(\frac{n\pi}{2}) & -\sin(\frac{n\pi}{2}) \\ \sin(\frac{n\pi}{2}) & \cos(\frac{n\pi}{2})\end{pmatrix}\begin{pmatrix} C_1 \\ C_2 \end{pmatrix}
$$
So taking a derrivative is equivalent to rotating the vector representing the function by 90 degrees. I believe that the inner product would then be defined as:
$$\langle C_1\sin(x)+C_2\cos(x),C_3\sin(x)+C_4\cos(x)\rangle=C_1C_3+C_2C_4$$
Though this doesn't seem to have an immediately useful interpretation. If you let $(n\in\mathbb{R})$, then (using the sum of angles formula) a possible value for the fractional derivative of $C_1\sin(x)+C_2\cos(x)$ is given by:
$$\frac{d^{n}}{dx^{n}}(C_1\sin(x)+C_2\cos(x))=C_1\sin(x+\frac{n\pi}{2}) + C_2\cos(x+\frac{n\pi}{2}) $$
for $f(x)=C_1\sin(x)$ and $n=\frac{1}{2}$, one obtains:
$$\frac{d^{0.5}}{dx^{0.5}}(C_1\sin(x))=C_1\sin(x+\frac{\pi}{4}) $$
Which coincides with the answer given here. Has such a representation of the derivative of $\sin(x)$ been investigated before? What useful applications can be obtained from this interpretation? As a sidenote I am using the equivalence notation loosely so if there is a better way to write it let me know.

REPLY [2 votes]: $$
\pmatrix{\frac{d^nS}{dx^n} \\ \frac {d^nC}{dx^n}} =\pmatrix{0 & -1 \\ 1 & \ 0 }^n\pmatrix{S \\ C }$$

How did I come to above formula?

We can use the change of basis of vectors(thanks to $3$Blue$1$Brown YT channel)
We know $\frac {d^nS}{dx^n} = S(x + \frac {n\pi}{2})$ and same for $\frac {d^nC}{dx^n} = C(x + \frac {n\pi}{2})$
Here we note the fact that every time we differentiate the result we get is the rotating axis with $90^0$ that is $\hat i \text { lands on } \hat j$
thus the same keeps happening every time we are differentiating.
$\pmatrix {\cos\theta && \sin\theta\\-\sin\theta&&\cos\theta}_{\theta = \frac\pi2} = \pmatrix{0&&-1\\1&&0}$
Thus, for $n$th time we have
$$
\pmatrix{\frac{d^nS}{dx^n} \\ \frac {d^nC}{dx^n}} =\pmatrix{0 & -1 \\ 1 & \ 0 }^n\pmatrix{S \\ C }$$


TITLE: Is high school contest math useful after high school?
QUESTION [21 upvotes]: I've been prepping for a lot of high school math competitions this year. Will  all the math I learn would actually mean something in college? There is a chance that all of it will be for naught, and I just wanted to know if any of you people found the math useful after high school.
I do like what I'm learning, so it's not like I'm only prepping by forcing myself to.
EDIT: I'm not really sure what the appropriate procedure is to thank everyone for the answers. So... thanks! All of your answers were really helpful, and they motivated me a little more. However, I would like to make it clear that I wasn't looking for a reason to continue but rather just asking a question out of curiosity.

REPLY [7 votes]: Math competitions are great. You learn a lot.  It will make you a smart aggressive problem solver.    But be warned: that is not all there is.  As you continue your study of mathematics, you will see this is true in spades.


TITLE: If $A,B,A+I,A+B$ are idempotent matrices how to show that $AB=BA$?
QUESTION [3 upvotes]: If $A,B,A+I,A+B$ are idempotent matrices how to show that $AB=BA$ ?

MY ATTEMPT:
$A\cdot A=A$
$B\cdot B=B$
$(A+I)\cdot (A+I)=A+I$ or, $A\cdot A+A\cdot I+I\cdot A+I\cdot I=A+I$ which implies $A\cdot I+I\cdot A=0$ (using above equations)
$(A+B)\cdot (A+B)=A+B$ or,$A\cdot A+A\cdot B+B\cdot A+B\cdot B=A+B$ which implies $A\cdot B+B\cdot A=0$
What's next?

REPLY [4 votes]: Let $a$ and $b$ be elements of a (possibly noncommutative) ring. If $a$, $b$, $a+1$ and $a+b$ are idempotent, then $ab = ba$.
Proof. From $a^2 = a$ and $(a+1)^2 = a+ 1$ one gets $a^2 + a + a + 1 = a + 1$, whence $a^2 + a = 0$. Since $a^2 = a$, it follows that $a + a = 0$ and finally $a = -a$. Now, from $(a+b)^2 = a + b$ one gets $a^2 + ab + ba + b^2 = a + b$. Again, since $a^2 = a$ and $b^2 = b$, it follows $ab + ba = 0$, and since $a = -a$, we finally get $ab -ab= 0$, that is $ab = ba$.


TITLE: How do you find new speed of a object knowing the momentum and impulse?
QUESTION [1 upvotes]: I know that both momentum and impulse (change in momentum) are measured in kg m/s and the formula for momentum is mass x velocity and the formula for impulse is force x time. However I have a question regarding both of them in one question.
The question is this:
A force of 8.6N acted for 2.5s on an object of mass 1.8kg initially moving at 50m/s. Calculate the objects new speed.
Is there a formula for this type of question?
Also here is what I have worked out so far.
Impulse = 8.6N x 2.5s = 21.5 Ns or kgm/s
Initial momentum = 1.8 x 50 = 90 kgm/s
I am not sure where to go from here. Do I add the impulse and initial momentum (111.5) and divide by the mass to find the new speed? Is that how it works?
Thanks for all the help.

REPLY [1 votes]: Impulse = Change in momentum ,
hence : $F \cdot t = m \cdot \Delta v$
where $\Delta v = v_2-v_1$
And therefore $F \cdot t = m \cdot (v_2-v_1) $
So You have one equation with one unknown $(v_2)$ .
Can You proceed from here ?

REPLY [0 votes]: When force is integrated,
$$ F \Delta t = m \Delta v,$$
$$ 8.6  \cdot 2.5 = 1.8 ( v_{new}-50).  $$
from which $v_{new} $ can be found. It is assumed the mass of the object (unlike a rocket burning fuel) does not change.


TITLE: Reducibility of Cyclic groups
QUESTION [3 upvotes]: Let $G$ be the cyclic group $C_{4}$ and consider the 2-dimensional representations of G. Why does extending scalars to the complex numbers let this representation become reducible? I understand how it is irreducible over $\mathbb{R}$ by don't see how it is reducible for $\mathbb{C}$.

REPLY [1 votes]: A $G$ is finite and abelian, its irreducible complex representations are all of dimension $1$. As your representation is of dimension $2$ and as dimension does not change when you extend scalars to $\mathbb C$, the resulting representation cannot be irreducible!


TITLE: Is a subspace of a product space also a product space?
QUESTION [0 upvotes]: Suppose $V$ is a product space of connected and separable spaces $V_1,...,V_n$. Let $W$ be a subspace of $V$ with the subspace topology. Is $W$ then a product space of subsets of $V_1,...,V_n$?
My attempt: It is not a product space of subsets of $V_i$. Is $V=(\{a,b\}\times\{c,d\},\tau)$ with $\tau$ the product topology and $W=(\{(a,c),(b,d)\},\tau_W)$ with $\tau_W$ the subspace topology a suitable counterexample?

REPLY [0 votes]: Well, you could literally just write down every possible product of two subspaces, and see if any of them turn out to be $W$.


TITLE: What are "parity considerations" in deciding the form of the Hamiltonian?
QUESTION [3 upvotes]: In "introductory Quantum Optics", by Gerry and Knight, the Jeynes model is considered. In this model of electron-EM field interaction the electron is approximated by a two state system ($\lvert g\rangle$ and $\lvert e\rangle$), and the form of the dipole operator $\hat{d}$ is said to be constrained by parity consideration not to have on-diagonal terms:

Only the off-diagonal elements of the dipole operator are
  nonzero, since by parity consideration $\langle e\rvert\hat{d}\lvert e\rangle=0=\langle g\rvert\hat{d}\lvert g\rangle$.

Why? What does parity have to do with it?

REPLY [2 votes]: This comes from the microscopic origin of the model. For example, in the case of the hydrogen atom, the dipole operator is given by (up to some signs) $\hat d=e \hat z E$ where I have assumed that the electric field is in the direction $z$, and $\hat z$ is the position operator of the electron (of charge $-e$).
Let's now have a look at the effects of the parity operator $\hat \Pi$. We have $[\hat H,\hat \Pi]=0$, meaning that the eigenstates such that $\hat\Pi\,|g/e\rangle=\pm|g/e\rangle$ and we also have $\hat \Pi\, \hat z\,\hat \Pi=-\hat z$. It is thus easy to show that $\langle g/e|\,\hat z\,|e/g\rangle=0$ by symmetry, which answers the question.
Microscopically, one can show that the selection rule of the of the matrix elements of $\hat z$ between the eigenstates $|nlm\rangle$ of the hydrogen atom are such that $\langle nlm|\,\hat z \,|n\,'l\,'m\,'\rangle\propto \delta_{m,m'}\delta_{l,l\,'\pm1}$.


TITLE: Trigonometric identity for $a\sin 2x + b\sin(x+\alpha )$
QUESTION [3 upvotes]: The following is a known trigonometric identity,
$$a\sin x+b\sin(x+\alpha )=c\sin(x+\beta )\,$$
where
$$c=\sqrt {a^2+b^2+2ab\cos \alpha },\,$$
and
$$\beta =\arctan \left(\frac {b\sin \alpha }{a+b\cos \alpha }\right) + \begin{cases} 0 & \text{if } a+b \cos \alpha \geq 0,\\
\pi & \text{if } a+b\cos \alpha <0.\end{cases}$$
Is there an identity for the following ?
$$a\sin 2x + b\sin(x+\alpha )$$
Alternatively, can you find the values of $x$ that satisfy the following equation?
$$a\sin 2x - b\sin(x+\alpha )=0$$

REPLY [0 votes]: As for the last question:
\begin{align*}
a\sin2x-b\sin(x+\alpha)&=0 \\
2a\sin x\cos x - b(\sin x\cos\alpha + \cos x\sin\alpha)&=0\\
-b\cos\alpha\sin x &= \cos x \cdot(b\sin\alpha-2a\sin x) \\
\frac{-b\cos\alpha\sin x}{b\sin\alpha-2a\sin x} &= \cos x \\
\bigg( \frac{-b\cos\alpha\sin x}{b\sin\alpha-2a\sin x} \bigg)^2 &= \cos^2 x = 1-\sin^2x
\end{align*}
gives you an equation of degree $4$ in $\sin x$ that you can try to solve your favorite way. (You'll need to check any solutions against the original equation, since squaring both sides will introduce extraneous solutions.)


TITLE: Is $I(\omega_0) = J(\omega_0)$ for this homogeneous continuous-time Markov chain?
QUESTION [0 upvotes]: Assume $(X_t)_{t\ge 0}$ is a homogeneous continuous-time Markov chain on the probability space $(\Omega, \mathcal{G}, \mathbb{P})$. Moreover, $X_1(\omega_0) = X_2(\omega_0)$ for some $\omega_0 \in \Omega$. Consider two random variables:

$I = \inf \left\{t \geq 1 \mid X_t \neq X_1\right\}$
$J = \inf \left\{t \geq 2 \mid X_t \neq X_2\right\}$

I would like to ask if we can conclude $I(\omega_0) = J(\omega_0)$. Thank you so much for your help!

REPLY [0 votes]: I convert @lan's comment as answer to close this question.

As random variables? Definitely not. Nor are they necessarily the same for this particular $\omega_0$. Nor do they even necessarily have the same distribution, unless you also assume that $X_3$ is the same (because effectively you have a kind of "Brownian bridge" between time $1$ and $2$ that you don't have after time $2$).


TITLE: Let $I$ be an ideal of ring $R$ contained in another ring $S$: what is $IS$?
QUESTION [1 upvotes]: In fact, I know the definition of $IS=\{$linear combinations of ab with a in I and b in S$\}$ and that it is an ideal in $S$. I was wondering what is the most general framework this fitted into? e.g. I initially thought it was a product of $R$-algebras but $I$ isn't a ring. Nor can it be thought of as a product of $R$-modules as multiplication of $R$-modules doesn't make sense in the general case even when one is a subset of the other.
This type of thing appears all the time when studying ramification in number fields.

REPLY [1 votes]: Let $R \subset S$ be rings and $I$ and ideal in $R$.
Define $J$ to be the smallest ideal of $S$ which contains $I$ (equivalently you can define it as the intersection of all ideals of $S$ which contain $I$).
Then, it is an easy exercise to show that $I \cdot S =J$.


TITLE: Find sum of Series, Binomial Theorem
QUESTION [2 upvotes]: how would you find the sum of the series
$\sum_{n=1}^{\infty} \frac{\pi(\pi-1)...(\pi-n+1)}{2^nn!}$ I know that it relates to the binomial theorem but I'm having trouble finding thhe function that the series is derived for

REPLY [1 votes]: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{n = 1}^{\infty}
{\pi\pars{\pi - 1}\ldots\pars{\pi - n + 1} \over 2^{n}\, n!} & =
\sum_{n = 1}^{\infty}
{\pi! \over  n!\pars{\pi - n}!}\pars{1 \over 2}^{n} =
\sum_{n = 1}^{\infty}
{\pi \choose n}\pars{1 \over 2}^{n}
\\[5mm] & =
\bbx{\pars{1 + {1 \over 2}}^{\pi} - 1 = \pars{3 \over 2}^{\pi} - 1}
\approx 2.5744
\end{align}