Help with one interview question --expected length of numbers drawnBrain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?Expected numbers of distinct colors when drawing without replacementProbability of randomly drawing all numbers from a setSampling with a random sample sizeSampling with Replacement QuestionProbability of picking some balls before other ballsSampling without Replacement and Non-uniform DistributionGiven a set of binary samples out of a given population, how to calculate the probability that the true ratio of one value is greater than ZThe expected number of unique elements drawn with replacementBrain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?Probability of the sum of cards?
How to judge a Ph.D. applicant that arrives "out of thin air"
How did Mysterio have these drones?
Symplectisation as a functor between appropriate categories
How to kill my goat in Goat Simulator
Struggling with cyclical dependancies in unit tests
Why/when is AC-DC-AC conversion superior to direct AC-AC conversion?
Could the rotation of a black hole cause other planets to rotate?
Is there an antonym for "spicy" or "hot" regarding food (NOT "seasoned" but "spicy")?
Where to find an interactive PDF or HTML version of the tex.web documentation?
Why isn't there any 9.5 digit multimeter or higher?
If my pay period is split between 2 calendar years, which tax year do I file them in?
Why can't my huge trees be chopped down?
How many oliphaunts died in all of the Lord of the Rings battles?
If Trump gets impeached, how long would Pence be president?
Are the named pipe created by `mknod` and the FIFO created by `mkfifo` equivalent?
Is it legal to use cash pulled from a credit card to pay the monthly payment on that credit card?
Japanese reading of an integer
How should we understand λαμβάνω in John 5:34?
Sci-fi change: Too much or Not enough
How can I write an interdental lateral in phonetic transcription?
Is there a wealth gap in Boston where the median net worth of white households is $247,500 while the median net worth for black families was $8?
What are the different qualities of the intervals?
Why is the number of local variables used in a Java bytecode method not the most economical?
How do I explain an exponentially complex intuitively?
Help with one interview question --expected length of numbers drawn
Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?Expected numbers of distinct colors when drawing without replacementProbability of randomly drawing all numbers from a setSampling with a random sample sizeSampling with Replacement QuestionProbability of picking some balls before other ballsSampling without Replacement and Non-uniform DistributionGiven a set of binary samples out of a given population, how to calculate the probability that the true ratio of one value is greater than ZThe expected number of unique elements drawn with replacementBrain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?Probability of the sum of cards?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
Random draw number from 1 to N without replacement and x(n) is the nth numbers you draw. continue drawing number if x(n)>x(n-1) and stop if x(n)
probability
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
Random draw number from 1 to N without replacement and x(n) is the nth numbers you draw. continue drawing number if x(n)>x(n-1) and stop if x(n)
probability
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
1
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago
add a comment |
$begingroup$
Random draw number from 1 to N without replacement and x(n) is the nth numbers you draw. continue drawing number if x(n)>x(n-1) and stop if x(n)
probability
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Random draw number from 1 to N without replacement and x(n) is the nth numbers you draw. continue drawing number if x(n)>x(n-1) and stop if x(n)
probability
probability
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
asked 9 hours ago
VickyfishVickyfish
61 bronze badge
61 bronze badge
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Vickyfish is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
1
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago
add a comment |
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
1
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
1
1
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.
Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=sum_k=0^N-1 P(X>k)$$
Here, $P(X>k)=frac1k!$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $frac1k!$ probability no matter what $N$ is. Expanding the sum yields:
$$E[X]=1+1+frac12!+frac13!+cdots+frac1(N-1)!$$
Notice that this converges to $e$ as $Nrightarrowinfty$
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
$endgroup$
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "65"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Vickyfish is a new contributor. Be nice, and check out our Code of Conduct.
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%2fstats.stackexchange.com%2fquestions%2f419545%2fhelp-with-one-interview-question-expected-length-of-numbers-drawn%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$
I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.
Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=sum_k=0^N-1 P(X>k)$$
Here, $P(X>k)=frac1k!$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $frac1k!$ probability no matter what $N$ is. Expanding the sum yields:
$$E[X]=1+1+frac12!+frac13!+cdots+frac1(N-1)!$$
Notice that this converges to $e$ as $Nrightarrowinfty$
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
$endgroup$
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
add a comment |
$begingroup$
I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.
Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=sum_k=0^N-1 P(X>k)$$
Here, $P(X>k)=frac1k!$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $frac1k!$ probability no matter what $N$ is. Expanding the sum yields:
$$E[X]=1+1+frac12!+frac13!+cdots+frac1(N-1)!$$
Notice that this converges to $e$ as $Nrightarrowinfty$
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
$endgroup$
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
add a comment |
$begingroup$
I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.
Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=sum_k=0^N-1 P(X>k)$$
Here, $P(X>k)=frac1k!$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $frac1k!$ probability no matter what $N$ is. Expanding the sum yields:
$$E[X]=1+1+frac12!+frac13!+cdots+frac1(N-1)!$$
Notice that this converges to $e$ as $Nrightarrowinfty$
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
$endgroup$
I'm assuming that we're uniformly drawing numbers (without replacement), and stop when we explicitly see that the currently drawn number is smaller than the previously drawn number. That means, if we draw $N$ first, we still draw another number and see if it is smaller than $N$, which is going to happen for sure. With this setup, it's certain that we'll draw numbers at least $2$ times. This way, the problem has a beautiful answer, however the OP should still clarify the question to help other readers who can benefit.
Let $X$ be the number of draws in this experiment. Since $X$ is nonnegative and integer we can express the expected value as $$E[X]=sum_k=0^N-1 P(X>k)$$
Here, $P(X>k)=frac1k!$ because for number of draws to be bigger than $k$, the first $k$ draws must be sorted, which happens with $frac1k!$ probability no matter what $N$ is. Expanding the sum yields:
$$E[X]=1+1+frac12!+frac13!+cdots+frac1(N-1)!$$
Notice that this converges to $e$ as $Nrightarrowinfty$
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
edited 1 hour ago
Michael Hardy
4,73415 silver badges30 bronze badges
4,73415 silver badges30 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
answered 7 hours ago
gunesgunes
12.2k1 gold badge5 silver badges22 bronze badges
12.2k1 gold badge5 silver badges22 bronze badges
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
add a comment |
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
The question says to keep drawing if the current number is larger (while you say to stop in that case) -- you may want to correct your statement in the first sentence.
$endgroup$
– Glen_b♦
5 hours ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
$begingroup$
Thanks @Glen_b ,I had flipped the question before solving since it has the same answer, bur forgot to rephrase it back.
$endgroup$
– gunes
1 hour ago
add a comment |
Vickyfish is a new contributor. Be nice, and check out our Code of Conduct.
Vickyfish is a new contributor. Be nice, and check out our Code of Conduct.
Vickyfish is a new contributor. Be nice, and check out our Code of Conduct.
Vickyfish is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cross Validated!
- 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%2fstats.stackexchange.com%2fquestions%2f419545%2fhelp-with-one-interview-question-expected-length-of-numbers-drawn%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
$begingroup$
from what distribution?
$endgroup$
– user158565
9 hours ago
1
$begingroup$
The distribution is the uniform(1,N). However, the question is not fully stated. Do you mean "... and stop if $x(n) < x(n-1)$?
$endgroup$
– Semoi
9 hours ago
$begingroup$
Possible duplicate of Brain-teaser: What is the expected length of an iid sequence that is monotonically increasing when drawn from a uniform [0,1] distribution?
$endgroup$
– Ben
2 hours ago