Tricky probablity question

Forums: Probability
Email this Topic • Print this Page

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 Smile

Topic Stats
Top Replies
Link to this Topic

Type: Question • Score: 0 • Views: 720 • Replies: 3

No top replies

@Aladdin,

1a) Because each draw is independent, the chance of not getting 1 is (k-1)/k. The chance of not getting 1 after n draws is [(k-1)/k]^n. If k is very large, this is equal to e^(-n/k). The expected number occurs when that equals 0.5, so

0.5 = e^(-n/k)
ln 0.5 = -n/k
n = .693k

1b) This is a lot easier. Since you don't have replacement, it is just k/2. Once I have drawn half the numbers, I have a 50% chance of drawing any given number.

2) I really don't get the question. Does k change for every pull? Is there a pattern to it?

1 Reply

@engineer,

My first question is: how do you understand the question itself? Smile From the question, do you understand the case is 1a, 1b or 2? Or, like me, you understand that the question is (deliberately) left unclear in order to see how you think about the problem?

In case 1a), we are assuming k=10^1000. Where does this e^(-n/k) come from? and why do you say that the expected number occurs when that equals 0.5?

Case 2) is just an hypothesis regarding what the guy who wrote the question could mean. I am asking myself if he really meant that k changes at every pull.

1 Reply

@Aladdin,

I think the question is ridiculously worded. That said, I read it as 1a. I do not see it as deliberately unclear.

One of the definitions of e = lim (1 + 1/x)^x as x goes to infinity. The probability of drawing n numbers from k possible and not getting 1 is

P = [(k-1)/k]^n
P = [1 - 1/k] ^ n
P = [1 - 1/k] ^ k(n/k)
let x = -k
P = [1 + 1/x] ^ x(n/x) = {[1 + 1/x] ^ x}^n/x
For large values of x you get:
P ~ e^n/x = e^(-n/k)

I am sure that the writer did not want k to change. I think the very large value was selected so that you could use the exponential simplification.

0 Replies

Tricky probablity question

Related Topics

Quick Links

My Account

able2know