Probability of an alternating series of random numbers in the range $[1,N]$ whose sum adds up to the desired number $N$?

71 Views Asked by At

Suppose any number $N$ can be represented as an alternating series of random numbers in the range $[1,N]$ whose sum adds up to the desired number $N$.

For example, let $N=5$, then generating random numbers in the range $[1,5]$ gives

$$4-2+4-1$$

Plotting this shows it took $4$ random terms to reach the desired number $5$

sum0

Another run showing over $60$ terms

sum1

The last run showing $7500+$ terms

sum2

Expressing this in mathematical notation

$$N = \sum_{i=1}^{n} (-1)^{i-1} a_i$$

where $a_i \in {1, 2, ..., N}$ is random.

Question

Is there a way to determine the probability of this method converging to the desired number $N$?

All tests eventually converged but took much longer as $N$ increased.

Got the idea from reading about a Random Walk--2-Dimensional

Amazingly, it has been proven that on a two-dimensional lattice, a random walk has unity probability of reaching any point (including the starting point) as the number of steps approaches infinity.