+ Reply to Thread
Results 1 to 2 of 2

Thread: Tricky question

  1. #1
    Points: 4, Level: 1
    Level completed: 7%, Points required for next Level: 46

    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Tricky question




    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

  2. #2
    TS Contributor
    Points: 22,410, Level: 93
    Level completed: 6%, Points required for next Level: 940

    Posts
    3,020
    Thanks
    12
    Thanked 565 Times in 537 Posts

    Re: Tricky question


    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.

+ Reply to Thread

           




Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts






Advertise on Talk Stats