Some intuition behind why we visit $\frac{2}{3}$ of Natural Numbers? Consider stating at $0$ on the number line of integers. Toss a fair coin and if heads advance $1$ space and if tails advance $2$ spaces.

*

*What number has the highest probability of being visited?

*What is the probability of visiting very large numbers roughly?

First part
The following recursive equation can be formed quite nicely conditioning on the first toss: $p_n = \frac{1}{2} p_{n-1} + \frac{1}{2}p_{n-2}$ (for $n \geq 3)$
In other words $p_n$ is the average of $p_{n-1}$ and $p_{n-2}$.
The average of $n$ values is less than or equal to the maximum of the values. Hence, for example, $10$ cannot be the most probably visited square because you visit either $8$ or $9$ with greater probability.
Likewise $9$ cannot be for the same logic continuing until we see $3$ cannot be. Hence the only candidates are $1$ or $2$.
The probability of visiting $1$ is $\frac{1}{2}$ and the probability of visiting $2$ is $\frac{1}{2} \cdot \frac{1}{2} + \frac{1}{2} = \frac{3}{4} $
Hence $2$ is the most probably visited square.
Second part
Solving the recurrence relation formed in the first part (using the intials $p_1$ and $p_2$ )  yields: $p_n = \frac{2}{3} + \frac{1}{3} \cdot (-\frac{1}{2})^n$
This explains the periodicity noticed prior and gives us the long-run average probability  of $\frac{2}{3}$
This number seems way to high for my intuition. I expected it to be $\frac{1}{2} $ can someone provide some intuition behind $\frac{2}{3}$?

The intuition behind it is very simple: the average step length is $\frac32$. Therefore you would expect to traverse a stretch of length $n$ in about $\frac{n}{3/2}=\frac23 n$ steps. So about $\frac23$ of the integers in that stretch will be visited.
