0
$\begingroup$

Problem

Given integers $n,m,k,v$ count the number of possible bit strings $s$ of length $n$ such that at least $m$ of the contiguous substrings of $s$ of length $k$ have value greater than $v$ when represented in decimal form.

Understanding

$S = \{s^0, s^1, ..., s^{2^n - 1} \}$, is the set of binary strings of length $n$. $|S| = 2^n$

Let $d(s)$ be the decimal value of a binary string.

A string, $s^x$, can be considered as a sequence of characters (1 or 0): $s^x_1, s^x_2, ..., s^x_n$

$s^x_{i,j}$ is a substring of $s^x$ from $i$ to $j$ and is the sequence of characters $s^x_i, s^x_{i+1}, ..., s^x_j$.

Let $k$ be the length of the substring.

Substrings of $s^x$ are: $\Omega^x =\{s^x_{1,k}, s^x_{2,k+1},..., s^x_{n-k+1,n}\}$. Each string has $n-k+1$ substrings.

The decimal values of the substrings of $s^x$ are $V^x = \{d(s^x_{1,k}), d(s^x_{2,k+1}),..., d(s^x_{n-k+1,n})\}$

$V^x_{\geq v} = \{V^x | \geq v\}$

If $|v^x_{\geq v}| > m$ then $s^x$ is valid.

For n, m, k, v, how many strings are valid?

Example

$n = 3, m = 1, k = 2, v = 2$

$S = \{000, 001, 010, 011, 100, 101, 110, 111\}$

$\begin{align}s^0 = 000, & \Omega^0 = \{00, 00\}, & V^0 = \{0, 0\}, & V^0_{\geq v} = \emptyset, & |V^0_{\geq v}| = 0 \\ s^1 = 001, & \Omega^1 = \{00, 01\}, & V^1 = \{0, 1\}, & V^1_{\geq v} = \emptyset, & |V^1_{\geq v}| = 0 \\ s^2 = 010, & \Omega^2 = \{01, 10\}, & V^2 = \{1, 2\}, & V^2_{\geq v} = \{2\}, & |V^2_{\geq v}| = 1 \\ s^3 = 011, & \Omega^3 = \{01, 11\}, & V^3 = \{1, 3\}, & V^3_{\geq v} = \{3\}, & |V^3_{\geq v}| = 1 \\ s^4 = 100, & \Omega^4 = \{10, 00\}, & V^4 = \{2, 0\}, & V^4_{\geq v} = \{2\}, & |V^4_{\geq v}| = 1 \\ s^5 = 101, & \Omega^5 = \{10, 01\}, & V^5 = \{2, 1\}, & V^5_{\geq v} = \{2\}, & |V^5_{\geq v}| = 1 \\ s^6 = 110, & \Omega^6 = \{11, 10\}, & V^6 = \{3, 2\}, & V^6_{\geq v} = \{3,2\}, & |V^6_{\geq v}| = 2 \\ s^7 = 111, & \Omega^7 = \{11, 11\}, & V^7 = \{3, 3\}, & V^7_{\geq v} = \{3,3\}, & |V^7_{\geq v}| = 2\end{align}$

6 strings of length 3 $(n)$ have at least 1 $(m)$ substring of length 2 $(k)$ of value greater than 2 $(v)$.

Solution

Any string in the set of valid strings must have at least $m$ ones in it.

Possible methods to explore:

Transition Matrix Method/Deterministic Finite Automaton

Goulden-Jackson Cluster Method:

How many Binary Strings of length N contain within it the substring '11011'?

Counting strings containing specified appearances of words

It is possible to set up a system of equations and then compute a generating function. To expand this to hundreds of terms takes a long time to compute.

The problem is easy to solve by brute force or by generating function for small values of $n,m,k$, but what if $n = 100$, $m = 50$, $k = 10$, and $0 \leq v \leq 2^k-1$? There are too many possibilities to try, and I cannot see an obvious way to reduce the search space. I am not certain that the problem can actually be solved in a reasonable time for the values above.

$\endgroup$
  • $\begingroup$ The simplest substring that satisfies the criteria of m values > v would be a series of consecutive 1s. By considering all the substrings of minimum length that satisfy m values > v, these substrings must not have a run of more than some number of consecutive 0s, depending on how the value of v relates to k (i.e. how many bits does it take to represent v, and how many surplus bits are provided by k-v). $\endgroup$ – user470451 Aug 10 '17 at 4:27
  • $\begingroup$ What exactly is the question? This seems more like a plan of research than a Q&A. $\endgroup$ – Peter Taylor Aug 10 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.