October 03, 2006

Long time, no blog

Life’s been keeping me busy.
I’ll post
an update
soon.
Briefly: finished my summer job for the Amalgamated Insight
(née TelegraphCQ)
folks. I’m now back at Queen’s for the last year of my
undergrad.

Interesting math

An assignment in one of my
classes
included an
interesting
bonus problem. It is very simple, but I confess I got it
completely wrong before I saw the
solution. Maybe one of you bright folks is smarter than I:

Let the alphabet A = {a, b, c, …, z} (A is the
set of 26 lowercase letters of the English alphabet). Let
S1(w) be true iff the string w over alphabet
A contains the substring aaa; let
S2(w) be true iff the string w contains the
substring abc.

Suppose we choose a w
of 10
characters; each
character in w is selected randomly and independently.

Let P1 be the probability
that
S1(w)
is true,
and let P2 be the probability that S2(w) is
true. Is P1 > P2, P1 < P2, or P1 =
P2
? Give a justification for your answer. (Hint: P1
!= P2
).

If you think you know the answer,
email me

I’ll post
the answer later (neilc A T samurai D O T com).
Obviously, the gist is in the
justification, not which alternative you think is true.

Hat Tip: Prof. Kai Salomaa
for showing me the problem.

Advertisements

Leave a comment

Filed under Advogato, PostgreSQL

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