+ Reply to Thread
Results 1 to 2 of 2

Thread: Inferring the Number of Sides of a Fair Die

  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

    Inferring the Number of Sides of a Fair Die




    Hello,
    Suppose that Alice has a fair die with N sides, labelled 1..N. Only Alice knows N, and Alice won't tell N to anyone else.
    However, you may ask Alice to toss the die, and then she'll tell you which side came up. You may repeat asking Alice to toss the die as finitely many times as you want.
    Can you devise an algorithm, which infers N with probability at least 99%?

    One possible direction (or maybe not):
    1. Let X be a random variable, which counts the number of tosses until any side comes up twice.
    2. Compute the expected value of X in terms of the unknown N.
    3. Toss the die until some side comes up twice, let Y be the actual number of tosses.
    4. Using some probabilistic bound (e.g. Markov inequality), deduce how many more tosses are needed in order to infer N with probability at least 99%.

    I'd be happy to develop this idea to a proven algorithm, or devise some other proven algorithm.
    Thanks.

  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: Inferring the Number of Sides of a Fair Die



+ 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