-1
$\begingroup$

For the purposes of this puzzle, a "string" means a sequences of zeros and ones, e.g. 1011.

Consider all the different strings of length eight — a good first step would be to figure out how many of these exist.

If you pick a length-eight string uniformly at random, what's the probability that it contains two (or more) consecutive 1s?

This problem is from an app called probability puzzles.

My approach: I solved using dp. My equations are:

Here dp(i)(0) and dp(i)(1) is the number of ways we can form string of length i having 2 or more consecutive 1's and having the last element as 0 and 1 respectively

  1. dp(i)(0)=dp(i-1)(0)+dp(i-1)(1)
  2. dp(i)(1)=dp(i-1)(0)+dp(i-1)(1)+1

Thus I am getting answer to be 127/256. But unfortunately the answer is not correct. Help please!

Improve this question
$\endgroup$
3
  • $\begingroup$ Looks like you're undercounting those strings which have two 1's at the very end and nowhere else. Your formula suggests there is only one of them which is obviously not true. $\endgroup$
    – loopy walt
    Jul 22, 2022 at 20:09
  • 1
    $\begingroup$ This question is off-topic as it is a math problem, not a puzzle. The solution using recursion involves counting the strings that do not contain consecutive ones, which gives an offset of the Fibonacci sequence. An entry for this specific problem is A008466 $\endgroup$
    – Daniel Mathias
    Jul 22, 2022 at 20:22
  • $\begingroup$ So will I delete the question? $\endgroup$
    – Charlie
    Jul 22, 2022 at 20:55

1 Answer 1

Reset to default
1
$\begingroup$

It is much easier to calculate the number of strings of a certain length that have no adjacent 1s, and this can be done recursively.

Let's assume we are trying to calculate the number of strings of length 6 that have no adjacent 1s, which we can define as f(6). Currently, we have:
XXXXXX
where X can be any digit. If we assume the first digit is a 0, we end up with the following:
0XXXXX
Since the only constraint is on adjacent 1s, the number of valid configurations of this string is exactly the same as the number of configurations of:
XXXXX
which can be calculated as f(5). On the other hand, if we choose the first digit as a 1, we get:
1XXXXX
However, since we can't have two adjacent 1s, we also know that the second digit is a 0, and we get:
10XXXX
The number of possibilities here is the same as:
XXXX
or f(4). Therefore, f(6) = f(5) + f(4). This can be generalized, since, in a string of length n, making the first digit a 0 shortens the string to n-1, and making it a 1 shortens it to n-2. The generalized formula is therefore f(n) = f(n-1) + f(n-2). This happens to be the formula for the Fibonacci sequence!

We also need our base case, and we can easily find that there are 2 possibilities for a string of length 1 (0 and 1). We can also see that there are 3 possibilities for a string of length 2 (00, 01, 10). Thus, our base case is f(1) = 2 and f(2) = 3.

From here, we can either calculate f(8) recursively by building up from f(1) and f(2) until we get to f(8), or just looking at the Fibonacci sequence itself. For our purposes, the sequence goes 2, 3, 5, 8, 13, 21, 34, 55..., so f(8) = 55.

Finally, we can remember what f(8) actually represents. f(n) is the number of strings of length n that have no adjacent 1s, and we are looking for the number of strings of length 8 that have at least one pair of adjacent 1s, so we need to calculate (TotalOutcomes - IncorrectOutcomes) / TotalOutcomes. For a string of length 8, there are 2 ^ 8 = 256 total outcomes, and we know from before that there are f(8) = 55 incorrect outcomes, so our final answer is (256 - 55) / 256 = 201 / 256, or about 0.785.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.