Transcript CS1512

CS1512
Foundations of
Computing Science 2
Lecture 22
Digital Simulations
Probability and statistics (3)
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
© J R W Hunter, 2006
1
Simulations
Programs regularly used to simulate real-world activities.
• city traffic
• the weather
• nuclear processes
• stock market fluctuations
• environmental changes
• shipping movements in the Straits of Dover!
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
2
Simulations
Simulations are normally only partial and involve simplification.
Greater detail has the potential to provide greater accuracy.
Greater detail typically requires more resource:
• Processing power.
• Simulation time.
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
3
Benefits of simulations
Support useful prediction.
• e.g. the weather
Allow experimentation.
• Safer, cheaper, quicker.
Example:
• ‘How will the wildlife be affected if we
cut a highway through the middle of
this national park?’
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
4
Basic Algorithm
set up a number of objects to represent the world that you are trying to model
add the objects to a collection maintained by the simulation
set the simulation time to zero
while the simulation time isn’t up
for each object
•
call the method that executes the behaviour of the object during
the simulation time step
•
do any necessary output
increment the simulation time by the time increment
wait for an amount of real time corresponding to the time
increment
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
5
ChanSim:
Main simulation loop
public void simulate(int timeStep, int speedUp) {
while (time < totalSimulationTime) {
for (int i = vessels.size()-1; i >= 0; i--){
Vessel vessel = (Vessel) vessels.get(i);
if (vessel.onChart())
vessel.erase(chart);
vessel.move(timeStep);
if (vessel.onChart())
vessel.draw(chart);
}
chart.update();
time = time + timeStep;
wait(timeStep*60*1000/speedUp);
//*60*1000 to convert minutes to msec
}
}
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
6
Vessel: move
/**
* Determine where the vessel will be after timeStep
*/
public void move (int timeStep)
{
// distance travelled in km per time step (in minutes)
double delta = speed*timeStep/60;
location = new Location(location.getx()+
Math.sin(bearing)*delta,
location.gety()Math.cos(bearing)*delta);
}
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
7
Probability
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
8
Initial thoughts
A person tosses a coin five times. Each time it comes down heads. What is the
probability that it will come down heads on the sixth toss?
½ or ‘1 chance in 2’ or 50%
• assumed that the coin is ‘fair’
• ignored empirical evidence of the first five tosses
less than ½ or ...
• assumed that the coin is ‘fair’
• thought about ‘law of averages’ – in the long run, half heads, half tails
• possibly confused about the question - which was not
“What is the probability that there will be six heads in a row?”
more than ½ or ...
•
cynical – assumed two headed (or biased) coin
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
9
Definition
Probability: the extent to which an event is likely to occur, measured by the ratio
of the number of favourable outcomes to the total number of possible outcomes.
• close eyes
• shake bag
• put in hand and
pick a ball
• 10 possible balls
(outcomes)
10 balls in a bag
7 white; 3 red
Can you think of any reason why any one ball
should be picked rather than any other?
If not, then all outcomes are equally likely.
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
10
Definitions
Probability of picking a red ball
• favourable outcome = red ball
• number of favourable outcomes = 3
• number of outcomes = 10
• probability = 3/10 (i.e. 0.3)
Note:
• probability of picking a white ball is 7/10 (0.7)
• probabilities lie between 0.0 and 1.0
• we have two mutually exclusive outcomes
(can’t be both red and white)
• outcomes are exhaustive (no other colour there)
• in this case the probabilities add to 1.0 (0.3 + 0.7)
• a probability is a prediction
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
11
More definitions
Trial
• action which results in one of several possible outcomes;
• e.g. picking a ball from the bag
Experiment
• a series of trials (or perhaps just one)
• e.g. picking a ball from the bag twenty times
Event
• a set of outcomes with something in common
• e.g. a red ball
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
12
Probability derived a priori
Suppose each trial in an experiment can result in one (and only
one) of n equally likely (as judged by thinking about it)
outcomes, r of which correspond to an event E.
The probability of event E is:
r
P(E) = ―
n
a priori means “without investigation or sensory experience”
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
13
More complex a priori probabilities
Probability of throwing 8 with two dice:
1
2
3
4
5
6
1
2
3
4
5
6
7
2
3
4
5
6
7
8
3
4
5
6
7
8
9
4
5
6
7
8
9
10
5
6
7
8
9
10
11
6
7
8
9
10
11
12
• 5 outcomes correspond to event “throwing 8 with two dice”
• 36 possible outcomes
• probability = 5/36
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
14
Probability derived from experiment
Toss a drawing pin in the air - two possible outcomes:
• point up
• point down
Can we say a priori what the relative likelihoods are? (c.f. ‘fair’ coin)
If not, then experiment.
Probability based on relative frequencies (from experimental data)
If, in a large number of trials (n), r of these result in an event E, the
probability of event E is:
r
P(E) = ―
n
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
15
Probability as a relative frequency
• number of trials must be ‘large’ (how large?)
• trials must be ‘independent’ - the outcome of any one
toss must not depend on any previous toss
• no guarantee that the value of r/n will settle down
• compare with the relative frequencies for existing data
• if we have enough experiments then we believe that the
relative frequency contains a general ‘truth’ about the
system we are observing.
www.csd.abdn.ac.uk/~jhunter/teaching/CS1512/lectures/
16