How to take a Passport Photograph – Part 2 | Eventually Almost Everywhere

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)

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

$\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.

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

How to take a Passport Photograph – Part 2

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

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

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply