Replied: Wed, 14 Jul 1999 08:29:34 -0400 Replied: Xiaohong Judy Qiu Received: from npac.syr.edu (foxhome5.npac.syr.edu [128.230.163.25]) by postoffice.npac.syr.edu (8.9.3/8.9.3) with ESMTP id XAA06698 for ; Tue, 13 Jul 1999 23:40:20 -0400 (EDT) Message-ID: <378C0AC2.E3F284AE@npac.syr.edu> Date: Tue, 13 Jul 1999 23:57:54 -0400 From: Xiaohong Judy Qiu X-Mailer: Mozilla 4.5 [en] (WinNT; I) X-Accept-Language: en MIME-Version: 1.0 To: Geoffrey Fox Subject: Re: The quesiton... References: <199907140300.XAA09388@boss.npac.syr.edu> Content-Type: multipart/alternative; boundary="------------CD307B288442F6B2D566508A" Content-Length: 3514 --------------CD307B288442F6B2D566508A Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Thanks. I'm glad I also got the same formula because from: C1 i-1 C 1 n-i ________________ C3 n = (i-1)(n-i)*3*2 ____________ n(n-1)(n-2) I just felt it was unbelievable that when take i for some small value, say 2, the probability = 6/n(n-1), which is much smaller than simple method 1/n! Judy Geoffrey Fox wrote: > So consider probability that integer k is median of 3 > random numbers chosen from integers 1...n > Assume that on chooses 3 distinct numbers > i.e. remove numbers when they are chosen > > Then of three numbers first has probability 1/n, second 1/(n-1), third 1/(n-2) > So any triple (k1,k2,k3) has probability 1/((n-2)(n-1)n) > > We need that one of these numbers is k and one of of others is > k and other < k > We get a factor of 3 as ny one of the threek1 k2 k3 can be k > > Chance of next number being < k is (k-1) (always dividing by 1/((n-2)(n-1)n)) > Chance of final number being > k is (n-k) > > We get a factor of 2 as either of two remaining numbers can be > So answer is 6(k-1)(n-k)/((n-2)(n-1)n) > > This vanishes if k=1 and k=n as it must > sum(k=1 to n) of this probability is 1 > > For large n, probability for k= (n+1)/2 is > 1.5/n compared to 1/n for simple case > > (I use k where questions uses i > Hope this is not confusing!) > > Reply by Geoffrey Fox gcf@npac.syr.edu, http://www.npac.syr.edu, > Phone 3154432163(3154431723 npac central) Fax:3154434741 --------------CD307B288442F6B2D566508A Content-Type: text/html; charset=us-ascii Content-Transfer-Encoding: 7bit Thanks.

I'm glad I also got the same formula because from:

 C1 i-1 C 1 n-i
________________

C3 n
 
 

= (i-1)(n-i)*3*2
 ____________
  n(n-1)(n-2)

I just felt it was unbelievable that when take i for some small value, say 2,
the probability = 6/n(n-1), which is much smaller than simple method 1/n!

Judy
 

Geoffrey Fox wrote:

So consider probability that integer k is median of 3
random numbers chosen from integers 1...n
Assume that on chooses 3 distinct numbers
i.e. remove numbers when they are chosen

Then of three numbers first has probability 1/n, second 1/(n-1), third 1/(n-2)
So any triple (k1,k2,k3) has probability 1/((n-2)(n-1)n)

We need that one of these numbers is k and one of of others is > k and other < k
We get a factor of 3 as ny one of the threek1 k2 k3 can be k

Chance of next number being < k is (k-1) (always dividing by 1/((n-2)(n-1)n))
Chance of final number being > k is (n-k)

We get a factor of 2 as either of two remaining numbers can be <k

So answer is 6(k-1)(n-k)/((n-2)(n-1)n)

This vanishes if k=1 and k=n as it must
sum(k=1 to n) of this probability is 1

For large n, probability for k= (n+1)/2 is
1.5/n compared to 1/n for simple case

(I use k where questions uses i
Hope this is not confusing!)

 Reply by Geoffrey Fox gcf@npac.syr.edu, http://www.npac.syr.edu,
          Phone 3154432163(3154431723 npac central) Fax:3154434741

--------------CD307B288442F6B2D566508A--