Sorting DVDs

So there are plenty of ways to arrange your DVDs, if indeed you chose to arrange them at all. The most popular one would probably be alphabetically. Alternatives may include arranging by release date, by director, actor, genre..

At one point there was some logic to the arrangement of my own DVD. But as I got more DVDs and less space, it mostly devolved into piles, arranged roughly based on the order they were bought in, and which were watched most recently.

If I ever get time, I will re-sort them.


I accept that alphabetical may be considered 'best'. In particular, if you have a significantly large collection, it can be the most efficient approach, and makes locating any given film much easier.

Now, ordering things alphabetically is usually considered quintessentially 'OCD'/fastidious behaviour. Though there is dispute over whether liking your DVDs (and things in general) to be in order really is, or should be, considered 'abnormal'.

My point is, I could do much worse.


First of all, I think, in general, films by the same director should be kept together; particularly when it's a notable director, say, Tarantino, Kubrick, Burton.. So you could group and sort groups alphabetically by director.

I would say that films of similar genre/theme/styles should be kept close as well - noting that films by a given director will generally stay close together when this criterion is applied.

And while you're at it, why not take into consideration: actors, writers, based on works by, producers, scored by.. Basically, there are a lot of potential connections which may be considered.


So I'd like to put forward two approaches:-



1) Salesman Sort

For this approach we take into consideration 'most meaningful connections' between films, and based on that, attempt to determine which films most belong together.

So, for a given set of films, we build a network graph where pairs of films are connected if they share a common director, actors, theme, etc.

Doing this for Tim Burton films, based on actors only, will give something like this

[NB/ There may be connections missing.]

Or like this without the actor nodes

The connections between films are then weighted based on how 'meaningful' they are.

For example, Moon and American Beauty both star Kevin Spacey. Fight Club and Choke, on the other hand, have no actors in common, but were both based on books by Chuck Palahniuk. I would argue that the connection in the latter case is more meaningful - and so should get a higher weighting - than that of the former.


Now, the trick is to find a way of translating this graph into an arrangement of films. It turns out, this is as 'simple' as running a Traveling Salesman algorithm on the graph.

The traveling salesman works like this - find a path around a graph which visits every node exactly once, while minimising the distance traveled.

In our case, we actually want to find a path which (effectively) maximises 'distance', since that will lead to the more significant connections being chosen by preference.

In the above graph, the connections haven't been weighted, so we can pick any path - for example

But ideally, the connections would be weighted first so that the path (and by extension, arrangement) chosen is more meaningful.

Once a path is found, this is turned into an arrangement by simply looking at the order in which the nodes (films) are visited.


The biggest problem with this approach is forming the graph in the first place. One possible solution is to write a program which can pull details from, say, imdb to build connection. Then you'd also need to come up with some system for weighting - which may vary from person to person, depending on their particular preferences.. So it's tricky.

By comparison, the Traveling Salesman part is relatively straight forward, given that it already has well establish (if potentially slow) algorithms for solution.

This approach can also throw up some eccentricities. For example, films by a common director may be split up by a film which has few other connection elsewhere in the graph. This is why I would advise 'fine tuning' by hand.

Similarly, it's possible that the addition of new DVDs to the collection may lead to a major re-shuffle being required. Obviously, how major or minor the re-arrangement depends on how well the film fits in with your pre-existing collection.



2) Hierarchical Grouping and Associative Sorting

This is actually the approach I started out with, before it went to shit.

You might start by grouping by director. Then you might group directors by genre/theme/style. And within the bigger director groups, you might sub-group by actor. And so on..

In particular, the 'hierarchy' is constructed so that some groupings get priority over others. For example, films with the same actor might be split up when those by the same director need to be kept together. (This will depend on how you chose to structure your hierarchy).

Then, within and amongst, DVDs and groups can be arranged according to alphabet, release date, genre, .., even by colour of cover. This is where the 'associative' part comes in. Ultimately, it can come down to how your own demented logic associates and puts things together.

When I was sorting mine, I did end up with some fairly esoteric, and sometimes laboured groupings and connections in places. But you can see some overall logic in it - e.g.

Nightmare Before Christmas / ... / Sweeney Todd / From Hell / ... / V for Vendetta / ... / X-Men..

In this case - Tim Burton, Johnny Depp, Alan Moore, Graphic Novels, and so on. Note that there is overlapping between adjacent groups. They were then sub-sorted so as to be grouped by theme, and so that they formed a natural thematic progression from one group to the next (as much as possible).



Or if you prefer, you could just arrange them alphabetically. Your call..



Oatzy.


