Random Algorithm HW1January 11, 20061Let Xkbe the number of white balls in the bin while there are k balls in the bin, Tkbethe random event of pick when there are k balls in the bin.We want to prove that for any 1 <= i, j <= k − 1, P r (Xk= i) = P r(Xk= j).We can prove this by induction:k = 2, then it is obvious that i = j = 1, P r(Xk= i) = P r(Xk= j) holds.Now assume that w hen k = m, for any 1 <= i, j <= m − 1, P r(Xm= i) = P r(Xm= j).then for k = m+1, for any 1 <= i, j <= m,P r(Xm+1= i) = P r(Xm= i − 1, Tm= W hite) + P r(Xm= i, Tm= Black)if 1 < i < m= P r(Tm= W hite|Xm= i − 1) ∗P r(Xm= i − 1) + P r(Tm= Black|Xm= i) ∗ P r(Xm= i)= (P r(Tm= W hite|Xm= i − 1) + P r(Tm= Black|Xm= i)) ∗ P r(Xm= j)=i−1m+m−im∗ P r(Xm= j)if i = m= P r(Tm= W hite|Xm= m−1)∗P r(Xm= m−1)+P r(Tm= Black|Xm= m)∗P r(Xm=m)= P r(Tm= W hite|Xm= m − 1) ∗ P r(Xm= j) because (P r(Xm= m) = 0)if i = 1= P r(Tm= W hite|Xm= 0) ∗ P r(Xm= 0) + P r(Tm= Black|Xm= 1) ∗ P r(Xm= 1)= P r(Tm= Black|Xm= 1) ∗ P r(Xm= j) because (P r(Xm= 0) = 0)in all cases=m−1m∗ P r(Xm= j)So th e proof is
View Full Document