
In this paper we study the inverse of socalled unfair permutations, and
explore various properties of them. Our investigation begins with comparing
this class of permutations with uniformly random permutations, and showing that
they behave very much alike for locally dependent random variables. As an
example of a globally dependent statistic we use the number of inversions, and
show that this statistic satisfies a central limit theorem after proper
centering and scaling. A secondary example of a globally dependent statistic to
be studied will be the number of fixed points. Finally, we introduce two
different generalizations of inverseunfair permutations.

The purpose of this paper is to analyze certain statistics of a recently
introduced nonuniform random tree model, biased recursive trees. This model is
based on constructing a random tree by establishing a correspondence with
nonuniform permutations, biased riffle shuffles. The statistics that are
treated include the number of nodes with a given number of descendants, the
depth of the tree, and the number of branches. The model yields the uniform
recursive trees as a certain limit, some new results for the uniform case are
obtained as well.

Thresholdtype counts based on multivariate occupancy models with log concave
marginals admit bounded size biased couplings under weak conditions, leading to
new concentration of measure results for random graphs, germgrain models in
stochastic geometry, multinomial allocation models and multivariate
hypergeometric sampling. The work generalizes and improves upon previous
results in a number of directions.

Let $(X_i)_{i \geq 1}$ and $(Y_i)_{i\geq1}$ be two independent sequences of
independent identically distributed random variables taking their values in a
common finite alphabet and having the same law. Let $LC_n$ be the length of the
longest common subsequences of the two random words $X_1\cdots X_n$ and
$Y_1\cdots Y_n$. Under a lower bound assumption on the order of its variance,
$LC_n$ is shown to satisfy a central limit theorem. This is in contrast to the
limiting distribution of the length of the longest common subsequences in two
independent uniform random permutations of $\{1, \dots, n\}$, which is shown to
be the TracyWidom distribution.

Let $\mathbf{X}^{(1)}_{n},\ldots,\mathbf{X}^{(m)}_{n}$, where
$\mathbf{X}^{(i)}_{n}=(X^{(i)}_{1},\ldots,X^{(i)}_{n})$, $i=1,\ldots,m$, be $m$
independent sequences of independent and identically distributed random
variables taking their values in a finite alphabet $\mathcal{A}$. Let the score
function $S$, defined on $\mathcal{A}^{m}$, be nonnegative, bounded,
permutationinvariant, and satisfy a bounded differences condition. Under a
variance lowerbound assumption, a central limit theorem is proved for the
optimal alignments score of the $m$ random words.

The tails of the distribution of a mean zero, variance $\sigma^2$ random
variable $Y$ satisfy concentration of measure inequalities of the form
$\mathbb{P}(Y \ge t) \le \exp(B(t))$ for $$ B(t)=\frac{t^2}{2( \sigma^2 + ct)}
\quad \mbox{for $t \ge 0$, and} \quad B(t)=\frac{t}{c}\left( \log t  \log \log
t  \frac{\sigma^2}{c}\right) \quad \mbox{for $t>e$} $$ whenever there exists a
zero biased coupling of $Y$ bounded by $c$, under suitable conditions on the
existence of the moment generating function of $Y$. These inequalities apply in
cases where $Y$ is not a function of independent variables, such as for the
Hoeffding statistic $Y=\sum_{i=1}^n a_{i\pi(i)}$ where $A=(a_{ij})_{1 \le i,j
\le n} \in \mathbb{R}^{n \times n}$ and the permutation $\pi$ has the uniform
distribution over the symmetric group, and when its distribution is constant on
cycle type.

Let $\mathbf{W}=(W_1,W_2,...,W_k)$ be a random vector with nonnegative
coordinates having nonzero and finite variances. We prove concentration
inequalities for $\mathbf{W}$ using size biased couplings that generalize the
previous univariate results. Two applications on local dependence and counting
patterns are provided.

We prove a central limit theorem for random sums of the form
$\sum_{i=1}^{N_n} X_i$, where $\{X_i\}_{i \geq 1}$ is a stationary
$m$dependent process and $N_n$ is a random index independent of
$\{X_i\}_{i\geq 1}$. Our proof is a generalization of Chen and Shao's result
for i.i.d. case and consequently we recover their result. Also a variation of a
recent result of Shang on $m$dependent sequences is obtained as a corollary.
Examples on moving averages and descent processes are provided, and possible
applications on nonparametric statistics are discussed.

This paper studies statistics of riffle shuffles by relating them to random
word statistics with the use of inverse shuffles. Asymptotic normality of the
number of descents and inversions in riffle shuffles with convergence rates of
order $1/\sqrt{n}$ in the Kolmogorov distance are proven. Results are also
given about the lengths of the longest alternating subsequences of random
permutations resulting from riffle shuffles. A sketch of how the theory of
multisets can be useful for statistics of a variation of top $m$ to random
shuffles is presented.