문제: 로봇이 x축에서 x = 0에 위치해 있음. 로봇은 한번 움직일때마다 오른쪽/왼쪽 방향을 똑같은 확률로 랜덤하게 정해서 그 방향으로 1만큼 이동함. 로봇이 k번 움직인다고 하고 로봇의 마지막 위치를 랜덤변수 Y라고 했을때 E[|Y|] = Theta(sqrt(k))를 증명하는게 문제.


upper bound는 Chernoff bound로 풀었음. lower bound가 문제인데 위키피디아에서 그냥 binomial distribution의 tail lower bound 가져다가 썼거든. 근데 이렇게 푸는거 아닌것 같은데 더 간단한 방법이 있나? Y의 standard deviation이 sqrt(k)니까 직관적으로 생각하면 Y가 구간 [-sqrt(k), +sqrt(k)] 밖에 있을 확률이 constant 확률은 될것 같긴 한데