7
$\begingroup$

A city's roadworks is laid out as a perfectly rectangular tiling. A commuter within this city has to travel to work a distance of 17 blocks east and 7 blocks north each day, and tries to take the same route one day as he does the next... with just a touch of novelty. He will choose at random one of the city blocks that he traveled two sides of yesterday, and modify his route today so that he sees the other two sides. For example, here is how his path might change from one day to the next: Path The first image is his path Tuesday; the second, all the blocks he could've chosen to pivot his path about, and the one he did choose; and the third, his path Wednesday. (This shows a 10x10 city)

After many many years spent following this pattern, how many turns on average will our commuter be taking on his daily route?

$\endgroup$
4
  • 2
    $\begingroup$ As I said in my edit reason, MathJax here is harming accessibility. Some screen readers (especially the affordable ones) are completely unable to parse it. You're essentially using MathJax to create a different font, for single numbers, which is not really a good enough reason to cut off screen readers from understanding the numbers. $\endgroup$
    – bobble
    Dec 2 '20 at 21:14
  • $\begingroup$ Very well, I fixed it. Chalk it up to a habit of mine. $\endgroup$
    – Feryll
    Dec 2 '20 at 21:15
  • $\begingroup$ @bobble I don't see any guidelines saying not to use MathJax. It was asked in Meta several years ago, but seems to have been left at "leave a comment and leave it up to the OP" $\endgroup$
    – SteveV
    Dec 2 '20 at 23:05
  • 1
    $\begingroup$ @SteveV That meta post is outdated, I think. Again, read what Bobble wrote above. Also, MathJax makes loading stuff also much slower. $\endgroup$ Dec 3 '20 at 0:35
4
$\begingroup$

The average number of turns is $$\frac{2 \cdot 7 \cdot 17-1} {7+17-1} \approx 10.30$$ Let's write the path that the commuter takes as a sequence of steps East (E) and North (N), with 17 E's and 7 N's. The commuter modifies his path each day by flipping a corner, swapping a consecutive NE or EN to the opposite, choosing one uniformly at random to swap.

Consider a modified commuter who, every day, swaps two adjacent steps in their path uniformly at random, with no regard to whether the same or not. So, they among the 23 pairs of adjacent steps uniformly at random and swap them. If they were EE or NN, this has no effect. Otherwise, it's just like the original commuter, with a uniformly chosen NE or EN among all such the sequence. If we write out the sequence of paths of the modified commuter and remove those that were unchanged from the previous day, we get a sequence of paths from the original commuter's distribution.

By repeatedly swapping adjacent elements, after enough steps, the modified commuter approaches a uniform permutation of 24 elements. (This is a random walk on a regular bipartite graph that restricts into even permutations on even days and odd ones on odd days, but over a long enough time range, these average out.) Applying a random permutation to the original path gives a uniformly random sequence of 17 E's and 7 N's. So, on a random day in a large interval far from the initial day, the modified traveler is equally likely to be taking any path.

What about the original commuter? Recall that the original commuter can be obtained from the modified one by collapsing all runs that repeat the same path unchanged. This can be though of as only keeping the last path in each run. We can sample a paths taken by the original commuter on a random day far in the future by taking such a path for the modified traveler and rejection-sampling it to the be the last one in its run repeating that path. The chance that the run is the last one equals the chance that two of its adjacent elements are different, that is the fraction of turns among the 23 adjacent steps. So, the eventual distribution of the original traveler's path weights each one by the number of turns that it has.


So now, our question is, what is the average number of turns on a path chosen at random, not uniformly, but weighted by its number of turns?

The remainder of the post computes that answer. One approach would be to try to bash out the probability of exactly $k$ turns and go from there. But, we don't need to do this to get the weighted average we want, which we'll see breaks into the probabilities of various pairs of positions containing turns. There's probably a still nicer way to do it, given how clean the end result is.

Let $T$ be the random variable for the number of turns in a uniformly random sequence of 17 E's and 7 N's. We're asked to find the expectation of the number of turns where each sequence has probability proportional to its number of turns. This is:
$$ E \left[ T \cdot \frac{T}{E[T]} \right] = \frac{E[T^2]} {E[T]} $$ We can break down $T = T_1 + T_2 + \cdots + T_{23}$ into sum the indicator random variables $T_i$ of whether there's a turn at some position $i$ from 1 to 23, that is, the symbols at positions $i$ and $i+1$ are different. Note that the distributions $T_i$ are not independent.

