We have developed Walk-Mate (WM) training using interactive rhythmic auditory cue, which is a new rehabilitation method concerning gait rhythm. Also, we have proposed the new evaluation method for gait rhythm generation disorders, which is often observed in Parkinson's disease (PD) patients. However, the recovery process by rehabilitation for gait rhythm was not yet evaluated from a viewpoint of gait rhythm generation disorders. In this paper, we aim to evaluate the recovery process by rehabilitation for gait rhythm by evaluation method for gait rhythm generation disorders in PD patients. For this purpose, we evaluated the effect of WM training compared to conventional Rhythmic Auditory Stimulation (RAS) training using fixed-tempo rhythmic auditory cue. To evaluate the rehabilitation effect, we hypothesized a transition probability model of discrete states in views of gait rhythm generation disorders. In detail, the state transition probability matrices of WM training, was compared with the probability matrices of RAS training. Thirty-one PD patients walked for approximately 2 minutes. We used the gait states constructed in previous study to evaluate the disease severity for gait rhythm generation disorders. Then we made state transition probability matrices from pre-WM training to post-WM training, and that from pre-RAS training to post-RAS training. The result showed the difference in effect between two training. Specifically, the WM training showed better gait state transition of the patients in severer states of gait rhythm generation disorders, compared to the RAS training. This suggests that this transition model is useful to identify the appropriate treatment of gait rhythm generation disorders.