Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-permutations]

The tag has no usage guidance.

1
vote
1answer
87 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
1answer
128 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 ...
5
votes
1answer
177 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
2answers
77 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 ...
3
votes
1answer
92 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, ...
4
votes
1answer
250 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 $...
0
votes
0answers
9 views

Removing correlation from a sequence generated by a DTMC

Suppose there exists an aperiodic and irreducible stationary (hidden) discrete time Markov chain $\mathcal{M}$ which generates a data stream $\mathbf{X}=\{X_i \in \mathcal{X}: i\geq 0\}$. Let $\mathbf{...
6
votes
0answers
121 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
1answer
60 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
0answers
107 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
1answer
618 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
0answers
97 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
0answers
245 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
0answers
164 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
3answers
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
0answers
132 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
5answers
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
1answer
1k 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
0answers
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
0answers
223 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
1answer
140 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
1answer
290 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
1answer
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
0answers
180 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
0answers
249 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
2answers
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?
26
votes
6answers
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 ...