All Questions
Tagged with pr.probability gr.group-theory
102 questions
42
votes
6
answers
4k
views
Measures of non-abelian-ness
Let $G$ be a finite non-abelian group of $n$ elements.
I would like a measure that intuitively captures the
extent to which $G$ is non-commutative.
One easy measure is a count of the non-commutative ...
- 151k
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 1,583
3
votes
1
answer
693
views
Size of automorphism group of random regular graph
If I pick a random regular graph on $n$-vertices and degree $d$ from uniform distribution what is the probability that its automorphism group is of size at least $m$?
--
I want to know what is the ...
- 37.7k
1
vote
2
answers
635
views
Mean value theorems for the Haar integral?
Let $G$ be a compact topological group (feel free to add hypotheses if necessary). Is there any mean value theorem for its (normalized to 1) Haar integral?
In general, are there mean value theorems ...
- 5,407
4
votes
1
answer
204
views
Estimates for simple random walks in groups of intermediate growth
I'm looking for references for the rate of escape and return probability for a group of intermediate growth.
Let $0<\alpha < 1$. If the volume growth is $\succeq \mathrm{exp}(n^\alpha)$, then (...
- 4,432
6
votes
1
answer
569
views
Liouville property - a very basic question
Let $\mathbb{F}_2$ be the free group on two generators. By a result of Kaimanovich and Vershik, for each measure $\mu$ on $\mathbb{F}_2$ such that the support of $\mu$ generates $\mathbb{F}_2$, we ...
- 11.6k
4
votes
0
answers
177
views
Is there any probabilistic characterization for generalized solvable groups?
References: This question is inspired by a conjecture of Alon Amit that is solved by Miklós Abért, Nikolay Nikolov and Dan Segal in the following papers:
(1) On the probability of satisfying a word in ...
CommunityBot
- 1
32
votes
1
answer
4k
views
Do invariant measures maximize the integral?
Update: The negative answer to the following question has been provided by Matthew Daws, who won, but also rejected, the bounty of 100 euro that I set over the question.
Let $\mathcal M(\mathbb Z)$ ...
- 63.9k
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 ...
- 22.5k
17
votes
3
answers
736
views
Probability that a word in the free group becomes (much) shorter?
Let $w$ be a word of length $2\ell$ chosen at random on the alphabet $\{x_1,x_1^{-1},x_2,x_2^{-1},\dotsc,x_k,x_k^{-1}\}$. By the reduction $\rho(w)$ I mean what you obtain by deleting substrings of ...
- 96.4k
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) = (...
2
votes
2
answers
381
views
Speed and absence of non-constant bounded harmonic functions
For a (symmetric) random walks on countable groups generated by $\mu$, there is a "brute-force computation" argument of Avez (1974) that shows that if the entropy $h_\mu$ is trivial then there are no ...
- 17k
2
votes
1
answer
261
views
Does the set of automorphisms of a cyclic group exhibit some sense of randomness?
I prefer to proceed with a concrete example if I may. I appreciate that the answer might well be better explained with group theory, geometry and/or notions from probability theory, which I welcome.
...
- 2,480
9
votes
3
answers
654
views
measure with given push-forwards
Let $X,Y$ be locally compact spaces (in my specific case, they are locally compact groups). Suppose that we are given a measure $\mu$ on $X$ and a finite number of quotient maps $p_1,\ldots,p_n:Y\...
CommunityBot
- 1
2
votes
1
answer
173
views
Proving that a closed walk of some odd length k exists on a Cayley graph
I'm trying to prove the following:
Let $G$ be a group with finite symmetric generating set $S$ and let $\Gamma(G,S)$ be the corresponding Cayley graph. Let $X_1, X_2,\cdots$ be a simple random walk ...
- 17k
21
votes
6
answers
3k
views
"The" random tree
One time I heard a talk about "the" random tree. This tree has one vertex for each natural number, and the edges are constructed probabilistically. Connect vertex $2$ to vertex $1$. Connect vertex $3$ ...
- 437
-2
votes
1
answer
190
views
Dixon's Theorem [closed]
I am going through a sketch of the proof of Dixon's Theorem (the probability that two randomly chosen elements of A_n generate A_n -> 1 as n -> infinity) due to M. Liebeck and its underlying idea is ...
- 19.6k
5
votes
3
answers
314
views
Tracking automorphism groups of graph processes
Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...
CommunityBot
- 1
4
votes
1
answer
556
views
Symmetries of the standard probability space
The standard probability space $(I, \mathcal B, \lambda)$ consists of the interval $I = [0,1]$, its Borel $\sigma$-algebra $\mathcal B := \mathcal B(I)$ and Lebesgue measure $\lambda$. In applications,...
CommunityBot
- 1
7
votes
2
answers
639
views
Is there an algebraically normal function from $\mathbb{Z}^{n}$ to $\{ 0 , 1\}$?
Definition: Let $h$ be a polynomial in $n$ variables, then :
$\gamma(h,r,R):=\{ v \in \mathbb{Z}^{n} : \vert h(v) \vert \leq r, \Vert v \Vert < R \}$
Let $\omega : \mathbb{Z}^{n} \to \{ 0 , 1\}$...
CommunityBot
- 1
3
votes
1
answer
324
views
A stronger version of supramenability?
A group $G$ is supramenable iff for all $\varnothing\ne A\subseteq G$ there is a finitely-additive left-$G$-invariant measure $\mu_A$ on $G$ with $\mu_A(A)=1$. I'm interested in a seemingly stronger ...
- 2,555
6
votes
0
answers
295
views
Is there an idempotent measure on the free LD system?
This is a follow up question to MO question "Idempotent measures on the free binary system?".
Let $(A,*)$ be the free binary operation on one generator which satisfies the left self distributive law:
...
CommunityBot
- 1
13
votes
1
answer
736
views
Idempotent measures on the free binary system?
Let $(S,*)$ be the free (non associative) binary system on one generator (so $S$ is just the set of terms in $*$ and $1$). There is an extension of $*$ to the space $P(S)$ of finitely additive ...
- 19.3k
3
votes
1
answer
263
views
Extending Tarski's Theorem on invariant measures
Tarski's Theorem says that if $G$ acts on $X$ and $E$ is a non-$G$-paradoxical subset of $X$, then there is a finitely additive $G$-invariant measure $\mu:2^X\to[0,\infty]$ with $\mu(E)=1$.
I am ...
- 352
4
votes
1
answer
400
views
Speed of random walks in groups
I've seen some estimates for the decay in $d$ of the probability a SRW makes a distance $d$ in time $n$, but is there any reference for the "speed" of a random walk in a group? I'm interested mostly ...
- 992
1
vote
1
answer
578
views
Fundamental inequality of entropy in random walks
I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely,
$\textbf{Question}$: ...
- 17k
5
votes
1
answer
774
views
Probabilities of a random walk exiting a set
Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...
- 1,791
2
votes
1
answer
141
views
Spanning subgaph with trivial Poisson boundaries
Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some $k$-...
- 17k
12
votes
3
answers
552
views
Estimate on currents in Cayley graphs
Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
- 4,432
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, ...
- 23.2k
2
votes
1
answer
337
views
Genericity of sets without unique mean value
Following Rosenblatt and Yang, I say that a subset $A$ of $\mathbb Z$ has a unique mean value if for all invariant means $\lambda_1,\lambda_2$ on $\mathbb Z$, one has $\lambda_1(A)=\lambda_2(A)$.
...
CommunityBot
- 1
5
votes
1
answer
437
views
Stationary, ergodic measures from the structuralist point of view
Stationary, ergodic measures are a class of objects very familiar to probabilists. In a sense, these are the weakest generalization of the classic case of independent, identically distributed random ...
CommunityBot
- 1
8
votes
2
answers
755
views
The Odds 3 (or More) Group Elements Commute
Some time ago I asked about the odds 2 group elements commute. I wonder about the odds that 3 group elements commute. Is there a "closed" formula for the sum
$$ \frac{1}{|G|^3} \sum_{g,h,k} \delta([...
CommunityBot
- 1
6
votes
0
answers
301
views
Generating stationary, ergodic random fields on a homogeneous space
Consider a homogeneous space $M$, which for the sake of concreteness, let's take to be $M = \mathbb R^d$. Fix some space $A$, and consider the space of functions $X = C(M,A)$, along with its Borel $\...
- 8,512
18
votes
1
answer
996
views
Existance of certain almost invariant functions related to amenability and piece-wise transformations
We would like very much to know the answer to the following question:
Let $\|\cdot\|$ be any norm on $\mathbb{Z}^d$ and let $W(\mathbb{Z}^d)$ be the group of all bijections of $\mathbb{Z}^d$ such ...
- 4,705
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
6
votes
1
answer
844
views
Random geometries
Let $M$ be a smooth $n$-dimensional manifold, and let $FM = GL(M)$ indicate its tangent frame bundle. Let $G$ be a fixed linear subgroup of $GL(n)$, and consider the space $\mathcal S$ of all $G$-...
- 561
9
votes
2
answers
726
views
Return probabilities for random walks on infinite Schreier graphs
Question: Is there a sequence $(\delta_n)_n$ of real numbers with $\delta_n \to 0$ as $n \to \infty$, such that the following holds:
Let $F$ be a free group on two generators, let $F \curvearrowright ...
CommunityBot
- 1
8
votes
3
answers
606
views
Many Brownian motions moving together
Let $ (B^i),\:{{i=1,\ldots,n}}$ be a set of independent Brownian motions. By $(X^i)$ we denote $(B^i)$ conditioned on the event
$|B^i_t-B_t^{i+1}|\leq 1,\quad \forall_{1\leq i\leq n-1}, \forall_{t\...
CommunityBot
- 1
7
votes
0
answers
743
views
Distribution of the sizes of conjugacy classes in the symmetric group.
This recent question makes me wonder: is there some known limit theorem for the distribution of the sizes of conjugacy classes in the symmetric group $S_n?$ A quick search seems to reveal nothing ...
CommunityBot
- 1
10
votes
0
answers
3k
views
Group Theory, Game Theory, a bit of Philosophy and a post in Tao's blog
I've decided to write this post after reading the incredibly beautiful and highly recomended post by Terence Tao http://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-...
CommunityBot
- 1
1
vote
1
answer
259
views
Amenability with respect to a function
Let $(G,\cdot)$ be a group and $\phi:G\rightarrow\mathbb R$ bounded. Let me say that the pair $(G,\phi)$ is amenable if there is a finitely additive probability measure $\mu$ on $G$ such that for all $...
CommunityBot
- 1
2
votes
0
answers
153
views
Reference request for a result on subsets unlikely to be hit by random walks in a group
Suppose we are performing a random walk in a group. More precisely, we have a finite generating set $S$ of a group $G$ and the probability of walking along generator $s$ is given by $\mu(s)$ for some ...
- 21
15
votes
3
answers
3k
views
Entropy of a measure
Let $\mu$ be a probability measure on a set of $n$ elements and let $p_i$ be the measure of the $i$-th element. Its Shannon entropy is defined by
$$
E(\mu)=-\sum_{i=1}^np_i\log(p_i)
$$
with the ...
- 1,101
2
votes
2
answers
389
views
Who is the weak* sequential closure of the set of finitely supported measures on the integers?
Let $X$ be a topological space and $Y\subseteq X$, the sequential closure of $Y$ is the set of elements in $X$ that are limit of sequences belonging to $Y$.
Let $\mathcal M_{\text{fin}}(\mathbb Z)$ ...
- 18.7k
6
votes
2
answers
461
views
Intrinsically measurable subsets of amenable semigroups.
This question is related to the one in https://mathoverflow.net/questions/65322/the-structure-of-certain-maximal-sets-of-means-into-amenable-semigroups. I open a different topic because they can be ...
CommunityBot
- 1
0
votes
3
answers
293
views
How can we pave the multiplicative semigroup $(\mathbb N,\cdot)$?
Let $(S,\cdot)$ be a semigroup and $W\subseteq S$ be a subset. Let me call $W$ "tile" if the following property is satisfied: there exist $s_1,...s_k\in S$ such that the sets $s_i\cdot W$ are pairwise ...
- 30.1k
10
votes
0
answers
809
views
Where can I find analogues of combinatorial central limit theorems for other groups
The statement of Hoeffding's combinatorial central limit theorem is as follows: given for each $n$, an $n \times n$ matrix $A = (a_{ij})$, one can consider the random diagonal sum:
$$\displaystyle f(\...
- 4,466
21
votes
0
answers
578
views
Density of first-order definable sets in a directed union of finite groups
This is a generalization of the following question by John Wiltshire-Gordon.
Consider an inductive family of finite groups:
$$
G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i \...
CommunityBot
- 1
23
votes
3
answers
1k
views
In an inductive family of groups, does the probability that a particular word is satisfied converge?
We have some group word $w$ in $k$ letters. We say a $k$-tuple of group elements $\vec{g} = (g_1, g_2, \ldots , g_k) \in G^k$ satisfies the word $w$ if $w$ gives the identity at $\vec{g}$. More ...
CommunityBot
- 1