高级算法 (Fall 2022)/Problem Set 4

From TCS Wiki
Revision as of 07:29, 12 December 2022 by Gispzjz (talk | contribs) (Created page with "== Problem 1 == Suppose there is a coin <math> C </math>. During each query, it outputs HEAD with probability <math>p</math> and TAIL with probability <math>1-p</math>, where <math> p \in (0, 1) </math> is a real number. * Let <math> q \in (0, 1) </math> be another real number. Design an algorithm that outputs HEAD with probability <math>q</math> and TAIL with probability <math>1-q</math>. There is no other random sources for your algorithm except the coin <math>C</math...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem 1

Suppose there is a coin [math]\displaystyle{ C }[/math]. During each query, it outputs HEAD with probability [math]\displaystyle{ p }[/math] and TAIL with probability [math]\displaystyle{ 1-p }[/math], where [math]\displaystyle{ p \in (0, 1) }[/math] is a real number.

  • Let [math]\displaystyle{ q \in (0, 1) }[/math] be another real number. Design an algorithm that outputs HEAD with probability [math]\displaystyle{ q }[/math] and TAIL with probability [math]\displaystyle{ 1-q }[/math]. There is no other random sources for your algorithm except the coin [math]\displaystyle{ C }[/math]. Make sure that your algorithm halts with probability [math]\displaystyle{ 1 }[/math].
  • What is the expected number of queries for the coin [math]\displaystyle{ C }[/math] that your algorithm use before it halts?
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2022)/Problem_Set_4&oldid=10289"