  We prove the existence of complex polynomials $p(z)$ of degree $n$ and $q(z)$
of degree $m<n$ such that the harmonic polynomial $ p(z) + \overline{q(z)}$ has
at least $\lceil n \sqrt{m} \rceil$ many zeros. This provides an array of new
counterexamples to Wilmshurst's conjecture that the maximum valence of harmonic
polynomials $p(z)+\overline{q(z)}$ taken over polynomials $p$ of degree $n$ and
$q$ of degree $m$ is $m(m-1)+3n-2$. More broadly, these examples show that
there does not exist a linear (in $n$) bound on the valence with a uniform (in
$m$) growth rate. The proof of this result uses a probabilistic technique based
on estimating the average number of zeros of a certain family of random
harmonic polynomials.
