各以1/2的概率输出0和1

各以1/2的概率输出0和1

在看CLRS中的第五章,发现课后的这道习题非常有意思。

题目:Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 – p, where 0 < p < 1, but you do not know what p is. Give an algorithm that uses BIASED-RANDOM as a subroutine, and returns an unbiased answer, returning 0 with probability 1/2 and 1 with probability 1/2. What is the expected running time of your algorithm as a function of p? 解答:(标准答案) To get an unbiased random bit, given only calls to BIASED-RANDOM, call BIASED-RANDOM twice. Repeatedly do so until the two calls return different values, and when this occurs, return the Þrst of the two bits: UNBIASED-RANDOM while TRUE do x ← BIASED-RANDOM y ← BIASED-RANDOM if x ≠ y then return x To see that UNBIASED-RANDOM returns 0 and 1 each with probability 1/2, observe that the probability that a given iteration returns 0 is Pr {x = 0 and y = 1} = (1 − p)p , and the probability that a given iteration returns 1 is Pr {x = 1 and y = 0} = p(1 − p) . (We rely on the bits returned by BIASED-RANDOM being independent.) Thus, the probability that a given iteration returns 0 equals the probability that it returns 1. Since there is no other way for UNBIASED-RANDOM to return a value, it returns 0 and 1 each with probability 1/2. Assuming that each iteration takes O(1) time, the expected running time of UNBIASED-RANDOM is linear in the expected number of iterations. We can view each iteration as a Bernoulli trial, where “success” means that the iteration returns a value. The probability of success equals the probability that 0 is returned plus the probability that 1 is returned, or 2p(1 − p). The number of trials until a success occurs is given by the geometric distribution, and by equation (C.31), the expected number of trials for this scenario is 1/(2p(1 − p)). Thus, the expected running time of UNBIASED-RANDOM is θ(1/(2p(1 − p)).

One thought on “各以1/2的概率输出0和1

  1. Breakthrough Bleeding While On Prometrium Red Asthma Yellow Zone Tbol Hair Loss Bd [url=https://archive.org/details/OrderTestosteroneSupplementDelivery ]Buy Testosterone Enanthate Online[/url]. Skin Care Reviews Acne Treatments Kamagra Chewable Tablet Cialis Generic How Does Fast Food Effects Diabetes Testosterone Peak . Sexual Risks Of Paxil Vicodin Fast Acting . Diabetes Discharge Summary Atenolol And Half Life [url=https://archive.org/details/OrderVicodinNoPrescription ]Vicodin Surly Buy Online No Prescription[/url] No Prescription Order Zoloft Online Price Acai Diet Toprol Nationwide Availability Vicodin Ecstasy And Alcohol
    [url=http://fueri.ch/gbz/viewtopic.php?f=8&t=11870&p=382930#p382930]Buy Free Overnight Pharmacy Mellaril, Online Doctor Consultation For Mellaril[/url]
    [url=http://www.urlstream.tv/forum/index.php?threads/feldene-no-script-required-express-delivery-feldene-no-prescription-uk.1061132/]Feldene No Script Required Express Delivery, Feldene No Prescription Uk[/url]
    [url=http://easycap.org.uk/viewthread.php?tid=497384&extra=&frombbs=1]Order Invega Over The Counter Fedex, Buy Invega Spain[/url]
    [url=http://www.urlstream.tv/forum/index.php?threads/order-geodon-mastercard-discount-geodon-no-prescription.1061211/]Order Geodon Mastercard, Discount Geodon No Prescription[/url]
    [url=http://shes.ir/newreply.php?tid=128&load_all_quotes=1]Order Sinequan Credit Card, Buy Sinequan In Ohio[/url]
    [url=http://easycap.org.uk/viewthread.php?tid=497424&extra=&frombbs=1]Purchase Dexamethasone Cod Cash Delivery – Dexamethasone Brand Name Canada[/url]
    [url=http://easycap.org.uk/viewthread.php?tid=497404&extra=&frombbs=1]Propecia No Prior Script, Reliable Online Pharmacy For Propecia[/url]
    [url=http://easycap.org.uk/viewthread.php?tid=497436&extra=&frombbs=1]Order Cystone Without Prescription From Us – Cystone Without Rx Fedex[/url]
    [url=http://easycap.org.uk/viewthread.php?tid=497395&extra=page%3D1&frombbs=1]Buy Tylenol Online With A Cod, Buy Tylenol No Scams[/url]
    [url=http://www.urlstream.tv/forum/index.php?threads/diamox-no-prescription-mastercard-diamox-overnight-discover-card.1061091/]Diamox No Prescription Mastercard – Diamox Overnight Discover Card[/url]
    [url=http://www.urlstream.tv/forum/index.php?threads/cod-noroxin-for-saturday-order-noroxin-rx.1061103/]Cod Noroxin For Saturday, Order Noroxin Rx[/url]

Leave a Reply

Your email address will not be published. Required fields are marked *