Integers from 1 to N are randomly generated . Each integer has an equal probability of being selected and unlimited repetition is permitted. A running sum is maintained.

Given any integer k, such that 1 <= k <= n , what is the probability that a sum of EXACTLY n will be reached?

Probabilities of Partial Sums

Let P(n,k) be the probability that a run using the integer n will produce a sum of exactly k.

 

Probability of Hitting Exactly n

Integers from 1 to k are repeatedly drawn uniformly at random (with replacement) and a running sum is maintained. We ask:
for a fixed target integer n, what is the probability that some partial sum equals exactly n?

1. Interpretation

At each step you add an independent uniform draw from the set \(\{1,2,\dots,k\}\) (each with probability \(1/k\)). If, at any time, the running sum equals \(n\) we say the target is hit. If the running sum exceeds \(n\) that trial has failed to hit exactly \(n\).

2. Recurrence (computational)

Let \(P(n)\) denote the probability that the process will reach exactly \(n\) starting from sum 0. Then

\[ P(0)=1,\qquad P(n)=\frac{1}{k}\sum_{i=1}^{k} P(n-i)\quad\text{for }n\ge1,\]
with the convention \(P(m)=0\) for \(m<0\).

This recurrence follows by conditioning on the first draw: if the first draw is \(i\) (probability \(1/k\)), we then need to reach \(n-i\) from there.

3. Generating function

Define \(G(x)=\sum_{n\ge0} P(n)x^n\). The recurrence implies

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

Equivalently,

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

4. Combinatorial (closed-form finite sum)

Let \(a(n,m)\) be the number of ordered sequences (compositions) of length \(m\) whose parts lie in \(\{1,\dots,k\}\) and that sum to \(n\). Then

\[ P(n)=\sum_{m=\lceil n/k\rceil}^{n} a(n,m)\left(\frac{1}{k}\right)^m. \]

The integer counts \(a(n,m)\) have an inclusion–exclusion formula (bounded-compositions / stars-and-bars with upper bounds):

\[ a(n,m)=\sum_{j=0}^{\left\lfloor\dfrac{n-m}{k}\right\rfloor} (-1)^j \binom{m}{j} \binom{n-kj-1}{m-1}. \]

Combining gives the finite-sum closed form

\[ P(n)=\sum_{m=\lceil n/k\rceil}^{n} \left(\frac{1}{k}\right)^m \sum_{j=0}^{\left\lfloor\dfrac{n-m}{k}\right\rfloor} (-1)^j \binom{m}{j} \binom{n-kj-1}{m-1}. \]

5. Special checks

• k=1: then the only draw is 1, so \(P(n)=1\) for every \(n\).
• Small k: for k=2 the recurrence becomes \(P(n)=(P(n-1)+P(n-2))/2\) with \(P(0)=1,P(-1)=0\), etc.

6. Small numerical example (corrected)

Take \(k=6\) (uniform on \(\{1,\dots,6\}\)) and compute \(P(n)\) up to \(n=10\) using the recurrence \(P(n)=\tfrac{1}{6}\sum_{i=1}^{6}P(n-i)\) with \(P(0)=1\) and \(P(m)=0\) for \(m<0\).

Exact rational values and decimals

P(0) = 1 = 1.0000000000