Rolling a certain total with a dice

Question

Suppose you roll a $k$-sided die repeatedly, totaling your scores as you go, until you reach or surpass $n$. (For a real-world usage ... if you have a non-looping game board and only move forward, what are your odds of landing on a specific square?)

What is the probability that you actually hit $n$?

I'm trying to solve this myself and have gotten an ugly closed form for $k=2$, and have a pair of interrelated recursion expressions for $k=3$ . But I feel like there ought to be more elegant solutions than the ones I've achieved, so I thought I'd propose the problem to the community to see if someone else comes up with an answer whilst I work on it.

Answer 1

A recurrence for the probability is given by

\begin{align*} f_n = \left\{\begin{matrix} \dfrac{\sum_{i=1}^k f_{n-i}}{k} & n > k\\ \dfrac{(k+1)^{n-1}}{k^n}& 1\le n \le k \end{matrix}\right. \end{align*} and the corresponding generating function can be written as \begin{align*} F(x) &= \dfrac{1}{1-\dfrac{\sum_{i=1}^kx^i}{k}} \end{align*}

Answer 2

Ok here is a numerical attempt from me. I am not convinced it is right but please show me where I am thinking wrong ( if it is wrong ).

I am thinking a circulant band-matrix $\bf P$ with entry 1/k for the columns $\{i-k,\cdots,i-1\}$ for row $i$ and 0 everywhere else. Start vector is $[1,0,\cdots,0]^T$. Then calculate the monomials $${\bf P}^k{\bf v}$$ will give us probabilities for each state after $k$ throws. Now to not have hit position $n$ after $l$ throws, should it not be with probability $$1-\left\{\prod_{k=0}^{l}({\bf 1}-{\bf P}^k{\bf v})\right\}_n$$

$\bf P$ being circulant makes it diagonalizable with FFT coefficients of a flat filter as eigenvalues ( ramp times a sinc in fourier domain ). Requiring only $O(N)$ operations for each new iterate if one does not count forward and backwards transform. However doubtful that this will be of computational advantage given the length and simplicity of the filter and that we probably need all iterates.