[To be honest, I wouldn't recommend either.]

The Cost of Loyalty

So if you have a loyalty card for, say, Costa you will get 5 points for every pound you spend. One point is worth 1 pence, so you're effectively saving 5p from each £1 you spend - a saving of 5%, right?

Yeah, it's not that simple.

For one thing, if you think of it as paying full price then getting 5p back per £1, then there's the restriction that these 5 pences you're 'saving' can only be spent in Costa. Also, you only get points for the whole pounds you spend (not the pence).

So what are you saving?

Think of it this way - let's say every time you go to Costa you buy the same thing, spending the same amount of money each time.

The question then is, how many visits does it take to earn enough points to get your usual order for free?


Okay, so we have our usual order, with price P. The amount of money you 'save' (in the form of points) per visits is 0.05*floor(P). The floor function - f() from now on - rounds the price down to the nearest pound, since you don't get points for pennies.

So we want to find the number, N, of purchases we need for the total points value to be greater than or equal to our order price P. In other words:

0.05*f(P)*N = P

or  N = P/(0.05*f(P))

Now, lets start by looking at the simplest case, where P is an exact number of pounds - i.e. P = f(P)

In this case, P and f(P) cancel each other out, so N = 20. Notice, regardless of whether your order is £1 or £20, it will always take 20 visits to get one 'free'.

More generally, the equation becomes N = ceil(20*P/f(P))

Where ceil is a function which rounds the value up to the nearest whole number. Because there's no such thing as a fractional visit, unless you count a visit in which you spend less than usual. Anyway.

Okay, so lets look at an example - a pot of tea costs about £1.60. So we work out N = ceil(20*1.6/f(1.6)) = ceil(32/1) = 32 visits. And just to check, for a pot of tea you get 5 points per visit (5p), and 32*0.05 = 1.60 = the price of a pot of tea. Perfect.


Now. What about savings?

In the tea example, you're buying 32 pots of tea and getting one for free. Which isn't a great saving, but it is a saving nonetheless.

So, the total amount you spend is P*N, and you're getting N+1 pots. That means the effective price per cup works out at P*N/(N+1).

For tea, that means you're effectively paying ~£1.55 per pot - a saving (S) of 5p per pot. What's that saving as a percent? Without going into too much detail, it turns out it's %S = 1/(N+1).

Which works out at 3% for tea. Which is less than the 5% saving you might have expected.


Incidentally..

The example for when the price is an exact number of pounds turns out to offer an effective saving of ~4.76%. Which, again, is less than 5%, but a little better. This, by the way, is also the maximum % saving you can achieve with a Costa card.

In general, the % saving is much worse when the pence amount of P is high and the pound amount is low - the worst case being when the price is £1.99. This would require 40 visits to 'get one free' and offers a saving of only 2.4%.

So based on best and worst case scenarios, we can say that your % saving will always be between 2.4% and 4.8%. Similarly, visits required to get one free, N, will always be between 20 and 40.

[In fact, the absolute worst case is when P is less than 1, in which case you never get any points.]


But to clarify..

This 'saving' is the saving over what you would have paid if you bought N+1 pots of tea and didn't have a loyalty card - i.e. not getting the N+1th one for free.

But what if you could spend the money you saved on something else?

Think of it this way - you've bought N pots of tea, and thanks to the loyalty card, you've saved the equivalent of the cost of one more pot of tea (£1.60). In this case, the saving per pot bought would be P/N. For the pot of tea, that's 1.60/32 = 5p.

To get the percent saving (per order), we divide this number by total price, P. For tea that works out at 3.1%. In fact, this is equivalent to the point-value saved per purchase, divided by the full order price - i.e. 0.05*f(P)/P == 1/N

So for the whole-pound values, this does, in fact, work out at a 5% saving. And the worst saving is still for £1.99 purchases, now working out at a 2.5% saving.


One more thing

All of this also goes for Tesco, and Waterstones, and wherever else does money-for-points loyalty cards too. You just replace 0.05 with however many points you get per pound, divided by 100 (e.g. Tesco = 0.01).

If we call this value rho (which looks a bit like a lower-case p), then the general formulas are:

But again, we're assuming you spend approximately the same amount (P) every time you visit a given place. If not, things get tricky. For a rough estimate, one thing we can try is using an average per visit spend (Pbar).

One other thing we can do is replace the P on the top of the fraction with a target points/saving; replacing f(P) with f(Pbar) if necessary.

So, for example, if the average order (Pbar) is £3.55 and you want enough points to get a free slice lemon cake (£2.50), then it will take N = 17 visits.


Oatzy.

Playing with Pac-Man

What the Puck?

For those unfamiliar, Pac-Man is an old arcade game, where you play as a cheese pizza trying to collect pellets while being chased round a maze by four whimsically named ghosts. Although really, if you are unfamiliar with Pac-Man, there's something wrong with you. Anyway, you can have a play online here.

The four ghost are Blinky, Pinky, Inky, and Clyde. For a good explanation of the ghosts' behaviours, here's a post from the tragically short-lived 'Game Internals' blog.

tl;dr Blinky chases, Pinky ambushes, Inky teams up with Blinky, and Clyde does pretty much whatever the fuck he wants. But really, you should read the article.

And as for the origin of the name, I'll let Scott Pilgrim explain. Or if you prefer to read, wikipedia.


Wakking Round in Circles

Graph Theory is a fantastic area of maths. Graph Theory can find you the shortest route, help you get out of a maze, tells you how to colour a map so no adjoining regions are of the same colour, to reconstruct DNA fragments, and help you find the best route for sight-seeing. Among many other things.

But sadly graph theory tends to be covered more in Computer Science courses than Maths courses. So for myself, i have to be content with books and the internet. Not that I let such thing hold me back.


So the question is this - Find the optimal route around the Pac-Man maze

What we want to do is find a route around the maze while collects every pellet. Or in graph theory terms, a route which travels along every edge at least once.

First of all, we need to turn the maze into a network graph. For this, we place a node at each junction, and join pairs of nodes according to whether or not there is a direct route between the pair.

So here's what the maze looks like, beside what the graph of that maze looks like.

The blue edges are the ones with pellets. The red edges are the ones without pellets, which you don't necessarily have to visit.

And we can assign to each edge a 'weight' - i.e. the distance (in grid squares) between the pairs of nodes

Now, first of all, we note that there are a lot of node where an odd number of edges meet (with odd degree). What this means is that the graph is not Eulerian - what that means is, there doesn't exist a route around the graph which visits each edge exactly once.

Which means that we will definitely have to travel along some paths more than once.


So the optimal path is going to be the one which minimises the total distance traveled. This is an example of the Chinese Postman Problem, and fortunately, there is an algorithm for finding the shortest route.

Without going into too much detail, what you do is pair up odd nodes, and find the shortest paths between them (using Dijkstra's Algorithm). This makes the graph Eulerian, i.e. so that a route that visits each edge at least once exists.

So if we take the bottom corner as an example, there are four node of odd degree (green).

By finding the shortest paths between pairs of odd nodes (red), we can make this mini-graph Eulerian - i.e. so all nodes have even degree. This means we can find the optimal tour around the graph (right). In this case we have to travel an additional 12 units.

Of course, it gets more complicated when you're working with the full Pac-Man graph.

When there are more than two nodes of odd degree, you also have to find the combination of pairings which minimises the total tour size. For an idea of scale, there are 20 odd nodes in the Pac-Man graph. That means there are 654,729,075 pair combinations to check and compare. And you have to run Dijkstra's algorithm 10 times for each of those permutations. It adds up.


So instead, I took the essence of the algorithm and constructed a route by hand. This is not necessarily the optimal route. For this route, you have to travel an extra 60 units - including 9 units along a path segment that doesn't contain any pellets.

There are other paths around the maze which cover (and recover) the same same ground as the above solution, and others that double back over different ground, but that add up to the same distance.

One constraint, in the case of Pac-Man, is that the path has to start at the point near the bottom of the maze, where Pac-Man starts in the game.

But also, it doesn't matter where the tour finishes (where as, the Chinese Postman starts and finishes at the same point). This means modifications to the 'optimal' solution may be possible/required.

In the bottom-corner example, we can eliminate some of the extra paths (up to 9 units worth) if we don't care where we end up.


If I ever get around to programming and running the proper algorithm, I'll let you know what the 'proper' solution is. And if you can find a better solution, let me know.


Of course what I haven't taken into account is the fact that, as you're making your way around the maze, you're also trying to avoid ghosts. I'll be honest, this path finding was more of an intellectual exercise than anything practical. You can find some strategic tips here.


This Maze Ain't Big Enough For the Both of Us.

If you follow me on Twitter, you may have already read about this - in a dream I formulated a multiplayer version of Pac-Man. But weird, subconscious machinations aside..

I looked it up on wikipedia, and there was already a multiplayer Pac-Man - Pac-Man Vs. But in that game you have one player playing as Pac-Man, and any additional players as ghosts. The aim is for the Pac-Man player to collect pellets and for ghost players to stop them. My idea is better.

First of all, you'd probably need to make the maze bigger. Each player plays as a Pac-Man, and like the normal game, their aim is to collect the most points, while trying to avoid ghosts. The game introduces a new special pellet which lets you cannibalise an opponent Pac-Man (much like the pellet that lets you eat ghosts).

Each player starts with two lives. If they lose both their lives they become a ghost. As a ghost, other ghosts can't hurt you, but you can't collect any pellets. If you catch an opponent Pac-Man, you steal one of their lives (becoming a 'living' Pac-Man again, with one life). If an opponent Pac-Man gets one of the special ghost pellets, they can eat a ghost opponent, killing them for good.

The game ends when all the pellets are collected or when all players are ghosts/dead. The winner is the player with the most points.

Or something like that.

If only I have the know how to make a real, playable version. But, hey, if there happens to be anyone out there reading this who could make it, please do..


Oatzy.

Picking and Scoring Words for Hangman

Hangman, for those unfamiliar, is a popular way for primary school teachers to teach spelling in the guise of a fun guessing game, and a way for secondary school teachers to pass the time at the end of term when they can't be bothered with teaching.


It Works Like This..

In a dystopian future where the powers that be like to play deadly games with their political prisoners, Hangman sees one such prisoner, 27 year old Adrian Silk, standing on a platform in front of a cheering crowd; his crime - logical thought.

Adrian is presented with an unknown word - 9 letters, title of a 21st century movie - and his task is to determine that word by guessing letters.

With each correct guess he gets closer to discovering the mystery word and winning a stay of execution. With each incorrect guess, another piece of the gallows is built. If he can't reveal the word before the gallows are fully constructed, he'll be dancing a dead man's jig for the crowd.

He starts by guessing the vowels - A, E, I, O, U - two incorrect guesses, two pieces of the gallows built: I__E__IO_

He guesses some common consonants - N, R, S, T - two more incorrect guesses, but still safe: IN_E_TION

Adrian stops to think - "are there any films called INFECTION? There are two, but they're pretty obscure.. Wait..!". And he hazards a guess - INCEPTION ..?

He's right! Adrian jumps for joy, and breathes a sigh of relief. And as the disappointed crowd jeers, Adrian is shot between the eyes by the Games Master - found guilty of the logical thought with which he'd been charged.

Still, if you think that's bad, you should see how they play KerPlunk!


Lets Play a Guessing Game

Okay, imagine you were guessing letters for an unknown word. But in this variation on the game, the hangman will only tell you when you've won, or else when you've run out of letters. That's all the information you get, nothing else.

The simplest approach to finding a word would be to just work your way through the alphabet - 26 letters, a maximum of 26 guesses to uncover any word.

But there will be a limit on how many incorrect guesses you can make - usually around 10. This means that, unless the word you're guessing contains 17+ unique letters this probably isn't the optimal approach.

So with no feedback and a guess limit, all you can do is guess letters 'at random'. But some letters appear more often in the English language than others. So you can make educated guesses, and go for the more common letters first: E, T, A, I, O, N, S, ...

If we assume that the probability, p(ci), of a person guessing a given letter is roughly equal to that letter's frequency in the English language, then the probability, big P, of that person guessing a correct letter in a word equals the sum of the probabilities of each unique letter in that word.

For example, in MISSISSIPPI, the unique letters would be {I,M,P,S}, so

P(MISSISSIPPI) = p(I)+p(M)+p(P)+p(S) = 4.025% + 2.406% + 1.929% + 6.327% = 14.687%


What this immediately suggests for choosing words is:

1) Words with 'uncommon' letters are better

Uncommon letters have lower probability p(ci), so will make totals lower. E.g. C is less common than H, so (in the game described above) CAT is harder to guess than HAT

2) Words with fewer unique letters are better

