waca's field

# random walk 술취한 바퀴벌레 문제 // 문제가 길다. 집중해서 살펴보자. 수학 분야에서 "random walk"로 불리워지며 오랫동안 관심의 대상이 되었던 많은 문제들이 있다. 이러한 문제 중 지극히 간단한 것조차도 해결하기 매우 어렵기 때문에 대부분의 문제들이 해결되지 못한 채 남아 있다. 그 하나의 예가 '술취한 바퀴벌레 문제'다. 한 (술취한) 바퀴벌레가 $m$$\times$$n$ 크기의 직사각형 방 중간의 한 타일 위에 있다. 바퀴벌레는 임의로 타일에서 타일로 이동한다. 바퀴벌레가 현재 타일에서 그 주위 8개의 타일(벽 옆에 있지 않은 경우에 한해)로 같은 확률을 가지고 움직인다고 가정하자. 이 때 적어도 한 번씩 방의 모든 타일을 지나가는 데 걸리는 시간은 얼마인가? 순수한 확률 이..