# 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.
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?
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
if i want to type mathematical formulas here, i need to write it in a latex editor then copy/paste the image to here?
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 Code: # 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.
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. Code: 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++; } } } }