Probability of 5+ consecutive heads in 20 coin tosses

[Kevin Schmit]

# Here is a closed-form approximation that works well enough:

probRunKofN <-function(n,k,p)
{ alpha <- function(n,k,p)
{ rho <- (1 - k * (1 - p) * p^k) / (1 - (k + 1) * (1 - p) * p^k)
(1 / rho^(n+1)) * (1 / (1 - (k + 1) * (1 - p) * p^k * rho^k))
}
1 - alpha(n,k,p) + p^k * alpha(n-k,k,p)
}

# Test it:
n <- 20
k <- 5
p <- 1/2
probRunKofN(n,k,p)
>> 0.2486627

There is also a two-line recursive function that gives an exact answer. I'll post it later or over the weekend if I have time. Also an exact closed-form n-state Markov representation but I haven't seen that one coded up algebraically.

 

[kandlekid]

For 5, I get 0.03125. (i.e. 0.5^5 = 0.03125).
For 6, 0.015625,
etc.

 

[silveredge]

Here's some python code that does this by counting in binary from 0 up to 2^20-1 and converting the resulting number into a coin flip sequence.

I also wrote this code which does the same thing but generates flips randomly. This could be useful if you're looking at very large sequences, are happy with an approximation, and don't want to blow up your computer.

GAT

I been self-learning Java and wonder if I wanna write various static Counting methods, say countConsecutive, countRepeated etc, then put all these static methods in a Count class, so I call by Count.staticMethodName(parameters). I wonder how are all those static methods organised inside the Math class? Those methods are independent and unrelated, if it goes like

public class Math{

public static method1{......}
public static method2{......}
.......................................
}

the class must be extremely long and difficult-to-read. How should I organize a Count class similar to Math?

 

[blueraincap]

Here's a script that works iteratively on increasingly long sequences. It looks like a closed form solution is possible, but my algebraic combinatorics is too rusty.

Thanks is an understatement.

 

[blueraincap]

I also wrote this code which does the same thing but generates flips randomly. This could be useful if you're looking at very large sequences, are happy with an approximation, and don't want to blow up your computer.

GAT

Went to our github then followed the link to your blog and bought your book on amazon. Look to do something like you in a few years

 

[entropytrading]

if i want to type mathematical formulas here, i need to write it in a latex editor then copy/paste the image to here?

 

[blueraincap]

https://latex2png.com/

 

[blueraincap]

 

[elt894]

Consider the sequences HHHHHXXXXXXXXXXXXXXTHHHHH. They get counted in both your first and last groups.

The Markov approach Kevin mentioned is probably easier to follow than my code.

You have six possible states:
1: No previous run of 5 heads, and the previous flip was T
2: No previous run of 5 heads, and the previous two flips were TH

3: No previous run of 5 heads, and the previous two flips were THH
4: No previous run of 5 heads, and the previous two flips were THHH
5: No previous run of 5 heads, and the previous two flips were THHHH
6: A run of 5 heads has occurred somewhere
​

# In the initial state there are no previous heads
x0 = np.array([1., 0, 0, 0, 0, 0])

# The transition matrix corresponding to one coin flip
T = np.array([
  [.5, .5, .5, .5, .5, 0.],
  [.5, 0., 0., 0., 0., 0.],
  [0., .5, 0., 0., 0., 0.],
  [0., 0., .5, 0., 0., 0.],
  [0., 0., 0., .5, 0., 0.],
  [0., 0., 0., 0., .5, 1.],
])

# After 20 flips the final state is xf = (T**20)x0
xf = np.matmul(np.linalg.matrix_power(T, 20), x0)
print(xf[-1])
# prints 0.24987030029296875

It's basically equivalent to what I posted earlier. Both update the state of the system with successive coin flips. The Markov approach only looks at the previous timepoint and uses intermediate states to keep track of how many partial runs there are, whereas my original code doesn't need the intermediate states but instead needs to store the history of the system so it can look back 4 steps in time.

 

[blueraincap]

I don't get the right answer, can you help.

We play a game, in which I pick an integer [1, 100] and you guess it in G guesses.
For each wrong guess, I tell you whether your pick is too low or high; you rationally play by guessing the middle in each round, until you win or run out of round.

What is the probability of guessing right when G = 4 guesses?

Below is my logic, which I am not sure if correct:

P(right in 1st guess) = 1/100; P(right in 2nd guess | wrong in 1st) = 1/50; P(right in 3rd | wrong in 1st & 2nd) = 1/25...
P(wrong in 1st) = 99/100, P(wrong in 1st&2nd) = (99/100)(49/50), P(wrong in 1&2&3) = (99/100)(49/50)(24/25)...

P(right within 4 guesses) = P(right 1st) + P(right 2nd|wrong 1st)P(wrong 1st) + P(right 3d|wrong 1st&2nd)P(wrong 1st&2nd) + P(right 4th|wrong...)P(wrong 1st&2nd&3rd) = (1/100) + (1/50)(99/100) + (1/25)(99/100*49/50) + (1/12)(99/100*49/50*24/25) = 0.14622.

I try to test the logic using following java. When G = 4, this java shows 0.15, but as G increases, the result starts to diverge dramatically. When G = 5, my calculation gives 0.289 but java is 0.31, G=6, the divergence widens to 0.1.

public class SimTry{
 
  static int totalWin = 0;
 
  public static void main(String[] args){
    int totalRun = 1000000; //# of simulation runs
    int currentRun = 0; //counter
   
    while(currentRun<totalRun){
      currentRun++;
      playGame();
    }
    System.out.println("win ratio is " + ((double)totalWin/totalRun)*100+"%");
  }
 
  private static void playGame(){
    int answer, guess, guessCount;
    int lowerRange, upperRange;
    int guessPermitted = 6; //max # of guesses allowed per game
    answer = (int)(Math.random()*100) +1;
    guessCount = 0;
    lowerRange = 1;
    upperRange = 100;
    while (guessCount < guessPermitted){
      guess = (upperRange - lowerRange)/2 + lowerRange;
     
      if (guess == answer){
        totalWin++;
        break;
      }
      else if (guess < answer){
        lowerRange = guess;
        guessCount++;
      }
      else {
        upperRange = guess;
        guessCount++;
      }
    }
  }
}