3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ted Dec 4 '15 at 5:10
  • $\begingroup$ The correct formula is $\frac{1}{|H|} \sum_{h \in H} h$. $\endgroup$ – Ted Dec 4 '15 at 5:29
  • $\begingroup$ Thank you for catching this. $\endgroup$ – 3-in-441 Dec 4 '15 at 6:24
2
$\begingroup$

The fact that this is tagged representation-theory makes me feel like the following isn't what you were looking for, but here it goes anyway...

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$.

$\endgroup$
  • $\begingroup$ I'm not familiar with Markov chains, but I appreciate the response. Is the condition that $a_1 > 0$ necessary? $\endgroup$ – 3-in-441 Dec 4 '15 at 6:23
  • $\begingroup$ @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. $\endgroup$ – Ted Dec 4 '15 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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