On mixing behavior of a family of random walks determined by a linear recurrence (Q2092394)

The research considers an integral sequence \(\{G_n\}\) with \(G_1 = 1\) and for larger values of \(n\), \(G_n\) is determined by a linear recurrence relation with constant coefficients: \[ G_n = \alpha_1 G_{n-1} + \alpha_2 G_{n-2} + \dots + \alpha_d G_{n-d}. \] This sequence is used to define a family of random walks: for fixed \(n\), consider the Markov chain \((X_t)_{t \ge 0}\) whose state space is \(\mathcal{S} = Z_{G_n}\). The initial state is \(X_0 = 0\) and from the current state \(X_t\), the next state is \(X_{t+1} \equiv X_t + z_t\pmod {G_n}\), where \(z_t\) is chosen uniformly randomly from \(\mathcal{M} = \{G_1,\dots, G_n\}\). Using this model, the eigenvalues of the transition matrices are computed and the bound of the mixing time of these random walks is obtained. Future research on the additional investigation of the mixing time is proposed, which seems to be of interest.