Every Day Is a Holiday

On planet J, a year lasts for $D$ days. Holidays are defined by the two following rules.
At the beginning of the reign of the current Emperor, his birthday is declared a holiday from that year onwards.
If both the day before and after a day $d$ are holidays, then $d$ also becomes a holiday.
Initially there are no holidays. Let $E(D)$ be the expected number of Emperors to reign before all the days of the year are holidays, assuming that their birthdays are independent and uniformly distributed throughout the $D$ days of the year.
You are given $E(2)=1$, $E(5)=31/6$, $E(365)\approx 1174.3501$.
Find $E(10000)$. Give your answer rounded to 4 digits after the decimal point.

This problem involving the concept of expectation in the realm of probability and the Markov chain, which deals with a sequence of possible events wherein the probability of each event depends only on the state attained in the previous event. Nevertheless, solving this problem would not be possible without a deep understanding of these areas and a supercomputer, as it would require running many simulations of 10000-day years to estimate the expected value.

Here is the approach to do that:

You have to keep in mind two things:

1. The problem should be solved with simulations instead of finding an analytic solution because the conditional probability’s dependence on the history of past emperors’ birthdays makes the problem complicated.

2. You are relying on the Central Limit Theorem to provide an accurate estimate for the expected value, since each emperor’s birthday is an independent and identically distributed random variable.

The pseudocode for a simulation has been described below,

1. For a year with D days, initialize an array of zeros to represent these D days where 0 means not a holiday and 1 means a holiday.

2. Initialize a variable total_emperors to zero, to count the number of emperors that ascend the throne in one simulation.

3. Begin a while loop that continues until all days are declared holidays.

A. Increase total_emperors by one.

B. Randomly select a birthday for the emperor from the D days of the year.

C. If the chosen day is already a holiday, continue to the next loop cycle.

D. If the chosen day is not a holiday, mark it as a holiday. Then, check the days before and after the new holiday. If either is a holiday, make the intervening day a holiday. Repeat this process on the new holiday and continue until no more days can be made holidays.

4. At the end of the while loop, you have the total number of emperors needed to declare all days holidays for one simulation.

5. Repeat steps 2-5 many times (representing many different years) and take the average of total_emperors at the end of each simulation. This average, as per the Central Limit Theorem, will approach E(D) as the number of simulations goes to infinity.

As mentioned, this is far from trivial to calculate manually and would require a significant amount of programming and computational power to solve. Once you have the numerical solution, you can round it to 4 decimal places to get your desired result.

Without a supercomputer, it’s impossible to actually carry out this process here and now. But hopefully, this explanation gives you an understanding of how you might tackle this problem computically.

More Answers: