Describe a fair coin algorithm to returns either 0 or 1

Assignment Help Data Structure & Algorithms

Reference no: EM1352315

1. Consider the following randomized algorithm for generating biased random bits. The subroutine FAIRCOIN returns either 0 or 1 with equal probability; the random bits returned by FAIRCOIN are mutually independent.

ONEINTHREE:
if FAIRCOIN = 0
return 0
else
return 1 - ONEINTHREE

(a) Prove that ONEINTHREE returns 1 with probability 1/3.

(b) What is the exact expected number of times that this algorithm calls FAIRCOIN?

(c) Now suppose you are given a subroutine ONEINTHREE that generates a random bit that is equal to 1 with probability 1/3. Describe a FAIRCOIN algorithm that returns either 0 or 1 with equal probability, using ONEINTHREE as your only source of randomness.

(d) What is the exact expected number of times that your FAIRCOIN algorithm calls ONEINTHREE?

Reference no: EM1352315

Questions Cloud

Exposure to domestic violence : Please provide four resolution strategies to the effects that exposure to domestic violence has on children, based on research based interventions.

Behavioural-dealing with dominat employee : Behavioural-dealing with dominat employee - Nikita is one of the 12 workers in Department X. She has strong leadership qualities and all her co-workers look up to her.

Explain how would you present the statistical information : Explain How would you present the statistical information within this case to the Industry Week decision maker

Illustrate what philosophical principle did google manager : Illustrate what philosophical principle did Google's managers adopt when deciding that the benefits of operating in China outweighed the costs.

Describe a fair coin algorithm to returns either 0 or 1 : Describe a FAIRCOIN algorithm that returns either 0 or 1 with equal probability, using ONEINTHREE as your only source of randomness.

Describe the acquisition affects : The book value of Nott's Nursery's total assets is $400,000. Assume Golden Gardens Inc. acquires Nott's Nursery's assets for 1 million dollar and finances the purchase by selling $600,000 in new stock,

What focal length does the lens need : A 0.280 kg ball is dropped from rest at a point 1.35m above the floor. The ball rebounds straight upward to a height of 0.780 m. What are the magnitude and direction of impulse of the net force applied to the ball during the collision with the flo..

Definition of cognitive psychology : Offer a 3-sentence definition of cognitive psychology. How important do you believe the understanding and employment of neuroscience to be in the study of cognition?

Management - : Bazerman makes a pretty convincing case in his writ-up regarding the futility of trying to beat the market

User Account

All Pages