If there are fewer (and smaller) targets, it's harder to hit one of them by just firing at random.


Parting Words

So what about in a real game, where you get lots of feedback - which letters are right or wrong, where each letter appears and how many times.. This makes deduction a lot easier.

Have you ever tried to cheat at a crossword? There are loads of 'helpers' online - put in the pattern and see what possible words match it. Well for hangman we take that a step further.
Say our pattern is E_UA_I__; there are 5 words it could be - EQUALITY, EQUALING, EQUALISE, EQUATION, EQUATING

First of all, EQUALISE is not a valid solution because it introduces an extra E. And if we'd guessed all the vowels to get that pattern, we can also rule out EQUATION since we've already determined that O doesn't appear in the solution word.

So to put it more concisely - we want to find words that match a given pattern, eliminating those which contain extra letters already guessed.

In the case above we're left with 3 words - EQUALITY, EQUALING, EQUATING - and which of the three the correct word is can be determined by guessing the letter T:

1) E_UA_IT_ which can only be EQUALITY
2) E_UATI__ which can only be EQUATING
3) T doesn't appear in the word, in which case it can only be EQUALING

The fact that T is the most common consonant probably means each of those 3 words are poor choices for hangman. This is an example of a low entropy pattern.

Imagine, instead, that you're presented with a 3 letter word, and you've gone through the vowel and found you're left with the pattern _A_

What could that be? Maybe you guess T next and get _AT - well that could be BAT, CAT, HAT, RAT, .. Or maybe T is wrong, then the word could be MAN, CAN, BAY, RAY, WAX, TAX, .. how many guesses have you got left?

In fact, there are 179 possible words which match this pattern. This would be a high entropy pattern.


So, more tips for picking good words:

1) Pick obscure words

Even if there is only one word a pattern could fit, if the opponent doesn't know that word, then they are forced to keep guessing letter-wise. Which makes things a little more tricky.

2) Pick shorter words

There are more 3 and 4 letter words in the English language than 8 and 9 letter words.

3) Avoid too many repeated letters

For example, MISSISSIPPI only has 4 unique letters, but once you've guessed I and S, you've uncovered 73% of the word, and there's really nothing else _ISSISSI__I could be.

