Interview Question
Country: United States
Interview Type: Phone Interview
But aren't they all dependent events?
Say I get an event that from n = 1 to n = k is one streak, then the chance of getting a streak from 2 to k+1 increases. Your approach would be valid is the chance of getting streaks to start from subsequent values of n (1,2,3...) would be independent probabilities.
For a run, the chance of it occurring is 2^n, where n is the length of the run. For example for the given run the probability is 0.015625.
The total number of runs found will be roughly N * 0.015625. To test this, I wrote a little program that runs this as a simulation. When running it, the first value I got was 0.0156219, so I'm pretty confident this is the right answer.
package a3;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;
public class RandomCoinFlipper {
static final Random rand = new Random();
public static class CoinFlipper
{
private List<Boolean> seq;
public CoinFlipper()
{
}
public void setSequence(List <Boolean> seq)
{
this.seq = seq;
}
public int simulate(int simNr)
{
int found = 0;
Queue <Boolean> curRun = new LinkedList<Boolean>();
for(int i = 0; i < simNr; i++)
{
boolean curFlip = rand.nextBoolean();
if(curRun.size() >= seq.size())
{
curRun.poll();
}
curRun.add(curFlip);
Queue <Boolean> copy = new LinkedList<>(curRun);
boolean isRun = true;
// System.out.println(seq.size() + ", " + curRun.size());
for(int at = 0; at < seq.size(); at++)
{
// System.out.print(seq.get(at) + ":" + copy.peek() + ", ");
if(seq.get(at) != copy.poll())
{
isRun = false;
break;
}
}
// System.out.println();
if(isRun)
{
System.out.println("Found one");
found++;
}
}
return found;
}
}
public static void main(String[] args)
{
//HTTTHH
List <Boolean> l = new ArrayList <>();
l.add(true);
l.add(false);
l.add(false);
l.add(false);
l.add(true);
l.add(true);
CoinFlipper flip = new CoinFlipper();
flip.setSequence(l);
int simNr = 10000000;
int runsFound = flip.simulate(simNr);
System.out.println(runsFound);
System.out.println((float)runsFound/(float)simNr);
}
}
Total tosses = n
- whatevva' June 21, 2013Given "k" tosses, probability that all "k" tosses have the same type of toss (or be a "Streak")
= probability of all heads in "k" tosses + probability of all tails in "k" tosses
= (1/2)^k + (1/2)^k = 2*(1/2)^k
Given "n" tosses, # of sets of subsequent "k" tosses
= (n-k+1)
expected number of k-streaks
= number of subsequent "k" tosses * probability that one set of "k" tosses is a streak
= (n-k+1)*2*(1/2)^k