University:
Amherst College
Course:
MATH 365 | Stochastic Processes
Academic year:

2022
Views:

265

Pages:

2
Author:

Origbo2ol

Math 365 Polya’s Urn Submit an R script and/or handwritten submission by next Wednesday. The objective of this lab is to explore an example of a martingale called Polya’s urn. 1 Description of Polya’s Urn Suppose you have an urn containing one red ball and one green ball. You draw one at random; if the ball is red, put it back in the urn with an additional red ball (so urn now has 2 red and 1 green), otherwise put it back and add a green ball (so urn now has 1 red and 2 green). Repeat this procedure and let the random variable Xn be the number of red balls in the urn after n draws. Note that X0 = 1. The random variables X0 , X1 , X2 , . . . form a Markov chain with transition probabilities k n+2 k = k + 1 | Xn = k} = n+2 P{Xn+1 = k | Xn = k} = 1 − P{Xn+1 1 Let Mn = n+2 Xn , the proportion of red balls in the urn after n draws. To prove that Mn is a martingale with respect to Xn , it’s sufficient to show that E(Mn+1 | Xn ) = Mn . Check the calculations below to make sure they make sense to you: E(Xn+1 | Xn )(k) = kP{Xn+1 = k | Xn = k} + (k + 1)P{Xn+1 = k + 1 | Xn = k} = so E(Mn+1 | Xn ) = 2 n+3 k, n+2 1 n+3 1 1 E(Xn+1 | Xn ) = · Xn = Xn = Mn . n+3 n+3 n+2 n+2 Simulation of Polya’s urn The following R code simulates 998 draws, until the urn contains 1000 balls. The simulation is run 2000 times, so you can examine the distribution of M998 at the end: nStop <- 998 nSim <- 2000 propRed <- matrix(0,nSim,1) for (n in 1:nSim) { nRed <- 1 nGreen <- 1 for (k in 1:nStop) { drawnball <- sample(0:1,size=1,prob=c(nRed,nGreen)/(nRed+nGreen)) nRed <- nRed+(1-drawnball) # drawnball=0 if red, 1 if green nGreen <- nGreen+drawnball } propRed[n] <- nRed/(nRed+nGreen) } hist(propRed) Exercise 1 Conjecture what the distribution of Mn is in general, based on the simulation results. Exercise 2 Prove using induction on n that 1 k = for k = 1, 2, . . . , n + 1. P Mn = n+2 n+1 That is, the distribution is uniform. Hint: as we often do with Markov chain calculations, look one step back in time at the possible previous values. 3 Another simulation of Polya’s urn Exercise 3 Revise the simulation code to run 100 simulations that each do 1,998 draws (so total of 2,000 balls when done). Store the proportion of red balls after 998 draws and also after 1,998 draws. How do these numbers compare for each simulation? Plot M1998 versus M998 from the 100 simulations. What is happening?

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock