Friday, December 23, 2011

computational Economics lecture 6


Loops

Computers are good at repetitive tasks
Loops are the most common way to implement them

For loops

Let's start with for loops
Consider the following program
X = [10, 20, 30]
for x in X:
    print "The value of x is", x
    print "The square of x is", x * x
    print "---------------------"
print "The loop is complete."
What happens when we run it?
  • At the start, x is bound to the first element of X
    • And the code block (i.e., three indented lines) is executed with x = 10
  • Next x is bound to the second element, which is 20
    • And the code block is executed with x = 20
  • Finally, x is bound to the last element, which is 30
    • And the code block is executed with x = 30
The loop is now finished, and control passes to the line after code block
The output is as follows
The value of x is 10
The square of x is 100
---------------------
The value of x is 20
The square of x is 400
---------------------
The value of x is 30
The square of x is 900
---------------------
The loop is complete.
The loop works the same way with tuples
X = 10, 20, 30   # Or, X = (10, 20, 30)
for x in X:
    # Do something
In fact a for loop can step through any sequence:
for letter in 'foo':
    print letter
So the general syntax is
for <name> in <sequence>:
    <code block>
In fact "sequence" should be replaced by "iterator", but more on that later.

Indentation

Getting the indentation right is critical
What happens when you run this?
X = 10, 20, 30   # Or, X = (10, 20, 30)
for x in X:
    print "The value of x is", x
   print "The square of x is", x * x
    print "---------------------"
print "The loop is complete."
Or this
X = 10, 20, 30   # Or, X = (10, 20, 30)
for x in X:
   print "The value of x is", x
    print "The square of x is", x * x
    print "---------------------"
print "The loop is complete."
What happens when we run this?
X = 10, 20, 30   # Or, X = (10, 20, 30)
for x in X:
    print "The value of x is", x
    print "The square of x is", x * x
    print "---------------------"
    print "The loop is complete."
Or this?
X = 10, 20, 30   # Or, X = (10, 20, 30)
for x in X:
    print "The value of x is", x
    print "The square of x is", x * x
print "---------------------"
print "The loop is complete."

Examples

Example 1:
>>> ord('a')   # Get ASCII code of character a
97
>>> chr(97)    # Get character from ASCII code
'a'
What does the next loop do?
  • Hint: ord('a') - 32 is equal to ord('A')
string = 'godzilla'
newstring = ''              # The empty string
for character in string:
    ascii_value = ord(character)
    cap_ascii_value = ascii_value - 32
    newstring = newstring + chr(cap_ascii_value)
print newstring
Example 2: Nested for loops
Suppose we have a matrix represented by
X = [[2.4, 7.0, 1.1],
     [3.3, 0.1, 4.2],
     [3.6, 0.0, 1.9]] 
To multiply each element by 5,
for i in range(3):
    for j in range(3):
        X[i][j] = 5 * X[i][j]
