monte-carlo Archives

여기에 정의 된 파란색 영역에서 샘플을 생성하고 싶습니다.

순진한 솔루션은 단위 제곱에서 거부 샘플링을 사용하는 것이지만 이는 $1 - π / 4$

1 - π / 4

$1-\pi/4$ (~ 21.4 %) 효율 만 제공합니다.

더 효율적으로 샘플링 할 수있는 방법이 있습니까?

답변

초당 2 백만 포인트가됩니까?

분포는 대칭입니다. 우리는 전체 원의 1/8에 대한 분포를 계산 한 다음 다른 낙엽 주위로 복사하면됩니다. 극좌표 에서 값 의 임의 위치 에 대한 각도 의 누적 분포 는 삼각형 및 에서 연장되는 원의 호 $(r, θ)$

(r, θ)

$(r,\theta)$ $Θ$

Θ

$\Theta$ $(X, Y)$

(X, Y)

$(X,Y)$ $θ$

θ

$\theta$ $(0, 0), (1, 0), (1, \tan θ)$

(0, 0), (1, 0), (1, \tan θ)

$(0,0), (1,0), (1,\tan\theta)$ ~ . 따라서 비례 $(1, 0)$

(1, 0)

$(1,0)$ $(\cos θ, \sin θ)$

(\cos θ, \sin θ)

$(\cos\theta,\sin\theta)$

F_{Θ} (θ) = Pr (Θ \leq θ) \propto \frac{1}{2} \tan (θ) - \frac{θ}{2},

$F_\Theta(\theta) = \Pr(\Theta \le \theta) \propto \frac{1}{2}\tan(\theta) - \frac{\theta}{2},$

밀도가

f_{Θ} (θ) = \frac{d}{d θ} F_{Θ} (θ) \propto \tan^{2} (θ) .

$f_\Theta(\theta) = \frac{d}{d\theta} F_\Theta(\theta) \propto \tan^2(\theta).$

우리는 거부 방법 (효율 )을 사용하여이 밀도에서 샘플링 할 수 있습니다 . $8 / π - 2 \approx 54.6479 %$

8 / π - 2 \approx 54.6479 %

$8/\pi-2 \approx 54.6479\%$

좌표 반경 조건부 밀도 비례 과 및 . CDF의 쉬운 반전으로 샘플링 할 수 있습니다. $R$

R

$R$ $r d r$

r d 아르 자형

$rdr$ $r = 1$

아르 자형 = 1

$r=1$ $r = \sec θ$

아르 자형 = 비서 θ

$r=\sec\theta$

우리는 독립 샘플을 생성하는 경우 직교 좌표로 변환 백 샘플이 팔분. 표본이 독립적이기 때문에 임의로 무작위로 좌표를 교환하면 원하는 경우 1 사분면에서 독립적 인 임의 표본이 생성됩니다. (랜덤 스왑은 스왑 할 실현 횟수를 결정하기 위해 단일 이항 변수 만 생성하면됩니다.) $(r_{i}, θ_{i})$

({아르 자형}_{나는}, θ_{나는})

$(r_i,\theta_i)$ $(x_{i}, y_{i})$

({엑스}_{나는}, {와이}_{나는})

$(x_i,y_i)$

각각의 그러한 구현 보통, 하나 개의 균일 변량에 (대해 필요 ) 플러스 2 개 배 균일 (위한 variates ) 및 (고속) 소량의 계산. 그것은 점 당 변화입니다 (물론 두 좌표가 있습니다). 자세한 내용은 아래 코드 예제에 있습니다. 이 수치는 생성 된 50 만 개 이상의 포인트 중 10,000 개를 나타냅니다. $(X, Y)$

(엑스, 와이)

$(X,Y)$ $R$

아르 자형

$R$ $1 / (8 π - 2)$

1 / (8 π - 2)

$1/(8\pi-2)$ $Θ$

Θ

$\Theta$ $4 / (π - 4) \approx 4.66$

4 / (π - 4) \approx 4.66

$4/(\pi-4) \approx 4.66$

R이 시뮬레이션을 생성하고 시간을 정한 코드 는 다음과 같습니다 .

