# Expected amount of number one can add before reach n

1. Given integer $n$ and real $0\leq d<1$, set $x := 0$, set $c := 0$.
2. set $y := n-x$, if $y < 1-d$, we are done
3. Randomly chose $l\in [1-d, \min(1+d,y)]$, set $x := x + l$, $c := c+1$. Go to 2.

So this is a program that count how many random numbers in $[1-d, 1+d]$ one can add until one reach $n$, except the program won't add a number to go over $n$ when one can add a smaller number.

What is the expected value of $c$?

In one part of my program it output the expected value of $c$ by running the above program many many times. But I don't know if my program is correct, therefore knowing what I should expect will help me test my program's correctness.

• For $d$ small(large), it seems that $c$ would be large(small). This looks like a random walk. – PrimeNumber Jan 5 '11 at 4:31
• Can you provide some results (obtained using your program), for various values of $d$ and $n$? – Shai Covo Jan 5 '11 at 8:07
• Since a uniform$(a,b)$ random variable can be written as $a+(b-a)U$, where $U$ is uniform$(0,1)$, simulation according to your algorithm is the best choice for approximating that expectation. A better solution is not likely to be found. – Shai Covo Jan 5 '11 at 10:53

As I commented above, implementation of the OP's algorithm is very easy, noting that a uniform$[a,b]$ variable can be written as $a+(b-a)U$, with $U \sim {\rm uniform}[0,1]$. We now show that, for $0<d \leq 1/3$, the exact expression is quite complicated (and probably the case $d>1/3$ is more complicated).
For $0<d \leq 1/3$, one should be able to show that the problem is equivalent to the following one (this is confirmed, as noted in the last paragraph). Suppose that $X_i$ are i.i.d. uniform$[1-d,1+d]$ variables, and let $S_k = \sum\nolimits_{i = 1}^k {X_i }$. Further, let $\tau$ denote the first index $k$ such that $S_k > n - (1-d)$. Find ${\rm E}(\tau)$. (The assumption $d \leq 1/3$ comes from $2(1-d) \geq 1+d$.)
As I described in some previous post, ${\rm E}(\tau)$ can be calculated as follows. Let $F^{(k)}$ denote the distribution function of $S_k$, that is, $F^{(k)}(x) = {\rm P}(S_k \leq x)$. Set $x = n-(1-d)$. Then, ${\rm E}(\tau) = 1 + \sum\nolimits_{k \ge 1} {F^{(k)} (x)}$ (note that the sum is finite). Now, the $X_i$ can be written as $(1-d)+2dU_i$, where $U_i$ are i.i.d. uniform$[0,1]$. However, the distribution function of the sum of i.i.d. uniform variables is complicated, and hence approximating ${\rm E}(\tau)$ using computer simulations is a good idea.
I implemented the OP's algorithm (as given in the question). Numerical results confirm that, for $d \leq 1/3$, the expectation in the question is indeed given by $1 + \sum\nolimits_{k \ge 1} {F^{(k)} (x)}$ (I approximated $F^{(k)} (x)$ using computer simulations). For example, for $n=3$, $d=0.1$, OP's algorithm gave $\approx 2.87488$, my formula gave $\approx 2.87474$; for $n=6$, $d=0.2$: $\approx 5.77619$ vs. $5.77694$; for $n=10$, $d=0.3$: $9.81563$ vs. $9.81554$. (Of course, we can increase accuracy by using a larger number of simulations.)