  Recently Bacon, Childs and van Dam showed that the ``pretty good
measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral
group D_n in the case where the hidden subgroup is chosen uniformly from the n
involutions. We show that, for any group and any subgroup H, the PGM is the
optimal one-register experiment in the case where the hidden subgroup is a
uniformly random conjugate of H. We go on to show that when H forms a Gel'fand
pair with its parent group, the PGM is the optimal measurement for any number
of registers. In both cases we bound the probability that the optimal
measurement succeeds. This generalizes the case of the dihedral group, and
includes a number of other examples of interest.
