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?