Homework I

Due in stages

Goals of this Assignment:

• start to become familiar with general simulation programming and DES
• become familiar with Python programming

Problem A (due Wednesday, January 16):

We are looking for a parking place on a long street, proceeding according to the following plan:

• Our destination is at location 0, and we start far to the left, at "-∞."
• As we are heading toward 0, our strategy will be to not take any space that we see until we get to space -c.
• Starting at -c, we take the first empty space we find (including past 0, if it takes that long).
• We cannot see ahead more than one space. (Hey, you never know, there may be a motorcycle parked in what initially seems to be an empty space.)

Each space is empty with probability p, and occupied with probability 1-p.

Write a Python simulation program to find E(D), the mean value of the distance D from the place we park to our destination 0. For each of several values of p of your choice, find the optimal c, reporting the results in a README file.

Here are some sample answers. In order to try a lot of values of c, I wrote a shell script. (Or I could have written another Python script which called my program.)

localhost:~/156% foreach c ( 6 5 4 3 2 1 0 )
foreach? python ParkingPlace.py $c 0.4 10000
foreach? end
mean distance is 4.6576
mean distance is 3.7464
mean distance is 2.898
mean distance is 2.1522
mean distance is 1.5836
mean distance is 1.2972
mean distance is 1.4886
localhost:~/156%
localhost:~/156%
localhost:~/156% foreach c ( 12 11 10 9 8 7 6 5 4 3 2 1 0 )
foreach?  python ParkingPlace.py $c 0.1 10000
foreach? end
mean distance is 8.0974
mean distance is 7.661
mean distance is 7.2868
mean distance is 6.9822
mean distance is 6.762
mean distance is 6.6244
mean distance is 6.5858
mean distance is 6.6548
mean distance is 6.8416
mean distance is 7.1546
mean distance is 7.615
mean distance is 8.2364
mean distance is 9.0366

Looks like, for instance, that with p = 0.1, the best c is 6. (I should have had better output labels.)

Problem B (due Friday, January 18):

This problem models a voting process similar to that of the recent Iowa caucuses. It's quite a simplified model, but good enough for our early learning purposes. Here's how it works:

• In a given round, each voter chooses a candidate at random, weighted according to the votes of the previous round. For instance, if in the last round the votes were 4, 3 and 2, each voter will choose from the three candidates with probability 4/9, 1/3 and 2/9.
• No one is eliminated in any round.
• The voting process goes through rounds, until some candidate gets the majority (not the plurality) of the votes.

Command-line usage will be:

% python Iowa.py initial_votes nrepetitions

where initial_votes is in descending numerical order

Your program will find the following quantities:

• P(top initial candidate wins); in the example above, with 4, 3 and 2 votes initially, we are interested in the probability that the one who originally has 4 votes wins (assume no initial tie for tops)
• E(number of rounds)

Here are some sample runs:

localhost:~/156% python Iowa.py 10 8 4 10000
P(init. top wins) = 0.5938
E(number of rounds) = 4.0092
localhost:~/156% python Iowa.py 12 6 4 10000
P(init. top wins) = 0.8235
E(number of rounds) = 3.2346

Problem C (due Wednesday, January 30):

Here you will write a SimPy program to simulate a cell phone network, as follows:

• Usage:

  python Cell.py HRate DrvTime LRate LDurRate NChn NRsrvd MaxSimTime
  

  where

  • HRate = rate of arrivals of handoff calls (reciprocal of mean time between arrivals)
  • DrvTime = drive-through time for the cell
  • LRate = rate of creations of local calls (reciprocal of mean time between creations)
  • LDurRate = reciprocal of mean duration of local calls
  • NChn = number of channels
  • NRsrvd = number of channels reserved for handoff calls
  • MaxSimtime = amount of time to simulate

• We are simulating one cell.
• A major highway runs through the cell, so calls in progress enter the cell at random times. The action of a call being transferred from one cell to another is called handoff.
• Handoff calls stay active for a constant time, the time it takes to drive through the cell. (In this simpler model, we assume that the call lasts the entire time the car is in the cell. There is a nice SimPy feature we can use later when we drop this assumption. We also assume that cars entering the cell without calls in progress don't start one in the cell.
• Calls also originate at random times from local people, who stay in the cell. Local calls last a random time.
• Each call uses a separate channel (frequency or time slot). Handoff calls have priority over local calls. Specifically, among whatever idle channels available at a given time, NRsrvd of them will be reserved for handoff calls that might come in. If we have more than that many idle channels, the excess are available for local calls.
  Say for example that NChn is 8 and NRsrvd is 3. If we currently have 3 or fewer idle channels, then any local call will be rejected. If we have more than 3 idle channels, then a local call will be accepted (and the number of idle channels will be reduced by 1).
• A rejected call is dropped, not queued.
• Times between handoff arrivals, times between creation of local calls, and local call durations are assumed to be exponentially distributed with the given means.

Your program will find the following quantities:

• The proportion of handoff calls that are rejected.
• The proportion of local calls that are rejected.
• The mean duration of periods during which no new local calls are allowed.

Here are some sample output values:

localhost:~/156% python Cell.py 2 0.5 2 2 3 1 1000000
percentage of rejected handoff calls: 0.123501763512
percentage of rejected local calls: 0.46789498383
mean banned period for locals 0.333385839636

localhost:~/156% python Cell.py 2 0.5 2 2 7 2 1000000
percentage of rejected handoff calls: 0.00110584029391
percentage of rejected local calls: 0.044118073593
mean banned period for locals 0.122240141744

localhost:~/156% python Cell.py 1 0.5 2 2 7 2 1000000
percentage of rejected handoff calls: 0.000100849431798
percentage of rejected local calls: 0.0158323129654
mean banned period for locals 0.111255902476

localhost:~/156% python Cell.py 1 0.5 2 2 7 2 1000000
percentage of rejected handoff calls: 0.000100849431798
percentage of rejected local calls: 0.0158323129654
mean banned period for locals 0.111255902476

localhost:~/156% python Cell.py 1 1 2 1 7 2 1000000
percentage of rejected handoff calls: 0.00345660940314
percentage of rejected local calls: 0.130168942564
mean banned period for locals 0.245352553346