We first look at the denominator. By linearity of expectation, $$ E[T] = \sum_{i=1}^{23} E[T_i]$$ We observe that $E[T_i]$ is the same for all $i$. Because the uniform distribution of sequence of 17 E's and 7 N's is invariant under permutation, any pair of indices is equivalent, and so the chance that two adjacent values are unequal is the same for any pair. Call this chance $p$. So, we have $$ E[T] = 23 p.$$ We show how to compute $p$, though it turns out we won't need its value because it will cancel in the computation. It equals the chance that if we draw 2 marbles from replacement from among 17 E's and 7 N's, they are different. Of the $24 \cdot 23$ pairs of draws, $2\cdot7\cdot17$ give two different values (N then E, or E then N), giving chance $\frac{2 \cdot 7 \cdot 17}{24 \cdot 23}$. Now let's break apart the numerator using linearity of expectation:
$$ E[T^2] = \sum_{i=1}^{23} \sum_{j=1}^{23} E[T_i T_j]$$ The joint expectation $E[T_i T_j]$ is the probability that there is a turn at both position $i$ and position $j$, which we write as $P[T_i, T_j]$. This equals the conditional probability of a turn at $j$, and given this a turn at $i$: $$P[T_i, T_j] = P[T_j] P[T_i | T_j] = p P[T_i | T_j].$$ So, our expression for the final result is now:
$$\frac{E[T^2]} {E[T]} = \frac{\sum_{i=1}^{23} \sum_{j=1}^{23} \cdot P[T_i | T_j]p}{23 p} = \frac{1}{23}\sum_{j=1}^{23} P[T_i | T_j]$$ Note how the $p$ cancelled when using the conditional probabilities. Now we need to answer the question "Given a turn at position $i$, what's the chance of a turn at position $j$." We can split this into cases:

1) If $i=j$, the conditional probability is clearly 1. There are 23 such terms in the sum.

2) If the two positions are adjacent, $|i-j|=1$, then the conditional probability is $1/2$. This is because switching around turn $i$ (positions $i$ and $i+1$) between EN and NE will flip whether or not position $j$ constitutes a turn. There are $2 \cdot 22$ summands for pairs $(i,j)$ where $|i-j|=1$.

3) For the remainder of $23^2$ pairs $(i,j)$, we have $|i-j|>1$ and the positions corresponding to the turns are completely disjoint. Here, the conditional probability $P[T_i | T_j]$ is just the chance that once we've removed one E and one N from the pool to make the turn $T_j$, we obtain a turn at $T_i$ by drawing two different symbols from the urn in which there remain 16 E's and 6 N's. This is just like the result for $p$, but with 16 E's and 6 N's, so $\frac{2 \cdot 6 \cdot 16}{22 \cdot 21}$.

Summing these all together, we have:
$$\frac{1}{23}\sum_{j=1}^{23} P[T_i | T_j] = \frac{1}{23} \left( 23\cdot 1 + 2 \cdot 22 \cdot \frac{1}{2} + (23^2 - 23 - 2 \cdot 22) \cdot \frac{2 \cdot 6 \cdot 16}{22 \cdot 21}\right)$$ This simplifies to get an overall average of $\frac{2 \cdot 7 \cdot 17-1} {7+17-1} \approx 10.30$.

$\endgroup$
16
  • $\begingroup$ "swapping adjacent elements at random for a sufficiently long time approaches a uniform permutation of those symbols" I don't know that I believe this to be true, but if it is I think it deserves a proof. The reason I doubt it is that we basically have a markov chain between valid strings, and some strings have more predecessors than others. E.g. the configuration with exactly one turn can only be reached by a single configuration, while other configurations have multiple valid predecessors. Assuming each state is equally likely would imply that each successor isn't. A contradiction. $\endgroup$
    – hdsdv
    Dec 2 '20 at 23:34
  • $\begingroup$ @hdsdv I think it's simpler than that. From a given state, there's some number of null moves and some number of non-null transitions to a different state. If we consider the next different state reached from that state, this is just removing all the null moves before the first non-null move. And so the next state has a the same distribution as the non-null transitions from that state. $\endgroup$
    – xnor
    Dec 2 '20 at 23:40
  • $\begingroup$ I understand that part. I'm saying that if you ignore the null moves, some states have more predecessors than others. So you need to prove that the stationary distribution of the reduced Markov chain is uniform. $\endgroup$
    – hdsdv
    Dec 2 '20 at 23:53
  • 1
    $\begingroup$ @Feryll Yeah, what I wrote was confusing from me trying to avoid writing too many symbols. I've rewritten the computations. $\endgroup$
    – xnor
    Dec 3 '20 at 22:58
  • 1
    $\begingroup$ @PaulPanzer I'm working over the distribution where each sequence is equally likely, not the stationary distribution where they're different. Please see my rewritten computation which I hope is less confusing. $\endgroup$
    – xnor
    Dec 3 '20 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.