Who Reaches the Checkout?

An online shop models a visit as a Markov chain on its pages. From page a the next page is b with probability P[a][b] (a missing entry means 0; each row adds up to 1). Some states are final: their row is {s: 1.0} (for example "buy" and "leave"), and once a visitor is there they stay. From every other state, a final state can be reached, so every visit ends.

Write funnel(P, goal), where goal is one of the final states. Return a dict with one entry for every non-final state s: a tuple

(probability that a visit now at s ends in goal, expected number of further clicks until it ends)

Each value must be accurate to within 1e-8.

The setup provides site_map(n, seed), which returns the table of a random shop with n pages plus the final states "buy" and "leave".

Examples

Input:  P = {"home":    {"search": 0.5, "product": 0.2, "leave": 0.3},
             "search":  {"product": 0.6, "search": 0.1, "leave": 0.3},
             "product": {"cart": 0.3, "search": 0.4, "leave": 0.3},
             "cart":    {"buy": 0.6, "product": 0.2, "leave": 0.2},
             "buy": {"buy": 1.0}, "leave": {"leave": 1.0}}
        goal = "buy"
Output: {"home": (0.14257425742574257, 2.937293729372937),
         "search": (0.1782178217821782, 2.838283828382838),
         "product": (0.26732673267326734, 2.5907590759075907),
         "cart": (0.6534653465346535, 1.5181518151815182)}
Explanation: a visitor on the home page buys with probability about 14% and ends
the visit after about 2.94 more clicks on average.

Constraints

• 2 <= len(P) <= 60, at least one final state, and goal is a final state
• floats are compared with a tolerance of 1e-6; results must not depend on the clock

Goals

• Model a process that ends in one of several final states as a Markov chain
• Compute, for every starting state, the probability of ending in a chosen final state
• Compute the expected number of steps until the process ends