Hypomnemata

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 17: Among the entrants to a jousting tournament, there are two twins: Balan and Balin. If there are 8 knights total, all equally matched, and the initial ladder is randomly assigned, what’s the probability of the twins jousting against each other?

#!/usr/bin/env ruby

TRIALS=100000

# Array of Knighs: BalIn and BalAn, and some schmucks.
KNIGHTS=["I","A","X","X","X","X","X","X"]

# The knights are equally matched, so we need to randomize
# the selection of who wins each round.  Otherwise, this is
# very similar to problem16.rb.

# We're going to abuse the weak typing of ruby here.  Don't
# do this for real.
#
# Returns an array if we just continue on, returns nil if the
# brothers meet.
#
def round(seedings)
  next_round = []

  # Walk the seedings pairwise, looking for "A" and "I"
  # Note that order doesn't matter.

  i = 0
  while (i < seedings.length())
    return nil if (["A","I"] & seedings[i..i+1]).length == 2 # rubylicious.
    next_round.push( seedings[i + rand(2)] )
    i += 2
  end
  return next_round
end

def tourney()
  first_round = KNIGHTS.shuffle
  quarters = round(first_round)
  return true if !quarters

  semi = round(quarters)
  return true if !semi

  final = round(semi)
  return true if !final

  return false # tourney over
end

srand() # Our first call to shuffle is before our
        # first call to rand()...

n_match=0
TRIALS.times do
  n_match += 1 if tourney()
end

puts "In #{TRIALS} trials, the brothers met #{n_match} times."
puts "P=#{n_match/TRIALS.to_f}"

I’ve been coding my way through Fifty Challenging Problems in Probabilities with Solutions. This post is a part of the Fifty Challenging Problems series. Read all of the Fifty Problems posts by clicking here.

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 10: An urn drawing game: an urn contains 10 black and 10 white balls. You call “black” or “white,” and a ball is drawn. If it matches your call, you win $10. a) What’s the most you will pay to play? b) Change the game such that the black/white mix is unknown to you. What would you pay if you were only allowed to play the game one time?

#!/usr/bin/env ruby

TRIALS=10000

# For the fair game, we can just try it a bunch of times.
# The game is symmetric about color choice, so we can
# ignore the details and just use the 50/50 odds.

wins = 0

TRIALS.times do
	wins +=1 if (rand() < 0.5)
end

payout = 10.0 * wins

puts "Out of #{TRIALS} fair plays, we won #{wins}, $#{payout}."
puts "Therefore, the maximum amount to pay would be "
puts "  $#{payout/TRIALS.to_f}"

# Now, for the weird game.  Your friend can vary the
# ratio of balls in the urn, so we need to try a lot
#of games at different probabilities.  We can do this
# stratified or randomly.  Let's do randomly first.

wins = 0
TRIALS.times do
	wins +=1 if (rand() < rand())
end
payout = 10.0 * wins

puts "Out of #{TRIALS} randomized friend-chosen plays"
puts " we won #{wins}, $#{payout}.  Therefore, the "
puts " maximum amount to pay would be "
puts "$#{payout/TRIALS.to_f}"

# And now stratified, to see if it makes any difference

wins = 0
TRIALS.times do |i|
	wins +=1 if (rand() < i.to_f/TRIALS.to_f)
end
payout = 10.0 * wins

puts "Out of #{TRIALS} stratified friend-chosen plays,"
puts " we won #{wins}, $#{payout}.  Therefore, the "
puts " maximum amount to pay would be "
puts " $#{payout/TRIALS.to_f}"

I’ve been coding my way through Fifty Challenging Problems in Probabilities with Solutions. This post is a part of the Fifty Challenging Problems series. Read all of the Fifty Problems posts by clicking here.

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 9: What are the odds of winning in Craps (using only Pass Line bets)?

#!/usr/bin/env ruby

# Modelling craps is weird.
# We roll two dice and sum them.
#
# if they're 7 or 11 => immediate win
#            2,3,12 => lose
# else, roll is the "point"
#       player keeps rolling until:
#         point => win
#             7 => lose
#
# So, what's the chance to win?

TRIALS=500000

def roll
	d1 = 1 + rand(6)
	d2 = 1 + rand(6)
	return d1+d2
end

def win()
	first_roll = roll()
	return true if (first_roll == 7 || first_roll == 11)
	return false if ([2,3,12].include?(first_roll))

	point = first_roll
	while (true) do
		next_roll = roll()
		return false if 7 == next_roll
		return true if next_roll == point
	end
end

wins = 0

TRIALS.times do
	wins += 1 if win()
end

puts "After #{TRIALS} games, won #{wins}"
puts "P(win) = #{wins.to_f/TRIALS.to_f}"

