This paper explores the recovery and rate capacity effect for batteries used in embedded systems. It describes the prominent battery models with their advantages and drawbacks. It then throws new light on the battery recovery behavior, which can help determine optimum discharge profiles and hence result in significant improvement in battery lifetime. Finally it proposes a fast and accurate stochastic model which draws the positives from the earlier models and minimizes the drawbacks. The parameters for this model are determined by a pretest, which takes into account the newfound background into recovery and rate capacity hence resulting in higher accuracy. Simulations conducted suggest close correspondence with experimental results and a maximum error of 2.65% .