It is essential to estimate how much power can be delivered from vehicles to grid, called achievable power capacity (APC), for practical vehicle-to-grid (V2G) services. We propose a method of estimating the APC in a probabilistic manner. Its probability distribution is obtained from the normal approximation to the binomial distribution, and hence represented with two parameters, i.e., mean and covariance. Based on the probability distribution of the APC, we calculate the power capacity that V2G regulation providers (or V2G aggregators) are contracted to provide grid operators with, called the contracted power capacity (CPC). Four possible contract types between a grid operator and a V2G regulation provider are suggested and, for each contract type, a profit function is developed from the APC and the penalty imposed to the V2G aggregator. The CPCs for four contract types are chosen to maximize the corresponding profit functions. Finally, simulations are provided to illustrate the accuracy of the estimated probability distribution of APC and the effectiveness of the profit functions.