On the Rate of Convergence of Some Stochastic Processes

We present a general technique for obtaining bounds on the deviation of the optimal value of some stochastic combinatorial problems from their mean. As a particular application, we prove an exponential rate of convergence for the length of a shortest path through n random points in the unit square. This strengthens a previous result of Steele (Steele, J. M. 1981. Complete convergence of short paths and Karp's algorithm for the TPS. Math. Oper. Res.).