円周上の複数の点を通る角度の期待値

質問

バリバリ文系の大学生です。こないだ中華料理店に行って中華テーブルを見た時にふとこの問題を思いついたのですが解法が全く思いつきません。
完全文系なので問題の出し方とかもかなり適当で申し訳ないのですがどなたかご教示いただければ幸いです、よろしくお願いいたします。

円周上にn個の点が与えられた際、それらの点すべてがある特定の位置を通る場合の最短の回転角度の求め方とn個の点の位置がランダムに与えられた場合の回転角度の期待値を求める方法を求めよ。

ものすごくわかりづらい表現で申し訳ないのですがイメージとしては円周上にある点が中華テーブルに置かれたお皿である位置に座っている人が回転テーブルを回してすべてのお皿から食べ物を取ろうとしているイメージです。

回答No.6

nag0720 · ベストアンサー

＞min(2π-Xi+ΣXa-1)
＞※a=1～a　もしくは　a=i+1～n+2まで

正確には、
min(2π-Xi+ΣXa)
※i=1～n+1
※a=1～i-1　もしくは　a=i+1～n+1
ですね。

＞回転角度は
＞2×A1＋A2　or　2×(2π-A2)+A1
＞とすることができます。

これも正しくは、
2×A1＋2π-A2　or　2×(2π-A2)+A1
です。
なので、
・左に一回回ってから右に逆回転する場合
A1＋A2　＞　2π
・右に一回回ってから左に逆回転する場合
A1＋A2　＜　2π
・どちらに回っても同じ場合
A1＋A2　＝　2π

要は、近いほうに回ってから逆回転するということです。

順序統計量については興味深いですが、そう簡単にはいかないのではないでしょう。

最初にn個を一様分布で配置し、それを順序統計量を使うことによってi番目の点の分布を求めることはできます。
しかし、整列するとそれぞれの点の位置は独立ではなくなるので、区間の幅の分布や、区間の幅と点の位置との差の分布を求めることはできないような気がします。
さらに、それぞれの点の確率分布関数は別々の関数になるので一層複雑になります。

統計学はまるっきりの素人なので、単なる感想ですが。

n=3の場合の期待値を計算しようしましたが、場合分けが思ったより複雑で挫折しています。

お礼

ご回答ありがとうございます！

たしかによく見たら色々間違えがっ！！（汗）訂正いただきありがとうございます！！

>最初にn個を一様分布で配置し、それを順序統計量を使うことによってi番目の点の分布を求めることはできます。
>しかし、整列するとそれぞれの点の位置は独立ではなくなるので、区間の幅の分布や、区間の幅と点の位置との差の分布を求めることはできないような気がします。
>さらに、それぞれの点の確率分布関数は別々の関数になるので一層複雑になります。

やはり、そう簡単にはいかないものですよね・・・地道に場合分けを行いたいと思います！！

ちなみに

http://mcm-www.jwu.ac.jp/~konno/pdf/statha18.pdf

のP64の例4.4に

X1,X2…Xnを（0,1）上の一様分布からの標本の大きさがnのランダム標本すなわち

Fx(x)＝x, 0<x<1
0,x≦0
　　　 1,x≧1
fx(x)=1 0<x<1
0 その他
とした時、i番目のX(i)の期待値E(X(i))は
i/(n+1)となる

という項目があったのですがこれを今回の円周上の点X1,X2,...に置き換えると

Fx(x)＝x, 0<x<2π
0,x≦0
　　　 1,x≧2π
fx(x)=1 0<x<2π
0 その他
となり

円周上のn個の点のうちのi番目の点は2πi / (n+1)となるのでしょうか？

重ね重ね申し訳ありません、積分が全くできないので検証ができなくて・・・

回答No.7

nag0720

＞円周上のn個の点のうちのi番目の点は2πi / (n+1)となるのでしょうか？

そうなりますが、分布関数、確率密度関数が違っています。