4) Pick words with high entropy patterns


A Question of Uncertainty

In Information Theory, entropy relates to the uncertainty in a piece of information. It's measured in bits, and, for a set of equally likely outcomes, is calculated as the base two logarithm of uncertainty.

So a coin toss has an uncertainty of 2, because there are two possible, equally likely outcome. That gives an entropy of 1 bit. For a given character in a word, if we assume all letters are equally likely, then there is an uncertainty of 26 - so that gives an entropy of log2(26) = 4.7 bits.

But as pointed out above, all letters are not equally likely in the English language. So the entropy is more complicated to work out: H = -SUM[p(ci)*log2(p(ci))]. Anyway, it turns out the entropy of a given unknown letter is 4.18 bits.

In the case of word patterns, we work out entropy as log2 of number of valid words matching the pattern, since all matching words have the same probability of being correct.

For the low entropy example above, there are 3 possible words that match the pattern so that would give an entropy of log2(3) = 1.58 bits. The 3 letter, high entropy example, on the other hand - with it's 179 possible solutions - would have an entropy of 7.48 bits.


So Where Does This Leave Us?

The idea is this - to come up with a scheme for scoring the 'quality' of a word in terms of how hard it is to guess in a game of hangman.

First, we score our word by its letter, as described above, to get the probability of guessing a correct letter. We then take one minus this to find the probability that a letter guess is wrong - the lower the probability of guessing a correct letter, the higher that word's score.

Entropy has a well define method of measurement in Information Theory, as discussed above.

But if we measure the entropy of a word before any letters are guessed, we find that all words of the same length have the same entropy. So instead, it would be more useful to measure a word's entropy after, say, some common letters have been filled in. Since most people start by guessing the vowels, that is what I'm going to go with.

In some cases, there are so many possible pattern matches, that you'd do better to simply make educated guesses at letters until the solution is found. For this, we work out the letter-wise entropy. Again, before any letters are guessed, all words with the same number of unique letters have the same entropy.

So. Each unknown, unique letter in a word can be one of those not already guessed. So we can work out the entropy, H(alpha), of the alphabet, sans the letters already guessed. Then, multiply that by the number of unique letters left to find, n.

So for example, if we guess the vowels and get the pattern _A_, then the entropy is  2*H(consonants) = 5.62 bits


From a Practical Stand Point

To work out the word entropy we can download a dictionary, then write some code which will find and count the words which match our required pattern, excluding those containing already guessed letters.

We then find the 'smallest maximum' entropy - which of the character entropy and the word entropy is smallest. In most cases it'll be the word entropy.

And finally we multiply that by the probability, one minus big P, to assign to each word a score:

(1-P)*min{H(W), H(C)}

Or you can use this code.

In and of themselves, the scores this gives don't have any specific meaning - the exact score for each word will depend on your choice of dictionary and initial guess letters. But so long as you use them consistently, the scores should stand as an indicator of each word's relative 'quality'.

For example, by this system, CAT gets a score of 5.3, and EQUALITY gets a score of 1.4. So CAT is a much better hangman word than EQUALITY.


So What's the Best Word

JAZZ, apparently. In fact, while researching this blog, I came across a few other people's attempts to find the best words for hangman. Pleasingly, they went with different approaches to me.

In fact, JAZZ never occurred to me when I was thinking up random good words. The best I thought of was WAX. Also reassuring is the fact that JAZZ does score highly under my system - 6.07 - and scores only slightly better than WAX, with its score of 5.92

QUIZ is an interesting word. It contains the two least common consonants and the two least common vowels (P=9.89%). But there are only 12 words that match _UI_, so it has low entropy. Its final score is 4.13 - lower than that of CAT, with its more common letter set (P=20.0%).

Similarly GYM; it has P=6.34% and has no vowels, but there are only 29 words it could be, so has a score of 5.48. Or MY, with P=4.38% but only 5 possibilities, score 3.18. So it's a matter of balance between probability and entropy.

Ideally, I'd have run a whole dictionary through my system to look for a list of best words. But I didn't. You can if you really want. Otherwise, I'd recommend one of the blogs linked above for lists.


In Summary

So there you go. You can score some of your own words if you so wish. But for on the fly word assessment, just remember, pick:

1) Words with 'uncommon' letters
2) Words with fewer unique letters
3) Obscure words
4) Shorter words
5) Words with fewer repeated letters
6) Words with high entropy patterns

And if you're trying to guess a 4 letter word with an A in the second position, odds are someone is trying to outfox you with JAZZ.


Oatzy.


[Full disclosure: If I got the information theory stuff wrong, it's because I only know as much as the one chapter of this book, and odd bits on wikipedia.]

Su Doku Solver

Cold Hard Logic

Let's be frank, Su Doku solvers are dime a dozen. My favourite is the one in Google Goggles - you point your camera at a puzzle and it uses OCR to interpret it, then solves it for you. None of that faffing with inputting the puzzle by hand. Anyway.

At the most basic level, computers run on maths and logic. So logic puzzles should be easy for computers to solve - it's just following a collection of logical rules. No creative thinking required.

The problem are,

1) Inputting a problem in a form that the computer can parse (understand)
2) Translating the logical rules into a form the computer can apply
3) Applying said rules to a given input problem to find its solution.

Here's the main puzzle I'll be using as the example for this post [source]. Feel free to try and solve it yourself before continuing (it should be easy).

The Rules

So what are the rules? In the traditional version you're presented with a 9x9 grid, with some numbers already filled in. The idea is to enter into the grid the numbers 1-9, so that each number appears only once in each row, column, or box (3x3 square).

So that's fairly straight forward. But in that particular form, the rules are really only good for checking if your solution is right.


Brute Force

This can be use in a brute-force approach to solving, e.g.

1) Stick numbers in empty squares at random
2) If any of the numbers break the rules, try again
3) Repeat until the right solution is found.

But that's incredibly inefficient and inelegant, and certainly not the way it's solved by people in the real world.

As an example, say our placement technique is this - take the numbers missing from each row, and just shuffle them around within their given row.

[There are probably better brute-force methods.]

If we use this approach on the puzzle above, there are ~4.95E26 possible number placements (permutations), of which only one is correct. Say our computer can check 1 billion solutions per second, it would take 16 billion years to solve. Which is about 2 billion years longer than the current age of the universe.

As a ball park estimate, the general formula for the number of permutations for a grid of side n is given by -> ((n-a)!)^n  - Where a is the average number of numbers already placed in each row.

