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.

  • $\begingroup$ For $d$ small(large), it seems that $c$ would be large(small). This looks like a random walk. $\endgroup$ – PrimeNumber Jan 5 '11 at 4:31
  • $\begingroup$ Can you provide some results (obtained using your program), for various values of $d$ and $n$? $\endgroup$ – Shai Covo Jan 5 '11 at 8:07
  • $\begingroup$ 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. $\endgroup$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.