Random이란?

• "닥치는 대로의", "무작위의"
• 자연 현상에서 가져온다면 random
• 컴퓨터가 뽑아내면 pseudo-random

Pseudo-random

• 하드웨어 기반의 RNG(random number generator)를 이용할 수도 있지만 비싸고 느림
• 
• 

PRNG

• 완전히 random한 seed값 하나만 이용해서 로직에 따라 일련의 값을 생성하는 방식
• Java는 2020년까지 선형 합동 생성기(Linear Congruential Generator) 알고리즘을 이용
  • mod 연산에 의존
  • Java 17부터는 다양한 생성기 알고리즘이 제공되며 커스터마이즈도 가능함

LCG

$$
X_ = (aX_ + c) mod m
$$

Random의 특성

• 예측하기는 어렵지만 분포가 균질하진 않음
• 중복이 발생하거나 특정 값 인근에서 몰려서 발생하기도 함
• 반대로 확률적으로 예측되는 값이 발생하지 않기도 함
  • 주사위를 60번 던져도 1이 한 번도 안 나올 수 있음

Uniform distribution

• 주사위를 60번 던졌는데 주사위 눈이 각각 10번씩 나오는 분포
  • 이렇게 예측이 가능하다면 게임을 할 수 있나?

분포의 비교

• uniform vs normal
  • 
• uniform vs random in 2 dimension
  • 
• 언제 어떤 분포를 사용하는 게 필요한가?
  • random은 예측이 어렵게 만들 때
  • uniform은 공평한 분배가 필요할 때
  • normal은 인구적 특성을 따라야 할 때

원주율 계산을 해보자

"Monte-Carlo" 방법에 의한 원주율 계산 시뮬레이션

• 랜덤하게 좌표를 구한 다음, 좌표 (0, 0)으로부터의 거리를 구해서
  • 반지름 이내에 들어온 갯수를 세고 ... n1
  • 반지름 바깥에 들어온 갯수를 세어 ... n2
• 그 비율을 계산하면 원주율을 구할 수 있음
  $$
  (n1+n2) : n2 = 4 : pi
  $$
• 오차가 상당히 큼
  • 수천 번에서 수만 번을 시도해도 3.0이나 3.2 정도의 값이 나오기도 함
  • 3.14에 가까운 값을 얻으려면 수십만 번 시도해야 함
• 오차의 발생원인?
  • random "bias"

중간적 성질을 가지는 random 분포

"Equi-distribution"
"quasi-random"

구체적인 수열 생성 방법

• Halton
• Sobol
• van der Corput
• R2

1차원에서

van der Corput 수열

• quasi-random한 random number sequence
  
• 계산 방식이 간단해서 컴퓨팅에서 많이 응용함
  • 분산 클러스터의 각 노드에 quasi-random으로 균등 분배할 때 편리함
  • 이 수열 사용 시, 클러스터 구성에 변경이 생겨도 재계산 불필요
    

다차원에서

R-sequence 알고리즘

$$
R_1(\alpha)\ :\ t_ = { s_ + n\alpha }
$$

• 알파는 무리수
• n = 1, 2, 3, ...
• { x }는 x의 소수점 이하 값
• s0는 seed 값

알파값으로 원주율을, s0값으로 0을 사용하게 되면, 수열은 다음과 같은 형태가 됨
0.618, 0.236, 0.854, 0.472, 0.090, 0.708, 0.327, 0.944, 0.562, 0.180, 0.798, 0.416, 0.034, 0.652, 0.271, 0.888, ...

품질 평가 기준

• "낮은 불일치"(low discrepancy)라는 수학적 개념이 있음
  • 중복되지 않고 몰리지 않음
• 모든 quasi-random 수열의 품질 기준은 원소들 사이의 거리가 고르게 멀어야 함
• van der corput은 최대 범위가 커질수록 품질이 선형으로 좋아지는 특성이 있음
  • 다양한 수열들의 lower bound 기준이 됨

R2

• R1 수열을 2개 사용하면 됨
• quasi-random에서 가장 널리 사용되는 Sobol이나 Halton, Kronecker에 비해서 월등히 품질이 좋음
  

R-sequence 알고리즘 평가

• 품질
  • s0는 품질에 영향을 끼치지 않으나 자유도를 부여할 수 있음
  • 알파는 품질에 영향을 끼치는데, 황금비(golden ratio, 1.6180339...)의 역수일 때 가장 품질이 높음
  • R1의 품질은 van der corput보다 더 좋음
  • R2의 품질은 다른 알고리즘에 비해 월등히 뛰어남
• 계산 방법이 크게 복잡하지 않아서 컴퓨팅에서 활용하기 좋음

Random의 (주의해야 할) 응용 - Shuffling

• 로직
  • 단순히 random mod 7로 반복해서 뽑으면 안 됨
  • 한 번 랜덤하게 뽑은 것은 별도 집합에 추가하고 대상 집합의 크기를 하나씩 줄여나가야 함

Fisher-Yates algorithm

Random의 (잘못된) 응용 - Unique ID 발급

• Unique ID 발급에는 중복 방지가 상당히 중요함
• random 대신에 key가 되는 값이 deterministic하게 결정되는 hashing을 이용할 것
• 100% 중복 방지가 되는 건 아니지만 확률적으로 극히 낮음

소프트웨어 개발자의 주의사항

in Java

• 간단한 random이 필요하면 Math.random()을 쓰자
• 정교한 random이 필요하면 java.util.Random을 쓰자
  • thread-safe하지만 동시에 사용하면 느려짐
  • 대신 ThreadLocalRandom을 쓰자
  • 스트림에서 쓰려면 SplittableRandom을 쓰자
• 암호학적으로 안전한 random이 필요하면, SecureRandom을 쓰자

in Linux

• 엔트로피를 '추정'만 함. 계산을 반복적으로 하진 않음
• /dev/random vs /dev/urandom
  • blocking IO vs non-blocking IO
  • 엔트로피가 낮아지면 /dev/random은 block됨 (안전함)
  • /dev/urandom은 block이 안 됨(취약함)
  • 중간 수준의 /dev/arandom이라는 것도 있음

공통

• 꼭 random을 써야 하는지 다시 생각해보자
  • 혹시 quasi-random이 필요한 경우가 아닌가?
  • 자주 중복되거나 값들끼리 몰려도 괜찮나?
• random을 사용할 때 암호학적으로 안전해야 하는지 생각해보자

참고자료

• https://recordsoflife.tistory.com/1055
• https://linuxhint.com/dev_random_vs_dev_urandom/
• https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/
• https://netflixtechblog.com/curbing-connection-churn-in-zuul-2feb273a3598