If, for example, we try to solve a 16-grid with a=8 (half the numbers already placed), then the number of possible permutations is a mind-meltingly inconceivable 4.88x10^73. At 1 billion checks per second, that would take 1.5x10^57 years to solve - 1 billionth the lifespan of a black hole with the mass of the sun (according to wikipedia).

This is an example of a non-polynomial time (NP) algorithm. More on that later.


Rewriting the Rules

The rules can be re-interpreted and applied in two fundamental ways

1) Which is the only square this number can appear in?

That is, a particular number has to go in one particular square, because if you try to put it in any other square in that row (or column, or box) it will break the rules.

This is the most common approach in real world solving - that is, "three can't go in that row, or those columns because they already have threes in them, so it must go there" sort of thing.

2) What is the only number that can go in this square?

That is, if every other number already appears in the same row, column, or box as a given square, then that square can only be one particular number.

This is most obvious in the case where every other number in a given row is already filled in, but can also be used by considering all the rows, columns and boxes a square belongs to.

This tends to be required more in the harder puzzles; you could probably solve the above puzzle by Rule One alone.


Setting Up The Problem

First of all, we create our grid. We can refer to each square in the grid by a sort of coordinate - (i,j) - with the square in the top left corner being (0,0) and the square in the bottom right being (8,8)

We reference Row i as the set {(i,j) : j in [0,8]} and Column j as {(j,i) : j in [0,8]}

For boxes, we note that the index for the top-left square of each box are multiples of 3 - (0,0) (0,3) (0,6) (3,0) etc. So, Box (m,n) is given as {(3m+i,3n+j) : i,j in [0,2]} for m,n in [0,2]

So from this we can, for example, check the correctness of a puzzle (by rows) like this:

for i in range(0,9):
    for j in range(0,8):
        for k in range(j+1,9):
            if Grid[i][j] == Grid[i][k]:
                return "incorrect puzzle"

Checking columns and boxes works similarly.


If we have a fancy GUI, then inputting and parsing the grid is pretty straight forward. But we don't. So instead, we input the puzzle as one long string -> puzzle = "???36?9???2?.."

The first row is given by the characters (numbers) numbered [0,..,8], the second row is [9,..,17], and so on. In general, row i is the set of characters with index [9i,..,9i+j,...,9i+8]. 

Parsing our puzzle into the Grid works like this then:

for i in range(0, 9):

    for j in range(0, 9):

        Grid[i][j] = puzzle[9i+j]

And so on..


Applying the Rules

Now, if you've done Su Dokus, you might be familiar with the technique of filling each square with the numbers one to nine and eliminating numbers as appropriate. That's basically the bulk of how this solver works:

1) Assign to each empty square ("?") the set [1,...,9]

2) For each number in a given square's set:
    a) Check to see if that number is already fixed in another square in the same row, column, or box as the square in question. If so, eliminate the number from that square's set.

3) Repeat for all squares in the grid

From there, we can apply Rule Two:

4) For each square:
    a) if that square's set contains only one number, fix that square's value accordingly.

5) Go back to (2). Repeat until no more squares can be fixed.

You can actually created a shortcut for this - create a collection of sets for each row (etc.), which contain the values already fixed in that row. That way, instead of checking every square along each row for fixed values, you just check in that row's set. (Trust me, it's easier.)

Applying Rule One is easy as looking along each row (or column, or box) to see if a given number appears in only one of the squares.

Or more technically,

1) For a given row (etc), for each number 1-9:
    a) count how many times that number appears in square sets in that row
    b) if a number's count equals 1, fix the value of the square it appears in accordingly.

2) If you fix any new squares this way, go back to (2) to see if that will allow you to set any more squares.

You then just loop through rules One and Two until the puzzle is (hopefully) solved.


One More 'Rule'

In fact, this is just Rule Two, but with an added 'quirk'.

Here's what happens if you apply the method, so far, to a more difficult puzzle

This is where the program gets stuck. What do you do from here? If we focus on the bottom-right corner box

Notice there are no squares that can take only one value, and no values that only appear in one of the squares.

But look on that bottom row - the circled boxes can only take the values 3 or 5. What this means is that 3 and 5 can't go in any other of the squares in that box. So we eliminate 3s and 5s from the other squares in that box. Similarly for the 1/6 squares in the middle.

We now have the square in the top-right of the box that can only be 8, and the middle-right that can only be 9. So we fix those values. And from there, it's pretty straight forward to solve the rest - going back to looping through Rules Two and One.

Not only is it tricky to spot in real world solving, it's also tricky to translate it into computer logic. It mostly involves looking for pairs of squares in a box (etc.) which have matching sets of size two (or triplets, size 3, or etc.). Fortunately, this sort of thing doesn't come up often.


A Note on P versus NP

So as mentioned above, it's easy enough to apply the standard rules (as states) to check if a solution is correct - you just check to make sure no number appears more than once in any given row, column, or box.

It turns out, checking the correctness of a puzzle can be done in polynomial time (fast). For a grid of side n, the time required to check a solution* is given by -> 3(n^3 - n)/2

..Multiplied by the amount of time it takes a computer to work out if 2 numbers are equal or not (call this time t). So for a 9-grid, that time is 972t.

For a grid of side n=100, the time is ~1.5million t. Which on a modern computer is peanuts. For example, if our hypothetical computer can check 1 billion 9-grids in one second, then it can check 650,000 100-grids in a second.

By comparison, actually solving the puzzle - by the method outlined about, and by all other known methods - is done in non-polynomial time.

What this means, is that if you apply this algorithm to a larger grid - say, a 25x25, or a 36x36 grid - then the amount of time it will take to solve the puzzle increases rapidly (exponentially), to the point where a puzzle couldn't be solve in the lifetime of the universe.

But, since checking the puzzle for correctness is polynomial, even if the puzzle took longer than the life of the universe to solve, you could still check to see if the solution is correct (that no number appears more than once in each row, etc) in a reasonable amount of time.

As mentioned above, the brute-force method outlined is non-polynomial (NP). Notice that it takes catastrophically longer - 70 orders of magnitude - to solve a 16-grid by brute-force, than it takes to check the solution to a, much larger, 100-grid.

Admittedly, I don't know what the time function is for the method outlined above. But suffice it to say, it's more efficient than the brute-force, but still non-polynomial.

What P versus NP asks, then, is

if the solution to a problem can be checked in polynomial time (quickly), then does there exist an algorithm that can solve the problem in polynomial time?

At present, this is one of the great unsolved questions of mathematics and computer science, and a proof of whether or not P=NP will earn its discoverer $1million...


