Expected Number of Draws to Get 1: A Probability Analysis

[Aladdin]

Here's the problem:
Let P(k) be a random draw of integers between 1 and k (inclusive). Assume you repeatedly apply P, starting at 10^1000. What's the expected number of repeated applications until you get 1? Why?

What is your understanding of the following statement?
Assume you repeatedly apply P, starting at 10^1000.

1) We are asked to repeatedly apply P(k), where k is given and equal to 10^1000.

• 1a) Each drawn element is redrawable again even after being drawn (i.e. each draw is independent)
• 1b) Each drawn element is undrawable after being drawn once (i.e. each draw is dependent on previous draws)

2) We are asked to repeatedly apply P(k), where k is an integer such that k=10^1000 on 1st draw and then k = some random integer from 2nd draw onward.

Case 1a)
Since best case is that it takes just one draw and worst case is that it takes k draws, I'd guess the expected number of repeated applications until you get 1 is k/2 but I can't really explain why.

Case 1b)
My understanding is that the probability of getting 1 is 1/k on 1st draw, 1/(k-1) on 2nd draw, ..., all the way up to 1 on kth draw. But how does this help me get to the expected number of repeated applications until you get 1?

Case 2)
Am I overcomplicating it? :)

Thank you for your hints :)

 

[jvicens]

Thank you for your interesting question. I would like to clarify the statement "repeatedly apply P, starting at 10^1000". This means that we are repeatedly drawing integers between 1 and 10^1000 (inclusive) until we get 1. Each draw is independent, meaning that the previous draws do not affect the probability of getting 1 in the current draw. This is different from dependent draws, where the probability of getting 1 in the current draw would be affected by the previous draws.

Now, let's consider the expected number of repeated applications until we get 1. In the best case scenario, we get 1 in the first draw itself. In the worst case scenario, we would have to draw 10^1000 times before getting 1. However, since each draw is independent, the probability of getting 1 in each draw remains the same, which is 1/10^1000. Therefore, the expected number of repeated applications until we get 1 is simply the reciprocal of this probability, which is 10^1000.

In case 1b, where each draw is dependent on the previous draws, the probability of getting 1 would change with each draw. However, the expected number of repeated applications would still be the same, which is 10^1000. This is because the probability of getting 1 in each draw would still be 1/10^1000, and the number of draws required to get 1 would still be 10^1000.

In case 2, where k changes after the first draw, the expected number of repeated applications would also change. However, without knowing the specific values of k, it would be difficult to determine the exact expected number of applications. It would depend on the distribution of k and the probability of getting 1 in each draw.

I hope this helps clarify the statement and the expected number of repeated applications until we get 1. If you have any further questions, please do not hesitate to ask.