Tricky question

#1
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 :)
 

BGM

TS Contributor
#2
1a) First you read about Geometric distribution. If you need to tackle this problem without mentioning geometric distribution, you can still work with the same principle and derive the expectation (which is a sum to infinity of a geometric series)

1b) Note that each permutation is equally likely so you are working with a Uniform distribution.

2) You need to define "some random integer". Otherwise it will be too vague to continue.