Expected Total Backward Steps When Called Guests Move to the Front of a Random Line

One hundred guests, numbered 1 to 100, stand in a single line to enter a party, in a uniformly random order. The host calls the numbers one at a time. When a number is called, that guest walks to the front of the line, and each guest who was standing ahead of them steps back one place to make room. The called guest then enters the party and leaves the line, and the host calls the next number. This repeats until every guest has entered. What is the expected total number of backward steps taken by all guests over the whole process? The report says only that, when a called guest comes to the front, the other guests step back one step. This version reads that as the guests who were standing ahead of the called guest, since those behind do not need to move, and assumes the host calls the numbers in the order 1, 2, ..., 100. Only backward steps are counted; guests closing the gap left by a guest who has entered are not. ```hint Watch the waiting guests Does calling a guest to the front and letting them in ever change the order of the remaining guests relative to one another? ``` ```hint Think in pairs Fix two guests. Under what condition does one of them step back because the other was called? ``` ### Clarifying Questions - When a guest is called to the front, does every remaining guest step back, or only those who were standing ahead of the called guest? - Are the numbers called in the order 1 to 100, or in some other order, and is that order independent of how the guests are lined up? - Is the starting line a uniformly random arrangement of the 100 guests? - Do steps forward, taken to close the gap after a guest enters, count toward the total? ### What a Strong Answer Covers - A precise reading of who steps back on each call, and how the answer would change under the other reading - How the order of the waiting guests evolves from one call to the next, and what each backward step can be attributed to - A decomposition of the total into indicator variables, with the probability of each indicator justified - An exact value for 100 guests, a general formula for n guests, and a check on a small case ### Follow-up Questions - Does the expected total change if the host calls the 100 numbers in a uniformly random order instead of 1 to 100? - How many backward steps, on average, does the guest whose number is called k-th take, and on average how many calls require nobody to step back? - What is the variance of the total number of backward steps, and roughly what does its distribution look like?