Where's The Code?

You'll probably have noticed, I've given a general, hand-wavy outline of how a program would work, and only given odd snippets of code.

I did write a solver in Python a few years back. I'd taken a Java programming course in my first year at university, and when the lecturer discussed a tic-tac-toe (naughts and crosses) playing program, it gave me the idea of how to represent a grid in a way a computer can parse. It also made me realise that there is actually a point to object-oriented programming.

Anyway, long story short, I wrote the solver 3 years ago. It's kind of sloppy and inelegant. And it can't handle the 'tricky' puzzles - although, oddly enough, according to my notebook, I had worked out a way of implementing it, but apparently never did.

Or to put it another way, it works, but compared to the myriad others out there, it's nothing special.

If you're interested, as I mentioned at the beginning there are plenty of other solvers out there. They might not work according to the methods discussed in this post. But you should at least have an idea of how one might work, now.

And as a final note, these methods can also be used for hand-solving. It's generally not necessary to be so rigidly systematic, though. It's easier for humans to pick out number placements at a glace, without having to go through the whole set-and-elimination approach.


In Case You Were Interested

Here's the solution to the Su Doku at the top of the page

You're on your own with finishing the other ('difficult') one..


Oatzy.

Quick Look: Don't Blink..

"..Don't even blink. Blink, and you're dead!" threatened the frustrated photographer, following a fifth failed photo..

No, this isn't a Doctor Who thing (sorry). No, this is based on another lost article I read a while back:

How many photos do you have to take in order to get at least one where no one's blinking?


First things first, what's the probability of one person blinking when you take a photo of them?

Well for one thing, that's going to vary depending on environment, lighting, etc. And also on the shutter speed of the camera being used to take the picture.. But for simplicity, I'm ignoring all that.

The average person blinks around 10 times per minute, with an average blink lasting 300-400 milliseconds (call it 350ms). So in any given minute, the average person's eyes will be closed for a total of 3.5 seconds.

We'll say the shutter is open for less than the duration of a blink. So the probability of a persons eyes being closed while the shutter is open -> p = 0.058.

[I'll be honest, I'm not not entirely convinced that's right. But I'll go with it anyway.]

So the probability they don't blink -> (1-p) = 0.942


If you're taking a picture of one person, that's only a 5.8% chance of the subject ruining a photo by blinking. So your odds of a good shot are pretty good.

But if we have a much larger group of people - n = 30 - the probability that none of those people blink while a photo is being taken:

p1 = (1-p)^n = 0.165

That's an 83.5% chance that at least one person will blink. Those odds aren't so good.


So if we take S number of photos, what is the probability that at least one of those is 'perfect'?

This goes back to the methods use in the Law Of Truly Large Numbers post - the probability of at least one perfect photo, big P, is one minus the probability that none of the S photos are perfect:

P = 1 - (1-p1)^S

So if we were to take, say, S = 5 photos -> P = 0.594

Bearing in mind that you have to make these 30 people stand around while you take your however many photos, an almost 60% chance of the perfect shot from 5 tries it pretty reasonable.

But let's say you're the panicky sort, and you want to be 90% certain that you have at least one perfect shot..?

Without going into the nitty-gritty, we can find S for P = 0.9, using some logarithms and algebra thus:

S = ln(1-P)/ln(1-p1) = 12.8 shots

And if you can get a group of 30 people to stand still for 13 photos, knowing that there's still a 10% chance you won't get that perfect shot, then more power to you.


When people know they're having their picture taken, they generally try harder not to blink. Especially if you use a count down. So the probability of blinking, and by extension, the number of photos you'd have to take, drops dramatically. The numbers worked out above are probably more applicable for candid shots.

On the other hand, maybe the flashing going off (if you use one) will cause some people to automatically blink. And, admittedly, I've taken pictures of myself that have still managed to get capture me mid-blink. Though that might be down to a delay between click and shutter.


Of course, in this day and age, of digital cameras with instant preview, you can just keep shooting until you get the photo you want. Not like the dark old days of film cameras and photo roulette...


Oatzy.


[The word 'blink' and its variants appear ~17 times in this post]

[As a random aside, working out the number of pokéball you need to throw to catch a given Pokémon is done in much the same.]

The Toilet Seat Conundrum

Gentlemen, do you leave to toilet seat up, or courteously put it down after use?

I read a (somewhat tongue-in-cheek) article a while back, I can't remember where, that explained the toilet seat conundrum in terms of game theory.  As best I can remember, it was quite clever. I was recently reminded of it when reading a Cracked article, and thought I'd try to recreate it, and - as is my wont - take it a step further.

Game theory, for those unfamiliar, is an area of maths/economics that studies 'competitive' interactions, "in which an individual's success in making choices depends on the choices of others".


Preamble

The (average) probability of the gentleman needing to 'sit down' when visiting the bathroom, we call p*. The probability of not is (1-p).

If the toilet seat is in the 'wrong position' for a given visit, we call the cost of this c1, and we assume that this cost is the same for both genders. This may not be strictly true.

The simplest cost would be in having to move the seat, typically in the form of mild inconvenience, and the potentially unpleasant experience of having to touch the underside of the seat. I'm also told that there are certain perils in visiting the toilet at the night, if the seat is in the upright position and is required to be otherwise. I can't say this is a cost I've ever experienced.

One might argue that the 'costs' are inconsequential; but for the sake of arguing, they aren't.

For the sheer hell of it, we'll call the woman Alice and the man Bob. Alice and Bob have been in a relationship/living together just long enough to quarrel over such matters. I suspect, for most people, this is a non-issue; but that's not the point of the post.

There is a third possible game, not discussed below, in which Bob can just leave the seat down at all times. In this case, we have c3, the cost of clean up if Bob's aim isn't quite up to scratch.

Oh, and there is a fourth game, where the default position of the the seat is upright. This is the worst possible game for Alice, and is only the best possible game for Bob if p<0.28. I can only imagine this game working in an all male household, and even then (a re-adjusted) Game One works out better.


Game One - Leave It As Is

Probability of the seat being down is the probability of Alice being the last to visit the lav plus the probability Bob was the last and left the seat down. Probability the seat is up is 1 minus the above.

Here's the cost matrix for this game

Where cost is c1 multiplied by the probability that the seat is in the wrong position

To get the total costs to Alice and Bob for this game, we work out

(Probability the seat is down x the cost if seat is down) + 

(probability seat is up x cost if seat is up)

And we can work out the ratio of costs

