Brief

A broad of computational algorithms.

Origin

## Warning: package 'leaflet' was built under R version 3.6.2

When the experiment procedure comes with high cost.

Application

Common usages

• To stimulate the real experiment procedure.
• Used as a computing method.
• Alternative solution for Multi-degree-of-freedom system.
• Alternative solution for Optimization problem.

Application on test statistic

One of the three keys.

Obtuse Triangle Method

Randomly get B pairs of (x,y) from U(0,1), the probability that a pair (x,y,1) can form a obtuse triangle is \(\frac{\pi -2}{4}\), next, we’ll show why.

1.
To form a triangle, the sum of two short side has to be longer than the third side. Thus, we can get the requirement \(x+y>1\)

2.
To form a obtuse triangle, the sum square of two short side has to be shorter than the sum square of the third side. Thus, we can get the requirement \(x^2+y^2<1\)

3.
Stack the two plot from (1) and (2), we can know that the area is the only place that can form a obtuse triangle. The probability that a point will fall in the area is \(\frac{\pi -2}{4}\), which we claim in the beging.

set.seed(12345)
n = 0
r = 1
B <- 10000
obtri <- function(B,r){
  n = 0
  for(i in 1:B){
  x_y = runif(2,0,r)
  runif(1)
  x <- x_y[1]
  y <- x_y[2]
  if(x+y>r && x^2+y^2<r^2){
    n = n+1
    }
  }
  return(n)
}
a = obtri(B,r)
a/B*4+2

## [1] 3.1532

Buffon’s Needle Method

1.
Given a angle \(\theta = \hat{\theta}\), and let the length of a needle = 1, and the distance of two parallel line = 1 either.
Under the condition given above, we can simply get that the probabilty a needle will be intersect with the parallel lines will be \[p(a\ needle\ intersect\ with\ parallel\ lines\ |\ \theta = \hat{\theta})=sin(\hat{\theta}) \]

2.
Make \(\theta\) be constrain in (0,\(\pi/2\)), we can know that \(\theta\) ~ U(0,\(\pi/2\)).
Thus \[p(\hat{\theta}) = \frac{2}{\pi}\]

3.
Simply times the consequence from 1 and 2 we can know that \[p(a\ needle\ intersect\ with\ parallel\ lines\ ,\theta) = \frac{2}{\pi}sin(\theta)\] \[p(a\ needle\ intersect\ with\ parallel\ lines) = \int_{0}^{\frac{2}{\pi}} \frac{2}{\pi}sin\theta \,d\theta = \frac{2}{\pi}\]

Thus, we now know that we randomly throw a needle on a surface full of parallel lines, the prob it will intersect any line is \(\frac{2}{\pi}\), by getting this consequence, we can go on and simulate \(\pi\). \[\pi \approx 2\frac{B}{n}\]

Note that the formula above can be generize to \[\pi \approx 2\frac{lB}{Dn}\], where \(l\) is the lengh of the needle and \(D\) is the distance of two parallel lines. (\(D>=l\))

Next, we trasfer it into algorithm
Step1 : Construct B vectors that has norm 1
Step2 : Construct B pair of (x,y) from U(0,1)
Step3 : Add the y in step1 and step2, if it is smaller than 0 of bigger than 1, it means that it intersect the parallel line.

Buffon_Needle <- function(B,D,L) {
  vec_x <- runif(B,0,1) - runif(B,0,1)
  vec_y <- runif(B,0,1) - runif(B,0,1)
  input_vec_x <- vec_x/sqrt(vec_x^2+vec_y^2)*L
  input_vec_y <- vec_y/sqrt(vec_x^2+vec_y^2)*L
  x1 <- runif(B,0,D)
  y1 <- runif(B,0,D)
  x2 <- x1+input_vec_x
  y2 <- y1+input_vec_y
  # Count how many needles intersect the bounderies
  yes <- no <- 0
  for(i in 1:B){
    ifelse(y2[i] <= D & y2[i] >= 0,no <- no+1,yes<-yes+1)
  }
  # Using the formula to find the value of Pi according to the 'Buffon's Needle' experiment that we have done.
  pi <- round((2*L)/(D*(yes/B)),digits = 5)
  return(pi)
}

# Example (B=1000, D=3, L=3)
pi_value <- c()
for(i in 1:100){
  bf <- Buffon_Needle(1000,3,3) # Note that in the Buffon's Needle experiment, L must < or = D
  pi_value <- c(pi_value,bf)
}
mean(pi_value)

## [1] 3.143841

hist(pi_value)