A set of numbers is generated starting from $0$ in the following way:

  • Add the current number to the resultset
  • In a chance of 50:50, do
    • Either add $2$ to the current number
    • Or subtract $1$ from the current number
  • Go to step 1 or terminate, when some number $n$ is reached or exceeded.

The question is, which percentage of the numbers between 0 and n are in the result set at the end of the process?

Empirically (with a computer program, large numbers and many iterations) I found a value of about 85,40%, but I have some trouble finding a way to calculate the exact value.

With a probability of $2^{-n/2}$ 50% of the numbers are in the result set (always case 1). But how do I proceed?

Can anyone shed some light on this?



You must log in to answer this question.

Browse other questions tagged .