Minimum number of trials to get >99% chance of getting the median

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

Context:

An algorithm is given (below); input array A is made of n elements, which are all odd, positive integers.

Algorithm:

Median(A[1, ... , *n*])
1. Uniformly at random pick i ∈ 1, ... , *n*.
2. c ← 0
3. foreach j ∈ 1, ... , *n* 
4. if A[j] < A[i] then c ← c+1

Note: the "if" statement (line 4) is supposed to be nested under the "foreach" statement (line 3).

5. if c = (n-1)/2 then return A[i]
6. else goto line 1

Question:

Assume each execution of line 1 is defined to be a "trial". How many trials are needed to have atleast a 99% chance of returning successfully with the median value as shown in line 5? The answer will have a lower bound, and it will be a function of $n$.

Thoughts:

Let $m$ be the number of trials, and $n$ be the possible values we're looking through. I realised that $fracmn = fractrialselements = $ the probability of finding the median. Assuming this is right, I go on to deduce that $fracmn geq 0.99$ because we need a probability of atleast 99%. Given this logic, I end up with $m geq 0.99n$ but when trying to figure out the lower boundary I am getting confused as my approach doesn't seem to lead to a lower boundary.

I'm not sure where I'm going wrong, so any help or hints on helping me understand any mistakes I'm making would be much appreciated!

combinatorics algorithms

share|cite|improve this question

edited Jul 24 at 21:47

asked Jul 24 at 21:20

abhimohit99

103

add a comment | 

up vote
0
down vote

favorite

Context:

An algorithm is given (below); input array A is made of n elements, which are all odd, positive integers.

Algorithm:

Median(A[1, ... , *n*])
1. Uniformly at random pick i ∈ 1, ... , *n*.
2. c ← 0
3. foreach j ∈ 1, ... , *n* 
4. if A[j] < A[i] then c ← c+1

Note: the "if" statement (line 4) is supposed to be nested under the "foreach" statement (line 3).

5. if c = (n-1)/2 then return A[i]
6. else goto line 1

Question:

Assume each execution of line 1 is defined to be a "trial". How many trials are needed to have atleast a 99% chance of returning successfully with the median value as shown in line 5? The answer will have a lower bound, and it will be a function of $n$.

Thoughts:

Let $m$ be the number of trials, and $n$ be the possible values we're looking through. I realised that $fracmn = fractrialselements = $ the probability of finding the median. Assuming this is right, I go on to deduce that $fracmn geq 0.99$ because we need a probability of atleast 99%. Given this logic, I end up with $m geq 0.99n$ but when trying to figure out the lower boundary I am getting confused as my approach doesn't seem to lead to a lower boundary.

I'm not sure where I'm going wrong, so any help or hints on helping me understand any mistakes I'm making would be much appreciated!

combinatorics algorithms

share|cite|improve this question

edited Jul 24 at 21:47

asked Jul 24 at 21:20

abhimohit99

103

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

Context:

An algorithm is given (below); input array A is made of n elements, which are all odd, positive integers.

Algorithm:

Median(A[1, ... , *n*])
1. Uniformly at random pick i ∈ 1, ... , *n*.
2. c ← 0
3. foreach j ∈ 1, ... , *n* 
4. if A[j] < A[i] then c ← c+1

Note: the "if" statement (line 4) is supposed to be nested under the "foreach" statement (line 3).

5. if c = (n-1)/2 then return A[i]
6. else goto line 1

Question:

Assume each execution of line 1 is defined to be a "trial". How many trials are needed to have atleast a 99% chance of returning successfully with the median value as shown in line 5? The answer will have a lower bound, and it will be a function of $n$.

Thoughts:

Let $m$ be the number of trials, and $n$ be the possible values we're looking through. I realised that $fracmn = fractrialselements = $ the probability of finding the median. Assuming this is right, I go on to deduce that $fracmn geq 0.99$ because we need a probability of atleast 99%. Given this logic, I end up with $m geq 0.99n$ but when trying to figure out the lower boundary I am getting confused as my approach doesn't seem to lead to a lower boundary.

I'm not sure where I'm going wrong, so any help or hints on helping me understand any mistakes I'm making would be much appreciated!

combinatorics algorithms

share|cite|improve this question

edited Jul 24 at 21:47

asked Jul 24 at 21:20

abhimohit99

103

Context:

An algorithm is given (below); input array A is made of n elements, which are all odd, positive integers.

Algorithm:

Median(A[1, ... , *n*])
1. Uniformly at random pick i ∈ 1, ... , *n*.
2. c ← 0
3. foreach j ∈ 1, ... , *n* 
4. if A[j] < A[i] then c ← c+1

Note: the "if" statement (line 4) is supposed to be nested under the "foreach" statement (line 3).

5. if c = (n-1)/2 then return A[i]
6. else goto line 1

Question:

Assume each execution of line 1 is defined to be a "trial". How many trials are needed to have atleast a 99% chance of returning successfully with the median value as shown in line 5? The answer will have a lower bound, and it will be a function of $n$.

Thoughts:

Let $m$ be the number of trials, and $n$ be the possible values we're looking through. I realised that $fracmn = fractrialselements = $ the probability of finding the median. Assuming this is right, I go on to deduce that $fracmn geq 0.99$ because we need a probability of atleast 99%. Given this logic, I end up with $m geq 0.99n$ but when trying to figure out the lower boundary I am getting confused as my approach doesn't seem to lead to a lower boundary.

