How Many Rainy Spells?

A holiday cottage publishes a forecast: p[i] is the probability that it rains on day i of the season. Assume that days are independent of each other.

A rainy spell is a maximal stretch of consecutive rainy days (the day before it and the day after it are dry, or it touches the start or end of the season). Write spell_forecast(p, L) that returns a tuple of three floats:

1. the expected number of rainy days,
2. the expected number of rainy spells,
3. the expected number of rainy spells that last at least L days.

The setup provides forecast(days, seed), which returns a list of days plausible daily probabilities for experiments with Run.

Examples

Input:  p = [0.5, 0.5, 0.5], L = 2
Output: (1.5, 1.0, 0.375)
Explanation: of the 8 equally likely weeks, RRR, RRD and DRR have one spell of 2+ days,
RDR has two short spells, RDD, DRD and DDR have one, and DDD has none: 8 spells in total,
so 1.0 on average, and 3/8 of a long spell.

Input:  p = [0.9, 0.2, 0.9, 0.9], L = 2
Output: (2.9, 1.73, 0.846)
Explanation: spells start on day 0 (0.9), day 1 (0.1 · 0.2), day 2 (0.8 · 0.9) or day 3 (0.1 · 0.9).

Constraints

• 1 <= len(p) <= 5000, every p[i] between 0 and 1
• 1 <= L <= 50
• floats are compared with a tolerance of 1e-6

Goals

• Write a count as a sum of indicator variables, one per place where the event can happen
• Use linearity of expectation to add up their probabilities
• Count each run exactly once by looking at where it starts