Section 10 - Markov Models

Section 10 - Markov Models

States -
Transition Probabilities - chances of moving one state to another

Ex: Students who are Alert or Bored
There are some probabilities that student would transfer to the others

Simple Markov Model

Use student example above with
20% of alert students become bored
25% of bored students become alert

Assume 100 alert and 0 bored  ==> 20 become bored, 80 stay alert
equilibrium is difficult to calculate

Use a Markov Transition Matrices as follows:

After a number of period it reaches at equilibrium @ ~58%

 

Now we want to calculate what the values at equilbrium more directly.  Here is what the calculation looks like.  (NOTE - the step in the middle he is just multiplying everything by 20)

 

 

  so P = 5/9 = 55.6%

 

Markov Model of Democritization

Initial Example
Assume democracies and dictatorships, where 5% of democracies becomes dictatorships, and 20% of dictatorships become democracies.

 

Model Involves Countries
Free, Not Free, Partly Free
Rules: 5% of free and 15% of not free become partly free, 5% of not free and 10% of partly become free, 10% of partly free become not free.  Leaving the follow matrix

 

Markov Convergence Theorem

Tells us that, if the transition probabilities stay fixed, the systems will lead us to an equilibrium

Four assumptions of Markov Processes

1.  Finite Number of States
2.  Fixed transition probabilities
3.  You can eventually get from any state to any other
4.  Not a simple cycle

Given 1 - 4 the process will converge

• this says the initial state doesn't matter
• History doesn't matter either
• Intervening to change the state doesn't matter in the long run

Interventions may be helpful as it may take a long time to get back to equilibrium

Why would transitions probabilities need to stay fixed?  Our interventions need to affect the transition properties in the right direction.

Exapting the Markov Model

Section 9 - Diversity and Innovation

Problem Solving and Innovation

Use Landscape to begin to get to the best value (hills and valleys)

Perspectives and Innovation

Perspective - how you represent a problem, to be able to encode it

Perspective - representation of all possible solutions, with encoding, by applying values, we get the landscape

Rugged Landscape - many peaks and valleys
Local Optima - peaks within the landscape
Mt Fuji - A landscape with one peak

Good Perspective - few local optima,

Shovel Size Landscape - by Taylor

Sum-to-Fifteen - Herb Simon
-  Cards 1-9 face up on the table
-  Player alternate selecting cards
- Win if you get to exactly 15

Magic Square - all rows add up to 15, all columns add up to 15 and all diagonals add up to 15

Savant Existence Theorem - for any problem there exists a Mt Fuji Landscape

Heuristics

Heuristics - how you move on the landscape (hill climbing, random search, etc)

Hill climb to get to local optima

Heuristic 1 - Do the Opposite - think about the current solution and do just the opposite
Heuristic 2 - Big Rocks First - Do important things first
Heuristic 3 - No Free Lunch (Wolpert  & McCready) - Algorithms that search the same number of points  with the goal of locating the maximum value of a function defined on a finite set perform exactly  the same when averages over  all possible functions
                  -  If you don't know if your perspective, no algorithm or heuristic performs better than any other.

Diverse heuristics provide better solutions

Teams and Problem Solving

Groups of people are better at solving problems - based on diversity of thought

Using Caloric Perspective
A = 10
B = 8
C = 6

Average = 8

Using the Masticity Perspective
A=10
B= 8
D =6
E = 4
F = 2

Average = 6

If they work as a team, then if they the person on Caloric finds C, then the person doing Masticity will not get stuck.  In this case the only place the team can get caught is A & B.

Claim: The team can only get stuck on solution that's a local optimum for every  member of the team.

So we want people with different perspectives and different heuristics

Assumptions
1) when you have a team, they are assumed to be able to communicate
2) There is some ability to recognize an error in our solution.  I propose something and people may actually not see the value.

Recombination

Recombination - take solutions from multiple problems, bring them together to recombine them to better and better solutions 

