How has the average distance between asteroids in the asteroid belt changed over time?
The asteroids formed roughly where they are now, from matter in the sun's protoplanetary disc that didn't form into a larger body (at least partly under the influence of Jupiter's gravity)
Since early in the solar system's story, the asteroids have been stable. Most asteroids haven't changed significantly in 4.5 billion years.  And 4.5 billion years ago the separation between asteroids was comparable to how it is now.