n.sim <- 1e6
x.time <- system.time({
  # Generate trial angles `theta`
  theta <- sqrt(runif(n.sim)) * pi/4
  # Rejection step.
  theta <- theta[runif(n.sim) * 4 * theta <= pi * tan(theta)^2]
  # Generate radial coordinates `r`.
  n <- length(theta)
  r <- sqrt(1 + runif(n) * tan(theta)^2)
  # Convert to Cartesian coordinates.
  # (The products will generate a full circle)
  x <- r * cos(theta) #* c(1,1,-1,-1)
  y <- r * sin(theta) #* c(1,-1,1,-1)
  # Swap approximately half the coordinates.
  k <- rbinom(1, n, 1/2)
  if (k > 0) {
    z <- y[1:k]
    y[1:k] <- x[1:k]
    x[1:k] <- z
  }
})
message(signif(x.time[3] * 1e6/n, 2), " seconds per million points.")
#
# Plot the result to confirm.
#
plot(c(0,1), c(0,1), type="n", bty="n", asp=1, xlab="x", ylab="y")
rect(-1, -1, 1, 1, col="White", border="#00000040")
m <- sample.int(n, min(n, 1e4))
points(x[m],y[m], pch=19, cex=1/2, col="#0000e010")

답변

@cardinal, @whuber 및 @ stephan-kolassa의 다른 솔루션보다 간단하고 효율적이며 계산적으로 저렴한 다음 솔루션을 제안합니다.

다음과 같은 간단한 단계가 포함됩니다.

1) 두 개의 표준 균일 샘플을 채집합니다 :

u_{1} \sim U n i f (0, 1) u_{2} \sim U n i f (0, 1) .

$u_1 \sim Unif(0,1)\\ u_2 \sim Unif(0,1).$

2a) 포인트 다음 전단 변환을 적용합니다 (오른쪽 아래 삼각형의 점은 왼쪽 위 삼각형에 반영되어 “반사되지 않음”) 2b)에서 :
$min {u_{1}, u_{2}}, max {u_{1}, u_{2}}$

min {u_{1}, u_{2}}, max {u_{1}, u_{2}}

$\min\{u_1,u_2\}, \max\{u_1,u_2\}$

[\begin{matrix} x \\ y \end{matrix}] = [\begin{matrix} 1 \\ 1 \end{matrix}] + [\begin{matrix} \frac{\sqrt{2}}{2} & - 1 \\ \frac{\sqrt{2}}{2} - 1 & 0 \end{matrix}] [\begin{matrix} min {u_{1}, u_{2}} \\ max {u_{1}, u_{2}} \end{matrix}] .

$\begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} 1\\1 \end{bmatrix} + \begin{bmatrix} \frac{\sqrt{2}}{2} & -1\\ \frac{\sqrt{2}}{2} - 1 & 0\\ \end{bmatrix} \, \begin{bmatrix} \min\{u_1,u_2\}\\ \max\{u_1,u_2\}\\ \end{bmatrix}.$

2b) 경우 와 교체하십시오 . $x$

x

$x$ $y$

y

$y$ $u_{1} > u_{2}$

u_{1} > u_{2}

$u_1 > u_2$

3) 단위 원 내부 (예 : 72 % 정도 허용) 인 경우 샘플을 거부합니다 (예 :

x^{2} + y^{2} < 1.

$x^2 + y^2 < 1.$

이 알고리즘의 직관이 그림에 나와 있습니다.

2a 단계와 2b 단계는 단일 단계로 병합 될 수 있습니다.

2) 전단 변형을 적용하고 스왑

x = 1 + \frac{\sqrt{2}}{2} min (u_{1}, u_{2}) - u_{2} y = 1 + \frac{\sqrt{2}}{2} min (u_{1}, u_{2}) - u_{1}

$x = 1 + \frac{\sqrt{2}}{2} \min(u_1, u_2) - u_2\\ y = 1 + \frac{\sqrt{2}}{2} \min(u_1, u_2) - u_1$

다음 코드는 위의 알고리즘을 구현하고 @whuber의 코드를 사용하여 테스트합니다.

