  We prove that random d-regular Cayley graphs of the symmetric group
asymptotically almost surely have girth at least (log_{d-1}|G|)^{1/2}/2 and
that random d-regular Cayley graphs of simple algebraic groups over F_q
asymptotically almost surely have girth at least log_{d-1}|G|/dim(G). For the
symmetric p-groups the girth is between log log |G| and (log|G|)^alpha with
alpha<1. Several conjectures and open questions are presented.
