Optimal algorithm to guess any random integer without limits? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Are there more rational numbers than integers?Are all infinities equal?The concept of infinityRegarding playing an infinite number of games that could last infinitely long amounts of timeIncorrect proof of the infinities between 0 and 1 and 0 and 2Uncountable vs Countable Infinity$.99999…=1$: What is the proof that we can multiply an infinite series by something to shift it?Stochastics in infinityWhat does infinity in complex analysis even mean?How compelling is this argument for multiple degrees of infinity?
How do I find out the mythology and history of my Fortress?
Is CEO the "profession" with the most psychopaths?
How do living politicians protect their readily obtainable signatures from misuse?
What order were files/directories outputted in dir?
How to unroll a parameter pack from right to left
What do you call the main part of a joke?
How to plot logistic regression decision boundary?
Project Euler #1 in C++
Maximum summed subsequences with non-adjacent items
Would it be possible to dictate a bech32 address as a list of English words?
What was the first language to use conditional keywords?
A term for a woman complaining about things/begging in a cute/childish way
One-one communication
How to add group product into the cart individually?
Co-worker has annoying ringtone
Should there be a hyphen in the construction "IT affin"?
Do wooden building fires get hotter than 600°C?
How many time has Arya actually used Needle?
Lagrange four-squares theorem --- deterministic complexity
Why do early math courses focus on the cross sections of a cone and not on other 3D objects?
Is it possible for SQL statements to execute concurrently within a single session in SQL Server?
How much damage would a cupful of neutron star matter do to the Earth?
What to do with repeated rejections for phd position
Why weren't discrete x86 CPUs ever used in game hardware?
Optimal algorithm to guess any random integer without limits?
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Are there more rational numbers than integers?Are all infinities equal?The concept of infinityRegarding playing an infinite number of games that could last infinitely long amounts of timeIncorrect proof of the infinities between 0 and 1 and 0 and 2Uncountable vs Countable Infinity$.99999…=1$: What is the proof that we can multiply an infinite series by something to shift it?Stochastics in infinityWhat does infinity in complex analysis even mean?How compelling is this argument for multiple degrees of infinity?
$begingroup$
Guessing Game In Range $[1, n]$
The classical guessing game goes something like this...
Our friend thinks of an integer between $1$ and $100$ (let's say they pick $42$).
We try to guess that number with the fewest guesses possible:
$$
100, 3, 7, 30, ...
$$But every time we guess, they say whether the actual number is higher or lower than what we guessed...
$$
100(lower), 3(higher), 7(lower), 30(lower), ...
$$
There is actually an optimal solution to this problem. By knowing whether their number is higher or lower than our previous guess, we can always choose our next guess in exactly the middle of the remaining range...
$$
beginarray
hline
text# & textOptions Range & textNumber of Options & textGuess & text42 Is Higher Or Lower \ hline
1. & 1...100 & 100 & 50 & textLower \ hline
2. & 1...49 & 49 & 25 & textHigher \ hline
3. & 26...49 & 24 & 37 & textHigher \ hline
4. & 38...49 & 12 & 43 & textLower \ hline
5. & 38...42 & 5 & 40 & textHigher \ hline
6. & 41...42 & 2 & 41 & textHigher \ hline
7. & 42...42 & 1 & 42 & textWin \ hline
endarray
$$
By using this method we are reducing the number of remaining options by roughly a half with each guess. It took us only $7$ guesses to guess a random number from $1$ to $100$.
Infinite Guessing Game $[1, infty)$
What if we ask our friend to pick an integer $k$ between $1$ and infinity?
Is there an algorithm which can be proven to be the most efficient in terms of the average number of guesses for finding the answer?
Can it be proven that there can not exist such an algorithm?
My guess is that we need to solve this problem in two separate steps:
Find an upper-bound $n$ that is higher than $k$.
Solve the original problem in the range $[1,n]$.
If we had all the time in the universe, and because the number $k$ is a finite number, we will guess it eventually.
We can even define some possible ways of finding $n$:
- Counting from 1 upwards. $1, 2, 3, 4, ...$ (Takes exactly $k$ guesses to reach the answer.)
- Guessing a random number in the sub-range of possibilities. (How to define selecting a random number between $1$ and infinity?)
- Squaring our guess until we find an upper bound. $10, 100, 10^4, 10^8, 10^16, ...$
Cubing our guess until we find an upper bound? $10, 1000, 10^9, 10^27, ...$ (What if we raise to an even higher power?)- Exponentially increasing our guess until we find an upper bound. $10, 2^10, 2^2^10, ...$
We could keep defining different techniques like these forever.
The questions are:
- Are all these techniques equally valid?
- If not, how can they be ordered in terms of efficiency?
- If the number $k$ can be anywhere between $1$ and $k$, does this automatically mean that the average number of guesses for any technique tends to infinity?
- The problem is not only finding the upper-bound as quickly as possible, but also finding it in a way that after we have found it we can find the number itself as quickly as possible.
Double-Infinite Guessing Game $(-infty, infty)$
You know the question to this...
infinity
asked Mar 27 at 20:54
andderoanddero
1012
$endgroup$
add a comment |
$begingroup$
Guessing Game In Range $[1, n]$
The classical guessing game goes something like this...
Our friend thinks of an integer between $1$ and $100$ (let's say they pick $42$).
We try to guess that number with the fewest guesses possible:
$$
100, 3, 7, 30, ...
$$But every time we guess, they say whether the actual number is higher or lower than what we guessed...
$$
100(lower), 3(higher), 7(lower), 30(lower), ...
$$
There is actually an optimal solution to this problem. By knowing whether their number is higher or lower than our previous guess, we can always choose our next guess in exactly the middle of the remaining range...
$$
beginarray
hline
text# & textOptions Range & textNumber of Options & textGuess & text42 Is Higher Or Lower \ hline
1. & 1...100 & 100 & 50 & textLower \ hline
2. & 1...49 & 49 & 25 & textHigher \ hline
3. & 26...49 & 24 & 37 & textHigher \ hline
4. & 38...49 & 12 & 43 & textLower \ hline
5. & 38...42 & 5 & 40 & textHigher \ hline
6. & 41...42 & 2 & 41 & textHigher \ hline
7. & 42...42 & 1 & 42 & textWin \ hline
endarray
$$
By using this method we are reducing the number of remaining options by roughly a half with each guess. It took us only $7$ guesses to guess a random number from $1$ to $100$.
Infinite Guessing Game $[1, infty)$
What if we ask our friend to pick an integer $k$ between $1$ and infinity?
Is there an algorithm which can be proven to be the most efficient in terms of the average number of guesses for finding the answer?
Can it be proven that there can not exist such an algorithm?
My guess is that we need to solve this problem in two separate steps:
Find an upper-bound $n$ that is higher than $k$.
Solve the original problem in the range $[1,n]$.
If we had all the time in the universe, and because the number $k$ is a finite number, we will guess it eventually.
We can even define some possible ways of finding $n$:
- Counting from 1 upwards. $1, 2, 3, 4, ...$ (Takes exactly $k$ guesses to reach the answer.)
- Guessing a random number in the sub-range of possibilities. (How to define selecting a random number between $1$ and infinity?)
- Squaring our guess until we find an upper bound. $10, 100, 10^4, 10^8, 10^16, ...$
Cubing our guess until we find an upper bound? $10, 1000, 10^9, 10^27, ...$ (What if we raise to an even higher power?)- Exponentially increasing our guess until we find an upper bound. $10, 2^10, 2^2^10, ...$
We could keep defining different techniques like these forever.
The questions are:
- Are all these techniques equally valid?
- If not, how can they be ordered in terms of efficiency?
- If the number $k$ can be anywhere between $1$ and $k$, does this automatically mean that the average number of guesses for any technique tends to infinity?
- The problem is not only finding the upper-bound as quickly as possible, but also finding it in a way that after we have found it we can find the number itself as quickly as possible.
Double-Infinite Guessing Game $(-infty, infty)$
You know the question to this...
infinity
asked Mar 27 at 20:54
andderoanddero
1012
$endgroup$
2
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
1
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
4
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13
add a comment |
$begingroup$
Guessing Game In Range $[1, n]$
The classical guessing game goes something like this...
Our friend thinks of an integer between $1$ and $100$ (let's say they pick $42$).
We try to guess that number with the fewest guesses possible:
$$
100, 3, 7, 30, ...
$$But every time we guess, they say whether the actual number is higher or lower than what we guessed...
$$
100(lower), 3(higher), 7(lower), 30(lower), ...
$$
There is actually an optimal solution to this problem. By knowing whether their number is higher or lower than our previous guess, we can always choose our next guess in exactly the middle of the remaining range...
$$
beginarray
hline
text# & textOptions Range & textNumber of Options & textGuess & text42 Is Higher Or Lower \ hline
1. & 1...100 & 100 & 50 & textLower \ hline
2. & 1...49 & 49 & 25 & textHigher \ hline
3. & 26...49 & 24 & 37 & textHigher \ hline
4. & 38...49 & 12 & 43 & textLower \ hline
5. & 38...42 & 5 & 40 & textHigher \ hline
6. & 41...42 & 2 & 41 & textHigher \ hline
7. & 42...42 & 1 & 42 & textWin \ hline
endarray
$$
By using this method we are reducing the number of remaining options by roughly a half with each guess. It took us only $7$ guesses to guess a random number from $1$ to $100$.
Infinite Guessing Game $[1, infty)$
What if we ask our friend to pick an integer $k$ between $1$ and infinity?
Is there an algorithm which can be proven to be the most efficient in terms of the average number of guesses for finding the answer?
Can it be proven that there can not exist such an algorithm?
My guess is that we need to solve this problem in two separate steps:
Find an upper-bound $n$ that is higher than $k$.
Solve the original problem in the range $[1,n]$.
If we had all the time in the universe, and because the number $k$ is a finite number, we will guess it eventually.
We can even define some possible ways of finding $n$:
- Counting from 1 upwards. $1, 2, 3, 4, ...$ (Takes exactly $k$ guesses to reach the answer.)
- Guessing a random number in the sub-range of possibilities. (How to define selecting a random number between $1$ and infinity?)
- Squaring our guess until we find an upper bound. $10, 100, 10^4, 10^8, 10^16, ...$
Cubing our guess until we find an upper bound? $10, 1000, 10^9, 10^27, ...$ (What if we raise to an even higher power?)- Exponentially increasing our guess until we find an upper bound. $10, 2^10, 2^2^10, ...$
We could keep defining different techniques like these forever.
The questions are:
- Are all these techniques equally valid?
- If not, how can they be ordered in terms of efficiency?
- If the number $k$ can be anywhere between $1$ and $k$, does this automatically mean that the average number of guesses for any technique tends to infinity?
- The problem is not only finding the upper-bound as quickly as possible, but also finding it in a way that after we have found it we can find the number itself as quickly as possible.
Double-Infinite Guessing Game $(-infty, infty)$
You know the question to this...
infinity
asked Mar 27 at 20:54
andderoanddero
1012
$endgroup$
Guessing Game In Range $[1, n]$
The classical guessing game goes something like this...
Our friend thinks of an integer between $1$ and $100$ (let's say they pick $42$).
We try to guess that number with the fewest guesses possible:
$$
100, 3, 7, 30, ...
$$But every time we guess, they say whether the actual number is higher or lower than what we guessed...
$$
100(lower), 3(higher), 7(lower), 30(lower), ...
$$
There is actually an optimal solution to this problem. By knowing whether their number is higher or lower than our previous guess, we can always choose our next guess in exactly the middle of the remaining range...
$$
beginarray
hline
text# & textOptions Range & textNumber of Options & textGuess & text42 Is Higher Or Lower \ hline
1. & 1...100 & 100 & 50 & textLower \ hline
2. & 1...49 & 49 & 25 & textHigher \ hline
3. & 26...49 & 24 & 37 & textHigher \ hline
4. & 38...49 & 12 & 43 & textLower \ hline
5. & 38...42 & 5 & 40 & textHigher \ hline
6. & 41...42 & 2 & 41 & textHigher \ hline
7. & 42...42 & 1 & 42 & textWin \ hline
endarray
$$
By using this method we are reducing the number of remaining options by roughly a half with each guess. It took us only $7$ guesses to guess a random number from $1$ to $100$.
Infinite Guessing Game $[1, infty)$
What if we ask our friend to pick an integer $k$ between $1$ and infinity?
Is there an algorithm which can be proven to be the most efficient in terms of the average number of guesses for finding the answer?
Can it be proven that there can not exist such an algorithm?
My guess is that we need to solve this problem in two separate steps:
Find an upper-bound $n$ that is higher than $k$.
Solve the original problem in the range $[1,n]$.
If we had all the time in the universe, and because the number $k$ is a finite number, we will guess it eventually.
We can even define some possible ways of finding $n$:
- Counting from 1 upwards. $1, 2, 3, 4, ...$ (Takes exactly $k$ guesses to reach the answer.)
- Guessing a random number in the sub-range of possibilities. (How to define selecting a random number between $1$ and infinity?)
- Squaring our guess until we find an upper bound. $10, 100, 10^4, 10^8, 10^16, ...$
Cubing our guess until we find an upper bound? $10, 1000, 10^9, 10^27, ...$ (What if we raise to an even higher power?)- Exponentially increasing our guess until we find an upper bound. $10, 2^10, 2^2^10, ...$
We could keep defining different techniques like these forever.
The questions are:
- Are all these techniques equally valid?
- If not, how can they be ordered in terms of efficiency?
- If the number $k$ can be anywhere between $1$ and $k$, does this automatically mean that the average number of guesses for any technique tends to infinity?
- The problem is not only finding the upper-bound as quickly as possible, but also finding it in a way that after we have found it we can find the number itself as quickly as possible.
Double-Infinite Guessing Game $(-infty, infty)$
You know the question to this...
infinity
infinity
asked Mar 27 at 20:54
andderoanddero
1012
asked Mar 27 at 20:54
andderoanddero
1012
asked Mar 27 at 20:54
andderoanddero
1012
asked Mar 27 at 20:54
andderoanddero
1012
asked Mar 27 at 20:54
andderoanddero
1012
1012
2
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
1
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
4
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13
add a comment |
2
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
1
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
4
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13
2
2
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
1
1
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
4
4
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $nge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.
This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.
By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
$endgroup$
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
add a comment |
Your Answer
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%2f3165121%2foptimal-algorithm-to-guess-any-random-integer-without-limits%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $nge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.
This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.
By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
$endgroup$
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
add a comment |
$begingroup$
A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $nge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.
This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.
By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
$endgroup$
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
add a comment |
$begingroup$
A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $nge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.
This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.
By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
$endgroup$
A practical approach to this is to start with $n=1$ (or $n=$ any positive integer you like), and double your guess until you reach an $nge k$. Then you can conduct your binary search on the remaining possibilities $n/2 < k < n$.
This can't be proven to be the most efficient method, because to do that you would need to know the probability of each $k$, which presumably you don't. But it is an approach I have used in more than one computer programming problem.
By the way, your Doubly Infinite Guessing Game can be reduced to the Singly Infinite version, simply by guessing $n=0$ at your first turn.
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
answered Mar 27 at 21:13
TonyKTonyK
44.1k358137
44.1k358137
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
add a comment |
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
This is actually a good strategy even without distribution on the input: you can prove a related lower bound on the number of guesses in the worst-case setting (as a function of $k$ itself). Namely, you will have $O(log k)$ number of guesses, and you need $Omega(log k)$ anyways (even if I give you an upper bound on $k$, say a value $n$ such that $n/100 leq k leq 100n$.)
$endgroup$
– Clement C.
Mar 27 at 21:30
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
$begingroup$
So how would the answer for the double-infinity question change if I said the probability had a Gaussian distribution?
$endgroup$
– anddero
Apr 2 at 23:05
add a comment |
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%2f3165121%2foptimal-algorithm-to-guess-any-random-integer-without-limits%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
2
$begingroup$
What is the distribution of the picked numbers?
$endgroup$
– Michael Biro
Mar 27 at 20:57
1
$begingroup$
You indeed cannot talk about "average number of guesses" without specifying a distribution on the choice of $k$. "Uniform" is not going to cut it here....
$endgroup$
– Clement C.
Mar 27 at 20:59
4
$begingroup$
As pointed out in the above comments, you need to specify the distribution of the input to make your question precise. However, your list of possible algorithms omits the one that comes first to my mind for the $[1, infty)$ case: namely, double your initial guess until you've got an upper bound. This will give an algorithm that has logarithmic complexity relative to the input $k$. I think your suggestions will all be much worse than this.
$endgroup$
– Rob Arthan
Mar 27 at 21:13