Fx(x)＝x/2π　,　0<x<2π
　　　　　0　,　x≦0
　　　　　1　,　x≧2π
fx(x)＝1/2π　,　0<x<2π
　　　　　0　,　その他

順序統計量の確率密度関数は、
fxi(x)=n!/(i-1)!(n-i)!*(1/2π)(x/2π)^(i-1)(1-x/2π)^(n-i)

期待値は、
E=∫x*n!/(i-1)!(n-i)!*(1/2π)(x/2π)^(i-1)(1-x/2π)^(n-i)dx　　（積分範囲は0～2π）

t=x/2πで置換積分すると、

=∫2πt*n!/(i-1)!(n-i)!*(1/2π)t^(i-1)(1-t)^(n-i)2πdt　　（積分範囲は0～1）
=2πn!/(i-1)!(n-i)!∫t^i(1-t)^(n-i)dt
=2πn!/(i-1)!(n-i)!*i!(n-i)!/(n+1)!
=2πi/(n+1)

お礼

ご連絡が遅くなってしまい申しわけございません。

ここまで来てあきらめるのも非常に残念なのですが、色々考えてこの問題の一般解は算出できないと結論を出しました。

回答は閉め切りますがもしどなたか回答がわかった方は投稿していただければと思います。

またnag0720さんにお手伝いいただけなければここまでくることはできませんでした、本当にありがとうございます。

久しぶりに数学に打ち込むことができ、とても楽しかったです！またいつかわからない数学の問題があったときは是非よろしくお願いいたします！！

回答No.5

nag0720

やはり場合分けがかなり厄介です。

＃４のn=2の場合分けを変えて、１方向のみの回転の場合と逆回転する場合に分けると、

