c:~I.~.~~とのコラムは .OR にかかわる概念，知識(手法，原理).それらの図解，よい教材や問題，実学

OR の実施経験，そ己から得られた知恵やアドパイス，失敗談と教訓，新しい視点，視座，フレー

ムワーク，未だ解けていない問題，面白い研究テーマなどを J ‘新鮮に'らしかも“コンパクト IC"
表現し，提示していただくものです.ユニークなアイディア，フレッシュな見方，発想，だれかとメモランダム

意見をたたかわせたい問題提起など，ふるってど投稿ください. (原稿は，刷り上がり，半ペーヅ

から 3 ベーク lζ納まるようにお書きください.簡単 IC/

加筆訂正をお願いする場合があります〉

円の中の 2 点聞の距離の期待値について伊藤忠雄
数の採用される割合が急激に悪くなるので工夫が要る.

，1.はじめに(n= ラのときが/60=0.16)

米国の古い OR の雑誌のニュースレター[ 1]に次の一般に，互いに独立な一様乱数 O 豆 U， V;:;玉 l を用いると.

ようなクイズが出ている.
「半径 1 の円の中にランダムにとった 2 つの点の聞の距(2π V) はそれぞれ独立に，平均 =0 ，分散 =1 の正規乱離の期待値を求めよ」
解答欄には，

X= 、/一二五五U ・ cos(2 1r U) , Y= 、/一二五五V ・ sin

数になり，このような n 組の正規乱数 (X k ， Yd を用い

ると ，正解 =8/3π=0.8488 …とだけ書いてあ

Xk=X k / ゾ X 1 2+ … +X n 2 ， Yk=Yk / ゾ-Y~平るが，後述のとおり，この“正解"は正しくない.そこ+Yn2(k=I ， 2 ，"'， n) は半径 i の n 次元の球面上で一様でまず数値実験(モンテカルロ法)による解を求め，次分布する.したがって，に一般化して数 O 壬 r. s 豆 1 ìこより ， xk'== 旬 ψ 子・ Xk， Yk'= η 、1-; ・ Yk

n 次元の球の場合，また，個別化して正5] 11 に求めた互いに独立な一様乱問角形の場合の正しい解について調べてみた.モンテカ(k=I ， 2 ， … ， n) とすれば ，ノレロ法の演習問題として紹介する.の n 次元の球面上のランダムな 2 つの点になる [22.

様乱数 IXkl.

J.

このようにしてランダムな 2 点聞の距離 Lπ= 、/辰子工円の場合

X 1 2+X 2 2 豆 1.

Xk' , Yk l はそれぞれ半径 r ， SYl')2+ ・田・ +(xn'-Yn')2 を求めて N組の平均値 Ln を計

Y12+Y2 2;;三 l を満たす互いに独立な一算する.

IYkl 豆 l(k=I.2) を N組作り. 2 点 (X J，X2). (Y1. 九)の聞の距離 L2= 、ぺ X 1

11=2.3 , "'， 10 の場合の結果は表 1 のとおりである.

-Yd 2干 (X 三24. 正 m 角形の場合Y2 )2 を求めて N組の平均値んを計算する.

半径 i の円に内接する正 m 角形 (m 孟 3) 内のランダ

3. n 次元の球の場合

ムな 2 つの点 P(X ，Y) , Q(X'. Y')の聞の距離 L=、! (X-X')2 十 (Y_Y')2 を求める.

半径 1 の n 次元の球の方程式 X12+X22+...Xn =1 の2場合も同様にして X 1 2 十… +X n 2 豆 1 ，

Y1 2+ … +Yn 2 孟 l

互いに独立な一様乱数 IXI.IYI 孟 l のうち図 1 のよを満たす互いに独立な一様乱数 IXkl ，IYkl 壬 1 (k=I , 2

うに正 m 角形を m 等分した小 3 角形 oPkPト 1 内に属す… ， n) を N組作り

2 点聞の距離表

Ln= J(X--;工百戸干て干 (X n -2Yn)2 を求めればよし、，はずであるがn が大きくなるとともに乱いとう

ただお東レ側情報シス

311 次元の球の場合の期待値 Lη

567

10002000
500081.2613

テム推進部
干 103 中央区日本橋室町 2-2-1
1993 年 1 月号

(N= ∞は厳密解， 11→∞のときは Ln→、/玄=1. 4142…)© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

41表 2る(次玉突を満たす)ものを採用し，これを点 P(X ， Y) とする.

3(Xk-Xk-d(Y-Yλ)一 (X-X k )( Yk‑ Y，ト d
主主 O

正 m 角形の次合の期待値 L

54

1000.
9086

2000
5000.
9045.
9044

ここで k ， s は次式から求める.

ω1s=tan- 1 (Z)-2 kS, S= π/m

73741.

.7937 仁ム631.
86001 .
876
1

1 側戸厄

(N= ∞は厳密解， m=4 のときは L=2 (1+ v'2)/15+v'
2 ln(1+v'2)/3)

sk_\=(2k ー 1 )s~s+2 kS
豆 (2k+1 )S=Sk叩 =1+ グ/，JZK,,

ただし

卸孟 1-yZ=Y/X (X 手 0)
=1

(X=O , Y;;;;O)=ー(X=O ，同様にして点 Q(X' ，5086lY<O)Y') を求PX¥めて PQ 聞の距離 L を求める.
これを N 聞くりかえして平均値 L、(d!)2=(/石亡耳 -.j w'- (x¥+dr\)勺 2+ (tk¥)'、を計算する .

m=3 ， 4 ， …， 50 の場

dl= 叫 l/wLxi、合の結果は表 2 のとおりである.

、、、、、、\5. 厳密解の計算方法、、

図 2(1) n 次元の球の場合

正 m 角形の場合

ただし

UD'=21dl=2j:J21/ ゾ 1 ー ((Xl- r )/叩 )2n=2 の場合，図 2 のように半径 i の円 O 内の点、 P(r ，0) を中心とする半径即の円 P を作ると2 つの円は /w=2 叩( sin- 1 t+π/2)

2)/(2rw)t=(l‑r2‑w-I/~r のとき交わる.その交点の x\ 座標の値を z とすれば(1)を(刷こ代入して ，z=(I+ ρ 一回 2)/(2r)r,t の順に積分すると

L 2 =8/(3 π) ・ (1+1/15)

L 2 (r)={J:九 (2π w)dw

=0.8488x1.0667+J;ッ(弱')伽 }/π=0.9054(1)

すなわち，正解は前述の“正解"より約 7%大きい.

L2=~:L2(r)(2r)dr(2)n ミ 3 の場合，一般に半径 R の n 次元の球の方程式はk=kX I 2+X 2 2+ … +Xn 2 =Rにその体P〆 dP=(2k- 1) 互

積 Vn ，

表面積 Sη は次式で表わされる.

Sk‑lk=k。

Vη=cηRη ，
ただし ，Q, dQn!
!

n!!=n(n-2) … 4 ・ 2=2< 削1l /2π <n- 1l /2/nn= 奇数 ，k=O。

sη =ncnRη-1c n =(2 π )n/2

n= 偶数 ，

2dP=xsec
td
xdt
lc'td
ydlc
dQ=ys
e
c2c=sms'cosS(ぬ=叫 k 十l) s
Yk=sin(2k+l)ss=π 1m
図n 次元の球の場合© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

!

n!!=n(n-2) … 3 ・ 1

前と同様に球 0 内の点 P を中心とする半径 w の球を作ると九 (Xk' Yk)

42(3)2 つの球の交わり部分は半径v' w 2 ー (xl-r)2 の n ー 1 次元の球となるから，その“切り口"の表
オベレーションズ・リサーチ

cos(tk+t ーが)

商積 QQ' ~土次式で表わされる.
ただし ，QQ'=fSη _Idl

人気 P ， Q がそれぞれの近傍にある確率は，小さな台形=(n ーI) cη →叩ト2

j入(ゾ 1 ー( (XI-r)/w)2)n- 3dx I
n=2 の場合と同様にして期待値 Ln(r) ，μ)Ln を求める. (3) から却を t の関数として表わして (4) に代入すると

A=1 ー (1 ーが )r 2

Ln(r)=~:ユSn d加/九 +j::; 叩弱'd加 /Cπ=c(n ー 1 )n!!/(n+l)!
!

zn=j;n 川 Ln(r)dr
I=j;rMifp( 川)( -rt)n+ ト i( 仔 )i
(J1二五)ト 3dt}drm̲

:
r

k=1

具体的には次のように計算する.

-F(-s , ‑s)}/2
ここで F(u ，v) は次式で計算する.
戸 =sin(Sk) ，n=2k の場合 ，R=(1-t 2 )r 2 と変換して3ln(B+(A I 3 l n IBI ー ZI )/(3ﾟ)+(A2+AI2BIl
n1B2+ZI
A1=XcOS(u+Sk) ー Y cos(v)A2= Xcos(u)‑Ycos(V‑Sk){f~r'ト 2j-l( J互 )2j+l dr}dtin(v)BI=Xsin(u+sk)‑Ys~f2k+1 \=Al2j+1)J;tE刊(1一判B 2 =Xs in(u) ー Ysin(v-Sk)

z= 、! X2+Y2‑2XYcoS(Sk+U‑V)

BIト-tρ
川2刈(ω2k 一 j， J+3/2)dt

次に ，

ただし

Bx(p , q) =J:.
.
.
RP‑I(1-R) ぺR

F(u ,v) を X ，

これらはガウスの趨幾何関数，ガウスの公式を用いて計算できるので最終的に次の結果を得る [3 ].

Lk={G(s , -s)-G(s , s)+G(-s , s)-G( ーにすなわち ，-s)}/2G(u ， v) を計算するプログラムを作ればよい.これは 2 次の無理関数が中心であるから不定積分がLπ =c ・ 2 2n + 2 .n ・ n!!(n!)2/(n+1 )(2n+l)

(n+I)
!
!
(2n)
!
!

容易に求められるので精密に計算できる.ただし m=4など特殊な場合を除くと簡単な式にはなりそうもない.

漸化式にまとめると

参芳文献

Lπ=4( n+1)(n+3)3Ln̲2/n(n+3)(2n+3)(2n+5)

LI=2/3 , L 2 =8/(3 π)( 16/15)[1] Paul. Hughes; “ BRAIN TEASERS" , OR/
M S TODAY, vol.7, No.1 (1980)

1computerprograｭ
[2] D.E. Knuth; Theart0(2) 正 m 角形の場合
図 1 のように小 3 角形に番号 k=0 ， 1 ， 2 ， … ， m ー 1 をつけて点 Q の属する小 3 角形を k=O に固定し，点 P の属する小 3 角形を k=k とすれば，Y で積分する.

G(u ， り )=ffF(u ， り )dXdY(不完全ベータ関数)
n=2k-1 の場合も同様な式になり，

点 P，Q の聞の距離mming‑vol.2/seminumericalalgorithms , Adisonｭ

WesleyPub. Co. (1969)[D.E. クヌース(渋谷訳) ;第 3 分冊一準数値計算法/乱数，サイエンス社(1 981 )J

Lk は，余弦定理を用いて
L k = 、! (Xsect)2+(Ysect')2‑2XY(sect)(sect')

1993 年 1 月号Z))/(3ﾟ)3
戸 =0 のとき ， F(u ， v) ・ COS3( u)=aZ/3‑aAI2ZTこだし，MA(!?:i)品川汽 l ー仰-3/2

ただし ，sk=2trk/rn , s=tr/rn

ß*O のとき ， F(u ， v) ・ COS3(U)= αZ3/3-2 AI
A2Z/3

n=2k , 2k ー l の場合にわけで r ， t の11慎に積分して求める

最終的な期待値 L はこれらを平均して求める.

日 =COS(Sk) ，偶数)

=1/2 n=2k‑1 ( 奇数)
1 は，t, t';[ - i , i] , X , Y;[0 , cos{i)]=(F(s , -S) -F {S, s)+F(-s , S)

ただし，

ここで ，Lk=ffffLkdPdQ

I=HLkdtdt'=c(n ー l)n!!/(n+1)!! ・ I

n=2k

次のような 4 重積分により計算できる.

L = Lk/mf‑I(-rt+ 、/互い+I(ゾ τ二万円 -3dt

c=l/ πの商積 dP， dQ に比例するから ， Lk の期待値 i k は，

ただし，積分区間は次のとおりである.

叩 =-rt+ 、11 ー ( 1-t 2 ) ρ=-rt+ 、互 ，

tk=2trk/m=2ki , i= π/m[3] 森口，宇多川，ー松:数学公式 m ，岩波全書(1 960)

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

43