El análisis de algoritmos autoestabilizantes a menudo se limita al tiempo de estabilización en el peor de los casos a partir de un estado arbitrario, es decir, un estado resultante de una secuencia de fallas. Teniendo en cuenta que estos algoritmos están destinados a proporcionar tolerancia a fallos a largo plazo, esta no es la métrica más relevante. Una situación común es que un sistema en funcionamiento se encuentra en un estado legítimo cuando es afectado por una sola falla. Este evento tiene una probabilidad mucho mayor que múltiples fallas concurrentes. Por lo tanto, el tiempo de recuperación en el peor de los casos de una sola falla es más relevante que el tiempo de recuperación de un gran número de fallas. Este documento presenta técnicas para derivar límites superiores para el tiempo medio de recuperación de una sola falla para algoritmos autoestabilizantes basados en cadenas de Markov en combinación con agrupamiento. Para ilustrar la aplicabilidad de las técnicas, se aplican a un nuevo algoritmo de coloreo autoestabilizante.