(As we'll see later, there are matrix libraries that handle this better)

Exercises

Problem 1:
  • Get n from user and compute n! with a for loop
  • Recall that n! = n * (n - 1) * ... * 2 * 1
Problem 2: (Redo an earlier exercise using a for loop)
  • Simulate a draw from Y ~ Bin(n, p) using uniform rvs.
    • num of successes in n indep trials with success prob p
    • Get n and p from the user
Problem 3:
  • Compute an approximation to pi using Monte Carlo
    • Note that if U is uniform on the unit square, then the probability U is in a subset B is equal to the area of B
    • And that if U_1,...,U_n are IID copies of U, then the fraction in B converges to the probability of B as n gets large
    • Finally, recall that for a circle, area = pi * radius^2
Problem 4:
  • Write a program which prints one random outcome of following game
    • 10 flips of an unbiased coin
    • If 3 consecutive heads occur, pays one dollar
    • If not, pays nothing
Problem 5:
  • Use Monte Carlo to estimate average payoff of previous game

Solutions

Solution to Problem 1:
n = int(raw_input("Enter the value of n: "))
factorial = 1                    # Starting value
for i in range(1, n + 1):        # Integers 1,...,n
    factorial = factorial * i    # Or, factorial *= i
print factorial
Solution to Problem 2:
from random import uniform

n = int(raw_input("Choose n: "))
p = float(raw_input("Choose p: "))
count = 0
for i in range(n):
    U = uniform(0, 1)
    if U < p:
        count = count + 1    # Or count += 1
print count
Solution to Problem 3:
## Filename: circle.py
## Author: John Stachurski

# Since pi = area / radius**2, we need to estimate the area of the circle
# and then divide by radius**2 = (1/2)**2 = 1/4.  First we estimate the area
# by sampling bivariate uniforms and looking at the fraction that fall into
# the circle.

from random import uniform
from math import sqrt

n = 100000

count = 0
for i in range(n):
    U, V = uniform(0, 1), uniform(0, 1)
    d = sqrt((U - 0.5)**2 + (V - 0.5)**2)
    if d < 0.5:
        count += 1

area_estimate = count / float(n)

print area_estimate * 4  # dividing by radius**2
Solution to Problem 4:
## Filename: 3heads.py
## Author: John Stachurski

from random import uniform

payoff = 0
count = 0

for i in range(10):
    U = uniform(0, 1)
    count = count + 1 if U < 0.5 else 0
    if count == 3:
        payoff = 1

print payoff
Solution to Problem 5:
## Filename: 3heads2.py
## Author: John Stachurski

from random import uniform

n = 100000

outcomes = []
for i in range(n):
    payoff = 0
    count = 0
    for j in range(10):
        U = uniform(0, 1)
        count = count + 1 if U < 0.5 else 0
        if count == 3:
            payoff = 1
    outcomes.append(payoff)

print sum(outcomes) / float(n)

The Break Statement

Notice an inefficiency in our solution to Problems 4 and 5:
In each round of the game, we may not need to flip 10 times
  • If 3 consecutive heads occur, then we can stop
We can terminate a loop at any time using the break keyword
Example:
for i in range(10):
    print i
    if i == 5:
        break
Thus, an improved version of the solution to Problem 5 is
## Filename: 3heads3.py
## Author: John Stachurski

from random import uniform

n = 100000

outcomes = []
for i in range(n):
    payoff = 0
    count = 0
    for j in range(10):
        U = uniform(0, 1)
        count = count + 1 if U < 0.5 else 0
        if count == 3:
            payoff = 1
            break
    outcomes.append(payoff)

print sum(outcomes) / float(n)
Note that we break out of the inner loop, not the outer loop

While loop

The syntax of the while loop is
while <expression>:
    <code block>
Flow is as follows
  1. Test whether expression is true (i.e., bool(expression) == True)
  2. If true, then
    • execute code block
    • go to step 1
  3. If not, then
    • finish: control goes to line after code block
Example: What will this print?
i = 0
while i < 10:
    print i
    i += 1  # Or i = i + 1
What happens here?
string = 'godzilla'
while string:
    letter = string[0]
    print letter,   # Trailing comma: print without newline
    string = string[1:]

Problems

Problem 1:
  • Compute n! using a while loop
    • Get n from the user
Problem 2:
  • Get numbers from user and print average
    • Keep prompting for a new number
    • Stop when user presses Enter (without number)
Problem 3:
  • A Monte Carlo study of random walks
    • X starts at zero and increments by 1 or -1 with 0.5 prob
    • Runs until either X = A or X = -B, where AB > 0
    • The probability of the first case (i.e., X = A) is known to be B / (A + B)
    • Verify this using Monte Carlo
      • Pick any values for A and B (e.g., A, B = 2, 12)
      • Draw a large number of such time series
      • What fraction of these series hit A first?

Solutions

Solution to Problem 1:
n = int(raw_input("Enter the value of n: "))
factorial = 1
while n > 0:
    factorial *= n   # factorial = factorial * n
    n -= 1           # n = n - 1
print factorial
Solution to Problem 2:
numbers = []
n = raw_input("Enter a number (Return to finish): ")
while n:
    numbers.append(float(n))
    n = raw_input("Enter a number (Return to finish): ")

print sum(numbers) / float(len(numbers))
Here is another solution:
numbers = []
while 1:
    n = raw_input("Enter a number (Return to finish): ")
    if not n:
        break
    numbers.append(float(n))

print sum(numbers) / float(len(numbers))
Even better:
numbers = []
while 1:
    n = raw_input("Enter a number (Return to finish): ")
    if not n:
        break
    numbers.append(float(n))

if numbers:
    print sum(numbers) / float(len(numbers))
else:
    print "You didn't enter any numbers"
Solution to Problem 3:
## Filename: randomwalk.py
## Author: John Stachurski

from random import choice

n = 10000
A, B = 2, 12
choices = 1, -1
count = 0

for i in range(n):
    X = 0
    while 1:
        X = X + choice(choices)
        if X == A:
            count += 1
            break
        if X == -B:
            break

print count / float(n)
print B / float(A + B)

0 comments: