Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  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.

share|improve this question
    
For $d$ small(large), it seems that $c$ would be large(small). This looks like a random walk. –  PEV 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
add comment

1 Answer

up vote 3 down vote accepted

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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