Chow Chow Chasing (11/4 – 11/17)
TwoYen is looking for her dog Simba (a Chow Chow, as you might have guessed) in a animal shelter. However, the shelter manager has no clue which one Simba is so she presents \(n\) dogs (labeled \(1\) through \(n\)) to TwoYen at a random order.
As Simba is her dog, TwoYen can recognize Simba immediately and will stop looking at the rest of the dogs once she found Simba.
As she leaves with Simba who was labeled \(n\), she realizes something interesting. If she lists out the dogs that she saw in order, the sequence is increasing in Two pieces! Meaning, if the numbers of the dogs were \(a_1, \dots ,a_k\), there exists \(1 \leq k’ \leq k\) such that \(a_1, \dots, a_{k’ – 1}\) is an increasing sequence and \(a_{k’}, \dots ,a_k\) is also an increasing sequence. (Assume the empty sequence is an increasing sequence)
Examples of sequences increasing in 2 pieces:
\(a_1 = 1\)
\(a_1 = 1, a_2 = 2\)
\(a_1 = 2, a_2 = 1\)
\(a_1 = 1, a_2 = 3, a_3 = 5, a_4 = 2\)
Given this information, let \(E_n\) be the expected number of dogs (including Simba) that Tuyen saw. Find
\[\lim_{n \to \infty} E_n \]
Solution:
First, we find the probability that TwoYen finds Simba at turn \(k\). There is a \(\frac{1}{n}\) chance Simba is at turn \(k\), and out of those, we need to calculate the probability that the sequence is increasing in two pieces.
Consider \(k\) numbers excluding Simba’s number. To count the number of ways the these numbers are increasing in two pieces, we can select a subset of these \(k\) numbers to form an increasing sequence in the beginning, and the rest to form an increasing sequence after that. For example, if the numbers are \(1, 2, 5, 6, 9\) and you pick \(\{1, 5\}\) as the subset, the sequence would be \(1, 5, 2, 6, 9\). This would be a bijection, except that we are overcounting the case \(1, 2, 5, 6, 9\). When we pick \(\emptyset, \{1\}, \{1, 2\},\dots\). Therefore, the probability that a given sequence of \(k\) numbers is increasing in two pieces is \(\frac{2^k – k}{k!}\).
Normalizing the probabilities to 1,
\(E_n = \sum_{k=0}^n \frac{(k+1)(2^k – k)}{k!}\) divided by \(\sum_{k = 0}^n \frac{2^k – k}{k!}\) and both can be calculated using the definition of \(e = \sum_{k=0}^\infty \frac{x^n}{n!}\). The numerator is equal to \(3e^2 – 3e\) and the denominator is equal to \(e^2 – e\), so \[\lim_{n \to \infty} E_n = 3\]