  In \cite{KSS06} it was shown that with respect to the simple non-backtracking
random walk on the free group $F_N=F(a_1,\dots,a_N)$ the Whitehead algorithm
has strongly linear time generic-case complexity and that "generic" elements of
$F_N$ are "strictly minimal" in their $Out(F_N)$-orbits. Here we generalize
these results, with appropriate modifications, to a much wider class of random
processes generating elements of $F_N$. We introduce the notion of a
''$(M,\lambda, \epsilon)$-minimal" conjugacy class $[w]$ in $F_N$, where $M\ge
1, \lambda>1$ and $0<\epsilon<1$. Roughly, being $(M,\lambda,
\epsilon)$-minimal means that every $\phi\in Out(F_N)$ either increases the
length $||w||_A$ by a factor of at least $\lambda$, or distorts the length
$||w||_A$ multiplicatively by a factor $\epsilon$-close to $1$, and that the
number of automorphically minimal $[u]$ in the orbit $Out(F_N)[w]$ is bounded
by $M$. We then show that if a conjugacy class $[w]$ in $F_N$ is sufficiently
close to a "filling" projective geodesic current $[\nu]\in PCurr(F_N)$, then,
after applying a single "reducing" automorphism $\psi=\psi(\nu)\in Out(F_N)$
depending on $\nu$ only, the element $\psi([w])$ is $(M,\lambda,
\epsilon)$-minimal for some uniform constants $M,\lambda,\epsilon$.
Consequently, for such $[w]$, Whitehead's algorithm for the automorphic
equivalence problem in $F_N$ works in quadratic time on the input $([w], [w'])$
where $[w']$ is arbitrary, and in linear time if $[w']$ is also projectively
close to $[\nu]$. We then show that a wide class of random processes produce
"random" conjugacy classes $[w_n]$ that projectively converge to some filling
current in $PCurr(F_N)$. For such $[w_n]$ Whitehead's algorithm has at most
quadratic generic-case complexity.
