반지름 R 의 원 안에 균일하게 임의의 점을 생성해야합니다 .
나는 간격 [0 … 2π)에서 균일하게 임의의 각도를 선택하고 간격 (0 … R ) 에서 균일하게 임의의 반경을 선택함으로써 주어진 두 개의 점 때문에 중심을 향한 더 많은 점으로 끝날 것이라는 것을 알고 있습니다. 반지름이 작을수록 반지름이 작은 점이 반지름이 큰 점보다 서로 더 가깝습니다.
여기 에서 블로그 항목을 찾았 지만 그의 추론을 이해하지 못합니다. 나는 그것이 옳다고 생각하지만 , 그가 (2 / R 2 ) x r 을 얻는 곳 과 그가 어떻게 최종 솔루션을 도출하는지 이해하고 싶습니다 .
업데이트 : 이 질문을 게시 한 지 7 년이 지난 지금도 여전히 제곱근 알고리즘의 수학에 관한 실제 질문에 대한 만족스러운 답변을받지 못했습니다. 그래서 답을 직접 쓰는 데 하루를 보냈습니다. 내 답변에 연결합니다 .
답변
아르키메데스처럼 접근 해보자.
삼각형 ABC에서 어떻게 점을 균일하게 생성 할 수 있습니까? | AB | = | BC |? 평행 사변형 ABCD로 확장하여이를 쉽게 만들어 봅시다. ABCD에서 점을 균일하게 생성하는 것은 쉽습니다. AB에서 랜덤 포인트 X와 BC에서 Y를 균일하게 선택하고 XBYZ가 평행 사변형이되도록 Z를 선택합니다. 원래 삼각형에서 균일하게 선택된 점을 얻으려면 ADC에 나타나는 점을 AC를 따라 ABC로 다시 접습니다.
이제 원을 생각해보십시오. 한계에서 우리는 그것을 원점에 B가 있고 원주에 A와 C가 서로 가깝게 가까운 무한히 많은 이등변 삼각형 ABC라고 생각할 수 있습니다. 각도 세타를 선택하면이 삼각형 중 하나를 선택할 수 있습니다. 이제는 은색 ABC에서 점을 선택하여 중심으로부터 거리를 생성해야합니다. 다시 ABCD로 확장합니다. 여기서 D는 이제 원 중심에서 반지름의 두 배입니다.
위의 방법을 사용하면 ABCD에서 임의의 점을 쉽게 선택할 수 있습니다. AB에서 임의의 지점을 선택하십시오. BC에서 무작위로 임의의 지점을 선택하십시오. 즉. 중심으로부터의 거리를 제공하는 [0, R]에서 한 쌍의 난수 x와 y를 균일하게 선택하십시오. 우리의 삼각형은 얇은 은색이므로 AB와 BC는 본질적으로 평행합니다. 따라서 점 Z는 단순히 원점으로부터의 거리 x + y입니다. x + y> R이면 다시 접습니다.
다음은 R = 1에 대한 완전한 알고리즘입니다. 나는 그것이 매우 간단하다는 데 동의하기를 바랍니다. Trig을 사용하지만 random()거부 샘플링과 달리 소요 시간과 필요한 호출 수를 보장 할 수 있습니다 .
t = 2*pi*random()
u = random()+random()
r = if u>1 then 2-u else u
[r*cos(t), r*sin(t)]
여기 Mathematica에 있습니다.
f[] := Block[{u, t, r},
u = Random[] + Random[];
t = Random[] 2 Pi;
r = If[u > 1, 2 - u, u];
{r Cos[t], r Sin[t]}
]
ListPlot[Table[f[], {10000}], AspectRatio -> Automatic]
답변
반경 R 의 원 안에 임의의 점을 생성하는 방법 :
r = R * sqrt(random())
theta = random() * 2 * PI
( random()0과 1 사이의 값을 균일하게 부여 한다고 가정 )
이것을 직교 좌표로 변환하려면 할 수 있습니다
x = centerX + r * cos(theta)
y = centerY + r * sin(theta)
왜 sqrt(random())?
이어지는 수학을 보자 sqrt(random()) . 우리가 단위 원으로 작업하고 있다는 것을 간단하게 가정하십시오 (예 : R = 1).
점 사이의 평균 거리는 중심에서 얼마나 떨어져 있는지에 관계없이 동일해야합니다. 예를 들어 원주 2의 원 둘레를 보면 원주 1의 원 둘레 점 수의 두 배를 발견해야합니다.
원의 둘레 (2π r )가 r 과 함께 선형으로 성장 하기 때문에 임의의 점 수가 r 와 함께 선형으로 증가해야합니다 . 즉, 원하는 확률 밀도 함수 (PDF)가 선형으로 증가합니다. PDF의 면적이 1이고 최대 반지름이 1이므로
따라서 임의의 값의 원하는 밀도가 어떻게 보이는지 알고 있습니다. 지금: 우리가 가진 모든 것이 0과 1 사이의 균일 한 임의의 값일 때 어떻게 이러한 임의의 값을 생성합니까?
우리는라는 속임수를 사용합니다 역변환 샘플링
- PDF에서 누적 분포 함수 (CDF)를
- y = x를 따라 이것을 미러링
- 결과 함수를 0과 1 사이의 균일 한 값에 적용하십시오.
복잡한 소리? 직관을 전달하는 작은 트랙이있는 인용구를 삽입하겠습니다.
다음 분포를 사용하여 임의의 점을 생성한다고 가정합니다.
그건
- 1과 2 사이의 점의 1/5
- 점의 4/5는 2에서 3 사이에서 균일합니다.
CDF는 이름에서 알 수 있듯이 PDF의 누적 버전입니다. 직관적으로 : PDF ( x )는 x 의 난수 값 을 설명 하지만 CDF ( x )는 x보다 작은 난수 값을 설명합니다 .
이 경우 CDF는 다음과 같습니다.
이것이 어떻게 유용한 지 보려면, 균일하게 분포 된 높이에서 총알을 왼쪽에서 오른쪽으로 쏘는다고 상상해보십시오. 총알이 선에 부딪히면 땅에 떨어집니다.
지상의 총알 밀도가 원하는 분포와 어떻게 일치하는지 확인하십시오! 거의 다 왔어!
문제는이 함수의 경우 y 축이 출력 이고 x 축이 입력이라는 것입니다 입니다. 우리는 “땅에서 총알을 똑바로 쏴”만 할 수 있습니다! 우리는 역함수가 필요합니다!
이것이 우리가 모든 것을 반영하는 이유입니다. x 는 y가 되고 y 는 x 가됩니다 :
이 CDF -1 이라고합니다 . 원하는 분포에 따라 값을 얻기 위해 CDF -1 (random ())을 사용합니다.
… 따라서 PDF가 2 x 인 임의의 반경 값 생성으로 돌아갑니다. .
1 단계 : CDF를 작성하십시오.
실수로 작업하기 때문에 CDF는 PDF의 필수 요소로 표시됩니다.
CDF ( x ) = ∫ 2 x = x 2
2 단계 : y = x를 따라 CDF를 미러링합니다 .
수학적으로이 교환으로 귀결 X 와 Y를 하고 대한 해결 Y :
CDF : y = x 2
스왑 : x = y 2
풀기 : y = √ x
CDF -1 : y = √ x
3 단계 : 결과 함수를 0과 1 사이의 균일 한 값에 적용
CDF -1 (random ()) = √random ()
우리가 도출 한 것은 다음과 같습니다. 🙂
답변
여기에 빠르고 간단한 해결책이 있습니다.
즉, 범위 (0, 1) 두 개의 난수를 선택 a하고 b. 인 경우 b < a교체하십시오. 요점은 (b*R*cos(2*pi*a/b), b*R*sin(2*pi*a/b))입니다.
이 솔루션에 대해 다음과 같이 생각할 수 있습니다. 원을 가져 와서 자른 다음 곧게 펴면 직각 삼각형이 나타납니다. 그 삼각형의 다운 스케일, 당신은에서 삼각형이 줄 (0, 0)에 (1, 0)에 (1, 1)에 다시와 (0, 0). 이러한 모든 변환은 밀도를 균일하게 변경합니다. 당신이 한 일은 삼각형에서 임의의 점을 균일하게 고르고 원에서 점을 얻기 위해 과정을 뒤집 었습니다.
답변
따라서 대신 따기의 반지름의 제곱에 반비례의 포인트 밀도를 참고 r에서 [0, r_max]에서 선택, [0, r_max^2]다음, 당신의 좌표로 계산 :
x = sqrt(r) * cos(angle)
y = sqrt(r) * sin(angle)
이렇게하면 디스크에서 균일 한 점 분포가 제공됩니다.
답변
이런 식으로 생각하십시오. 하나의 축이 반지름이고 다른 하나가 각도 인 사각형이 있고이 사각형 내부의 반지름 0 근처에있는 점을 사용하는 경우 원점에 매우 가깝습니다 (원에 가깝습니다). 반경 R 근처의 점은 모두 원의 가장자리 근처에 있습니다 (즉, 서로 멀리 떨어져 있음).
이렇게하면 왜이 동작이 발생하는지 알 수 있습니다.
해당 링크에서 파생 된 요소는 원에 매핑 된 반지름에 의존하지 않도록 사각형의 해당 영역을 얼마나 조정해야하는지 알려줍니다.
편집 : 그래서 그가 당신이 공유하는 링크에 쓴 것은 “그것은 누적 분포의 역수를 계산함으로써 쉽게 할 수 있고, 우리는 r :을 얻는 것입니다.”입니다.
기본 전제는 여기에서 원하는 확률 밀도 함수의 누적 분포 함수의 역함수로 유니폼을 매핑하여 유니폼에서 원하는 분포로 변수를 만들 수 있다는 것입니다. 왜? 당분간은 당연한 것으로 여기지만 사실입니다.
다음은 수학에 대한 직관적 인 설명입니다. r에 대한 밀도 함수 f (r)은 r 자체에 비례해야합니다. 이 사실을 이해하는 것은 기본 미적분학 서적의 일부입니다. 극지방 요소에 대한 섹션을 참조하십시오. 다른 포스터들도 이것을 언급했습니다.
그래서 우리는 그것을 f (r) = C * r이라고 부릅니다.
이것은 대부분의 작업으로 밝혀졌습니다. 이제, f (r)은 확률 밀도 여야하므로, 간격 (0, R)에 걸쳐 f (r)을 적분함으로써 C = 2 / R ^ 2를 얻는다는 것을 쉽게 알 수 있습니다. .)
따라서 f (r) = 2 * r / R ^ 2
자, 이것이 링크에서 수식을 얻는 방법입니다.
그런 다음 마지막 부분은 (0,1)의 균일 한 랜덤 변수 u에서 나옵니다.이 원하는 밀도 f (r)에서 누적 분포 함수의 역함수로 매핑해야합니다. 이것이 왜 그런지를 이해하려면 Papoulis와 같은 고급 확률 텍스트를 찾거나 직접 파생해야합니다.
f (r)을 적분하면 F (r) = r ^ 2 / R ^ 2
이것의 역함수를 구하려면 u = r ^ 2 / R ^ 2를 설정하고 r을 구하면 r = R * sqrt (u)가됩니다.
이것은 완전히 직관적으로도 의미가 있으며, u = 0은 r = 0에 매핑되어야합니다. 또한 u = 1 shoudl은 r = R에 매핑됩니다.
답변
순진한 솔루션이 작동하지 않는 이유는 원 중심에 가까운 점에 높은 확률 밀도를 제공하기 때문입니다. 즉, 반지름이 r / 2 인 원은 선택된 점을 얻을 확률이 r / 2이지만 면적 (점 수) pi * r ^ 2 / 4를 갖습니다.
따라서 반지름 확률 밀도에 다음과 같은 속성이 있어야합니다.
주어진 r보다 작거나 같은 반경을 선택할 확률은 반경이 r 인 원의 면적에 비례해야합니다. (우리는 점에 균일 한 분포를 원하고 더 큰 영역은 더 많은 점을 의미하기 때문에)
다시 말해, 우리는 [0, r] 사이의 반지름을 선택할 확률이 원의 전체 영역에서 차지하는 비율과 같기를 원합니다. 총 원 면적은 pi * R ^ 2이고 반경이 r 인 원의 면적은 pi * r ^ 2입니다. 따라서 [0, r] 사이의 반지름을 (pi * r ^ 2) / (pi * R ^ 2) = r ^ 2 / R ^ 2로 선택할 확률을 원합니다.
이제 수학이 온다 :
[0, r] 사이의 반지름을 선택할 확률은 p에서 (r) dr의 0에서 r까지의 적분입니다 (작은 반지름의 모든 확률을 추가하기 때문입니다). 따라서 우리는 integral (p (r) dr) = r ^ 2 / R ^ 2를 원합니다. 우리는 R ^ 2가 상수라는 것을 분명히 알 수 있습니다. 그래서 우리가해야 할 일은 r ^ 2와 같은 것을 줄 때 p (r)를 알아내는 것입니다. 대답은 분명히 r * 상수입니다. 적분 (r * 상수 dr) = r ^ 2 / 2 * 상수. 이것은 r ^ 2 / R ^ 2와 같아야하므로 상수 = 2 / R ^ 2입니다. 따라서 확률 분포 p (r) = r * 2 / R ^ 2
참고 : 문제에 대해보다 직관적으로 생각할 수있는 또 다른 방법은 반경 ra의 각 확률 원이 원주에있는 점 수의 비율과 동일하게하려고한다는 것을 상상하는 것입니다. 따라서 반지름 r을 갖는 원은 원주에 2 * pi * r “점”을 가질 것이다. 총 포인트 수는 pi * R ^ 2입니다. 따라서 원 ra의 확률은 (2 * pi * r) / (pi * R ^ 2) = 2 * r / R ^ 2와 같아야합니다. 이것은 이해하기 쉽고 직관적이지만 수학적으로 들리는 것은 아닙니다.
답변
ρ (반지름) 및 φ (방위각)를 원 안의 임의의 점의 극좌표에 해당하는 두 개의 임의 변수로 둡니다. 점이 균일하게 분포되면 ρ와 φ의 분포 함수는 무엇입니까?
r : 0 <r <R의 경우 반경 좌표 ρ의 확률이 r보다 작을 때 r은
P [ρ <r] = P [점은 반경의 원 안에 있습니다 r] = S1 / S0 = (r / R) 2
여기서 S1과 S0은 각각 반경 r과 R의 원의 영역입니다. 따라서 CDF는 다음과 같이 주어질 수 있습니다.
0 if r<=0
CDF = (r/R)**2 if 0 < r <= R
1 if r > R
그리고 PDF :
PDF = d/dr(CDF) = 2 * (r/R**2) (0 < r <= R).
R = 1의 경우 랜덤 변수 sqrt (X)가 X가 [0, 1에서 균일 한 경우]이 정확한 CDF를 갖습니다 (P [sqrt (X) <y] = P [x <y ** 2] = y *). 0 <y <= 1의 경우 * 2).
φ의 분포는 분명히 0에서 2 * π까지 균일합니다. 이제 임의의 극좌표를 생성하고 삼각 방정식을 사용하여 직교 좌표로 변환 할 수 있습니다.
x = ρ * cos(φ)
y = ρ * sin(φ)
R = 1에 대한 파이썬 코드 게시에 저항 할 수 없습니다.
from matplotlib import pyplot as plt
import numpy as np
rho = np.sqrt(np.random.uniform(0, 1, 5000))
phi = np.random.uniform(0, 2*np.pi, 5000)
x = rho * np.cos(phi)
y = rho * np.sin(phi)
plt.scatter(x, y, s = 4)
당신은 얻을 것이다
