2
votes
1answer
123 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 ...
-3
votes
1answer
101 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 ...
9
votes
3answers
427 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 ...
4
votes
3answers
159 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 ...
3
votes
1answer
186 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 ...
9
votes
0answers
292 views

Spectral radius of a simple random walk. Convergence

Let $G_n$ be a sequence of groups generated by a finite sets $S_n$ and let $k>1$ be a natural number. Assume that for all $m\geq k$ and for all $n$ the set $\{g^m:g \in S_n\}$ is free, I.e. ...
4
votes
0answers
63 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 ...
25
votes
3answers
539 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 ...
1
vote
1answer
172 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 ...
7
votes
2answers
599 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 , ...
3
votes
1answer
170 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 ...
3
votes
1answer
219 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 ...
1
vote
1answer
155 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}$: ...
4
votes
1answer
257 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 ...
18
votes
6answers
1k 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 ...
15
votes
2answers
951 views

What is a Gaussian measure?

Let $X$ be a topological affine space. A Gaussian measure on $X$ is characterized by the property that its finite-dimensional projections are multivariate Gaussian distributions. Is there a direct ...
1
vote
1answer
67 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 ...
12
votes
3answers
456 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 ...
1
vote
1answer
242 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 ...
7
votes
1answer
263 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, ...
4
votes
1answer
232 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 ...
6
votes
2answers
467 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} ...
5
votes
4answers
556 views

Symmetries of probability distributions

When talking about a single random variable, knowing only its distribution, the construction of a probability space is quite easy. Namely, let $(X,\mathscr A)$ be a measurable space and let $\mathsf ...
12
votes
2answers
426 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 ...
5
votes
0answers
167 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 ...
18
votes
1answer
857 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
votes
2answers
294 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 ...
11
votes
3answers
611 views

Looking for at least one beautiful and not too technical result in asymptotic group theory

We have a student seminar devoted to the problems of asymptotic group theory with some connections to ergodic theory and measure theory in general. Each talk concerns one of the problems of this ...
2
votes
1answer
331 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)$. ...
4
votes
1answer
469 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 ...
9
votes
2answers
381 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 ...
13
votes
4answers
665 views

The critical value of percolation on Cayley graphs.

Let $\Gamma$ be a discrete group with a generating set $S$. Let $p_c(\Gamma,S)$ be the critical probability for percolation of the Cayley graph of $\Gamma$. Is it known that if $\Gamma$ is ...
7
votes
3answers
479 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}, ...
6
votes
0answers
348 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 ...
9
votes
0answers
2k 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 ...
0
votes
1answer
229 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 ...
30
votes
1answer
3k views

100€ bounty ended: 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)$ ...
2
votes
0answers
135 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 ...
9
votes
3answers
883 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 ...
2
votes
2answers
295 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)$ ...
5
votes
2answers
402 views

Intrinsically measurable subsets of amenable semigroups.

This question is related to the one in http://mathoverflow.net/questions/65322/the-structure-of-certain-maximal-sets-of-means-into-amenable-semigroups. I open a different topic because they can be ...
2
votes
9answers
977 views

Examples of Amenable Groups other than Z_n

I'm reading about amenable groups. What are explicit examples of nonabelian discrete amenable groups other than finite groups? Perhaps a group presentation or matrix representation would be useful.
0
votes
3answers
234 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 ...
5
votes
0answers
274 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: ...
12
votes
1answer
662 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 ...
10
votes
0answers
345 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 ...
16
votes
0answers
401 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 ...
20
votes
3answers
921 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 ...
2
votes
1answer
426 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 ...
6
votes
3answers
673 views

Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance Part II

For some context see Random Walks in $Z^2$/$Z^2$-intrinsic characterization of Euclidean distance As per Noah's answer and JBL's comment this was false as stated. However, I think the following ...