Number of positive integer solutions to inequality in $\mathbb{Z}^d$

Question

I have a probability question which boils down to a combinatoric question.

$\textbf{Problem Statement:}$ You have a dice with sides with numbers labeled $[1\dots k]$, with equal probability $(\frac{1}{k})$ of being rolled. Call the value of each roll $d_i \in [1\dots k]$, and $s_i= \sum_{j=1}^i d_j$ the running sum. I want the expected number of times that $s_i$ divides $k$ in a total of $r$ rolls.

---

So I call $X$ the R.V. that is the number of times that $s_i$ divides $k$. Then $X$ = $\sum_{i=1}^r \mathbb{1}_{k \vert s_i}$, and so $\mathbb{E}[X] = \sum_{i=1}^r \mathbb{P}(s_i \vert k) = \sum_{i=1}^r \sum_{m=1}^i \mathbb{P}(s_i = mk)$ (the inner summand is only up to $i$ because the support of $s_i$ is only up to $ik$).

Now I must evaluate $\mathbb{P}(s_i = mk)$. This is equal, using the law of conditional probability, to $\sum_{n_1 = 1}^k \mathbb{P}(s_{i-1} = mk - n_1)\mathbb{P}(s_i =n_1) = \frac{1}{k}(\sum_{n_1=1}^k \mathbb{P}(s_{i-1} = mk - n_1))$. We recurse back to the base case, and it is equal to $\frac{1}{k^{i-1}} \sum_{n_1 = 1}^k \sum_{n_2 = 1}^k \dots \sum_{n_{i-1} = 1}^k \mathbb{P}(s_1 = mk -\sum_{j=1}^{i-1}n_j)$.

Now, essentially now I must count the number of times $(mk -\sum_{j=1}^{i-1}n_j)$ lies in the support of $s_0$ which is $[1,\dots,k]$. So I want to count the number of times $1 \leq (mk -\sum_{j=1}^{i-1}n_j) \leq k$, or $(mk-1) \leq \sum_{j=1}^{i-1}n_j \leq (m+1)k$, where each $n_j \in [1,\dots,k]$. I am stuck here. If I could somehow arrive at an inequality to when $\sum_{j=1}^{i-1}n_j \leq a$ for some $a$, with restriction on $n_j$, this would be greatly helped. Thanks.

Answer 1

On each roll, the probability of landing on a multiple of $k$ is $\frac1k$. Thus, by linearity of expectation,

$$\mathbb E[X]=\frac rk\;.$$

Answer 2

From your question I thought you wanted the expected number of times $s_i | k$. Apparently that's not what you wanted, but I may as well answer that original question since I've thought about it. Here the number of rolls can be infinite, since after $k$ rolls your sum will be at least $k$ so you can't have any more divisors of $k$ in the partial sums.

You can take a generating function approach here. If $a_{i,j}$ is the number of ways of rolling $i$ dice so that they sum to $j$, then $$\sum_{j=0}^\infty a_{i,j} x^j = (x + x^2 + \cdots + x^k)^i = \Big(\frac{x(1 - x^k)}{1-x}\Big)^i.$$

So for a fixed divisor $d$ of $k$, $P(s_i = d)$ is $a_{i,j} / k^i$, or the coefficient $x^d$ in $$\Big(\frac{x(1 - x^k)}{k(1-x)}\Big)^i.$$

Then by linearity of expectation the expected number of times $s_i = d$ is the coefficient of $x^d$ in $$\sum_{i=0}^\infty \Big(\frac{x(1 - x^k)}{k(1-x)}\Big)^i = \frac{k(1-x)}{k(1-x) - x(1 - x^k)}.$$

Now extract the coefficient of $x^d$ for all divisors $d$ of $k$ and add them to get the expected number of times $s_i | k$. e.g., for $k=9$ I compute an expectation of $196190821/387420489 \approx 0.5064.$