Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be a group with $n$ element. Fix $x\in G$.

If you choose randomly two elements from $G$, what is the probability of $x$ being product of these two elements?

At first, I thought answer was $1/n$, because, if $ab=x$ and if I choose $a$, it uniquely determines $b$. I guess it is true answer when $G$ is abelian.

But when $G$ is nonabeliean, $ab$ and $ba$ may be different elements; therefore, the probability is higher than $1/n$. I can't say the answer is $2/n$ since some pairs may still commute in nonabelian group.

I also noticed that the probability also depends on $x$, because, if $x=e$, you must choose $a,a^{-1}$ as a pair, so answer is $1/n$ regardless of $G$ is abelian or not.

If we denote this probability as $P_x(G)$, I think $1/n\leq P_x(G)\leq 2/n$.

Any further result will be appreciated.

As Geoff Robinson request let me clarify what I mean,

Let $w\in GxG$ i,e, $w=(a,b)$ let say that $w$ know answer if $ab=x$ or $ba=x$.

What is the probability that $w$ know the answer?

share|improve this question
1  
I think you have to decide what question you are asking. If you think of the pair as an ordered pair, you will get a different answer to that which you would get thinking about an unordered pair. Also you need to decide if you way to choose the group elements with or without replacement. This is not a contradiction: there are $|G|^{2}$ ordered pairs and $|G|(|G|-1)/2$ unordered pairs of genuinely distinct elements). –  Geoff Robinson Mar 5 at 21:08
    
you can choose $a,a$ also ,I mean these two elements need not be different. –  mesel Mar 5 at 21:24

3 Answers 3

up vote 3 down vote accepted

One could equally ask for the probability with ordered or unordered pairs, with different results.

It suffices to count the number of pairs $a,b$ satisfying $x=ab\vee x=ba$, where $x\in G$ is fixed.

Say we wish to count ordered pairs of not necessarily distinct elements. Notice the equivalence $x=ab\vee x=ba\iff b=a^{-1}x\vee b=xa^{-1}$. If we naively count two $b$s for each $a\in G$ be overcounting by one for each $a$ satisfying $a^{-1}x=xa^{-1}$, the number of which is $|C_G(x)|$, where $C_G(x)$ is the centralizer of $x$. So we conclude the number of pairs is $2|G|-|C_G(x)|$.

The corresponding probability is $$P=\frac{2|G|-|C_G(x)|}{|G|^2}. \tag{ordered}$$

Define $\sqrt{x}:=\{a\in G:x=a^2\}$, the set of "square roots" of $x$. Let $\Pi:=(x=ab\vee x=ba)$.

Suppose we wish to count the unordered pairs of not necessarily distinct elements satisying $\Pi$; say there are $N$ such pairs. If we take $N$ and subtract $|\sqrt{x}|$ we will have the number of unordered pairs of distinct elements satisfying $\Pi$. If we then multiply by two we will have the number of ordered pairs of distinct elements satisfying $\Pi$. If we then add on $|\sqrt{x}|$ we will have the number of ordered pairs of not necessarily distinct elements satisfying $\Pi -$ we already know this number. Therefore,

$$2\left(N-|\sqrt{x}|\right)+|\sqrt{x}|=2|G|-|C_G(x)|\iff N=|G|+\frac{|\sqrt{x}|-|C_G(x)|}{2}.$$

We wound up proving $|C_G(x)|\equiv|\sqrt{x}|$ mod $2$. The total number of unordered pairs of not necessarily distinct elements of $G$ is $(|G|^2+|G|)/2$. Therefore the corresponding probability is

$$P=\frac{2|G|+|\sqrt{x}|-|C_G(x)|}{|G|^2+|G|}. \tag{unordered}$$

If you force the elements to be distinct, the probabilities then become

$$P=\frac{2|G|-|\sqrt{x}|-|C_G(x)|}{|G|^2-|G|}, \tag{distinct}$$

for both ordered and unordered pairs.

share|improve this answer
    
it seems reasonable, let me think. –  mesel Mar 5 at 21:29
1  
So,$P_x=1/n$ if and only if $x\in Z(G)$,this also explain the case when $G$ is abelian. Thanks. –  mesel Mar 5 at 21:38
1  
If you sum this probability over all $x \in G,$ you will get $\frac{2|G|^{2} - k(G)|G|}{|G|^{2}}$, where $G$ has $k(G)$ conjugacy classes.This will be greater than $1$ unless $G$ is Abelian. –  Geoff Robinson Mar 5 at 22:01
    
Yes,with same reason, I opened my computer again since $\sum_{x\in G}P_x=1 \implies \sum_{x\in G}|C_G(x)|=|G|^2 \implies $ average of $|C_g(x)|=|G|$ which is only true in abelian groups. –  mesel Mar 5 at 22:49
    
@Geoff Correct, when you add up these probabilities it will be greater than $1$. Note that $x\ne y$ doesn't mean $x=ab\vee x=ba$ and $y=ab\vee y=ba$ are mutually exclusive, so this is to be expected. –  anon Mar 5 at 23:26

Assuming $a,b$ are uniformly and independently distributed: $P(ab=g\mid a=c)=P(b=a^{-1}g)=\frac{1}{n}$. Now sum over $c$ to get $P(ab=g)=\sum _{c\in G}P(ab=g\mid a=c)\cdot P(a=c)$ to get $\frac{1}{n}$ as the final answer.

share|improve this answer
1  
The OP is asking about $x=ab\vee x=ba$. –  anon Mar 5 at 21:19
    
Yes,for any pair $(a,b)$ if $ab=x$ or $ba=x$ we are done,I guess this change the probability. –  mesel Mar 5 at 21:27

Your reasoning in the case that $x = e$ is perfectly good, and would work just as well with other group elements. There are $|G|^{2}$ ordered pairs $(a,b)$ and for every $x \in G$ there are precisely $|G|$ ordered pairs $(a,b)$ such that $ab= x.$

share|improve this answer
    
The OP is asking about $x=ab\vee x=ba$. –  anon Mar 5 at 21:19
    
This was not clear, which is why I put the earlier comment. –  Geoff Robinson Mar 5 at 21:47
    
Your comment was asking about pairs vs. ordered pairs, which is different from $x=ab$ vs. $x=ab\vee x=ba$. –  anon Mar 5 at 21:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.