How to take a Passport Photograph – Part 2

Recall that by the end of the last post, we had given a complete strategy for the (slightly degenerate) stochastic control problem that modelled how to select a photo from a photobooth. The strategy was determined by an infinite sequence, defined inductively by:

$a(1)=1,\quad a(n+1)=a(n)\left[1-\frac{a(n)}{2}\right]$.

At the very end of the post, I gave a selection of highly non-rigorous justifications for why

$a(n)\approx \frac{2}{n}$ for large $n$.

After trying a bit more carefully, I think I can show the following:

$a(n)=\Theta(\frac{2}{n}).$

More precisely, eventually

$a(n)\in [\frac{2}{n}-g(n),\frac{2}{n}+h(n)],$

where $g(n)=h(n)=2n^{-3/2}$, so in particular $g(n),h(n)=o(\frac{1}{n})$.

To set this up, just to avoid having ‘2’s everywhere, we rescale the $a(n)$s by 1/2, so that the recursive definition is now:

$a(n+1)=f(a(n)):=a(n)\left[1-a(n)\right].$

I will show that for suitably large $n$, (though in practice this won’t be very large at all)

$\Rightarrow\quad a(n+1)\in[\frac{1}{n+1}-(n+1)^{-3/2},\frac{1}{n+1}+(n+1)^{-3/2}].$

It will then suffice to show that the left hand side of this deduction holds for some $n$.

To show that

$f(\frac{1}{n}-g(n))\geq \frac{1}{n+1}-g(n+1),$

it suffices to verify that:

$\frac{1}{n^2(n+1)}\leq g(n+1)-(1-\frac{2}{n})g(n)-g(n)^2.$

When $g(n)=n^{-3/2}$, we can bound using the difference of two squares:

$(\frac{1}{(n+1)^{3/2}}-\frac{n-2}{n^{5/2}})=(\frac{1}{(n+1)^3}-\frac{(n-2)^2}{n^5})/(\frac{1}{(n+1)^{3/2}}+\frac{n-2}{n^{5/2}})$

$\geq \frac{\frac{n^4-5n^3}{(n+1)^3n^5}}{2n^{3/2}} \stackrel{n\geq 10}{\geq}\frac{n^4}{4n^{11/2}}=\frac{1}{4n^{5/2}}$

so for $n\geq 16$

$\geq\frac{1}{n^3}\geq \frac{1}{n^2(n+1)}.$

A similar calculation, which is relatively straightforward to perform and a bit of a hassle to write up into WordPress, gives the corresponding upper bound. It remains to check that

$a(16)\in [\frac{1}{16}-\frac{1}{64},\frac{1}{16}+\frac{1}{64}],$

and a direct computation (I used MATLAB) confirms this.