Google Is Fast May 31st, 2009
Patrick Stein

A few hours after posting about constrained shuffles and the Fibonacci numbers, I decided to search for papers on constrained shuffles. Google had already indexed my article. I came up second. I like.

It may be they monitor pingomatic. Or, it may be because I have Google ads on the page. Either way, it feels oddly powerful to be able to type and be recorded.

Umm… now if only some other people searched for constrained shuffles. 😉

I Discovered The Fibonacci Numbers May 31st, 2009
Patrick Stein

Alright, I wasn’t the first. But, I wasn’t particularly expecting to find them either.

One nascent game concept that I have in my head requires me to do some constrained shuffling. As an example constraint, imagine that you need to shuffle a deck of cards while ensuring that no card moved more than five spots away from where it started. Or, imagine that you had to shuffle the deck so that a card of rank r could only move to spot that had been held by a card of rank r-1, r, or r+1.

In the general case, you have a directed graph with vertexes \left\{ v_1, v_2, v_3, \ldots, v_n \right\} and a permutation \pi such that \pi(i) can only equal j if there is an edge in the graph from v_i to v_j.

Well, as this is for a game, it would get pretty boring if there were only a few possible shuffles. On the other hand, if there are a large number of possible shuffles, then I haven’t really restricted the shuffling at all for all practical purposes. So, then the question is: for a given directed graph, how many possible shuffles are there? Can I generate them without generating any of the invalid permutations, too?

Today, I started with the How many?-question. I started with a very simple graph. The vertexes are spaced evenly along an east-west line. Each vertex is connected only to itself, its nearest neighbor to the east, and its nearest neighbor to the west. Put another way, \left| \pi(i) - i \right| \le 1 for i \in [1,n].

Let’s say we already had a row of n-1 vertexes. If we add another vertex at the beginning of the row, then there are two things that a shuffle can do to that new vertex: leave it where it is or swap it with what had been the first vertex in the row. Now, suppose that c(n) is the count of valid shuffles for n vertexes in this configuration. The case where our new vertex stays where it is leaves c(n-1) possibilities for the rest of the row. The case where our new vertex swaps places with the old first vertex leaves c(n-2) possibilities. As such, c(n) = c(n-1) + c(n-2).

Cha-ching. Note that c(1) = 1 and c(2) = 2, then c(n) = F_{n+1} where F_i are the Fibonacci numbers.

Things get a great deal messier if we move up to \left| \pi(i) - i \right| \le 2. More on that some other time…

Still No Word On The Clifford Algebra Text May 29th, 2009
Patrick Stein

I still haven’t heard back from Cambridge University Press about using one of their books to publicly study Clifford algebras. So, I started looking around for alternate texts.

My second choice book is Clifford Algebras and Spinors by Pertti Lounesto. This, too, is published by Cambridge University Press. Feh.

I started poking around for other topics instead. How about a related topic? I grabbed Differential Forms and Connections by R.W.R. Darling from my shelf. It, too, is Cambridge University Press.

Alright, different topic. How about Galios theory? I grabbed A Course In Galois Theory by D.J.H. Garling from my shelf. It is Cambridge University Press. The other two Galois theory books that I have are not from Cambridge University Press, but I’m not sure they are as useful.

I can’t find any good Clifford algebra texts that are not Cambridge University Press. This Geometry of Differential Forms by Shigeyuki Morita is published by the AMS. It looks decent from a quick glance on Google books.

Any suggestions?

Bad Math On Drugs May 28th, 2009
Patrick Stein

Let’s look at the estimated street value of marijuana in some recent arrests:

Some simple stats…

This was by no means a scientifically random sample. But, the sample mean here is $150.95/oz. with a sample deviation of $87.53.

What’s the moral? The smart-minded pot consumer should shop in El Paso. It’s way cheaper.

Why the variance?

The Michigan University daily paper claims the DEA values marijuana at $62.50/oz. in an effort to make everyone (except the people in El Paso, apparently) think they’re paying too much for it. That’s an interesting theory.

I would think the DEA has conflicting interests though. It sounds more impressive to seize $700,000 worth of drugs than to seize $59,763.20 worth. [The New York City marijuana at the El Paso value.]

I would also bet that higher numbers result in longer sentences, higher conviction rates, or both.

The only thing that’s crystal clear though is that they may as well be pulling the numbers out of a hat.

Who’s Knocking On My Disk Drive? May 28th, 2009
Patrick Stein

I rebooted my Linux box into Windows Vista several times in the last two days while moving things over to VMWare Fusion. All day today, my disk drive has given a little spin every two or three seconds.

When I first noticed it, I tried searching around with iostat and top to see if I had some process run amok. Finding nothing, I tried rebooting.

The magical reboot was not so magical. My machine was still merrily hitting the disk every couple seconds.

I searched around the web for “disk activity” linux and “disk activity” ubuntu. I found recommendations that I:

All of those seemed bogus to me. None of them seemed like anything that would have changed yesterday or today. But, the last one got me thinking. What logs do I have that do get flushed on every message? Are any of them going batty today?

Sure enough, /var/log/auth.log was getting hit every two or three seconds. Someone was trying to guess logins on my machine.

May 28 04:57:57 evariste sshd[6966]: pam_unix(sshd:auth): authentication failure
; logname= uid=0 euid=0 tty=ssh ruser= rhost=nitro.xyzdns.net  user=backup
May 28 04:57:59 evariste sshd[6966]: Failed password for backup from 209.51.159.
194 port 54874 ssh2
May 28 04:57:59 evariste sshd[6968]: Invalid user guest from 209.51.159.194
May 28 04:57:59 evariste sshd[6968]: pam_unix(sshd:auth): check pass; user unkno
wn
May 28 04:57:59 evariste sshd[6968]: pam_unix(sshd:auth): authentication failure
; logname= uid=0 euid=0 tty=ssh ruser= rhost=nitro.xyzdns.net
May 28 04:58:01 evariste sshd[6968]: Failed password for invalid user guest from
 209.51.159.194 port 54992 ssh2

Looking back through the last week, I’ve had a few spats of bogus login attempts. Most of them were just four or five attempts in a row. This one today had gone for twelve hours.

I threw that IP address into /etc/hosts.deny. Now, all is quiet. Well, except my need to make sure I don’t let things go for twelve hours again….

Updates In Email

Email:

RSS Feeds

l