Lecture 4: Math. background

Lecture 4: Math. background

Markov Chain: (Random Walk) : 닫힌 DFS에서 다른 state로 전이할 때 probabilistic 하게 다음 state를 선택함.

마르코프 연쇄는 시간에 따른 시스템 상태의 변화를 나타낸다. 매 시간마다 시스템은 상태를 바꾸거나 같은 상태를 유지한다. 상태의 변화를 전이라 한다. 마르코프 성질은 과거와 현재 상태가 주어졌을 때의 미래 상태의 조건부 확률 분포가 과거 상태와는 독립적으로 현재 상태에 의해서만 결정된다는 걸 뜻한다. – Wikipedia

Picking a random person among facebook users

  1. Pick an arbitaraly person i
  2. Choose a friend j of i at uniformly at random
  3. Set j <- i with probability min(1, # friends of i / # friends of j)
  4. Go to Step 1
  5. Iterative Step 1, 2, 3, 4 1000 times to choose final person.

Notation:
<PPT 붙여넣을 것 >

Card shuffling : < WRONG EXAMPLE!! >

X(t) = P^tX(0).

converges only when uP = u where u is uniform distribution.

How fast does this converge?

Leave a Reply