Shopping

radosr

Baruch MFE Faculty
You are out shopping one day with $N, and you find an item whose price has a random value between $0 and $N. You buy as many of these items as you can with your $N. What is the expected value of the money you have left over? (Assume that $N is large compared to a penny, so that the distribution of prices is essentially continuous.)
 
If I didn't mess up the details, it works out to \(N ( 1 - \frac{\pi^2}{12})\). Not one of your harder problems, but definitely surprising!
 
correct.
it is
\(\sum_{k=1}^\infty \large(\frac{1}{k} - \frac{1}{k+1}\right)\cdot \large(N\cdot\large(\frac{1}{k} - \frac{1}{k+1}\right)\cdot \frac{k}{2}\right)\)

one distinguishes cases depending on the number of articles bought (Pr in the first bracket) and computes the expected change in each case (the second bracket).
 
With brutal force.

For k=1,..., if x is in [N/(k+1), N/k), then
the expectation of the change is \(\int_{N/(k+1)}^{N/k} (N-kx) \frac{1}{N}dx =\frac{N}{2} \frac{1}{ k (k+1)^2}\)

Then adding them altogether, we have
\(\sum_{k=1}^\infty \frac{N}{2} \frac{1}{ k (k+1)^2}=\frac{N}{2} \sum_{k=1}^\infty \{\frac{1}{ k (k+1)} - \frac{1}{ (k+1)^2}\} \)

Ignoring the N/2 for the moment, the sum of the first term is 1 and the sum of the second term (ignoring the subtraction sign) is \(\pi^2/6-1\)
Putting these two pieces together,
we have \(\frac{N}{2} \{1 -(\pi^2/6-1)\}=N(1-\pi^2/12)\)

As other people have mentioned, for this problem, brutal force is quite easy. I'm not sure if you have a cute solution other than the brutal force.

correct.
it is
\(\sum_{k=1}^\infty \large(\frac{1}{k} - \frac{1}{k+1}\right)\cdot \large(N\cdot\large(\frac{1}{k} - \frac{1}{k+1}\right)\cdot \frac{k}{2}\right)\)

one distinguishes cases depending on the number of articles bought (Pr in the first bracket) and computes the expected change in each case (the second bracket).
 
Top