I’ve been coding my way through Fifty Challenging Problems in Probabilities with Solutions. This post is a part of the Fifty Challenging Problems series. Read all of the Fifty Problems posts by clicking here.

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 8: What is the chance of being dealt a perfect hand in bridge? (being dealt 13 cards of the same suit?)

This is one place where Monte Carlo falls flat on its face. Modeling this in any sort of reasonably simple (read: naive) fashion results in a program that takes quite some time to run. It’s far better to find the probability through direct combinatorial calculations. This still poses some interesting programming problems, but they’re of the numerical sort, so they won’t appear in this series. (It would be really great if someone would post a comment linking to a solution of this problem using hadoop on EC2 or EMR!)

#!/usr/bin/env ruby

TRIALS=100

# We model this by laying out the 52 cards in an
# array, calling the spades 1..13.
#
# Then, we "deal" by breaking it up into contiguous
# 13-card chunks.  If any the 4 chunks of 13 are
# 1..13, we win the "deal a perfect hand" game.
# Otherwise, we lose.

perfect_hands = 0

# I had some concerns about the performance here.
def perfect_hand_by_sort?(a)
	ap = a.sort
	return 12 == ap[12]-ap[0]
end

def perfect_hand_by_scan?(a, handno)
	x = (handno-1)*13
	min = 0
	max = 53
	while (x < (handno)*13)
		ai = a[x]
		min = ai if ai < min
		max = ai if ai > max
		x += 1
	end

	return 12 == max-min
end

def perfect_hand_by_minmax?(a, handno)
	x = (handno-1)*13
	min = a[x..x+12].min
	max = a[x..x+12].max

	return 12 == max-min
end

t_by_sort = 0.0
t_by_scan = 0.0
t_by_minmax = 0.0

TRIALS.times do
	cards = (1..52).to_a
	cards.shuffle!

	t0 = Time.now
	hand1 = cards[0..12]
	hand2 = cards[13..25]
	hand3 = cards[26..38]
	hand4 = cards[39..51]

	p_sort = 0
	[hand1, hand2, hand3, hand4].each { |hand|
		p_sort += 1 if perfect_hand_by_sort?(hand)
	}
	dt_sort = Time.now - t0
	t_by_sort += dt_sort

	p_scan = 0
	t0 = Time.now
	[1,2,3,4].each { |handno|
		p_scan += 1 if perfect_hand_by_scan?(cards, handno)
	}
	dt_scan = Time.now - t0
	t_by_scan += dt_scan

	p_minmax = 0
	t0 = Time.now
	[1,2,3,4].each { |handno|
		p_minmax += 1 if perfect_hand_by_minmax?(cards, handno)
	}
	dt_minmax = Time.now - t0
	t_by_minmax += dt_minmax

	perfect_hands += p_sort
end

puts "After #{TRIALS} trials, we got #{perfect_hands}"

puts "Times: "
puts " sort: #{t_by_sort}"
puts " scan: #{t_by_scan}"
puts " minmax: #{t_by_minmax}"

I’ve been coding my way through Fifty Challenging Problems in Probabilities with Solutions. This post is a part of the Fifty Challenging Problems series. Read all of the Fifty Problems posts by clicking here.

(This is another part of the Fifty Problems series, a set of example applications of Monte Carlo methods. In each post, I present source code which answers a probabilistic question using simulated models of the underlying system.)

Problem 7: Mr Brown has a problem: he compulsively puts a dollar on number 13 in American roulette. To help him see the error of his ways, Mr Pink gives him a bet: Pink bets Brown $20 if, after 36 rounds of roulette, Brown is ahead. (That is: if Brown is up after 36 compulsive rounds, he gets an extra $20; if he’s behind, he loses an extra $20.)

#!/usr/bin/env ruby

# We'll play from Mr Brown's perspective.
#
# Modelling this game is tricky.  We need to play 36
# rounds of roulette, then see if we're up.  If so,
# we get an extra $20; if not, we lose $20.  At the
# end, we want the expected payout per unit stake.

TRIALS=10000

def payout()
	p = 0
	36.times do
		p += 36 if ( rand() < 1/38.to_f)
	end
	if p > 26
		p += 20
	else
		p -= 20
	end

	# puts "This round: $36 in, $#{p} out\n"
	p
end

total_payout = 0
total_bet = 0

TRIALS.times {
	total_payout += payout()
	total_bet += 36
}

puts "After #{TRIALS} rounds of betting, we bet #{total_bet}"
puts "We won #{total_payout}, so the expected loss is "
puts "  $#{(total_bet-total_payout)/total_bet.to_f}"

I’ve been coding my way through Fifty Challenging Problems in Probabilities with Solutions. This post is a part of the Fifty Challenging Problems series. Read all of the Fifty Problems posts by clicking here.