Innovation comes from recombination of many solutions.

How many ways to pick 3 objects from 10?

10 things to pick 1st, 9 to pick second, 8 to pick 3rd, .....

divided by 3 chances for 1st pick, 2 chances for 2nd, and 1 for third.

leaving 120 ways

Picking 20 cards from a deck ==> 52 x 51 x 50 x 49... / 20 x 19 x 18 x ...... leaving 125 trillion possibilities

Martin Weitzman - Recombinant Growth - whereby things continuously get recombined new growth. 

Ex: car - steering wheel, wheels, brakes, etc coming together to make a car.

Exaptation - some innovation comes up for one reason, but then gets applied to another.

Joel Mokyr - Gifts of Athena - how ideas are transferred from one location to another and between people.

Section 8 - Economic Growth

Exponential Growth

GDP -

X - dollars
r - % interest

X*(1+r) where interest is eventuall X*(1+r)^t (years)

Rule of 72 - Divide the growth rate into 72.  The answer gives you how many years to Double.

Continuous Compounding
If you show growth in infinitesimally small  time frames, the growth rate is:
        =  e^(rt)

Simple Growth Model

Economy
-  Workers
-  Coconuts
-  Machines
-  Machines wear out

Solow Growth Model

Bob Solow - Economist w/ MIT

Add A(t) which is innnovation

O(t) = A(t)K(t)^b*L(t)^*(1-b)

This will allow productivity to double

Will China continue to Grow?

The required Innovation to maintain 8-9% growth rates have never been seen.

So Chinas growth will be driven to show innovation and will likely only see 1-5%.

Why do some countries not Grow?

Botswana did well, while Zimbabwe didn't do so grow

- Strong government control is required to protect equpiment, etc.
- Too strong a central government (1-2 people), they will extract resources, which will reduce investment and lower incentive to improve.

Growth requires some Creative Destruction - old equipment isn't required as it is replaced by new.

Fertility
- Can't apply to trees or people.
- We can apply it to our own GDP.  If we don't innovate, we will slow our own growth.

Section 7 - Tipping Point

Tipping Points

Tipping points are different from Exponential Growth

Percolation Models

Does water percolate through soil
P - Probability of percolating
If P<59.2 then no percolation

Forest Fires

Percolating Banks
- Models failing banks - Generally you add more details for the banks, like assets, liabilities, etc.

Information Percolating
- If I pass a piece of information will it pass through to everyone

Works well for networks

Can work for technology

Contagion Models

SIS - Susceptible - Infected - Susceptible
Diffusion Model - uses a Transmission Rate - tau

what if 2 people meet
W = number of people  with Disease
(N-W) = number of people w/out Disease

tau(W/N)((N-W)/N) = probability of two people meeting and it spreading

Add the contact rate: c

multiple above by N*C

When W is small you get
When W = N/2

This is not Tipping, this is natural diffusion

SIS Model

Now once they get over the disease, they can get infected again

Just add a new factor to the end of the equation

     For SIS, we have added the -aW component which are cured people who can get infected again.
which can be simplified to:

     so for small Wt, then if ct>a, then disease moves on.  If ct<a the disease will not spread.

now call R(0) = ct/a,  if >1, then it spreads, if <1, then not  (R(0) is the basic reproduction number)

Classifying Tipping Points

Dynamical System

  In this graphi, there are 2 stable points, but the one labeled U is unstable and any small movement will push it one way or the other.

 

He will call this a "DIRECT TIP" - Small action or event has a large effect on the long run.

 

Contextual Tipping Points
- Where the environment changes forcing to a new class



Between/Within Class
Changing between classes

Measuring Tips

Utilize change in the likelihood of outcomes

Diversity Index - Social Science
-  Amount of Information
is based upon how different the outcomes are between the classes.

Diversity = Summation(1/Summation(P^2))


Entropy - from physics
-  Number of types
Entropy = - summation(P*log(2) (P))