  Random braids that are formed by multiplying randomly chosen permutation
braids are studied by analyzing their behavior under Garside's weighted
decomposition and cycling. Using this analysis, we propose a polynomial-time
algorithm to the conjugacy problem that is successful for random braids in
overwhelming probability. As either the braid index or the number of
permutation-braid factors increases, the success probability converges to 1 and
so, contrary to the common belief, the distribution of hard instances for the
conjugacy problem is getting sparser. We also prove a conjecture by Birman and
Gonz\'{a}lez-Meneses that any pseudo-Anosov braid can be made to have a special
weighted decomposition after taking power and cycling. Moreover we give
polynomial upper bounds for the power and the number of iterated cyclings
required.
