All Questions
14 questions
41
votes
4
answers
2k
views
What is the probability two random maps on n symbols commute?
It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
- 38.6k
21
votes
2
answers
1k
views
Generating random finite groups
I would like a method to efficiently generate a random finite group of a given order $n$.
If there are $g(n)$ non-isomorphic groups of order $n$,
ideally each group would occur with probability $1/g(n)...
- 151k
18
votes
4
answers
3k
views
Markov chain on groups
Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
- 85.6k
17
votes
1
answer
1k
views
Can this probability be obtained by a combinatorial/symmetry argument?
Suppose that $a_1,\dots,a_n,b_1,\dots,b_n$ are iid random variables each with a symmetric non-atomic distribution.
Let $p$ denote the probability that there is some real $t$ such that $t a_i \ge b_i$ ...
- 128k
15
votes
1
answer
1k
views
In how many steps a random walk visits all the elements of a finite group, with a probability 1/2?
This question is a variation of the return to the origin problem.
Let $G$ be the finite group $\mathbb{Z}/n \times \mathbb{Z}/n$ and let the random transformation $T: G \to G$ such that $T(a,b) = (...
12
votes
2
answers
406
views
Does asymmetric fraction of finite groups tend to $0$?
Let’s define asymmetric fraction of a finite group $G$ as the number $$\mathrm{af}(G) = \frac{|\{(g, a) \in G \times \mathrm{Aut}(G)\mid a(g) = g\}|}{|G|\cdot|\mathrm{Aut}(G)|}.$$ Equivalently it can ...
- 2,618
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 ...
- 96.4k
8
votes
1
answer
452
views
What is the probability that a random subset of a finite group is generic?
Definition 1: Given a group $G$, a subset $X \subseteq G$, and a natural number $k$,
we say that $X$ is (left) $k$-generic in $G$ if there are $k$ many left translates of $X$ that cover $G$.
That is, ...
- 83
5
votes
1
answer
412
views
Random pairs of commuting permutations
Let $\Omega_n \subseteq \mathrm{Sym}(n)^4$ be the set of all $4$-tuples $(\sigma_1,\sigma_2,\tau_1,\tau_2)$ of permutations of $\{1,\ldots,n\}$ such that $\sigma_j \tau_k = \tau_k \sigma_j$ for each ...
- 1,769
4
votes
2
answers
420
views
Generating a group by randomly sampling generators
Let $G$ be a finite abelian group, $n$ a positive integer and let $G^n$ denote the direct product of $n$ copies of $G$. We say an element of $G^n$ is full if it acts as a nonidentity element of $G$ in ...
- 2,649
4
votes
0
answers
266
views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
- 24.9k
3
votes
1
answer
539
views
Probability of generating the symmetric group
The statement is simple:
What is the probability that a set of n-1 transpositions generates the symmetric group, $S_n$?
The motivation is that I remembered reading that this was an open problem ...
- 543
2
votes
0
answers
138
views
Update on Viskov's paper on random processes, Lagrange inversion, and the Heisenberg–Weyl algebra
"A Random Walk with a Skip-Free Component and the Lagrange Inversion Formula" by Viskov presents connections among Lagrange inversion and measures of random Lévy processes. The freely ...
- 10.5k
1
vote
1
answer
519
views
How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices
Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let:
$N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ ...
- 175