(1)１方向のみの回転の場合
　2π×4{∫[0～1/2]∫[0～s]sdtds + ∫[1/2～3/4]{∫[s-1/2～1-s]sdtds}
(2)逆回転する場合
　2π×4{∫[0～1/4]∫[0～s](s+2t)dtds + ∫[1/4～1/2]{∫[0～1/2-s](s+2t)dtds}

これだと少しは楽になるので、n=3,4にも適用できそうです。

いずれにしろ、この方法では一般化は無理ですね。

あとは、近似値になりますが乱数を使ってシミュレーションするしかないでしょう。

お礼

お礼が遅くなってしまい申し訳ございません。。

ご回答ありがとうございます！

なるほど右回りと左回りの場合分けを減らす事ができたわけですね！！たしかにnの数が増えた場合の場合分けが楽になりそうです！！
しかし積分は高校以来一切やってないので相当なリハビリが必要になりそうです（笑）

また新しいアプローチを考えてみました。

前回の回答で円の回転角度を

min(2π-Xi+ΣXa-1)　
※a=1～a　もしくは　a=i+1～n+2まで

としたのですがこの時のXiの2つの点を原点からの角度をA1、A2と置くと（左回りから数えてA1、A2）

回転角度は
2×A1＋A2　or　2×(2π-A2)+A1
とすることができます。

この時
・左に一回回ってから右に逆回転する場合
2×A1＋A2　＜　2×(２π-A2)+A1
↓
A1＋3A2　＞　4π

・右に一回回ってから左に逆回転する場合
2×A1＋A2　＞　2×(２π-A2)+A1
↓
A1＋3A2　＜　4π

・どちらに回っても同じ場合
2×A1＋A2　=　2×(２π-A2)+A1
↓
A1＋3A2　＝　4π

となるので

min(2π-Xi+ΣXa-1)
A1＋3A2　＞=　4π の時：a=1～a (=のときはどちらにも含めて良いので仮に左回りとしておく)
A1＋3A2　<　4π の時：a=1～a

とできるのではないかと考えました。

そしてインターネットを調べていると順序統計量なるものを発見しました。（下記のURLはpdfです）

http://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E7%B5%B1%E8%A8%88%E9%87%8F

円周上に置かれた点をD={d0,d1,d2・・・dn+1}　
※d0,dn+1は原点でそれぞれ0と2π

とするとXiはdi+1 - di、A1はdi、A2はdi+1と表すことができるので

min(2π-(di+1-di)+ΣXa-1)
di＋di+1　＞=　4π の時：a=1～i (=のときはどちらにも含めて良いので仮に左回りとしておく)
di＋di+1　<　4π の時：a=i+1～n+1

とすることができます。もしこれを関数の式F(x)で表すことができれば下記URLの最小値の法則に従い

Fx(1) = 1 -｛1-F(x)^n

として期待値を求められるのではないかと考えました！

順序統計量に関してはかなり曖昧な理解なのでもしかしたらトンチンカンなことを言っている部分があるかもしれません。。。

参考URL　順序統計量（Wikipedia）：http://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E7%B5%B1%E8%A8%88%E9%87%8F

回答No.4

nag0720

＞・常に原点から最小の距離にある点に回転させる
＞という方法を使うと最短回転角度になっているような気がしました！

これは違いますね。
＃３の例で言うと、O→D→O→A→B→Cの回転が最短ですが、ここに弧CD以外の箇所に新たな点を追加しても、そこはすでに通過しているので最短角度は変わりません。

つまり、原点の近くに点をどのように追加しても最短角度には影響しないので「常に原点から最小の距離にある点に回転させ」たとしても最短角度にはならないこともあります。

円周を360、X0=0、Xn+1=360として、n個の点を、
X0≦X1≦X2≦X3≦・・・・≦Xn-1≦Xn≦Xn+1
と配置したとします。

弧XiXi+1を通らない回転方法は、
(1) Xiに回転してから、Xi+1に逆回転する。
(2) Xi+1に回転してから、Xiに逆回転する。
の２通りあります。
その回転距離は、
(1) Xi×2＋(360－Xi+1)
(2) (360－Xi+1)×2＋Xi
原点を含めると弧の数はn+1個あるから、
回転の方法は全部で2n+2通りあり、その中での最短のものが求める回転距離になります。

しかし、この方法では期待値を簡単に計算することはできません。

実際に回転角度の期待値を求めてみましょうか。

n=1のときは、
期待値はπ/2であることは簡単に分かります。
2π×2∫[0～1/2]tdt=2π×2×1/8=π/2
という計算式で求めることもできます。

n=2のときは、
(1) ２点とも右半分、または、左半分にあるとき
(2) ２点とも下半分にあるとき
(3) ２点とも上半分にあるとき
(4) ２点が、右上と左下、または、右下と左上にあるとき
に分けて計算すると、
(1) 2π×4∫[0～1/2]{∫[0～s]sdt}ds=π/3
(2) 2π×4∫[0～1/4]{∫[0～s](s+2t)dt}ds=π/12
(3) 2π×4∫[1/4～1/2]{∫[1/4～s](1-s)dt}ds=7π/48
(4) 2π×4∫[1/4～1/2]{∫[0～1/2-s](s+2t)dt+∫[1/2-s～1/4](1-s)dt}ds=π/8+7π/48=13π/48
なので、期待値は合計して5π/6

n=3、4くらいまでなら丁寧に場合分けすればなんとか手計算できるかもしれませんが、
それ以上はパソコンでも使わないと計算できないでしょう。
パソコンを使ってもせいぜいn=10くらいまでで、それ以上は発想を変えないと計算は無理かと思います。

お礼

ご回答ありがとうございます！

たしかにnag0720さんのおっしゃる通り点をどこに配置しても最短の回転角度が変わらないということは最短の方向に動くことと最短距離とは関連がなさそうですね！！

またn=1とn=2の場合の期待値の算出ありがとうございます！！

なるほど、これは場合分けがかなり厄介ですね。。nag0720さんにしていただいた計算をn=10でやることを考えるとぞっとしてしまいます（汗）

やはり最短の回転角度を求める式を場合分けが必要ない形にしなければならないのでしょうか？

回答No.3

nag0720

＃２です。

よくよく考えてみたら、＃２の方法も間違っていました。

円周の長さを360、特定の位置を原点O(=0)として、４個の点を次のように配置します。
A=45、B=120、C=240、D=330

＃１さんの方法だと、最大弧長はBC間の120なのでO→A→B→A→O→C→Dと回転して回転距離は、360
O→A→B→C→Dと回転すると回転距離は、330
O→D→C→B→Aと回転すると回転距離は、315

でも、O→D→O→A→B→Cと回転すると回転距離は、30+30+240=300でこれが最短でしょう。

残念ながら「これが最短だ」という方法はすぐには浮かびません。
何か別の方向から考察する必要がありそうです。

お礼

お礼が遅くなってしまい申し訳ございません。

ご回答ありがとうございます！たしかにnag0720さんが示された場合の例では最長の弧を通らなかったとしても最小値になりませんね！！先日確かめたときは完全に見落としておりました・・・

あとこの数日間色々と考えてみたのですが

円を原点も含めてn+1個の点で分割してn+1個の弧としたとき、分割された弧の長さをX=（X1,X2・・・Xn+1）とすると

360°＞最小の回転角度

360°=ΣXi　※i=1～n+1

ということは

「X1,X2・・・Xn+1の中でどこか必ず一つ通らない弧がある」

と考えられると思いました。

そしてその通らない弧をXiとすると原点からの短いほうの距離Dは

D = ΣXa-1　
※a=1～a　もしくは　a=i+1～n+2まで

となるので

最小の回転角度は2πから弧の長さを引いて逆回転する長さを足した値

360-Xi+ΣXa-1

※a=1～a　もしくは　a=i+1～n+2まで

が最小となるXiを見つければよいということになるのかと思いました！

またいくつかの例で試してみたときに

・常に原点から最小の距離にある点に回転させる

という方法を使うと最短回転角度になっているような気がしました！

回答No.2

nag0720

＃１さんの方法は、たしかに全ての点が特定の点を通過しますが、それが最小距離になるとは限りません。
最長の弧の位置によっては、回転角度が３６０度を超える場合があります。

右または左へ一方の方向にだけ回転して全ての点を通過させれば、最小の回転角度は最大でも３６０度より小さくなるはずですから、
最小の回転角度は、＃１さんの方法と右回転、左回転それぞれ回転角度を較べる必要があります。

分布については、実数上の分布であれば「他の点と重ならない」はほとんど影響ないので、単に「円周上での一様分布」としたほうがいいでしょう。

お礼

ご回答ありがとうございます！

nag0720のお話をいただいてalice_44さんの方法を式にしてみました！

最大の弧Aの長さ：L
原点から短いほうの点までの長さ：D

としたとき円の回転の仕方は

1.弧A上を通る場合：
D+L

2.弧A上を通らない場合（短いほうの点から逆回転する場合）:
D+2π-L

となり2.の場合にD>Lとなると2πを超えてしまうということですね！！

また分布に関しても教えていただきありがとうございます！

回答No.1

alice_44

n 個の点で円周を分割した n 個の弧のうち、
その「特定の点」を含まない中で最長の弧の両端
を A,B とする。A,B のうち近いほうの点を
最初に「特定の点」まで移動し、次に
もう一方の点を「特定の点」まで移動すれば、
最小の回転で、n 個全ての点が
「特定の点」を通過する。

期待値の話にするためには、n 個の点の分布を
具体的に仮定しなければ、計算にならないが。

お礼

ありがとうございます！まさかこんなに早く回答いただけるとは思っておらずびっくりです！！

昨日の夜いくつかの例で試してみて、たしかにalice_44さんのおっしゃる方法が最小の回転距離になりそうなのですがなぜそうなるのかが全くわかりませんでした（泣）

重ね重ね申し訳ないのですがもしよろしければなぜそうなるのか理由も教えていただいてもよろしいでしょうか。

また点の分布に関しましては

他の点と重ならないすべての位置に対して等しい確率で配置される

という仮定でお願いいたします↑（わかりづらい表現で申し訳ありません、、）