DOC PREVIEW
Pitt CS 3150 - HOMEWORK

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Pitt CS 3150 - HOMEWORK

Documents in this Course
JouleSort

JouleSort

12 pages

Load more
Download HOMEWORK
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view HOMEWORK and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view HOMEWORK 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?