**Question:** Consider n elements—e_{1}, e_{2}, . . . , e_{n}—that are initially arranged in some ordered list. At each unit of time a request is made for one of these elements—e_{j} being requested, independently of the past, with probability P_{j}. After being requested the element is then moved to the front of the list. That is, for instance, if the present ordering is e_{1}, e_{2}, e_{3}, e_{4} and e_{3} is requested, then the next ordering is e_{3}, e_{1}, e_{2}, e_{4}. We are interested in determining the expected position of the element requested after this process has been in operation for a long time.

**Analytical Solution****:** This is an interesting problem that has many applications. Understanding of this problem requires understanding of conditional expectations. We will understand the problem in two ways. In order to further understand the problem we will perform simulations at the end.

- The list has n elements.
- Each element from the list has a probability of P
_{j}of being chosen- This is regardless of its current position

- If the selected element is already in the front of the list, it stays there
- Note that more likely the element is likely to be selected, lower is its mean position
- the lowest position is the front of the line
- the highest position is at the back of the line

- Hence, the expected position of any of the elements would be a number between 1 and n

- Each element from the list has a probability of P
- Setting the problem up
- To start off, the expected position of the element can be written as
- E[ position of the element of interest ]
- With a conditional on the element that has been selected at any time we can rewrite the expectation as
- E[ position of the element of interest | ej has been selected ] P
_{j} - E[ position of ej | ej has been selected ] P
_{j}

- E[ position of the element of interest | ej has been selected ] P
- The above can be simplified using our observation from above that expected position is independent of the current position thus yielding
- E[ position of ej ] P
_{j}

- E[ position of ej ] P

- The expected position of the element ej can be calculated by first obtaining an expression for the position of ej
- The expression is elegantly defined in the book as follows
- Define an indicator random variable called I
_{k} - I
_{k }= 0 when the element k is behind element j - I
_{k}_{ }= 1 when the element k is ahead of element j - Given we have a bunch of I
_{k }in order to find the absolute position of the element j we need to sum the I_{k}for all the k values that are not j - Also note that if j is the first one in the list, this means all the other elements are behind it and all the I
_{k}variables would sum up to zero - Thus, position of ej = 1 + Σ I
_{k}for all the k that are not j - ⇒ E [ position of ej ] = E [ 1 + Σ I
_{k}] = 1 + E [ Σ I_{k}] = 1 + Σ E I_{k} - Since I
_{k}is an indicator variable, the expectation is also the probability of the occurrence of the indicator elements- E [ I
_{k }] = E [ P occurrence of I_{k }] = E [ P that ej > ek ] - This is simple as we just need to compute the
*“relative pick probability of j with respect to k”* - ⇒ E [ I
_{k }] =^{ej}⁄_{ej+ek} - 1+ Σ
_{k}(P_{j }Σ_{k }^{ej}⁄_{ej+ek})

- E [ I

- Define an indicator random variable called I

**Simulation**

- The first plot shows the probabilities of being chosen to be bumped up to the front of the line
- The second plot shows the distribution of the item’s position over 1000 selections

**Code**

associateLists[list1_List, list2_List] := Association[MapThread[{#1 -> #2}&, {list1, list2}]]

associationFunctionMap[associationIn_Association, function_Symbol] := Module[{association = associationIn, keys, values}, keys = Keys@association; values = function /@ Values@association; associateLists[keys, values]]

ClearAll[swap, position, expectedPosition]; swap[list_List, superiorNumber_] := Module[{tempList = list, current}, Prepend[DeleteCases[tempList, superiorNumber], superiorNumber]]; expectedPosition[probabilitiesIn_Association, key_] := Module[{probabilities = probabilitiesIn, element, keys}, 1 + (element = probabilitiesIn[#]; probabilities = KeyDrop[probabilitiesIn, #]; element Plus @@ (# / (element + #) & /@ Values[probabilities])) &[ key]] position[list_List, item_] := Position[list, item][[1, 1]] Module[{n = 10, probabilities, list, choices, queue, plotData}, list = Range[n]; probabilities = unitize[Association@ MapThread[#1 -> #2 &, {list, RandomReal[{0, 1}, n]}]]; choices = RandomChoice[Values@# -> Keys@# &[probabilities], 1000]; queue = {list}; Table[AppendTo[queue, list = swap[list, choices[[r]]]], {r, 1, Length@choices}]; plotData = Association@ SortBy[Table[r -> (position[#, r] & /@ queue), {r, 1, n}], Mean[Values[#]] &]; ListPlot[probabilities, GridLines -> {Keys@probabilities, Automatic}, Frame -> True, ImageSize -> 788, FrameLabel -> {"Item", "Probability of being chosen"}] // Print; DistributionChart[Values@plotData, ImageSize -> 788, ChartElementFunction -> "Density", ChartStyle -> Lighter@Red, ChartLabels -> Placed[{Keys@KeySort@plotData, N@Values@ KeySort@associationFunctionMap[plotData, Mean]}, {Below, Above}], FrameLabel -> {"Item", "Position of item over 1000 selections"}, PlotLabel -> "The top of each bar is the mean position over 1000 selections"] // Print; ]

End of the post 😉

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.