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)

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s