test.py

import random
count = 0.0
for i in range(10000):
  state = 0
	while True:
		count += 1
		if state == 1:
			break
		r = random.random()
		if state == 0:
			if  r < 0.5:
				state = 0
				continue
			if r < 0.75:
				state = 1
				continue
			if r <= 1:
				state = 2
				continue
		else:
			if r < 0.5:
				state = 1
				continue
			else:
				state = 2
				continue 
				
count /= 10000.0

print "%f" % count