Skip to main content

Questions tagged [random-permutations]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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=...
Bill Bradley's user avatar
  • 3,819
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 ...
Grandes Jorasses's user avatar
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, ...
mathoverflowUser's user avatar
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 ...
Kaiyue Wen's user avatar
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 ...
Command Master's user avatar
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 $\...
Greg Zitelli's user avatar
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 ...
Alexander Chervov's user avatar
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 ...
Alexander Chervov's user avatar
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 ...
sdd's user avatar
  • 109
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_\...
MikeG's user avatar
  • 665
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\...
KhashF's user avatar
  • 3,230
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[\...
Greg Zitelli's user avatar
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 ...
Zach H's user avatar
  • 1,899
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 ...
user381021's user avatar
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_{...
kerzol's user avatar
  • 335
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 (...
user979797987678's user avatar
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, ...
Bernardo Recamán Santos's user avatar
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 ...
gradstudent's user avatar
  • 2,146
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 ...
Andrew Larkin's user avatar
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\...
Anuj Dawar's user avatar
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 ...
David Harris's user avatar
  • 3,407
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 ...
mvc's user avatar
  • 153
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)=\...
D.R.'s user avatar
  • 741
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 ...
Zachary Vance's user avatar
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^\...
VS.'s user avatar
  • 1,826
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 $...
H A Helfgott's user avatar
  • 19.3k
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. ...
H A Helfgott's user avatar
  • 19.3k
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,\...
0xbadf00d's user avatar
  • 181
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 ...
tigerjack's user avatar
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$ ...
H A Helfgott's user avatar
  • 19.3k
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 ...
Michael Hardy's user avatar
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, ...
Guoyang Qin's user avatar
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 $...
H A Helfgott's user avatar
  • 19.3k
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, ...
Shannon S.'s user avatar
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 $\...
Satya Prakash's user avatar
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. ...
gradstudent's user avatar
  • 2,146
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 ...
Andreas Thom's user avatar
  • 25.3k
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 \...
Manfred Weis's user avatar
  • 12.7k
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 ...
Minkov's user avatar
  • 1,117
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 ...
untitled459's user avatar
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), ...
thibo's user avatar
  • 333
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$...
user51780's user avatar
  • 275
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 ...
Igor Rivin's user avatar
  • 95.7k
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 ...
Igor Rivin's user avatar
  • 95.7k
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) \...
passerby51's user avatar
  • 1,669
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 ...
user avatar
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 ...
Zur Luria's user avatar
  • 1,623
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 ...
Igor Rivin's user avatar
  • 95.7k
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 ...
Alex R.'s user avatar
  • 4,902
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 ...
gmath's user avatar
  • 141