B:A  =>  2p+1 : 1

In the extreme case, where p=0 (Bob never poops), their costs are equal. But in all other cases, Bob's cost is greater than Alice's.


Game Two - Return to Default

Default meaning the seat is always returned to the downright position after use. The probability of the seat being up is always 0.

Here's what the matrix looks like

In this case, Alice incurs no cost. Bob, on the other hand, incurs double cost - when he needs to urinate, he has to move the toilet seat twice: up before use, and down afterwards.

It's obvious that Alice, once again, fairs better than Bob.

Game Three, mentioned in the preamble, works the same as this, but with 2c1 replaced with c3. Alice still comes out better though. Unless she doesn't like the thought of sitting on a toilet seat that's (potentially) been peed on - even if it is cleaned - in which case, there's some abstract cost to her.

If she doesn't mind, then which of games Two and Three Bob would prefer depends on which is smaller: 2c1 or c3.


Lowest Costs

First of all, we note that in both games Alice comes out better than Bob - incurring a lower cost in both cases. That said, Alice does better in the latter game, incurring no cost at all in that one. So Game Two is preferable to Alice.

But what about Bob?

If we take the cost ratio of game one to game two for Bob, this is what we get

B1:B2  =>  2p+1 : 4

In the extreme case of p=1 (Bob never urinates), Game Two incurs a greater cost for Bob (3:4) - and by extension, Game Two always incurs a greater cost to Bob.

THIS is where and why the conflict arises.

Alice prefers Game Two, Bob prefers Game One.


Tipping the Scales

So Alice would prefer to play Game Two, but she has to encourage Bob towards it. So Alice introduces a new penalty - c2 - for Bob leaving the toilet seat up.

The cost will typically be something along the lines of a bollocking, silent treatment, arguments, or whatever.

So what we do is this - the odds of Bob leaving the toilet seat up, and Alice being the next to use the bathroom -> (1-p)/2

Multiplied by the cost, c2, and added to the pre-existing total cost for game one

Now, we - or rather, Alice - wants the cost to be such that Game Two is preferable, i.e. B'1 > B2

Rearranging and simplifying, we get

c2 > 4c1(2p+1)

However, if Alice were feeling kind, she could introduce a 'reward' for putting the toilet seat down, instead. It works effectively the same - barring psychological, carrot/stick considerations.

For this, Alice would have to offer a reward, R, with

Arguably, Bob could introduce a new cost - or enticement - himself, to 'persuade' Alice towards Game One. But TV leads me to believe that this is seldom thought of, or executed.

This might be because Alice has more to gain/lose - in as much as, Alice can avoid any cost by 'playing' Game Two. Bob, on the other hand, incurs some cost in both games.

You can draw your own conclusions on that one.

In terms of a co-operative solution, if we add together Alice and Bob' costs in each game and compare, we find that Game One has a lower total cost than Game Two.

So one could argue that Game One is better overall. The challenge, though, is convincing Alice that that is the best solution for both of them, given that, from Alice' point of view, she does worse in Game One.


Casino Bathrooms

So this is all well and good, but it's kind of a specialised case - the situation of a house with one male, one female, and one toilet. In our house, for example, we have two males, two females and three toilets. What then?

There are a few other problems with the probability-based approach, as well. For one thing, it uses an average poop-probability for the gentleman. It also assumes both Alice and Bob use the bathroom about the same number of time during a given time period - whereas some people have more robust insides than others.

So for this, we create a Monte Carlo simulation.

[This is what we call excessive commitment to an idea.]

In the simulation, we create a 'person' object, and assign to them a gender, an average number of bathroom visits, and, for males, an average bladder to bowel movement ratio. To capture the day to day variability in number of visits to the bathroom, we use Poisson distributions.

We also create a 'toilets' set, representing however many toilets there are, and their current states -> 1 = toilet seat up, 0 = toilet seat down. Each toilet has an equal chance of being chosen for use by any given person at any given time.

Each person has a counter, which is incremented when the person in question has to move the seat. At the end, these counters are grouped by gender for comparison.


In the Middle of Our Street

So I created a 'house' of two males, two females, and three toilets (variables chosen arbitrarily). Then ran the simulation for 10,000 hypothetical days.

The Game One simulation gives a result of ~ 3.28 seat moves per male per day, and 2.27 seat moves per female per day. That's a male:female seat move ratio of 1.44.

The Game Two simulation gives a result of 9.11 seat moves per male per day - bearing in mind, men have to move the seat twice per standing visit, in this version - and women never have to move the seat.

Code here.

Fun fact: Without additional costs and rewards, Game One is always preferable to men, Game Two to women. Regardless of the balance of men and women in a house.

So now you know!


Of course, in some cultures the conflict never really arises, since it is 'the norm' for men to sit for all visits to the lavatory.


Oatzy.


*[inb4 shouldn't p be the probability of needing to urinate lol]

Social Posting - Part Two: We Post Together

Where were we..

So the main limit to the stripped down model in the previous post is that it only puts people into one of two states - posting, or not posting.

A more realistic model would take into account how much people are posting. The nice thing is, the change to the model is only minor - T no longer has the condition that makes its value has to be either one or zero.

The values T_i now represents the post rate of each user - that is, the number of posts posted during some arbitrary time period, n.

Here is the full, modified equation for the model

Two More Things

As you've probably noticed, we've introduced two new variables. They are:

2) Beta

Beta is a column matrix, with values represent each user's baseline post rate - that is, the rate at which a user would post if there was no-one else online - no audience, no-one to talk to.


1) Alpha

Alpha is a little more complicated. But loosely speaking, its values relate to the upper limit of each user's post rate (ignoring external effects).

It works like this: first, imagine everyone has some maximum post rate. Tbar (T with a line over the top) is the column matrix of these values. Now, suppose everyone is posting at their maximum rate. Alpha values are calculated by rearranging the model equation, thus

Any negative values in W are set to 0, since (in theory) a user has their highest post rate when any of their antagonist are not online.

What this means, is that post rates are capped by their appropriate upper limits; when all members of the population reach their maximum post rates, we find that T(n) = T(n-1) for all n - i.e. the post rates all remain constant, unless externally affected.

For technical reasons alpha is a diagonal matrix.

Alpha and Beta look like this

They won't all ways be size 4, of course. Their size will depend on the size of each particular network. The values of alpha and beta could vary over time, but for all intents and purposes, it will suffice to hold them constant.


Rainbow Graphs

Going back to the graph from last time, we might get a system equation like this

