4
$\begingroup$
  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.

  • 0
    For $d$ small(large), it seems that $c$ would be large(small). This looks like a random walk.2011-01-05
  • 0
    Can you provide some results (obtained using your program), for various values of $d$ and $n$?2011-01-05
  • 0
    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.2011-01-05

1 Answers 1

3

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 $01/3$ is more complicated).

For $0 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.)