Sheldon Ross 10: Section 3.6.1 A List Model

Sheldon Ross 10 Section 3.6.1 A List Model-01.jpg

Question: Consider n elements—e1, e2, . . . , en—that are initially arranged in some ordered list. At each unit of time a request is made for one of these elements—ej being requested, independently of the past, with probability Pj. After being requested the element is then moved to the front of the list. That is, for instance, if the present ordering is e1, e2, e3, e4 and e3 is requested, then the next ordering is e3, e1, e2, e4. 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 Pj 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
  • 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 | ehas been selected ] Pj
      • E[ position of e| ehas been selected ] Pj
    • The above can be simplified using our observation from above that expected position is independent of the current position thus yielding
      • E[ position of e] Pj
  • The expected position of the element ecan 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 Ik
    • I= 0 when the element k is behind element j
    • Ik = 1 when the element k is ahead of element j
    • Given we have a bunch of Iin order to find the absolute position of the element j we need to sum the Ik 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 Ik variables would sum up to zero
    • Thus, position of ej  = 1 + Σ Ik for all the k that are not j
    • ⇒ E [ position of e] = E [ 1 + Σ Ik ] = 1 + E [ Σ Ik ] = 1 + Σ E Ik
    • Since Ik is an indicator variable, the expectation is also the probability of the occurrence of the indicator elements
      • E [ I] = E [ P occurrence of I] = E [ P that e> e]
      • This is simple as we just need to compute the “relative pick probability of j with respect to k”
      • ⇒ E [ I] = ejej+ek
      • 1+ Σk (P Σk ejej+ek)

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 😉


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.