Probability Question

[Shaun9887]

There is a pre-chosen, random number between 1-1000. Your goal is to guess the number.

You are given one chance to guess the number. If you guess it wrong, that number is removed from the available numbers.

For example, you guess the number 1 and you're wrong. Now the remaining potential numbers are 2-1000.

You are allowed to guess until you get it right. Every time you make an incorrect guess, that number is removed from the potential numbers.

How many guesses, on average, will it take to correctly guess the number?

 

[Shaun9887]

Does this work:

We divide 1 by the number of remaining numbers. So, to begin, we divide 1/1000.

We then remove 1 choice from the available numbers and divide 1 by the remaining choices, which is 1/999.

We then remove 1 choice from the available numbers and divide 1 by the remaining choices, which is 1/998...

We then add 1/1000 + 1/999 + 1/998...

We continue with this pattern until the total sum is equal to 1?

 

[Dr.Peterson]

There is a pre-chosen, random number between 1-1000. Your goal is to guess the number.

You are given one chance to guess the number. If you guess it wrong, that number is removed from the available numbers.

For example, you guess the number 1 and you're wrong. Now the remaining potential numbers are 2-1000.

You are allowed to guess until you get it right. Every time you make an incorrect guess, that number is removed from the potential numbers.

How many guesses, on average, will it take to correctly guess the number?

What is the probability that your first guess will be correct? How about the second, and the third, and so on? (This is easy, but it's also easy to make a mistake!)

Then find the expected value of X, the number of the correct guess.

Does this work:

We divide 1 by the number of remaining numbers. So, to begin, we divide 1/1000.

We then remove 1 choice from the available numbers and divide 1 by the remaining choices, which is 1/999.

We then remove 1 choice from the available numbers and divide 1 by the remaining choices, which is 1/998...

We then add 1/1000 + 1/999 + 1/998...

We continue with this pattern until the total sum is equal to 1?

Can you explain why you think this would work, or are you just making a guess?

If those fractions are supposed to be probabilities (you didn't say what they are), why would you add them?

 

[Shaun9887]

What is the probability that your first guess will be correct? How about the second, and the third, and so on? (This is easy, but it's also easy to make a mistake!)

Then find the expected value of X, the number of the correct guess.

Thanks for responding, Dr. Peterson.

The probability that our first guess will be correct is 999 to 1. In other words, we will guess incorrectly 999 times and make one correct guess.

The second guess is 998 to 1. We will guess incorrectly 998 times and make one correct guess.

Assuming we don't guess the correct number, this pattern continues until there is only 1 number left, in which case our chances of guessing correctly are 100%.

 

[Shaun9887]

What is the probability that your first guess will be correct? How about the second, and the third, and so on? (This is easy, but it's also easy to make a mistake!)

Then find the expected value of X, the number of the correct guess.


Can you explain why you think this would work, or are you just making a guess?

If those fractions are supposed to be probabilities (you didn't say what they are), why would you add them?

Those fractions are supposed to be probabilities.

I am making my best guess on how the equation works, and that is how I arrived at my answer.

I did this based on what I could learn about expected value of a binomial variable on Khan Academy.

This reason I could not calculate the answer based entirely on what I could learn about expected value of a binomial variable is because the probability that we will choose the correct number on each subsequent guess improves.

I'm 42 years old and I have not studied math since high school. So this is anything but easy for me ?

 

[Dr.Peterson]

Thanks for responding, Dr. Peterson.

The probability that our first guess will be correct is 999 to 1. In other words, we will guess incorrectly 999 times and make one correct guess.

The second guess is 998 to 1. We will guess incorrectly 998 times and make one correct guess.

Assuming we don't guess the correct number, this pattern continues until there is only 1 number left, in which case our chances of guessing correctly are 100%.

You're using the language of odds rather than probabilities; that's generally harder to work with mathematically. The probability of the first guess being correct is 1/1000 (1 in 1000, which corresponds to odds of 1:999).

The probability that the second guess is correct, GIVEN THAT the first was incorrect, is 1/999 (corresponding to odds of 1:998). But the probability (a priori) that you will be correct on the second guess is P(correct on second | wrong on first) * P(wrong on first) = 1/999 * 999/1000 = 1/1000. The same reasoning shows that you are equally likely to be correct on any one guess. This makes sense, because after the fact we could just list all your guesses (including what you would have guessed if you hadn't already won), and each of those is equally likely to have been correct.)

This reason I could not calculate the answer based entirely on what I could learn about expected value of a binomial variable is because the probability that we will choose the correct number on each subsequent guess improves.

This is not a binomial variable. It's actually uniform, as I've shown that each value (each number of guesses before being correct) is in fact equally likely.

Can you use what you've learned about expected value based on that?

 

[Shaun9887]

I appreciate you responding. This has gone way over my head.

I'm trying to determine how many guesses, on average, it will take to correctly guess the number.

Although each value is in fact equally likely, I am thinking that this is not relavent in determining how many guesses it will take to correctly guess the number.

Am I wrong about that?

 

[Shaun9887]

You're using the language of odds rather than probabilities; that's generally harder to work with mathematically. The probability of the first guess being correct is 1/1000 (1 in 1000, which corresponds to odds of 1:999).

As I understand it, if incorrect guesses were not removed each time they were made, then it would take 1000 guesses to correctly guess the number, on average.

The part that I am stuck on is how we adjust for the fact that incorrect guesses are being removed each time they occur.

This is what led me to the number 632-633.

I took the % chance of the first guess being correct, and then added it to the % chance of the second guess being correct, until I reached the number 1.

The reason I think this is correct is because, if we add the percentage chance of each guess together until we come to the number 1, we have summed up all of our chances to create an average. Does that make sense? Can you tell me if this formula is correct?

 

[Dr.Peterson]

As I understand it, if incorrect guesses were not removed each time they were made, then it would take 1000 guesses to correctly guess the number, on average.

The part that I am stuck on is how we adjust for the fact that incorrect guesses are being removed each time they occur.

Removing incorrect guesses does nothing more than to ensure that you don't make the same guess twice. That's why each guess you make is equally likely to be correct (because each number in the list is equally likely to have been chosen in the first place).

I took the % chance of the first guess being correct, and then added it to the % chance of the second guess being correct, until I reached the number 1.

The reason I think this is correct is because, if we add the percentage chance of each guess together until we come to the number 1, we have summed up all of our chances to create an average. Does that make sense? Can you tell me if this formula is correct?

It will in fact be an average; that's what expected value is. More specifically, it is a weighted average, each possibility being weighted by its probability. In this case, all the weights are equal.

So, what is the average of the numbers 1 through 1000?

 

[Shaun9887]

Removing incorrect guesses does nothing more than to ensure that you don't make the same guess twice. That's why each guess you make is equally likely to be correct (because each number in the list is equally likely to have been chosen in the first place).

Am I correct in saying that removing incorrect guesses improves the odds of each subsequent guess? For example, Our first guess has odds of 999 to 1, while our second guess has odds of 998 to 1?

I thought that would be relevant to the answer. But it sounds like you're saying it's not. (I'm confident you're right, it's just not intuitive to me)

So, what is the average of the numbers 1 through 1000?

The average of the numbers 1 through 1000 is 500. Are you saying that the answer is 500? (Intuitively, it feels like it should be a more complicated equation than that.)

 

[Dr.Peterson]

Am I correct in saying that removing incorrect guesses improves the odds of each subsequent guess? For example, Our first guess has odds of 999 to 1, while our second guess has odds of 998 to 1?

I thought that would be relevant to the answer. But it sounds like you're saying it's not. (I'm confident you're right, it's just not intuitive to me)

What improves each time is the CONDITIONAL probability for each guess, which is what you are citing. What you need to find the expected value is the probability that your nth guess will be the correct one, and that (the probability as judged from the start, not after n-1 guesses) is the same for each.

You're right, it's not intuitive, and in fact is counter-intuitive for most people. That's why you have to apply what you're learning, not your untrained intuition!

Here's what I said before:

The probability that the second guess is correct, GIVEN THAT the first was incorrect, is 1/999 (corresponding to odds of 1:998). But the probability (a priori) that you will be correct on the second guess is P(correct on second | wrong on first) * P(wrong on first) = 1/999 * 999/1000 = 1/1000. The same reasoning shows that you are equally likely to be correct on any one guess. This makes sense, because after the fact we could just list all your guesses (including what you would have guessed if you hadn't already won), and each of those is equally likely to have been correct.)

Have you carefully thought through that?

The average of the numbers 1 through 1000 is 500. Are you saying that the answer is 500? (Intuitively, it feels like it should be a more complicated equation than that.)

Almost, but not quite.

Let's take a small case. Suppose there are three choices, A, B, and C. The probability that the correct one is A is 1/3, and likewise for B and for C. Say I guess in the order B, A, C. The probability that my first guess, B, is correct is 1/3. So is the probability for my second guess, and my third guess. (And the sum of these is 1, as it has to be, but wouldn't be if the probabilities increased as you think!)

So the expected value of X, the number of guesses I need, is 1*P(1) + 2*P(2) + 3*P(3) = (1+2+3)*1/3 = 6/3 = 2. And that is the average of 1, 2, and 3. It's also the average of 1 and 3, the first and last numbers. (Observe that this is not half of 3!)

Now, what is the average of 1 and 1000? (Again, both you and I first go for a slightly wrong number -- intuition is not always right, even for me!)

 

[Shaun9887]

Now, what is the average of 1 and 1000? (Again, both you and I first go for a slightly wrong number -- intuition is not always right, even for me!)

The average of 1 and 1000 is 500.5!

Is it safe to assume that this would work for any range of numbers?

For example, as you mentioned above, the average of 1 and 3 is 2. The average of 1 and 10 is 5.5. The average of 1 and 2 is 1.5 etc

So, we don't have to worry ourselves with calculating the odds of each guess, as I was saying earlier with 999:1, 998:1 etc.

We can simply take the average of the range of numbers, and that will always be the correct answer to this question, regardless of what range we use?

 

[Dr.Peterson]

The average of 1 and 1000 is 500.5!

Is it safe to assume that this would work for any range of numbers?

For example, as you mentioned above, the average of 1 and 3 is 2. The average of 1 and 10 is 5.5. The average of 1 and 2 is 1.5 etc

So, we don't have to worry ourselves with calculating the odds of each guess, as I was saying earlier with 999:1, 998:1 etc.

We can simply take the average of the range of numbers, and that will always be the correct answer to this question, regardless of what range we use?

If the probabilities were different, you would have to take them into account. It is only because they are equal that we can take an ordinary average. So in that sense, you do have to work them out.

But whenever you have an arithmetic sequence (that is, numbers equally spaced, as these are all 1 apart), the average of all of them is the same as the average of the first and last. That's because the average of the second and next to last, and of the third and the second from last, and so on, are all equal. For example, in 1, 2, 3, 4, 5, we have 1+5=6, and 2+4=6, so their averages are 3, and 3 is its own average. The sum of all the numbers is just the number of numbers times that average: 1+2+3+4+5 = 15 = 5*3.

 

[Shaun9887]

If the probabilities were different, you would have to take them into account. It is only because they are equal that we can take an ordinary average. So in that sense, you do have to work them out.

I see now that I was not being precise enough with my question.

What I could have asked was, if the rules regarding the scenario are the same, can we always take the average of the first and last numbers to find the answer?

For example, if the range of numbers is 1-20, will it take 10.5 (the average of 1 and 20) guesses on average to correctly guess the number?

 

[Dr.Peterson]

I see now that I was not being precise enough with my question.

What I could have asked was, if the rules regarding the scenario are the same, can we always take the average of the first and last numbers to find the answer?

For example, if the range of numbers is 1-20, will it take 10.5 (the average of 1 and 20) guesses on average to correctly guess the number?

No, you were sufficiently precise, and so was I. If the guesses are done in such a way that each possible number of guesses is equally likely (that's a more precise version of your "if the rules regarding the scenario are the same"), then the expected number of guesses is the average of all the possible numbers; and, if a set of numbers form an arithmetic sequence (equally spaced), then their average is the average of the first and last.

So, yes, if you have the same problem but a different number of items (say N), then the expected number of of guesses is (N+1)/2. That is an appropriate conclusion from what I said.

 

[Shaun9887]

Thanks very much Dr Peterson. It's been a fascinating discussion, I learned a lot.