Mixing
Identifying all the 1s in a sea of 0s
$begingroup$
I have an $N$-length binary string, the total number of 1s in the string is D. Assume N is much larger than D. Also, D is fairly larger than 1. (For example, N=1000, D=40).
Now, my aim is to find all the 1s in this string with a minimal number of tests.
Could someone suggest any classical methods or existing algorithms addressing such problems?
What constitutes a test:
Tests can be observing the output of a binary operation on a set of bits in the string. (Eg: XOR of randomly picked 5 bits, Boolean sum( OR) of 3 bit sets...)
I would also like to know what are the best method if my test only constitutes finding if any of the digits in a chosen set of digits is 1.
combinatorics estimation hypothesis-testing
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
$endgroup$
|
show 7 more comments
$begingroup$
I have an $N$-length binary string, the total number of 1s in the string is D. Assume N is much larger than D. Also, D is fairly larger than 1. (For example, N=1000, D=40).
Now, my aim is to find all the 1s in this string with a minimal number of tests.
Could someone suggest any classical methods or existing algorithms addressing such problems?
What constitutes a test:
Tests can be observing the output of a binary operation on a set of bits in the string. (Eg: XOR of randomly picked 5 bits, Boolean sum( OR) of 3 bit sets...)
I would also like to know what are the best method if my test only constitutes finding if any of the digits in a chosen set of digits is 1.
combinatorics estimation hypothesis-testing
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
$endgroup$
5
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
2
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
1
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
2
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01
|
show 7 more comments
$begingroup$
I have an $N$-length binary string, the total number of 1s in the string is D. Assume N is much larger than D. Also, D is fairly larger than 1. (For example, N=1000, D=40).
Now, my aim is to find all the 1s in this string with a minimal number of tests.
Could someone suggest any classical methods or existing algorithms addressing such problems?
What constitutes a test:
Tests can be observing the output of a binary operation on a set of bits in the string. (Eg: XOR of randomly picked 5 bits, Boolean sum( OR) of 3 bit sets...)
I would also like to know what are the best method if my test only constitutes finding if any of the digits in a chosen set of digits is 1.
combinatorics estimation hypothesis-testing
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
$endgroup$
I have an $N$-length binary string, the total number of 1s in the string is D. Assume N is much larger than D. Also, D is fairly larger than 1. (For example, N=1000, D=40).
Now, my aim is to find all the 1s in this string with a minimal number of tests.
Could someone suggest any classical methods or existing algorithms addressing such problems?
What constitutes a test:
Tests can be observing the output of a binary operation on a set of bits in the string. (Eg: XOR of randomly picked 5 bits, Boolean sum( OR) of 3 bit sets...)
I would also like to know what are the best method if my test only constitutes finding if any of the digits in a chosen set of digits is 1.
combinatorics estimation hypothesis-testing
combinatorics estimation hypothesis-testing
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
edited Jan 16 at 20:41
Jyotish Robin
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
asked Jan 16 at 19:21
Jyotish RobinJyotish Robin
1355
1355
5
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
2
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
1
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
2
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01
|
show 7 more comments
5
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
2
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
1
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
2
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01
5
5
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
2
2
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
1
1
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
2
2
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01
|
show 7 more comments
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076169%2fidentifying-all-the-1s-in-a-sea-of-0s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3076169%2fidentifying-all-the-1s-in-a-sea-of-0s%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
5
$begingroup$
What kinds of "test" are allowed?
$endgroup$
– Hagen von Eitzen
Jan 16 at 19:24
$begingroup$
If the $1$s are uniformly distributed, I doubt you can do any better than checking each bit one by one.
$endgroup$
– Jam
Jan 16 at 19:25
2
$begingroup$
Is checking whether a string contains only zeros one test? That would suggest repeatedly splitting a nonzero string and checking its two parts.
$endgroup$
– timtfj
Jan 16 at 19:35
1
$begingroup$
...or checking the total number $k$ (i.e., sum) of $1$s in a substring another test? If so, then split each substring into $k+1$ substrings and iterate...
$endgroup$
– David G. Stork
Jan 16 at 20:10
2
$begingroup$
If each test can only reveal 1 bit of information, it seems like it is impossible to do better than $D$ tests and, without knowing $D$, would require $N$ tests. If $D=1$, then a binary search seems optimal, which is $O(log N)$. Maybe there is an information-theoretic argument to at least get a similar kind of lower bound for general $D$, though the bound may not be optimal?
$endgroup$
– Aaron
Jan 16 at 21:01