Return to Question

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.

For example, the terminating sequence could be '11', and what is the probability that the number is a multiple of 3. Answer is 10/17.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

The simpler matrix solution is O(n^2) for n states = (sequence length * modulo). Ideally we would expect an O(n) solution for these problems like Penney's.

O(n^2) code: https://github.com/anitasv/coins/blob/master/src/main/java/me/asv/coins/Coins.java

Generate a binary number, using coin toss. Until you receive a predefined terminating sequence. What is the probability that the number is a multiple of some $k$.

For example, the terminating sequence could be $`11`$, and what is the probability that the number is a multiple of $3$. Answer is $\dfrac{10}{17}$.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

The simpler matrix solution is $O(n^2)$ for $n$ states = (sequence length * modulo). Ideally we would expect an $O(n)$ solution for these problems like Penney's.

$O(n^2)$ code: https://github.com/anitasv/coins/blob/master/src/main/java/me/asv/coins/Coins.java

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.

For example, the terminating sequence could be '11', and what is the probability that the number is a multiple of 3. Answer is 10/17.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

The simpler matrix solution is O(n^3) for n states = (sequence length * modulo). Ideally we would expect an O(n) solution for these problems like Penney's.

O(n^3) code: https://github.com/anitasv/coins/blob/master/src/main/java/me/asv/coins/Coins.java

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.

For example, the terminating sequence could be '11', and what is the probability that the number is a multiple of 3. Answer is 10/17.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

The simpler matrix solution is O(n^2) for n states = (sequence length * modulo). Ideally we would expect an O(n) solution for these problems like Penney's.

O(n^2) code: https://github.com/anitasv/coins/blob/master/src/main/java/me/asv/coins/Coins.java

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.

For example, the terminating sequence could be '11', and what is the probability that the number is a multiple of 3.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

Generate a binary number, using coin toss. Until you receive a predefined sequence. What is the probability that the number is a multiple of some k.

For example, the terminating sequence could be '11', and what is the probability that the number is a multiple of 3. Answer is 10/17.

I understand questions like this can be answered by generating the whole transition matrix, and then solve like a markov chain. Is there a simpler rule which can give the probability for these type of questions?

Like the Conway's Algorithm in Penney's game;

http://plus.maths.org/content/os/issue55/features/nishiyama/index

The simpler matrix solution is O(n^3) for n states = (sequence length * modulo). Ideally we would expect an O(n) solution for these problems like Penney's.

O(n^3) code: https://github.com/anitasv/coins/blob/master/src/main/java/me/asv/coins/Coins.java