Solving Randomized Algorithm Problems: Exploring Math Behind it

[Fellowroot]

I find this problem pretty interesting and I'd like to know more about it and what topic of math it comes from.

Amy and Chris stand opposite from each other at a table. Amy has a bag filled with certain shapes and these shapes are squares, circles and triangles. On the table there are 5 separate containers which at max can only hold a single shaped object. At the start of this process all containers are empty. Amy then randomly selects objects from her bag and then places them into the containers. The entire process is measured with steps where each step represents an object being placed into a container. Chirs likes collecting triangles and when a triangle appears in a container he immediately grabs it and removes it. What is the probability that Chirs will no longer be able to collect any more triangles after X amount of steps have passed?

I asked my professor about this and he said that it was a randomized algorithm problem. Could anyone possibly tell me more about this problem and how to go about solving it?

Thanks.

 

[jedishrfu]

The first place to start is:

http://en.wikipedia.org/wiki/Randomized_algorithm

from there you can branch out into genetic algorithms and the use of random changes to potential solutions.

 

[FactChecker]

This sounds to me like a stochastic process called a Markov chain. A Markov chain has a fixed state transition matrix whose elements are the probabilities of transitioning from anyone state to another. The question is when the game you describe will end with non-triangles in all 5 containers. The states are the shapes in the containers. The transition matrix elements are the probabilities that, starting in one state, the next draw by Amy will put a certain shape into a certain container and transition to another state. The transition matrix can be analysed to determine the probabilities of terminating in a state with all containers containing a non-triangle.