Titles/abstracts of talks will be posted as they become available. Unless indicated otherwise, these seminars will take place on Tuesday afternoons, during the free period, in the Business & Science Building, Room 335.
Date: Thursday, April 5, 2012 (Free Period, BSB 335)
Speaker: Dr. Guy Kortsarz, Rutgers-Camden, Computer Science Dept.
Title: Random Walk on Undirected Graphs and a bit on Markov Chains
Abstract: I will describe some of the properties of random walks in undirected graphs. This means that if you are at vertex v and have d neighbors you will choose to go to each of these neighbors with probability 1/d. Interestingly under some simple conditions, the expected number of steps until you visit all vertices of the graph is only O(n^3) (there is a graph for which it is indeed Omega(n^3)).
To simplify the proof of the above we state some properties of a more general topic called Discrete Markov Chains and a fundamental theorem in this field.
We will discuss examples too. Like shuffling cards: If you iteratively take the top of the deck of cards and place it in one of the n possible places (back on top is one of them), what is the expected time for the cards to be shuffled?
A knowledge of basic probability is all that is required for this talk.
Please send email to Roxanne Huertas, the department secretary, at ude.sregtur.nedmacnull@satreuhr to be included on the seminar mailing list.