n.sim <- 1e6
x.time <- system.time({
    # Draw two standard uniform samples
    u_1 <- runif(n.sim)
    u_2 <- runif(n.sim)
    # Apply shear transformation and swap
    tmp <- 1 + sqrt(2)/2 * pmin(u_1, u_2)
    x <- tmp - u_2
    y <- tmp - u_1
    # Reject if inside circle
    accept <- x^2 + y^2 > 1
    x <- x[accept]
    y <- y[accept]
    n <- length(x)
})
message(signif(x.time[3] * 1e6/n, 2), " seconds per million points.")
#
# Plot the result to confirm.
#
plot(c(0,1), c(0,1), type="n", bty="n", asp=1, xlab="x", ylab="y")
rect(-1, -1, 1, 1, col="White", border="#00000040")
m <- sample.int(n, min(n, 1e4))
points(x[m],y[m], pch=19, cex=1/2, col="#0000e010")

일부 빠른 테스트에서는 다음과 같은 결과가 나타납니다.

알고리즘 /stats//a/258349 . 백만 포인트 당 3 : 3 초 중 최고.

이 알고리즘. 3 분의 1 : 0.18 초

답변

글쎄, 더 효율적으로 할 수는 있지만 더 빨리 찾지 않기를 바랍니다 .

$x$

x

$x$ $x$

x

$x$

f (x) = 1 - \sqrt{1 - x^{2}} .

$f(x) = 1-\sqrt{1-x^2}.$

Wolfram은 다음을 통합하는 데 도움을줍니다 .

\int_{0}^{x} f (y) d y = - \frac{1}{2} x \sqrt{1 - x^{2}} + x - \frac{1}{2} \arcsin x .

$\int_0^x f(y)dy = -\frac{1}{2}x\sqrt{1-x^2}+x-\frac{1}{2}\arcsin x.$

So the cumulative distribution function $F$

F

$F$ would be this expression, scaled to integrate to 1 (i.e., divided by $\int_{0}^{1} f (y) d y$

\int_{0}^{1} f (y) d y

$\int_0^1 f(y)dy$ ).

Now, to generate your $x$

x

$x$ value, pick a random number $t$

t

$t$ , uniformly distributed between $0$

0

$0$ and $1$

1

$1$ . Then find $x$

x

$x$ such that $F (x) = t$

F (x) = t

$F(x)=t$ . That is, we need to invert the CDF (inverse transform sampling). This can be done, but it's not easy. Nor fast.

Finally, given $x$

x

$x$ , pick a random $y$

y

$y$ that is uniformly distributed between $\sqrt{1 - x^{2}}$

\sqrt{1 - {엑스}^{2}}

$\sqrt{1-x^2}$ 과 $1$

1

$1$ .

아래는 R 코드입니다. CDF를 그리드에서 사전 평가하고 있습니다. $x$

엑스

$x$ 값까지도 걸리지 만이 과정은 몇 분 정도 걸립니다.

약간의 생각을 투자하면 CDF 반전 속도를 상당히 높일 수 있습니다. 그런 다음 다시 생각이 아프다. 나는 개인적으로 내가 가진하지 않는 한, 더 빠르고 훨씬 적은 오류가 발생하기 쉬운입니다 거부 샘플링, 갈 것이다 매우 에 좋은 이유가 없습니다.

epsilon <- 1e-6
xx <- seq(0,1,by=epsilon)
x.cdf <- function(x) x-(x*sqrt(1-x^2)+asin(x))/2
xx.cdf <- x.cdf(xx)/x.cdf(1)

nn <- 1e4
rr <- matrix(nrow=nn,ncol=2)
set.seed(1)
pb <- winProgressBar(max=nn)
for ( ii in 1:nn ) {
    setWinProgressBar(pb,ii,paste(ii,"of",nn))
    x <- max(xx[xx.cdf<runif(1)])
    y <- runif(1,sqrt(1-x^2),1)
    rr[ii,] <- c(x,y)
}
close(pb)

plot(rr,pch=19,cex=.3,xlab="",ylab="")

How IT

언제든지 물어보세요.

태그 보관물: monte-carlo

단위 원과 단위 사각형 사이에서 효율적으로 점 생성 솔루션은 단위 제곱에서 거부 샘플링을

답변

답변

답변

답변