n個取った最大値は,何番目に大きいか

Last-modified: 2009-09-13 (日) 22:00:46

(わかりにくい表題で申し訳ないです)
N個のデータから,無作為にn個を取り出し,さらにその中で最大のものを選ぶ時,N個中でK番目のデータが選ばれる確率はいくつかという問題です.
どういう場合のことを想定しているかというと,大量にあるデータから,なるだけ大きい値のデータを選びたい.でも,データが多すぎて,全部の大きさを比べることができないといった場合,全体から一部をサンプリングして,その中で最大値を選ぶという方法で代用することにしたとしましょう.
では,その時選ばれた最大値は,本当のところ全体で何番目に大きいデータであるかということを確率的に知っておきたいということです.
以下に,確率の式と,理論値,実測値(実験した値)を示します.

*******************************************************************
pnk.sas
2009.09.13 翔
n個取った最大値は,何番目に大きいか
*******************************************************************;
/*
大きさの異なるNN個のデータから,無作為にn個を取り出し,
さらにその中で最大のものを選ぶ.
NN個中でK番目のデータが選ばれる確率をPn(K)とすると,

          n(NN-K)(NN-1-K)・・・(NN-n+2-K)
Pn(K) = -----------------------------------
         NN(NN-1) (NN-2) ・・・ (NN-(n-1))
となります.

P2(K)=Prob(最初の1個目がK)Prob(次がKより小さい)+Prob(最初がKより小さい)Prob(次がK)
P3(K)=Prob(最初がK)Prob(次がKより小さい)Prob(その次もKより小さい)
     +Prob(最初がKより小さい)Prob(次がK)Prob(その次がKより小さい)
     +Prob(最初がKより小さい)Prob(次もKより小さい)Prob(その次がK)
*/


options nocenter compress=yes;

%let NN=10;
%let n=5;

******************
理論値
******************;

data;
drop i;
do k=1 to &NN;
  pnk=&n/&NN;
  do i=1 to &n-1;
    pnk=pnk*(&NN-i+1-k)/(&NN-i);
  end;
  output;
end;
run;
proc print;run;

/*
OBS     k      pnk

  1     1    0.50000
  2     2    0.27778
  3     3    0.13889
  4     4    0.05952
  5     5    0.01984
  6     6    0.00397
  7     7    0.00000
  8     8    0.00000
  9     9    0.00000
 10    10    0.00000
*/

******************
実測値
******************;

data trial;
do trial=1 to 10000; /*10000回試行する*/
do k=1 to &NN;  /*k=1が,1番大きいデータとする*/
  r=ranuni(1);  /*NN個に無作為な乱数を割り付ける*/
  output;
end;end;
run;

proc sort;by trial r;run;

data trial;set trial;by trial;
  if first.trial then seq=0;
  seq+1;
  if seq<=&n then output; /*無作為にn個選ぶ*/
run;

proc summary data=trial nway;
  class trial;
  var k;
  output out=min min()=mink; /*n個中最大のもの,すなわちkが最小のものをminkとする*/
run;

data trial;merge trial min(keep=trial mink);by trial;
if k=mink then output; /*kが最大(minkに一致)のものを選ぶ*/
run;

proc freq;tables k;run;

/*
                                 累積         累積
k      度数      パーセント      度数      パーセント
-----------------------------------------------------
1        5004       50.04          5004       50.04
2        2748       27.48          7752       77.52
3        1412       14.12          9164       91.64
4         606        6.06          9770       97.70
5         190        1.90          9960       99.60
6          40        0.40         10000      100.00
*/