# Questions tagged [random-permutations]

The tag has no usage guidance.

53 questions
Filter by
Sorted by
Tagged with
206 views

• 949
1 vote
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 ...
• 24.2k
1 vote
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 ...
• 24.2k
1 vote
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 ...
• 109
89 views

• 335
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 (...
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
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 ...
• 2,146
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 ...
79 views

• 19.3k
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. ...
• 19.3k
1 vote
196 views

• 19.3k
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, ...
• 129
90 views

• 12.7k
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 ...
• 1,117
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 ...
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), ...
• 333
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$...
• 275
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 ...
• 95.7k
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 ...
• 95.7k
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,669
1 vote
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 ...
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 ...
• 1,623
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 ...
• 95.7k
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 ...
• 4,902
1 vote
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 ...