Getting a Head a probability of p and getting a tail of probability 1-p .then find Whats The Expected Number of Tosses to to Get Head.?
Thursday, October 20, 2011
Thursday, August 25, 2011
what is the expected number of times he will have to toss his coin to see that pattern.
One day Rohil was getting very bored so he was tossing an unbiased coin randomly. He observed that certain patterns (a sequence of Head and Tail) appear very frequently while some other are very rare. Being a programmer he decided to code a solution which takes a pattern string as input and tells what is the expected number of times he will have to toss his coin to see that pattern. He wrote this program very quickly. Can you?
Input
First line contains ( 1<=T<=25 ) the number of test cases. Each of following T lines contains a pattern string of 'H' and 'T' only. H is for Head and T is for Tail.
|S| <= 40
Output
For each test case print the output in a new line (it is guaranteed that answer will always be an integer and fits in 64 bit type).
Example
Input:
3
H
HTHT
TTHTHTHTHTHHTHTHTHTTTTTTHTHHHHHTT
Output:
2
20
8589934598
Solution http://www.se.cuhk.edu.hk/~seem3570/12-pattern.pdf
http://deepblue.lib.umich.edu/bitstream/2027.42/24435/1/0000708.pdf
Input
First line contains ( 1<=T<=25 ) the number of test cases. Each of following T lines contains a pattern string of 'H' and 'T' only. H is for Head and T is for Tail.
|S| <= 40
Output
For each test case print the output in a new line (it is guaranteed that answer will always be an integer and fits in 64 bit type).
Example
Input:
3
H
HTHT
TTHTHTHTHTHHTHTHTHTTTTTTHTHHHHHTT
Output:
2
20
8589934598
Solution http://www.se.cuhk.edu.hk/~seem3570/12-pattern.pdf
http://deepblue.lib.umich.edu/bitstream/2027.42/24435/1/0000708.pdf
Thursday, August 11, 2011
6 Bullet & a Pesron Puzzle
You have been taken hostage by terrorists. Terrorist has a revolver with 6 empty chambers. He now loads the revolver with 2 bullets in front of you. These two bullets are kept next to each other (contiguously) in the 2 adjacent chambers, the terrorist now spins the barrel so that now you don't know what is location of bullets in chamber. He keep the revolver against your head and pulls the trigger. But its lucky day for you. It was the empty chamber. Now terrorist gives a slight chance to get free. He gives you a choice whether he should spin the barrel first then pull the trigger again.. or should just simply pull the trigger again ? If you get lucky again, terrorists will let you go..otherwise ..!!!
So what would you prefer ? Would you want him to spin the barrel first then shoot or just shoot without spinning the barrel ?
So what would you prefer ? Would you want him to spin the barrel first then shoot or just shoot without spinning the barrel ?
Minimum number of cuts to the bar of gold that will allow you to pay to worker 1/7th each day ?
A worker is to perform work for you for seven straight days. In return for his work, you will pay him 1/7th of a bar of gold per day. The worker requires a daily payment of 1/7th of the bar of gold. What and where are the fewest number of cuts to the bar of gold that will allow you to pay him 1/7th each day?
Solution
Gold bar need minimum two cuts. It should be divided in powers of two.
e.g. for i=0 to k where 2^k is nearly equals to N length of gold piece. 1 ,2 , 4........assuming 7 parts which is divided into a total of 1,2,4.
first day : 1 ---(1)
second day: take back one and give 2----(2)
third day : give back one----(1,2)
fourth day : take back 2,1 and give 4 ----(4)
fifth day : give back 1------(1,4)
sixth day : give 2 and take back 1-----(4,2)
sevent day : give back one-------(1,2,4)
Solution
Gold bar need minimum two cuts. It should be divided in powers of two.
e.g. for i=0 to k where 2^k is nearly equals to N length of gold piece. 1 ,2 , 4........assuming 7 parts which is divided into a total of 1,2,4.
first day : 1 ---(1)
second day: take back one and give 2----(2)
third day : give back one----(1,2)
fourth day : take back 2,1 and give 4 ----(4)
fifth day : give back 1------(1,4)
sixth day : give 2 and take back 1-----(4,2)
sevent day : give back one-------(1,2,4)
Tuesday, August 9, 2011
What is the probability that you toss next time, heads turns up.
A bag contains 5 coins. Four of them are fair and one has heads on
both sides. You randomly pulled one coin from the bag and tossed it 5
times, heads turned up all five times. What is the probability that
you toss next time, heads turns up. (All this time you don't know you
were tossing a fair coin or not).
The probability of getting n consecutive heads is
P(n heads) = 1/5 * 1 + 4/5 * (1/2)^n,
Thus, the probability of getting a head on the n+1st roll given that
you have gotten heads on all n previous rolls is
P(n+1 heads | n heads) = P(n+1) / P(n)
= ( 1/5 * 1 + 4/5 * (1/2)^(n+1) ) / ( 1/5 * 1 + 4/5 * (1/2)^n ).
Multiplying numerator and denominator by 5* 2^(n-1) and recognizing 4
as 2^2 gives
P(n+1 heads | n heads) = (2^(n-1) + 1) / (2^(n-1) + 2)
put n=5 in above expression probability that you toss next time, heads turns up will be 17/18
both sides. You randomly pulled one coin from the bag and tossed it 5
times, heads turned up all five times. What is the probability that
you toss next time, heads turns up. (All this time you don't know you
were tossing a fair coin or not).
The probability of getting n consecutive heads is
P(n heads) = 1/5 * 1 + 4/5 * (1/2)^n,
Thus, the probability of getting a head on the n+1st roll given that
you have gotten heads on all n previous rolls is
P(n+1 heads | n heads) = P(n+1) / P(n)
= ( 1/5 * 1 + 4/5 * (1/2)^(n+1) ) / ( 1/5 * 1 + 4/5 * (1/2)^n ).
Multiplying numerator and denominator by 5* 2^(n-1) and recognizing 4
as 2^2 gives
P(n+1 heads | n heads) = (2^(n-1) + 1) / (2^(n-1) + 2)
put n=5 in above expression probability that you toss next time, heads turns up will be 17/18
Saturday, August 6, 2011
What is the probability that the outside of this cube is completely black?
Twenty seven identical white cubes are assembled into a single cube,
the outside of which is painted black. The cube is then disassembled
and the smaller cubes are thoroughly shuffled in a bag.
A blindfolded man (who cannot feel the paint) reassembles the pieces
into a cube. What is the probability that the outside of this cube is
completely black?
the outside of which is painted black. The cube is then disassembled
and the smaller cubes are thoroughly shuffled in a bag.
A blindfolded man (who cannot feel the paint) reassembles the pieces
into a cube. What is the probability that the outside of this cube is
completely black?
Thursday, August 4, 2011
Some Interesting Probablity Puzzles
Balls into Bins
1. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls
2. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?
3. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.
Balls out of Bin
1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.
2. A bin contains n balls numbered 1,2,...,n . We pick a bunch of k balls from the bin uniformly randomly. What is the
(i) expected number of the greatest numbered ball in the bunch.
(ii) expected number of the least numbered ball in the bunch.
3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?
4. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out.
1. Given n balls and n bins. We throw each ball uniformly randomly into the bins. What is the expected number of (i) empty bins (ii) bins containing one ball (iii) bins containing k balls
2. Given an unlimited supply of balls and a set of n empty bins. We take a ball from the supply and throw it randomly among the bins so that its chances of landing into any of the n bins is same. We continue throwing the balls until no bin is left empty. What is the expected number of balls thrown before no bin is left empty ?
3. Consider the following experiment that proceeds in a sequence of rounds. For the first round, we have n balls, which are thrown uniformly randomly into n bins. After round i , we discard every ball that fell into a bin itself in round i . The remaining balls are retained for i+1 round, in which they are again thrown independently and uniformly at random into the n bins. We stop when there is no ball left. Prove that with probability 1- o(1) the experiment will finish in loglog n number of rounds.
Balls out of Bin
1. A bin contains a white balls and b black balls. We take out the balls at random from the bin without replacement. What is the probability that first ball is white, second ball is white, kth ball is white.
2. A bin contains n balls numbered 1,2,...,n . We pick a bunch of k balls from the bin uniformly randomly. What is the
(i) expected number of the greatest numbered ball in the bunch.
(ii) expected number of the least numbered ball in the bunch.
3. There are n bins and n players, and each player has an infinite supply of balls. The bins are initially empty. We have a sequence of rounds : in each round, each player throws a ball into an empty bin chosen independently at random from all currently empty bins. Let the random variable Z be the number of rounds before every bin is non-empty. Determine the expected value of Z. What can you say about the distribution of Z?
4. A bin contains m white balls and n black balls. We take out the balls uniformly randomly from the bin without replacing them. What is the expected number of black balls left when all the white balls have been taken out.
Subscribe to:
Posts (Atom)