K-Sided Coin Toss Experiment

A k-Sided Coin Toss Experiment is a Multinomial Trial that involves the Uniform random selection of one of k-Random Experiment Outcomes (an k-Nomial Experiment).

• AKA: k-Coin Toss Experiment.
• Context:
  • It can be:
    • an Unbiased k-Sided Coin Toss Experiment.
    • a Biased k-Sided Coin Toss Experiment.
• Example(s):
  • a 2-Sided Coin Toss Experiment.
• See: Multinomial Experiment.

---

---

References

• http://www.cs.bgu.ac.il/~kobbi/courses/complexity_06/Assignments/ex5.pdf
  • Exercise: Consider the following procedure for flipping k-sided coins given two-sided coins:
    • 1. Flip a two-sided coin for dlog2 ke times; the result is a binary number r.
    • 2. If r 2 [0, ..., k − 1] output r. Otherwise, repeat the process.
      • (a) Give an upper bound on the expected number of repetitions in the above procedure.
      • (b) What is the probability of no success after t repetitions?
      • (c) To flip n k-sided coins, repeat the above procedure n time. Show that the probability you will need more than 2n log k coins is exponentially small.
• http://www.k-state.edu/stats/tch/dubnicka/stat510/handout9.pdf
  • TERMINOLOGY : A multinomial experiment is simply a generalization of a bi-nomial experiment. In particular, consider an experiment where
    • the experiment consists of n trials (n is fixed),
    • the outcome for any trial belongs to exactly one of k ≥ 2 classes,
    • the probability that an outcome for a single trial falls into class i is given by
      • pi, for i = 1, 2, . . ., [math]\displaystyle{ k }[/math], where each pi remains constant from trial to trial (and
      • p1 + p2 + · · · + pk = 1), and
    • trials are independent.

---