Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Solving graphs with probabilities associated with edges. | Reply
Problem
You are given a graph with n nodes (states) and the edges between them have probabilities associated with it. You are initially in state "start" and asked to calculate the probability/expectation of a "end" state

Solution

1) Build state graph (states as nodes and transitions as edges) from the description of problem statement. Identify the start states and end states.

2)

A) If the graph is a DAG (Directed Acyclic Graph) use Dynamic Programming to calculate the probability of values associated with required state.

B) If the graph is not a DAG and has cycles, build a set of equations describing the state transitions and use Gaussian Elimination to solve for the probability/expectation

Another approach is simulation.
If desired accuracy of result is less for eg 1e-6 or so, simulate above transitions large number of times. The values should converge to actual values. This will work only if desired accuracy of result is less. For most accurate answer use Equation solving.

Description

Example 1 (Using Gaussian Elimination / Simulation)
A manufacturer of a Chutes And Ladders game (also called Snakes and Ladders) wants to know what is the expected number of dice throws (6 sided ) to finish the game by a single person. If expected value is high user will get bored as it takes lot of time to finish. If it is less user will finish game quickly and lose interest. The board is given in input as an array t[] which denotes where a player will end if he reaches the cell i. If there is no chute or ladder at cell i, then t[i] = i , else it will be the cell where chute or ladder points to.
Note : Here we are not looking at game as 2 player, but trying to evaluate how much time a single user will take to finish.

- States - Position of player position 0 .. n-1 where n is number of cells. Start state is 0 and end state is >= n-1 ( when user goes beyond last cell it is considered a finish)
Transitions - Dice throw probability = p = 1/6. Additionally with the presence of chutes and ladders, user will move to other cells.

- This graph has cycles as based on chutes and ladders user can go back to previous cells. So build a set of equations and solve , say using Gaussian elimination

- Let e[i] be expected number of throws to finish game from state i.

e[i] = 0   i >= n-1
     = 1 + p * e[i0] +  p * e[i1] + p * e[i2] + p * e[i3] + p * e[i4] + p * e[i5] 

where i0 .. i5 are 6 states calculated from where player goes when dice shows 1 .. 6 as well as combining the fact where the resulting position has a chute or ladder
While buidling the equation you might need to bring the non-constant terms of RHS of last relation to LHS (to make it a equation in standard form)

- Writing relation for each state above you will have n variables and n equations
- Solve using Gaussian elimination and e[0] is the answer

int m=6;   
double p =1/m;
double e[n,n+1];   // equation for n x n+1 matrix 
For(i,0,n-1)
{
 e[i,i] = 1.0;
 if(i==n-1)
   continue;
 For(j,1,m)
 {     
   e[i,n] += 1;
   int a = i+j;
   a=min(a,n-1);
   int b=t[a];
   e[i,b] -= p;
 }
}
 
GaussianSolve(e)
answer = e[0,n];


Practice : CoinGame, BranchPrediction

Simulation
- Set initial values of e[i] to 0 and simulate above relation large number of times. The values should converge to actual values.

  
double e[n];  
For(u,1,1000000)   // simulate 1000000 times
{
 For(i,0,n-1)
 {
  if(i == n-1)
  {
    e[i]=0;
    continue;
  }
  e[i] += 1;  
  For(j,1,m)
  {          
   int a = i+j;
   a=min(a,n-1);
   int b=t[a];
   e[i] += p * e[b];
  }     
 }
}
answer=e[0];  


Practice : SchoolTrip,

Example 2 (using DP)
- You are throwing a n sided fair dice and noting the face which comes up. What is the expected number of throws before which you will be able to see all n faces at least once.

State: i , the number of faces seen till now. Start state is 0 and end state is n.
Transitions : Each with probability 1/n to other states, as to how many are seen newly after a throw.

Let e[i] be the expected number of throws required to see all n faces assuming you have already seen i faces (i 0 .. n)

e[i] =  0    i == n   // seen all faces
     =  1 + (i/n) * e[i] + (n-i)/n * e[i+1]


- (i/n) probability that you will see already seen faces and (n-i)/n probability that you will see a unseen face at which seen count goes up by 1.
- Since RHS has e[i], we can bring it to LHS and regrouping

e[i] = (n/(n-i) + e[i+1]) 


This now is a DAG and hence use DP to solve ie find all e[i], i in 0 .. n. Answer is e[0]

e[n]=0;
For(i,n-1,0)
  e[i] = (n/(n-i) + e[i+1]) 
answer = e[0];


Practice : Favdice , PartyGame
RSS