The probability for guessing a dynamic value (one that changes for each wrong guess)

Question

Please correct me if I am wrong...

For a random number X between 1 and 100, the probability for guessing X correctly would be 1/100

For 2 random numbers X and Y between 1 and 100, the probability for guessing X then Y correctly would be (1/100) * (1/100)

For a random number X between 1 and 100, what is the probability for guessing X, if X gets a new random value each time we guess X wrong?

(Assuming we can guess 100 times, each wrong guess generates a value that is different than the previous one only.)

Answer 1

The answer to the original question: The probability is 1, because we can simply guess 42 each time, and since the first 100 numbers must be different elements of a 100-element set, and we get to guess (at least) 100 times.

To the update: As André points out, we're not going to see a ton of improvement. This is because there isn't any useful strategy for this game: regardless of the number that we choose, the only information we ever know about the number is that it can't be the same one that it was before (except the first guess where we know nothing); in particular it has no relationship to the number we chose. Therefore, every strategy is effectively equal to choosing 42 every time.

However, we do improve slightly on the merit that it is an easier game: on any turn there are only 99 possibilities that the number has, which means that from the second guess forward, we have probability $\frac{1}{99}$ of getting it right. The first guess we still have probability $\frac{1}{100}$.

The easiest way to get from probability that the samples are right to the probability we're right ever is to say that being right at least once is the same thing as not being wrong every time. The total probability of being wrong every time is $P'=\left(1-\frac{1}{100}\right)\left(1-\frac{1}{99}\right)^{99}$, and so the probability of being right one of these times is $P=1-\left(1-\frac{1}{100}\right)\left(1-\frac{1}{99}\right)^{99}$, or if you prefer, $1-\left(\frac{99}{100}\right)\left(\frac{98}{99}\right)^n$.

It's worthwhile to try to use these principles to find the probabilities in this game for any $n$ (the number of guesses), and then any $n$ and $k$ (the "memory" of the variable; in this case 1), and finally any $n$ and $k$ and $S$ (the number of initial options for the variable). This is relatively straightforward, if not necessarily easy. The end result is pretty non-trivial and impressive-looking, though, and you can look back at it and say "Wow, I ended up coming up with this big formula just because of this tiny idea," which is personally one of my favorite things about math.

(If you work on this, it might be helpful to know that there is a widely accepted notation analogous to $\displaystyle \sum_{i=a}^b f(i)$, but that gives, instead of the $\mathbf{s}$um of the terms, their $\mathbf{p}$roduct. We write this as $\displaystyle\prod_{i=a}^b f(i)$. For instance, you could write that $x!=\displaystyle\prod_{i=1}^x i$ because the factorial of $x$ is the product of the integers between $1$ and $x$.)

Answer 2

This perhaps gives a step towards an answer. Suppose that each time, a number is selected, possibly the same number as before, with all numbers equally likely. Then the probability that in $k$ or fewer guesses we will get a match is $$1-\left(1-\frac{99}{100}\right)^k.$$ For $k=100$, this is about $0.6339677$.

Suppose now that we know that if we guess incorrectly, a new number will be selected, with all allowed numbers equally likely. We use the strategy of guessing $1,1,1,\dots$.

If at any stage we are wrong, then with probability $\frac{1}{99}$ the next number is the number we guessed, a slight improvement over the previous $\frac{1}{100}$. Thus the probability that in $k$ or fewer iterations of the guess $1$ we will get a match is $$\frac{1}{100}+\frac{99}{100}\left(1-\left(1-\frac{1}{99}\right)^{k-1} \right).$$ For $k=100$, this is about $0.6376465$.

Thus the information there is an actual change can be used to get at least a small advantage over the unrestricted choice model.