I'm not sure where I'm going wrong, so any help or hints on helping me understand any mistakes I'm making would be much appreciated!

combinatorics algorithms

share|cite|improve this question

edited Jul 24 at 21:47

asked Jul 24 at 21:20

abhimohit99

103

share|cite|improve this question

share|cite|improve this question

edited Jul 24 at 21:47

edited Jul 24 at 21:47

edited Jul 24 at 21:47

asked Jul 24 at 21:20

abhimohit99

103

asked Jul 24 at 21:20

abhimohit99

103

asked Jul 24 at 21:20

abhimohit99

103

103

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
0
down vote



accepted

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is
$$
p = 1-frac 1n .
$$
Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is
$$
p^K = left(1-frac 1nright)^K .
$$
For a rather big $n$ we have
$$
left(1-frac 1nright)^napprox frac 1e=exp(-1) .
$$
To get a value $p^K$ under $0.01=frac 1100$, we need to repeat the experiment roughly some $K=nlog 100 =2nlog 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a large 'n' why does p^K have an exponent of n as opposed to K?
  – abhimohit99
  Jul 24 at 23:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
  – abhimohit99
  Jul 24 at 23:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
  – dan_fulea
  Jul 25 at 10:19
  

  
  
  
  

add a comment | 

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',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861777%2fminimum-number-of-trials-to-get-99-chance-of-getting-the-median%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
0
down vote



accepted

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is
$$
p = 1-frac 1n .
$$
Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is
$$
p^K = left(1-frac 1nright)^K .
$$
For a rather big $n$ we have
$$
left(1-frac 1nright)^napprox frac 1e=exp(-1) .
$$
To get a value $p^K$ under $0.01=frac 1100$, we need to repeat the experiment roughly some $K=nlog 100 =2nlog 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a large 'n' why does p^K have an exponent of n as opposed to K?
  – abhimohit99
  Jul 24 at 23:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
  – abhimohit99
  Jul 24 at 23:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
  – dan_fulea
  Jul 25 at 10:19
  

  
  
  
  

add a comment | 

up vote
0
down vote



accepted

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is
$$
p = 1-frac 1n .
$$
Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is
$$
p^K = left(1-frac 1nright)^K .
$$
For a rather big $n$ we have
$$
left(1-frac 1nright)^napprox frac 1e=exp(-1) .
$$
To get a value $p^K$ under $0.01=frac 1100$, we need to repeat the experiment roughly some $K=nlog 100 =2nlog 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a large 'n' why does p^K have an exponent of n as opposed to K?
  – abhimohit99
  Jul 24 at 23:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
  – abhimohit99
  Jul 24 at 23:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
  – dan_fulea
  Jul 25 at 10:19
  

  
  
  
  

add a comment | 

up vote
0
down vote



accepted

up vote
0
down vote



accepted

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is
$$
p = 1-frac 1n .
$$
Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is
$$
p^K = left(1-frac 1nright)^K .
$$
For a rather big $n$ we have
$$
left(1-frac 1nright)^napprox frac 1e=exp(-1) .
$$
To get a value $p^K$ under $0.01=frac 1100$, we need to repeat the experiment roughly some $K=nlog 100 =2nlog 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is
$$
p = 1-frac 1n .
$$
Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is
$$
p^K = left(1-frac 1nright)^K .
$$
For a rather big $n$ we have
$$
left(1-frac 1nright)^napprox frac 1e=exp(-1) .
$$
To get a value $p^K$ under $0.01=frac 1100$, we need to repeat the experiment roughly some $K=nlog 100 =2nlog 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

share|cite|improve this answer

share|cite|improve this answer

answered Jul 24 at 23:08

dan_fulea

4,1421211

answered Jul 24 at 23:08

dan_fulea

4,1421211

answered Jul 24 at 23:08

dan_fulea

4,1421211

4,1421211

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a large 'n' why does p^K have an exponent of n as opposed to K?
  – abhimohit99
  Jul 24 at 23:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
  – abhimohit99
  Jul 24 at 23:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
  – dan_fulea
  Jul 25 at 10:19
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  For a large 'n' why does p^K have an exponent of n as opposed to K?
  – abhimohit99
  Jul 24 at 23:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
  – abhimohit99
  Jul 24 at 23:39
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
  – dan_fulea
  Jul 25 at 10:19
  

  
  
  
  

For a large 'n' why does p^K have an exponent of n as opposed to K?
– abhimohit99
Jul 24 at 23:29

For a large 'n' why does p^K have an exponent of n as opposed to K?
– abhimohit99
Jul 24 at 23:29

Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
– abhimohit99
Jul 24 at 23:39

Or is it that we're saying we will need n trials when we have a big n? If so, why is that?
– abhimohit99
Jul 24 at 23:39

K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
– dan_fulea
Jul 25 at 10:19

K was a variable, an unknown used in between to have a light notation. We are searching for a "good K" depending on n. It turns out that a good value for K that approximatively works for bigger values of n is like $K=(4.605dots)n$. To have a clear situation, please declare an explicit value of $n$. Then we can also use Monte-Carlo to get numbers and the statistic. (I would use sage to ilustrate the situation experimentally.)
– dan_fulea
Jul 25 at 10:19

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2861777%2fminimum-number-of-trials-to-get-99-chance-of-getting-the-median%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Name Email

Name Email

Name

Email

Name Email

Name

Email