Expected value suggested by simulation

Question

If $X$ is random variable giving the first $n$ value such as $X_1+\cdots+X_n$ is multiple of $m \in \mathbb{N}^*$, where $X_i$ are independent variables with uniform distributions on $\{1,\cdots,k\}$. The following simulation let think that the expected value of $X$ is $m$, but I can't prove it in general case.

import random

def D(k):
    return random.randint(1,k)

def X(m,k):
    s = D(k)
    n = 1
    while not s%m == 0:
        s = s+D(k)
        n = n+1
    return n

Answer 1

Let us assume $k \geq 2$ without losing the generality. Let $Y = (Y_n)_{n\geq 0}$ be the stochastic process defined by

$$ Y_n = (X_1 + \cdots + X_n) \text{ mod } m.$$

Then $Y$ is an aperiodic and irreducible Markov chain on the state space $\mathcal{S} = \{0,1,\ldots,m-1\}$. In particular, $Y$ has a unique stationary measure $\pi = (\pi_i)_{i\in\mathcal{S}}$. Then it is easy to check that

$$ \pi_i = \frac{1}{m}, \qquad i \in \mathcal{S} $$

using the definition of $Y$.

Also, if $m_i$ denotes the expected return time to state $i \in \mathcal{S}$, then the general theory of Markov chain tells that $m_i = 1/\pi_i = m $. Since the answer to OP's question corresponds to $m_0$, the expected return time to $0$, we are done.