Timeline for Algorithm to select a random bit string with constraints
Current License: CC BY-SA 4.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2023 at 15:17 | comment | added | user13062187 | Yes, due to the definition of $M, a$ and $n$, all ones must be isolated. | |
| Jan 2, 2023 at 17:48 | comment | added | user16034 | Do you mean that all ones must be isolated ? | |
| Jan 2, 2023 at 17:45 | comment | added | user13062187 | The condition that a bit string has two consecutive ones is negated in the definition of $K$, so $s$ cannot be in $K$ or a subset of $K$. | |
| Jan 2, 2023 at 17:45 | comment | added | user13062187 | Consider a superset $K$, $M \subset K$. Since $s \in M$, $s \in K$ must also hold. $ M \\ = \{s \in \{0,1\}^n \mid s_1 = s_n = 1 \land \\ \forall i \in \{1, 2, \ldots n-1\}: s_i = 1 \Rightarrow AZ_s(i+1, \min\{i+a, n\}) \land \lnot AZ_s(i+1, \min\{i+b, n\}) \} \\ \subset \{s \in \{0,1\}^n \mid \forall i \in \{1, 2, \ldots n-1\}: s_i = 1 \Rightarrow AZ_s(i+1, i+1)\} \\ = \{s \in \{0,1\}^n \mid \forall i \in \{1, 2, \ldots n-1\}: s_i = 1 \Rightarrow s_{i+1} = 0\} \\ = \{s \in \{0,1\}^n \mid \lnot (\exists i \in\{1, 2, \ldots n-1\}: s_i = 1 \land s_{i+1} = 1)\} \\ = K $ | |
| Jan 2, 2023 at 17:44 | comment | added | user13062187 | @YvesDaoust: If I understand you correctly, the presence of a one which is not isolated means that there are two ones next to each other. Proof by contradiction: Assume $s \in M$ and $s$ has two consecutive ones, i.e. $\exists i \in \{1,2, \ldots, n-1\}: s_i = s_{i+1} = 1$. | |
| Jan 1, 2023 at 11:16 | comment | added | user16034 | That still does not answer my question. | |
| Dec 31, 2022 at 17:49 | vote | accept | user13062187 | ||
| Dec 31, 2022 at 17:11 | history | edited | user13062187 | CC BY-SA 4.0 |
M definition clarification according to D.W's comment
|
| Dec 31, 2022 at 17:08 | comment | added | user13062187 | @Stef: There is no special reason for $a < b$. $a=b$ would be a trivial case where $M$ is either empty or has one element, so I've omitted this case. Furthermore, $M$ can be empty for certain values of $a$, $b$ and $n$ (e.g. $a=2, b=3, n=6$), in which case no algorithm exists to solve my problem; I didn't mention this for brevity. | |
| Dec 31, 2022 at 17:07 | comment | added | user13062187 | @D.W.: The condition on the number of zeros refers to every pair of successive ones. My formal definition of $M$ with first order logic is directly below that sentence. | |
| Dec 31, 2022 at 17:07 | comment | added | user13062187 | @YvesDaoust: In the example, all ones are isolated because for all positions $i$ where the bit string has a one ($s_i = 1$), the following bits must be zero at least up to the position $i+a$ ($AZ_s(i+1, min\{i+a,n\})$). $a$ is always at least one and I've added the minimum because $s_y$ is undefined for $y>n$. | |
| Dec 31, 2022 at 17:07 | comment | added | user13062187 | I've defined the set $M$ with first order logic. In this definition the $AZ_s(x,y)$ predicate is true if and only if in $s$ the bits starting with the $x$-th bit and ending with the $y$-th bit are all zero, for example $AZ_{100001}(2,4)$ is true because the second, third and fourth bit are zero. | |
| Dec 31, 2022 at 12:07 | comment | added | Stef | Is there a reason why you imposed $a < b$ and not just $a \leq b$? | |
| Dec 30, 2022 at 19:49 | comment | added | user16034 | In your examples, all ones are isolated, but I don't see that in the definition. | |
| Dec 30, 2022 at 18:09 | answer | added | Nathaniel | timeline score: 2 | |
| S Dec 30, 2022 at 17:20 | review | First questions | |||
| Dec 30, 2022 at 18:23 | |||||
| S Dec 30, 2022 at 17:20 | history | asked | user13062187 | CC BY-SA 4.0 |