Can You Survive The Great Bar Crawl? [Solution]

Solution for the week of 3/9

Last week our problem was

It’s Tuesday evening and you and your friends decide to celebrate Mardi Gras the fun way—with a legendary bar crawl. Your neighborhood has N bars, all within stumbling distance of each other. But rather than meticulously planning a route, you embrace the chaos:

• Every hour, you pick a bar at random. No strategy, no preferences. And let’s be honest, you’re not going to remember which bars you’ve already been to.

• It’s going to be a late night. You and your friends will keep hopping between bars for a while.

But since the bar crawl hasn’t started yet and you’re still lucid, you realize it might be awkward if you all return to the same bar too soon. So you decide to figure out how how long it would typically take for this to happen.

So, our question is: Assuming it’s your first time returning to a bar you’ve already been to (i.e., it’s your first “repeat” bar), on average, how many hours will have passed between your first arrival and your second?

In an X’s Puzzle Corner first, we had TWO unique solutions submitted! Thanks to

Seth Cohen

and

Benjamin Phillabaum

for their submissions. Their solutions also made evident that there was a bit of an ambiguity in the problem. One could either assume that the group randomly choose the next bar to go to from any of the N possible bars or they could randomly choose a bar different from their current representing N-1 possibilities. These different assumptions do result in a meaningfully different answers.

Starting with the slightly simpler case where the party can randomly select the same bar they were just at, we first consider a random variable T representing the number of hours until the first repeat is encountered (recall that this isn’t quite the answer we’re looking for). The first repeat can’t occur at T=0 (since we’ve only visited a single bar). For T=1 we will have just arrived at the second bar so there’s a 1/N chance that we select the bar we were just at.

\(\begin{align*} P[T=2] &= \frac{N-1}{N} \frac{2}{N} \\ P[T=3] &= \frac{N-1}{N} \frac{N-2}{N} \frac{3}{N} \\ P[T=3] &= \frac{N-1}{N} \frac{N-2}{N} \frac{N-2}{N} \frac{4}{N} \\ \vdots \\ P[T=t] &= \frac{t (N-1)_{t-1}}{N^t} \end{align*}\)

Here (N)_t is the falling factorial function. Of course, what we really want is the duration between visits to the same bar. Since T represents the first repeat, you know every other bar visit was to a unique bar and you’re equally likely to end up at any bar you’ve been to previously. As such we have a uniform probability of ending up at any of the previous bars

\(P[L=l|T=t] = \frac{1}{t}\)

L represents the length of the loop formed when we return to a bar (thus creating a loop if we image our bar crawl as forming a path between the different bars). Pulling these together into an expectation we have

\(\begin{align*} \mathbb{E}[L] &= \sum_{l=1}^N l \cdot P[L=l] \\ &= \sum_{l=1}^N l \cdot \sum_{t=l}^N P[L=l \cap T=t] \\ &= \sum_{l=1}^N l \cdot \sum_{t=l}^N P[L=l | T=t] P[T=t] \end{align*}\)

Note that for a given loop of length l, the values of t that generate that loop must be at least as large as l. By summing over all possible values t of P[L=l|T=t] we would get the unconditional probability P[L=l]. Plugging everything in we have

\(\begin{align*} \mathbb{E}[L] &= \sum_{l=1}^N l \left( \sum_{t=l}^N \frac{1}{t} \frac{ t(N-1)_{t-1}}{N^t} \right) \\ \mathbb{E}[L] &= \sum_{l=1}^N l \left( \sum_{t=l}^N \frac{ (N-1)_{t-1}}{N^t} \right) \end{align*}\)

And there’s our expression!

We can follow a similar line of reasoning for the case where we don’t go back immediately to the same bar but can return to any of the others. This yields

\(\mathbb{E}[L] = \sum_{l=2}^N l \left( \sum_{t=l}^N \frac{ (N-2)_{t-2}}{(N-1)^{t-1}} \right) \)

Solver

Benjamin Phillabaum

also evaluated the asymptotic behavior of this function for large N and created the handy plot below (E is the exponential integral).

\(\mathbb{E}[L] \sim \frac{1}{2} + \frac{e^n (n-1) E_{2-n}(n-1)}{2 e}\)

Benjamin Phillibaum’s plot. The y-axis is the duration in hours between visits to the same bar and the x-axis is the number of bars N in the neighborhood.

If we assume your neighborhood has 10 bars, the expected duration (in the case where we can’t immediately go back to the same bar) between repeat visits ends up being 3.23. Ouch! Looks like we’re going to be making fools of ourselves.

As always, please comment with any thoughts or feedback you had on this problem or if you approached it differently. Thanks for reading!