2
$\begingroup$

First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically include taxes, but cash payments and transactions are now rounded up/down to the closest multiple of 5 cents. For instance, if two products A and B are worth 67¢ and 1\$21¢ respectively, one would have to pay 1\$80¢ to buy them together, instead of their accumulated price 1\$78¢. In this particular instance, the seller wins 2¢ more than expected in the transaction.

With my wife, we were wondering whether a supermarket could manipulate the prices of its products in such a way that the rounded totals translate, on average, into a benefit for the company. Not overly paranoid about it, but a fun problem to think about during the holidays...

In a very simple model, we may assume that a consumer chooses a product uniformly at random within a collection ${\cal A}=\{a_i\}_{i=1}^k$ of products, each being assigned a price $p_i$. Consider now the Markov chain over states $Q=\{q_0, ..., q_4\}$, which 'remembers' the value of the grand total modulo 5¢. Its transitions are $$q_i \to q_{i+a_j\textbf{ mod }5} \text{ with probability } 1/|{\cal A}|, \forall i\in[0,4],\forall j\in[1,k].$$ For non-degenerate collections $\cal A$ (i.e. unless $a \textbf{ mod }5= 0, \forall a\in{\cal A}$), this Markov chain is ergodic but not reversible with respect to the uniform distribution.

Let $G$ be the random variable that denotes the "rounding-off" gain of the supermarket, then its asymptotic expected value can be expressed in term of the stationary distribution $\pi(\cdot)$ of the Markov model, as: $$ \mathbb{E}(G) = \pi(q_1)+2\pi(q_2)-2\pi(q_3)-\pi(q_4).$$

For any given collection ${\cal A}$, it is possible to determine $\pi(\cdot)$ exactly, using a variety of methods (I personally favor basic enumerative combinatorics/singularity analysis a la Flajolet/Sedgewick). For any non-degenerate collection ${\cal A}$ ($\exists a\in{\cal A} \text{ such that } a \textbf{ mod }5\neq 0$), I obtained (and subsequently conjecture) that $$ \pi(q_0) = \pi(q_1) = \pi(q_2) = \pi(q_3)= \pi(q_4) = 1/5.$$

Is there a simple/elegant argument to (dis)prove this conjecture?

A corollary of such a result is that, under these (fairly unrealistic, but amenable to an exact analysis) hypotheses, being a smart supermarket simply wouldn't pay off...

Improve this question
$\endgroup$
3
  • $\begingroup$ The chain is invariant under cyclic rotation of the states. If you renumber 0,1,2,3,4 as, say, 2,3,4,0,1, you leave the transition matrix the same. So, since the stationary distribution is unique (as long as there is a product whose price is not a multiple of 5), this stationary distribution must be invariant under rotations also, i.e. uniform. $\endgroup$
    – James Martin
    Jan 10, 2015 at 15:23
  • $\begingroup$ Alternatively, consider two copies of the chain, one started from state 0 and one from state 1. Couple their evolutions so that they use the same increments $a_j$ at each step, and so they stay distance 1 apart for ever. The long-run average occupancies in either chain converge to the stationary distribution, by the ergodic theorem. But the long-run average occupancy of $i$ in the first chain is the long-run average occupancy of $i+1$ in the second chain. $\endgroup$
    – James Martin
    Jan 10, 2015 at 15:26
  • $\begingroup$ I love the simplicity of the first argument, this is a great answer. Also, the argument can be trivially adapted for a 'Bernoulli' non-uniform consumer, and maybe extended for general 'Markovian consumers'. Could you make this an answer? $\endgroup$
    – Yann Ponty
    Jan 11, 2015 at 18:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy