An Entropy Law Governing Retail Shopper Decisions: Supplemental Material

Nicholas Sohre¹ [email protected] Alisdair Wallis² Stephen J. Guy¹ [email protected] University of Minnesota¹, Computer Science & Engineering, Tesco PLC²

Appendix A Proofs

Lemma: Simulated Inversion rate of two items

Given two items having true geodesic distances $b$ and $c$ from the agent, their estimated distances $\hat{b}$ and $\hat{c}$ under our simulation model are

\begin{split}\hat{b}=b+w_{b},\epsilon_{b}\sim\mathcal{N}(0,\alpha*b)\\ \hat{c}=c+w_{c},\epsilon_{c}\sim\mathcal{N}(0,\alpha*c)\end{split}

(1)

Which produce Gaussian random variables of the estimated distances $B\sim\mathcal{N}(b,\alpha*b)$ and $C\sim\mathcal{N}(c,\alpha*c)$ . Suppose $b<c$ (that is, item $b$ is closer to the agent than item $c$ ). Then, the probability of an inversion is the probability that the estimated distances swap in magnitude: $C<B\rightarrow C-B<0$ . Let $Y=C-B$ be a new Gaussian random variable, then

\begin{split}Y\sim\mathcal{N}(c-b,\sqrt{(\alpha*c)^{2}+(\alpha*b)^{2}})\\ =\mathcal{N}(c-b,\alpha*\sqrt{c^{2}+b^{2}})\end{split}

(2)

and the likelihood of inversion is $P(Y<0)$ . For a given $b$ , $c$ , and $\alpha$ , this quantity can be computed analytically from the CDF of $Y$ evaluated at $0$ :

P(Y<0)=\frac{1}{2}\left[1+\text{erf}\left(\frac{0-(c-b)}{\alpha*\sqrt{2(c^{2}+b^{2})}}\right)\right]

(3)

Theorem: Simulated inversion chance increases with distance to the closer item

First, we note that $1+\text{erf}(x)$ is a positive, increasing function of $x$ . Then, given equation 3, it suffices to show that for any $b$ (the distance to the closer item), the input to erf is increasing:

\forall b\left[\frac{\delta}{\delta b}\,\frac{b-c}{\alpha*\sqrt{2(c^{2}+b^{2})}}\geq 0\right],\;0<b\leq c

(4)

Proof: evaluating the partial derivative in equation 4 with respect to $b$ , we have

$\displaystyle\frac{\delta}{\delta b}\,\frac{b-c}{\alpha*\sqrt{2(c^{2}+b^{2})}}$
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\frac{\delta}{\delta b}\,\frac{b-c}{\sqrt{c^{2}+b^{2}}}$
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\frac{\sqrt{b^{2}+c^{2}}-\frac{(b-c)b}{\sqrt{b^{2}+c^{2}}}}{(b^{2}+c^{2})}\;\;$	(quotient rule)
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\frac{c(c+b)}{(b^{2}+c^{2})^{\frac{3}{2}}}\;\;$	(simplify)	(5)

Since equation 5 is positive whenever $b,c$ and $\alpha$ are positive, the derivative is positive with respect to $b$ and constrains equation 3 to be increasing with increasing $b$ .

Theorem: Simulated inversion chance decreases with increasing distance between items

Another important property for maintaining the relationship between difficulty and inversion chance is that the inversion chance must decrease with increasing $W=c-b$ .
Proof: We wish to show that the derivative with respect to $W$ is always negative:

\forall W=c-b,\left[\frac{\delta}{\delta W}\,\frac{b-c}{\alpha*\sqrt{2(c^{2}+b^{2})}}\leq 0\right],\;0<b\leq c

(6)

Noting that $(b^{2}+c^{2})=W^{2}+2cb=W^{2}+2b(b+W)$ , we can substitute into equation 6 and get

\frac{\delta}{\delta W}\,\frac{-W}{\alpha*\sqrt{2(W^{2}+2b(b+W))}}

(7)

While we cannot write the derivative in terms of only $W$ , we can treat $b$ as a positive constant and take the partial with respect to $W$ . If the result is negative for any value of $b$ , then the derivative with respect to $W$ is negative regardless of $b$ and the property is satisfied:

$\displaystyle\frac{\delta}{\delta W}\,\left[-\frac{W}{\alpha*\sqrt{2(W^{2}+2b(b+W))}}\right]$
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\frac{\delta}{\delta W}\,\left[-\frac{W}{\sqrt{W^{2}+2b(b+W)}}\right]$
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\left[-\frac{\sqrt{W^{2}+2b(b+W)}-\frac{W(W+b)}{\sqrt{W^{2}+2b(b+W)}}}{W^{2}+2b(b+W)}\right]\;\;$	(quotient rule)
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\left[\frac{W(W+b)}{(W^{2}+2b(b+W))^{\frac{3}{2}}}-\frac{W^{2}+2b(b+W)}{(W^{2}+2b(b+W))^{\frac{3}{2}}}\right]\;\;$	(simplify)
$\displaystyle=\frac{1}{\alpha\sqrt{2}}\frac{-b(2b+W)}{(W^{2}+2b(b+W))^{\frac{3}{2}}}\;\;$	(simplify)	(8)

Since $W$ and $b$ are both positive non-zero quantities, the resulting derivative is always negative as desired.

Theorem: Simulation inversion chance increases monotonically with difficulty

To show this property, it is sufficient to show that difficulty also increases monotonically with decreasing $W$ and increasing $b$ , since both these two values fully specify both the inversion rate (given an $\alpha$ ) and the difficulty.
Proof: First, we note that $W$ and $b$ are sufficient to fully describe difficulty:

\text{{difficulty}}=log_{2}\left(\frac{A}{W}\right)=log_{2}\left(\frac{b+W}{W}\right)

(9)

Then we can construct the partial derivatives with respect to both $W$ and $b$ for difficulty and see that they are always positive and negative respectively:

\frac{\delta}{\delta W}\frac{A}{W}=\frac{\delta}{\delta W}\frac{b+W}{W}=\frac{-b}{W^{2}}

(10)

\frac{\delta}{\delta b}\frac{A}{W}=\frac{\delta}{\delta b}\frac{b+W}{W}=\frac{b+W}{W^{2}}

(11)

Thus, both inversion rate and difficulty monotonically increase with increasing $b$ and decrease with increasing $W$ . Since $W$ and $b$ are both sufficient to fully specify both inversion rate and difficulty, we cannot make one smaller or larger (by adjusting $W$ or $b$ ) without having the same effect on the other. Therefore, both these quantities will have a monotonic relationship with each other.

Appendix B Simulation Details

Input: itemsToRetrieve;

Output: itemOrder;

itemOrder = [];

alpha = 0.30;

while While itemsToRetrieve.length $<$ 1 do

distances = [];

for i in 0 : itemsToRetrieve.length-1 do

trueDistance = getGeodesicDistance(itemsToRetrieve[i]);

noisyDistance = trueDistance + sampleNormal(0, alpha * trueDistance);

distances.push(noisyDistance);

end for

itemsByEstimatedDist = sort(itemsToRetrieve, by = distances);

itemOrder.push(itemsByEstimatedDist[0]);

itemsToRetrieve.remove(itemsByEstimatedDist[0]);

end while

itemOrder.push(itemsToRetrieve[0]);

return itemOrder;

Algorithm 1 Basket Simulation