Draws are independent and uniformly chosen from the set \{1,2,\dots,k\} (with unlimited repetition).
Let p(n) denote the probability that at some time the running sum equals exactly n.

1. Recurrence

With the convention p(m)=0 for m<0 and p(0)=1, the probability satisfies the recurrence

    \[ p(0)=1,\qquad p(n)=\frac{1}{k}\sum_{i=1}^{k} p(n-i)\quad\text{for }n\ge1. \]

(This comes from conditioning on the value of the first draw: if the first draw is i then we must subsequently hit n-i.)

2. Generating function

Let P(x)=\sum_{n\ge0} p(n)x^n. Summing the recurrence gives the closed form

    \[ P(x)=\frac{1}{1-\dfrac{x(1-x^k)}{k(1-x)}}. \]

Equivalently,

    \[ P(x)=\frac{k(1-x)}{k(1-x)-x(1-x^k)}. \]

The coefficient of x^n in this rational function equals p(n).

3. Combinatorial (explicit) formula

Another useful representation counts ordered compositions of n into m parts each in \{1,\dots,k\}.
If c_{n,m} denotes the number of such compositions with exactly m parts, then

    \[ p(n)=\sum_{m=1}^{n}\frac{c_{n,m}}{k^m}. \]

By inclusion–exclusion one can write

    \[ c_{n,m}=\sum_{j=0}^{\left\lfloor\frac{n-m}{k}\right\rfloor} (-1)^j\binom{m}{j}\binom{n-jk-1}{m-1}, \]

so a fully explicit formula is

    \[ \boxed{\,p(n)=\sum_{m=1}^{n}\frac{1}{k^m}\sum_{j=0}^{\left\lfloor\frac{n-m}{k}\right\rfloor} (-1)^j\binom{m}{j}\binom{n-jk-1}{m-1}\, }. \]

4. Remarks and small cases

  • k=1: p(n)=1 for every n (every draw is 1 so every positive integer is hit).
  • k=2: p(n)=\tfrac12\big(p(n-1)+p(n-2)\big) with p(0)=1; values can be computed quickly from the recurrence.
  • The generating function form is convenient for extracting asymptotics or for computing p(n) by partial fractions (roots of the denominator polynomial).

Recap (as before): draws are iid and uniform on \{1,2,\dots,k\}. Let p(n) be the probability that some partial sum equals exactly n.
With the convention p(m)=0 for m<0 and p(0)=1,

    \[ p(n)=\frac{1}{k}\sum_{i=1}^{k} p(n-i)\qquad (n\ge1). \]

Numerical examples

Below are computed values of p(n) for k=2,3,4 and n=0,1,\dots,12. (Remember p(0)=1.)

k=2 (each draw is 1 or 2 with probability 1/2)
n p(n)
0 1.000000000000
1 0.500000000000
2 0.750000000000
3 0.625000000000
4 0.687500000000
5 0.656250000000
6 0.671875000000
7 0.664062500000
8 0.667968750000
9 0.666015625000
10 0.666992187500
11 0.666503906250
12 0.666748046875
k=3 (each draw is 1, 2 or 3 with probability 1/3)
n p(n)
0 1.000000000000
1 0.333333333333
2 0.444444444444
3 0.592592592593
4 0.456790123457
5 0.497942386831
6 0.515775034294
7 0.490169181527
8 0.501295534217
9 0.502413250013
10 0.497959321919
11 0.500556035383
12 0.500309535772
k=4 (each draw is 1,2,3 or 4 with probability 1/4)
n p(n)
0 1.000000000000
1 0.250000000000
2 0.312500000000
3 0.390625000000
4 0.488281250000
5 0.360351562500
6 0.387939453125
7 0.406799316406
8 0.410842895508
9 0.391483306885
10 0.399266242981
11 0.402097940445
12 0.400922596455

Observations

  • For k=2 the probabilities converge quickly to 2/3\approx 0.666666\ldots (the table shows values oscillating about that limit).
  • For k=3 and k=4 the values for moderate n tend to a limiting value (the limit exists and equals the reciprocal of the mean waiting-time to cross a large interval — this can be analyzed via renewal theory or by studying the generating function). Numerically you can see the values settle near about 0.5 for k=3 and near 0.401 for k=4 at the n shown.

— End

 

— End