In this full model, it's not just a matter of online or offline. So instead of a series of network graphs, we represent the progression of a network as a set of line graphs.

What we find then is that the system described by this equation seems to tend towards some constant, stable point - regardless of initial conditions.

For example, with the equation described above, and starting at T(0) = [1,0,0,0] we get

And even if we start from T(0) = [100, 100, 100, 100], we get

In each case, the system converges to [15, 10, 5, 10] - Tbar - the maximum rates set when defining the variables for this system.


Interestingly, here's what happens when you set beta = 0 for all users - alpha values recalculated as [1.5, 1.11, 0.5, 1.11]

You get this weird bouncing about. It does seem like they're converging towards some fixed points. And it's converging to points roughly in proportion to Tbar, though much lower.

In fact, in online/offline form, the system looks like this

It's this early jumping on and off -line that causes the system to oscillate at first, before starting to settle down as time goes on.

We also see that, because the system starts much lower than its defined stationary point (Tbar), and because it doesn't have the boost of the base-rates, the actual stationary point the system is converging to is much lower.

If, however, T(0) were set to Tbar, then the system would have stayed constant at Tbar. Similarly, if T(0) were set to [0,0,0,0], then the system would stay there, since it wouldn't have the base-rates to get any of them off the ground.


Antagonistic Altercations

If we set up an antagonist system like that in the last post - with beta and Tbar as above, and conjugate alpha - we get a line graph that looks like this

In this case, the base-rates act to temper A's dislike of B, so that B stays online; though the result is that the stable point is lower than the maximum for everyone. The stable point for A is lowered the most.

But if we remove the base-rates (and recalculate alpha accordingly), the system progresses much like it did last time

That is, as soon as B shows up, A leaves - eventually followed by everyone else.


Upping The Tension

Now, what if we change the setup so that A and B both want to avoid each other.

One might question why two people who dislike each other would be 'friends' (in the social networking sense). I dunno. This is a hypothetical situation meant to demonstrate a point, god damn it!

Here's the system equation

Matrix of maximums, Tbar, stays the same as above at [15,10,5,10].

So if we set T(0) = [0, 10, 5, 10], here's what happens

A comes online because of their base-rate, and once they do, B disappears. Here's this system's initial and stable points

In antagonistic systems such as this and the one before, Tbar isn't a stable point.

In this case, for example, the peak rate for A occurs when B is offline and C is at their peak rate. But C is at their peak rate when both A and B are online. So if B is offline, C can't be at their peak rate, and as a result neither can A. And vice versa. So Tbar can't be achieved, since the tension between A and B pushes down the rates of everyone, themselves included.

The system does still stabilise however. It just to stabilises with B offline, and everyone else at a slightly lower rate in this case.


Now, if we do as we did in the previous blog, and take A offline (indefinitely), here's how the system evolves

In this case, the stable rates of C and D are lower than they were when B was 'forced' offline by A. And even though A isn't online, B isn't posting at their maximum rate.


Exogenous Effects

So as before, we also have to consider external effects.

People can suddenly, and unexpectedly disappear - maybe fall ill, get a job, or just not post for a while. Conversely they could find themselves in a situation where they're posting more - maybe because of a major news event, or because they're at work (procrastinating).

We can quite easily create these effects artificially, then observe how the model responds to that change. For example, we could gauge a person's importance (to a network) by removing them and seeing how dramatic an effect that has.

So in the antagonist examples above, we could say that A is more important to that network than B, since removing B had a greater (negative) effect on the C and D.


For this, we define some arbitrary function, E(n). We then multiply our model equation by this function

So for the example last time, where we removed two users C and D, then later reintroduced C, the function(s), E(n), might look like this

Or, if some major news story broke between n=2 and 5, then the function might look like this

So, if we were to, say, remove A (indefinitely) from the top system above, then the result would look like this

The important thing to note here is that even though B is the only person directly linked to A in the network, removing A from the graph lowers the rates of everyone.

Alternatively, we could double A

In this case, multiplying A by two brings everyone else's stable points up. It's also worth noting that A' stable point isn't just doubled, but multiplied by 2.7. This is a good example of the feedback effect mentioned at the start of the previous blog - increasing A' rate increases everyone else's rates, increases A' rate.

Or if we half A

In this case, everyone else' rates drop too, and A's rate stabilises at less than half it's maximum.


Agitated Antagonist

So what if we go back to our antagonist system, and start poking it...

First of all, if we half A

Then B is able to stay online, but with a stable point much lower than their maximum.

But, here's where things get interesting - if instead we double B, here's what happens

This time, they each scare each other off. But, once the other goes offline, they each come back in the next turn, only to scare each other off again. And so on. And all this jumping between extremes makes C and D jump about as well, but half a cycle out of sync.

At least, that's what happens for initial conditions [0, 10, 5, 10]. If we start with all at 0, the behaviour is nearer to that with no external effects.


In General

So it seems to be the case that externally changing one user affects (almost) everyone in the graph.

That being said, I would expect that when the model is generalised to much larger networks, we would find that the greater the distance between two users, the less affect they will have on each other.

It probably stands to reason then that, for a given user, it's only worth considering a graph as wide as friends of friends. Maybe friends of friends of friends for (a collection of) dramatic changes at that distance.

More in general, when you apply the model to a system of more than four people (as we've looked at here), you would expect things to get more complicated.

But the overall results should be similar - that is, in most cases the system will tend towards some stable state. It may just take longer to reach that point, depending on the size of the graph.


In Conclusion


So the long and short of it is this - in most cases, a group's post rates will typically converge towards some stable point.

If there aren't any antagonists, and if the base-rates aren't zero for everyone in the network, then the stable state will typically be the common maximum, Tbar. Otherwise, the system may oscillate, or else become stable at a much lower set of rates.

If we set all base-rates to 0, we find that the systems behave much like they did in the simplified online/offline model discussed in the previous blog; with some quirks of their own.

In the absence of base-rates, or in the presence of antagonists, initial conditions become important, affecting if and where the system stabilises.

When we consider external effects, the same will tend to be true - but with the stable points altered, according to what that effect is.

Modifying one user affects everyone else in the graph (to some degree). Modifying different users will have different effects on the rest of the graph, depending on the 'importance' of that user.

Of course, in the real world, external effects are unpredictable, and will tend to keep the system off-balance (unstable). But we do what we can.


Oh, and if you were wondering how I got the numbers for the graphs, here's the code I used. But be forewarned, it's very sloppy.


Oatzy.


[..and the fundamental interconnectedness of all users.]