This paper explores the recovery and rate capacity effect for batteries used in embedded systems. It throws new light on the battery recovery behavior, which can help determine optimum discharge profile 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. Simulations conducted suggest close correspondence with experimental results and a maximum error of 2.65%.