On the average path length of a cycle plus random edges

The average path length of a connected undirected graph is the expected distance of a randomly chosen pair of vertices. The n-cycle initially has an average path length of about n/4; it is known that an additional ϵn random edges is enough to reduce it to of order at most O(ϵ−1log⁡n), with high probability. We give more precise upper and lower bounds for the average path length when ϵn random edges are added to the n-cycle.