# Probability distribution on finite group

I'm preparing for finals and this is a practice question. I'm not really sure how to start, so any solutions/hints/starting points are appreciated.

Suppose $P = \sum a_gg$ were a probability distribution on a finite group $G$. If $a_1 > 0$, then $\lim_{k\rightarrow \infty} P^k$ exists and is equal to ${1\over|H|}\sum_{h\in H}a_hh$, where $H$ is the subgroup of $G$ generated by elements with $a_g > 0$.

• Something is wrong here. Suppose $a_g = 1/|G|$ for all $g \in G$. Then $P$ is idempotent ($P^2 = P$), and hence the limit is $P$. Your formula would give $(1/|G|) P$ instead. – Ted Dec 4 '15 at 5:10
• The correct formula is $\frac{1}{|H|} \sum_{h \in H} h$. – Ted Dec 4 '15 at 5:29
• Thank you for catching this. – 3-in-441 Dec 4 '15 at 6:24

The element $P$ describes a Markov chain on $H$, where $a_h$ is the transition probability between $x$ and $xh$, for all $x,h \in H$. It is easy to check that $P^k$ is the probability distribution over $H$ after $k$ steps of the Markov chain. Since $a_1 > 0$, the Markov chain is aperiodic, and since every element of $H$ can be expressed a product of $a_g$ with $a_g > 0$, the Markov chain is irreducible. Now by standard results in the theory of Markov chains, an irreducible aperiodic Markov chain has a unique stationary distribution $S = \lim_{k \to \infty} P^k$, and this stationary distribution is given by the unique solution to the equation $PS=S$ such that $S$ is a probability distribution. It is easy to check that $S = \frac{1}{|H|}\sum_{h \in H} h$ is a probability distribution and satisfies $PS=S$.
• I'm not familiar with Markov chains, but I appreciate the response. Is the condition that $a_1 > 0$ necessary? – 3-in-441 Dec 4 '15 at 6:23
• @algebra Yes, the condition $a_1 > 0$ is necessary. Otherwise you could take an element $g \ne 1$ and set $P = g$. Then $P^k$ repeatedly cycles through the powers of $g$, and has no limit. – Ted Dec 4 '15 at 6:38