Finding the probability that a specific state is reached in an absorbing state Markov Chain

Question

Suppose an RNG generates a random number in the inclusive range [1, M] and continues to generate numbers in the inclusive range [1, m], where m is the previously generated number, until a 1 is generated. I'm interested in knowing the probability that a specific value, x, is generated at some point during this process.

I have the Markov Chain set up and know the probability of the range being [1, m] at the end of the Nth generation, denoted as P(m, N). However, I'm having difficulty in using this information to answer the above question. I've simulated various results and am noticing that the answer is equal to the sum of P(x+1, N) for all N >= 1, but I don't know why this is the case. For example, with M = 10 and x = 2, the answer appears to be 50%, which is equal to P(3, 1) + P(3, 2) + P(3, 3) + ...

Any insight on this problem in particular or tips on what I should study in order to find the answer would be greatly appreciated!

Answer 1

Here is a process that generates a uniformly random integer in the range $[1,m]$. Start going through the values $m, m-1, m-2, \dots, 1$ in descending order; at each value $k$, stop and return $k$ with probability $\frac1k$, and keep going otherwise. (If we get to $1$, the probability of stopping is $\frac11 = 1$.) This is uniform because the overall probability that we stop at $k$ (and not earlier) is $\frac{m-1}{m} \cdot \frac{m-2}{m-1} \cdots \frac{k}{k-1} \cdot \frac1k = \frac1m$: the same for every $k$.

Suppose that at every step in our overall algorithm (pick a random number between $1$ and the previously picked number, inclusive) we use the process above. However, we have a particular value, $x$, in mind, and we want to know if we'll ever see $x$.

After some variable number of steps, we will get to a range $[1,m]$ for which the subprocess that picks a random integer in the range $[1,m]$ gets to the point of considering the value $k=x$. It is at this moment in time that the fate of $x$ is decided!

• With probability $\frac1k = \frac1x$, the subprocess stops and returns $x$. This means that from the point of view of the overall algorithm, $x$ has now been generated.
• With probability $1 - \frac1k$, the subprocess keeps going to $k-1$, and then maybe onwards to $k-2, k-3, \dots$. The subprocess will now return a value smaller than $x$, and from then on, there will no longer be any chance of generating $x$ in the overall algorithm.

Therefore the probability of ever generating $x$ is equal to $\frac1x$, for all integers $x \in [1,M]$. (This is true regardless of whether we use this particular subprocess for picking random integers, because the method we use should not affect the distribution.)

This process is often considered with the goal of knowing how many numbers are generated overall. There are many ways to answer that question, but after what we've done here, it becomes easy to answer: if the probability of ever generating $x$ is $\frac1x$, then the expected number of values generated is $$\sum_{x=1}^M \frac1x = 1 + \frac12 + \frac13 + \dots + \frac1M$$ which is $H_M$, the $M^{\text{th}}$ harmonic number.