[📚정보] Walker's alias method for weightedRandom

[Ms.Yoon..(pianist9736)]

아래 게이가 쓴 글에 보충 설명 없을 것 같아서 뻐킹 걍 Chat 갓 GPT 한테 물어봤다. ㅋ

https://gall.dcinside.com/m/game_dev/161430

weighted random alias method에 대해 알아보자

일단 가중치 랜덤 알고리즘은 왜 쓰냐? 그냥 랜덤 함수 쓰면 될 것을? 이라고 생각할 수 있음.

룰렛을 예로 들면 (걍 인터넷에 아무 룰렛이미지 가져옴)

위에 빨간색 영역이 꽝이라고 할 때 대충 70%라고 치자. 이 값을 내가 60%로 바꾸고 싶어. 그럼 어떻게 함? 다른 파란색이나 초록색 영역들 확률까지 다 바꿔야하지?

저건 값이 3개라 금방 바꾸겠지만 확률 리스트가 막 100개라고 하면 그 중에 하나 바꾸면 나머지 99개 확률도 다 조정해야하잖아?(합계가 100%이어야 하기 때문에)

그래서 가중치 랜덤 알고리즘이 나온 것임. 가중치를 토대로 확률이 정해지기 때문에, 간단하게 원하는 확률의 가중치 값만 변경하면 나머진 자동으로 계산됨.

근데 이 알고리즘은 시간복잡도가 O(n)이라서 비효율적이라 A. J. Walker라는 게이가 좀 더 효율적인 알고리즘으로 만든 것 임(

https://en.wikipedia.org/wiki/Alias_method). 그리고 그리 크게 어렵지 않음.

요점은 그거임. 기존 가중치 랜덤 방식은 무식하게 for문 돌려서 지정된 값이 나올 때까지 값을 더해가면서 찾는 방법이었다면,

이건 미리 난수테이블 만들어서 그거 사용하는거. for문 돌릴 필요도 없고, 값도 더할 필요도 없음 이미 다 해놨기 때문에 편하게 난수테이블 배열에서 찾아 쓰면됨.

난수테이블에서 예외가 발생되면 그거 보완용으로 alias 테이블도 하나 더 만드는 것임.

아래부터는 Chat GPT 답변

다음 확률을 가진 세 가지 결과가 있다고 가정합니다.

결과 A: 50% 확률

결과 B: 30% 확률

결과 C: 20% 확률

별칭 방법을 적용하는 단계는 다음과 같습니다.

1단계: 확률 정규화

먼저 확률을 조정하여 확률의 합이 결과 수(이 경우 3)와 같아지도록 합니다.

정규화된 확률:

A: 0.5 * 3 = 1.5

B: 0.3 * 3 = 0.9

C: 0.2 * 3 = 0.6

2단계: 두 개의 목록 만들기

결과를 두 개의 목록으로 분리합니다.

확률 ≤ 1의 경우 small

확률 > 1의 경우 large

small: B(0.9), C(0.6)

large: A(1.5)

3단계: 표 채우기

두 개의 배열 prob와 alias를 초기화합니다. 둘 다 크기가 3(결과의 수)입니다.

배열 초기화:

prob = [0, 0, 0]

alias = [-1, -1, -1] (별칭이 없음을 나타내기 위해 -1 사용)

각 쌍 처리:

1. small에서 한 요소와 large에서 한 요소를 가져옵니다.

small: C (0.6)

large: A (1.5)

C의 prob를 0.6(정규화된 확률)으로 설정합니다.

prob = [0.6, 0, 0]

C의 alias를 A(더 큰 요소)를 가리키도록 설정합니다.

alias = [A, -1, -1]

C에서 사용한 양을 빼서 A의 확률을 조정합니다.

A의 조정된 확률 = 1.5 - (1 - 0.6) = 1.1

(A의 확률의 0.4를 사용하여 C의 총 확률을 1.0으로 만들었으므로)

이제 A의 조정된 확률(1.1)은 여전히 1보다 크므로 large에 남아 있습니다.

2. 다음 쌍:

small: B (0.9)

large: A (1.1)

B의 prob를 0.9(정규화된 확률)로 설정합니다.

prob = [0.6, 0.9, 0]

B의 alias를 A를 가리키도록 설정합니다.

alias = [A, A, -1]

A의 확률을 조정합니다.

A의 조정된 확률 = 1.1 - (1 - 0.9) = 1.0

이제 A의 조정된 확률은 정확히 1이므로 더 이상 aliasing이 필요하지 않습니다.

3. 나머지 요소 A는 prob를 직접 설정합니다.

prob = [0.6, 0.9, 1.0]

alias = [A, A, -1]

4단계: 샘플링

결과를 샘플링하려면 다음을 수행합니다.

1. 임의 인덱스 i(0, 1 또는 2)를 생성합니다.

2. 0과 1 사이의 다른 난수 r을 생성합니다.

3. r < prob[i]이면 인덱스 i의 결과를 사용합니다. 그렇지 않으면 인덱스 i의 별칭을 사용합니다.

예제

다음과 같은 난수 값을 얻는다고 가정해 보겠습니다.

난수 인덱스 i = 1(결과 B 또는 별칭 A에 해당)

난수 r = 0.7

i = 1(B)의 경우:

prob[1] = 0.9

r = 0.7 < 0.9이므로 결과 B를 선택합니다.

r = 0.95인 경우:

r = 0.95 > 0.9이므로 A를 가리키는 별칭을 사용합니다.

요약

사전 처리된 배열:

prob = [0.6, 0.9, 1.0]

alias = [A, A, -1]

다음 배열은 효율적인 샘플링을 허용합니다.

인덱스를 무작위로 선택합니다.

prob 및 alias 배열을 사용하여 결과를 확인합니다.

이 방법은 초기 전처리 단계 이후 각 샘플이 일정 시간 O(1) 내에 생성되도록 보장합니다.

난 걍 복붙(+약간의 정리)했고, 이해안되면 니들도 물어봐라 ㅋㅋ 그는 갓갓!

[불타는키보드(1bnmaker)]

[태보미(taebomi)]

왜쓰는지에대한 너무좋은설명이야