The other day, we woke as a family to discover insufficient material for the execution of breakfast.
My wife rattled off a shopping list, my eldest (six years old) daughter transcribed and I grabbed the car keys. My other two children attempted to thwart us through a combination of crying and physical intimidation but we managed to beat them off.
When my eldest daughter and I arrived at the shops, we had a disagreement about the way we should tick off the shopping list. I wanted to do it aisle-by-aisle, however my daughter wanted to go linearly through the shopping list, potentially visiting aisles multiple times.
Clearly, the latter way is inefficient but I decided it would be best to allow my daughter to discover this through experimentation and so we proceeded down this path. And, delightfully, I spent the additional time thinking of the expected amount of time it takes to fulfil a shopping list in this way:
Problem. Suppose we have a shopping list of 
We have to make some assumptions. We assume it takes a fixed time (say 1 unit) to move between two adjacent aisles. We can, for now, neglect the amount of time it takes to actually explore the aisle to find the thing as we can deal with this later.
So, what I’m looking for here can be expressed as follows. If I select 
If you have any ideas, go ahead and comment below!
Dynamical Mathematical Gazette 
Nice question! Letting X be the given sum, thanks to linearity of expectation we get that E(X) = E(A_1) + (n-1)*E(|A_i – A_{i-1}|). The expectation of the first value is (1+k)/2, so the quantity of interest is E(|A_i – A_{i-1}|).
By definition it’s the sum from i=0 to i=k-1 of i*(# of pairs in {1,…,k} which differ by i)/(k^2).
Which I reckon is 0 + the sum from i=1 to i=k-1 of i*(2(k-i))/(k^2).
By relentless abuse of sums I got this in terms of the first k-1 integers and the first k-1 squares, and simplified to (k-1)(k+1)/3k.
So our expectation becomes (k+1)[1/2 + (n-1)(k-1)/3k]. Which is (unsurprisingly) linear in n and (surprisingly) asymptotically linear in k as well. I guess the increasingly large walks to the far away aisles also get proportionally less likely so that the average walk only grows linearly with the growth of the number of aisles. There’s a a nice continuous-analogue intuition for the 1/3 asymptotic growth rate in terms of a large fixed k and variable n (https://math.stackexchange.com/questions/195245/average-distance-between-random-points-on-a-line-segment), but the asymptotic growth rate of (1/2 + (n-1)/3) for a fixed n and variable k doesn’t make a lot of sense to me. Unfortunately I can’t seem to say anything interesting about the n=k case either, but it sure smells interesting.
LikeLike
Hi Adrian, my idea is based on adding up the distance of all possible paths and dividing by the number of paths.
Firstly, consider that there will be k^n possible paths {a1, a2…an} with each ai in {1, 2…k}.
Consider the distance to the first aisle of any path, assuming that we start at an aisle 0. There will be k^n/n paths starting with each ai. Therefore, the total distance to the first aisle from each path will be given by k^(n-1)*(sum from l=0 to k of l).
Consider next, the distance between all consecutive pairs in all possible paths. Each pair will occur an equal number of times when all paths are summed. Each pair will occur (n-1)*k^(n-2) times out of k^n paths. Summing the distances between (ai,aj) for all ai and aj in {1, 2…k} is then given by (sum from l=1 to k of (2*(k-l-1)*l)).
Therefore, the distance of all paths summed is given by (k^(n-1)*(sum from l=0 to k of l) + (n-1)*k^(n-2)*(sum from l=1 to k of (2*(k-l-1)*l))). Dividing this by the total number of paths gives the expected time to move through a list in the manner you described with n items and k aisles.
This comes out to (k+1)[n(k-1)/3k+1/6+1/3n]
This could easily be altered to include a variable for the amount of time to walk down an aisle, even accounting for whether the item is found in the first half of an aisle and you turn around and go back the way you came, or is found in the second half of the aisle and you continue to the end.
LikeLiked by 1 person
Interesting way to look at it. Our answers disagree, but I think it comes down to our summand for determining E(|A_i – A_{i-1}|). I have the sum from i = 1 to i = k-1 of i*(2(k-i)/k^2). To get this I let i be each possible distance (the max distance is k-1 not k, and we can ignore i=0 as we will multiply by i), and 2(k-i)/k^2 is the probability of seeing each distance (There are k^2 pairs (ordered with replacement), and there are 2(k-i) distances of length i, k-i of them starting with (1,i+1) and ending with (k-i, k), and doubling that for (i+1,1) up to (k, k-i)).
Equivalently your sum would be the sum from l = 1 to l = k of l*(2(k-l-1)/k^2). Can you go into more detail as to how this was obtained?
LikeLike