시에르핀스키 삼각형 위의 두 점의 평균 거리

짧은 수학 트리비아. 한 변의 길이가 1인 시에르핀스키 삼각형에서 두 점을 균일하게 선택했을 때 두 점 사이를 연결하는 시에르핀스키 삼각형 위의 경로를 잡아 그 거리를 생각할 수 있다. 그 거리의 평균은 466/885이라고.[1]

이 시에르핀스키 삼각형은 하노이의 탑과 연관이 있다는게 잘 알려져 있는데, n개의 링을 이용한 configuration들로 이루어진 그래프는 n번째 시에르핀스키 중간 도형 모양으로 나온다. 즉 위 결과는 달리 말하자면 임의의 두 configuration에 대해 한 상태에서 다른 상태로 바꾸는데 필요한 최소 턴 수의 평균이 asymptotically \frac{466}{885}2^n이 된다는 것. 이 해석을 이용해서 finite automata를 만들어 증명하는 방법도 있다.[2]

트윗 타래를 정리. (2019/03/01)

References

[1] A. M. Hinz and A. Schief, “The average distance on the Sierpinski gasket” Probability Theory and Related Fields, March 1990, 87(1), pp 129-138. DOI: 10.1007/BF01217750

[2] D. Romik, “Shortest Paths in the Tower of Hanoi Graph and Finite Automata” SIAM J. Discrete Math., 20(3), 610-622. DOI: 10.1137/050628660

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중