# Questions tagged [random-permutations]

The random-permutations tag has no usage guidance.

53
questions

5
votes

1
answer

206
views

### Non-adjacent permutations

Suppose we have an $N$ by $M$ table. Suppose that $x=(a,b)$ and $y=(c,d)$ are two locations in the table, specified by their row and column indexes. We say that (x,y) is horizontally adjacent if $c=...

2
votes

1
answer

203
views

### Sum of arrival times of Chinese Restaurant Process (CRP)

Suppose that a random sample $X_1, X_2, \ldots$ is drawn from a continuous spectrum of colors, or species, following a Chinese Restaurant Process distribution with parameter $|\alpha|$ (or ...

4
votes

0
answers

515
views

### Is the integer factorization into prime numbers normally distributed?

Edit:
Sorry, for the inconvenience: I have edited the question, since there was a misconception in my thinking.
Let $P_1(n) := 1$ if $n=1$ and $\max_{q\mid n, \text{ } q\text{ prime}} q$ otherwise, ...

0
votes

0
answers

97
views

### Expectation of the operator norm of projection of a random permutation matrix

Assuming I have a fixed dimension $p$ subspace of $\mathbb{R}^d$ orthogonal to $1^d$ and $VV^\top$ with $V \in \mathbb{R}^{d \times p}$ is the orthogonal projection to the subspace.
What bound can I ...

13
votes

2
answers

357
views

### Expected sorting time of random permutation using random comparators

In sorting networks, a comparator of positions $i < j$ is an operator which takes a permutation, checks if $p_i > p_j$, and if it is the case, swaps $p_i$ and $p_j$.
Using this, we can define ...

0
votes

0
answers

73
views

### Do finite exchangeable random sequences behave asymptotically independently?

Let $(X_{n,k})_{k=1,\ldots,n}^{n\in\mathbb{N}}$ and $(Y_{n,k})_{k=1,\ldots,n}^{n\in\mathbb{N}}$ be triangular arrays of row-wise exchangeable random variables, that is for any $n$ and permutation $\...

1
vote

1
answer

174
views

### What is the function defined by f(k) = #σ1({1,2,…,k})∩σ2({1,2,…,k})∩{1,2,…,k}, where σ1,σ2 are a uniformly random permutations of size N?

Thanks to David Pechersky excellent answer we know that
expectation of $ | σ({1,2,…,k}) ∩ \{1,2,…,k \} | \rightarrow k^2/N$ for σ uniformly random permutation over $N$.
What about the same ...

1
vote

1
answer

234
views

### What curve is defined by the formula $f(k) ={}$length of intersection of the first $k$ elements for two random permutations?

Let us fix $N$. Note that function $f$ defined below will satisfy $f(0)=0, f(N) = N$ and it is monotonically increasing (not strictly).
The code for the function seems to me more clear way to ...

1
vote

1
answer

98
views

### Popular algorithms (stopping rules) with output - a prefix of a permutation

What are some popular settings, when we look at the elements of a randomly generated permutation one by one, and we use certain stopping rule which, as a result gives us a prefix of the observed ...

4
votes

0
answers

89
views

### (Asymptotic) Cycle structure in a random permutation given total number of cycles?

A random $N$-permutation is the one drawn uniformly from all possible permutations on $N$ points.
We know that the expected number of cycles of length $\ell$ in a random $N$-permutation, $\mathbb{E}C_\...

2
votes

0
answers

131
views

### Random permutations constructed via randomly chosen transpositions

Given positive integers $k$ and $n$, we define the probability distribution $p_{n,k}$ on $S_n$ as:
$$
p_{n,k}(\sigma):=\frac{\#\{(\tau_1,\dots,\tau_s)\mid \sigma=\tau_1\dots\tau_s, \text{ each }\tau_i\...

2
votes

1
answer

311
views

### Law of large numbers for triangular arrays whose moments "look independent"

Let $(X_{n,k})_{k=1,\ldots,n}^{n\in\mathbb{N}}$ be a triangular array of random variables with finite moments of all orders, with no assumptions on their independence. Suppose that
$$
\mathbb{E}\left[\...

3
votes

1
answer

131
views

### Cycle counts in Ewens measure as $\theta$ diverges

For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...

0
votes

0
answers

79
views

### Relating sequence with or without replacement

I derived a relationship between sequences drawn with and without replacement for an application in genetics. The proof is easy enough, but I would rather find a source than provide a derivation of a ...

8
votes

2
answers

444
views

### Random permutations without double rises (avoiding consecutive pattern $\underline{123}$)

A permutation avoiding a consecutive pattern $\underline{123}$ is permutation
$\pi = \pi_1 \pi_2 \ldots \pi_n$ with the property that there does not exists $i \in [1, n-2]$
such that $\pi_i < \pi_{...

0
votes

0
answers

84
views

### What probability distribution is this?

Thank you in advance for any suggestions or feedback.
I have a discrete 1D probability distribution represented as a vector $\textbf{p}$, $p_i = p(x_i)$.
I am interested in finding the Wasserstein (...

5
votes

1
answer

229
views

### Dealing cards numbered $1$ to $n$ into piles

Is anything known about the following?
I hold in my hand a shuffled pack of cards numbered $1$ to $n$. One by one, I place them all, face up, on a table in piles. For each card I deal from my hand, ...

1
vote

0
answers

63
views

### About symmetric rank-1 random matrices

Consider a $2n-$dimensional symmetric random matrix $M$ of form, $M = \begin{bmatrix} aa^T & ab^T \\ ba^T & bb^T \end{bmatrix}$ where $a$ and $b$ are $n$ dimensional random vectors.
Are there ...

3
votes

2
answers

211
views

### Showing that the inverse of a function is approximately equivalent to $\frac{1}{n^{1/\alpha}}$

I'm currently working with someone on my PhD, and last week they asked me to check that a certain approximation holds as an exercise. Unfortunately, I couldn't figure out how to do it, and we've since ...

3
votes

0
answers

79
views

### Counting sets whose alternation is preserved by a permutation

Say a set $X \subseteq \{1,\ldots,n\}$ is alternating if successive elements of $X$ are of opposite parity. That is to say for any $x \in X$, if $y = \min \{z \in X \mid x < z\}$ then $x \not\...

3
votes

0
answers

82
views

### Number of cells in array covered by a random permutation

Consider a set $A \subseteq [n] \times [n]$ with $|A| = a = \alpha n$ for some $\alpha \in [0,1]$.
Suppose we select a permutation $\pi \in S_n$ uniformly at random. This permutation $\pi$ can also be ...

0
votes

0
answers

260
views

### Expected position in random permutation

Let $S$ be a set of $n$ numbers, and $\pi(x):S\rightarrow \left\{ 1,\ldots,n\right\}$ define a permutation. The position $p(x, \pi)$ of an element $x \in S$ in a given permutation $\pi$ is the sum of ...

4
votes

1
answer

194
views

### Rates of convergence to Tracy-Widom?

$\renewcommand{\!}{\mathbf}
\renewcommand{\Ai}{\operatorname{Ai}}$
One can define the Tracy-Widom distribution as the Fredholm determinant $F_2(t)=\det(\mathbf I-\mathbf A)$ where
$$\mathbf A(x, y)=\...

2
votes

1
answer

114
views

### How to turn a shuffled deck of card into bits

Suppose I fairly shuffle a deck of 52 playing cards, and I want to generate some bits. You could look at each pair of cards, see which is higher or lower, and output either a 0 or 1. That's 26 ...

1
vote

1
answer

122
views

### Tight estimates for binomial summation

Is there tight estimates for the following logarithmic summation ($\gamma\in(0,1)$)
$$\ln\Bigg(\sum_{t=\frac{n^{}}2-\gamma n^\gamma}^{\frac{n^{}}2+\gamma n^\gamma}\sum_{\ell=\frac{n^{}}2-\gamma n^\...

12
votes

2
answers

946
views

### How rare are unholey permutations?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...

4
votes

0
answers

211
views

### How frequent are permutations with small interleaving?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$.
Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...

1
vote

1
answer

196
views

### Can we order random variables in a measurable way in a general setup?

Let
$(\Omega,\mathcal A,\operatorname P)$ be a probability space
$(E,\mathcal E)$ be a measurable space
$n\in\mathbb N$
$X_1,\ldots,X_n$ be $(E,\mathcal E)$-valued random variables on $(\Omega,\...

4
votes

1
answer

192
views

### Generating bitstring combinations using a butterfly network

I'm using a butterfly network to generate a random combination of a bitstring of length $n$ and weight $w$. Let me clarify it with an example. Suppose I want a random bitstring of length 8 and Hamming ...

6
votes

1
answer

480
views

### Rank and frequency of permutations

(a) Let $[n] = \{1,\dotsc,n\}$, and let $\pi:[n]\to [n]$ be a permutation. Define an $n$-by-$n$ matrix $A=A(\pi)$ as follows: $A_{i,j}=1$ if $j>i$ and $\pi(j)>\pi(i)$, $A_{i,j}=-1$ If $j<i$ ...

1
vote

2
answers

105
views

### Another question on provable non-existence of an efficient deterministic numerical method

Herewith I submit what may or may not be considered a simpler version of this question.
The question is whether it is provable that there is no efficient deterministic numerical method for a ...

4
votes

2
answers

379
views

### What is the expected minimum total matching distance between two partitions of identically and independently distributed points?

Suppose a square $[0,1]\times [0,1]$ in which $N$ vehicles $V_i$ and $N$ riders $R_i$ are distributed identically and independently (say, uniform distribution), a bipartite matching (or a permutation, ...

5
votes

1
answer

650
views

### Number of permutations that are products of disjoint cycles of distinct length

What is the number of permutations $\pi\in S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $...

6
votes

0
answers

201
views

### Existence of stick breaking representations for random measures

The Dirichlet process has a roughly size ordered representation in terms of beta random variables, called a stick-breaking representation (Sethuraman, 1994). Similar results hold for the beta process, ...

2
votes

1
answer

90
views

### Proving symmetry of trace function of special matrix

Let $W = aI_{n\times n} + bJ_{n\times n}$, where $I$ is an identity matix, $J$ is the matrix of all ones, $a,b\in\mathbb{R}$ and a+b>0. Also, let $A = \mathbf{P} - \mathbf{p}\mathbf{p}^{T}$, where $\...

1
vote

0
answers

271
views

### A question about permutation matrices

This question is trying to abstract out in a self-contained way the point that is probably being made in page 6 of this paper, https://arxiv.org/pdf/1604.03544.pdf and why Theorem 4.1 there works.
...

21
votes

1
answer

765
views

### Girth of the symmetric group

Let $n \in \mathbb N$ and $\{\sigma,\tau\} \subset {\rm Sym}(n)$ be a generating set.
Question: What is the maximal possible girth (if one varies $\sigma, \tau$) of the associated Cayley graph?
I ...

1
vote

0
answers

209
views

### Testing Randomness of Permutation Sequences

Maybe this question is too simple, but I couldn't find anything that is concerned with measuring how random a sequence of permutations of $n$ elements( w.l.o.g. of the numbers $\lbrace 1,\ \dots,\ n \...

3
votes

0
answers

384
views

### Sum of random permutation matrices

Let $A$ be a uniformly random $k\times k$ permutation matrix, and $A_1,\ldots, A_m$ be the $m$ independent copies of $A$. Here the uniform distribution is with respect to the $k!$ possible permutation ...

7
votes

0
answers

178
views

### Can one "smooth over" k-wise independence to get actual independence?

I came across the following toy problem and was curious if there was a simple solution or counterexample. Suppose you have a distribution $p$ on $m$ random variables $X_1, \ldots, X_m$, each with ...

18
votes

3
answers

2k
views

### What is the probability that two random permutations have the same order?

I am interested in the orders of random permutations. Since the law of the logarithm of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), ...

7
votes

0
answers

190
views

### irregular LDPC code construction algorithm

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties
1- Faction of columns of weight $i$ is ${v_i}$ .
2- Fraction of rows of weight $i$...

10
votes

5
answers

2k
views

### fixed points of permutation groups

As is well-known (see, for example, a nice exposition by our own Qiaochu: https://qchu.wordpress.com/2012/11/07/fixed-points-of-random-permutations/) that the distribution of the number of fixed ...

3
votes

1
answer

3k
views

### variance of the number of fixed points for a permutation group

It is reasonably well-known that the variance of the number of fixed points for $S_n$ equals $1.$ Now, what about other transitive permutation groups on $\{1, \dotsc, n\}?$ Presumably much is known. I ...

2
votes

0
answers

56
views

### Smooth bivariate functions identifiable under permutations

Consider a "smooth" $f : [0,1]^2 \to [0,1]$ and let $\pi : [n] \to [n]$ be a permutation of $[n] =\{1,\dots,n\}$. Let us define
$$
A^{f,\pi} := \Big( f\Big(\frac{\pi(i)}{n},\frac{\pi(j)}{n}\Big) \...

1
vote

0
answers

307
views

### Horizontal vs Vertical sides Exit from a Rectangle for simple symmetric Random Walk on $\textbf{Z}^{2}$

Consider simple symmetric random walk, $X_{n} = (X_{n}^{(1)}, X_{n}^{(2)})$ with $X_0= (0,0)$, on the 2 dimensional integer lattice, $\textbf{Z}^{2}$.
Let $T_{M}, T_{N}$ be the smallest $n$ such ...

3
votes

1
answer

170
views

### What is the probability of a given induced ordering of a random permutation?

I ran into the following problem in a calculation involving permutations.
Let $[n] = \{1,...,n\}$, and assume that $[n]$ is partitioned into equivalency classes. That is, $[n]$ is the disjoint union ...

6
votes

1
answer

357
views

### Partial sums of partitions

Suppose I have two random partitions of $N.$ ("random" really means "the cycle type of a random permutation", but if there is an answer with any definition, I am interested). The question is: what is ...

5
votes

1
answer

2k
views

### Number of Permutations with k-inversions and with a single clamped value

This question is cross-posted from math.stackexchange because it might be too technical.
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the ...

1
vote

0
answers

243
views

### Factorization of permutations.

Let $n,k$ be positive integers such that $3n=2k$ and $N = \lfloor \alpha n\rfloor$ for some constant $0<\alpha<1$. Let $S_{3n}$ denote the permutation group of order $3n$. Consider the following ...