# Questions tagged [random-permutations]

The random-permutations tag has no usage guidance.

32
questions

**4**

votes

**1**answer

95 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)=\...

**1**

vote

**0**answers

36 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 ...

**0**

votes

**0**answers

9 views

### Sampling distribution on permutations with multi-dimensional constraints and nesting

Let $\mathcal{X}$ be some space (for argument's sake, a finite, discrete space of large cardinality), and let $D > 1$ be a positive integer.
For $d = 1, \ldots, D$,
Let $\Phi_d: \mathcal{X} \to ...

**1**

vote

**1**answer

98 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

894 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

202 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

99 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

153 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

333 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

96 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

**1**answer

132 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

312 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

164 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

69 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

140 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.
...

**20**

votes

**1**answer

658 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

133 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 \...

**2**

votes

**0**answers

287 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 ...

**8**

votes

**0**answers

170 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 ...

**17**

votes

**3**answers

1k 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

150 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

1k 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

2k 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

50 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

244 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

145 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

305 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

1k 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

196 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 ...

**1**

vote

**0**answers

254 views

### Random Permutation with fixed cycle length.

Suppose $ S_{n,N} $ be the set of $n$ elements with $N$ many cycles where $N$ is proportional to $n$. $U_{n,N}$ is an element picked randomly from this. It is known that the length of any cycle cannot ...

**1**

vote

**2**answers

2k views

### What is the expected number of increasing subsequence? [closed]

Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?

**28**

votes

**6**answers

2k views

### Combinatorial Morse functions and random permutations

This question has its origin in combinatorial topology. In the 90s R. Forman proposed a discrete counterpart of Morse theory. In his case, a Morse function on a triangulated space is a function ...