DP and Markov Chain

Decided to give a little push on projecteuler. Almost 10 years since I actively solve problems. Many new problems have been added but the average difficulty drops a bit comparing to P200-300. This is good as the site does not necessarily serve the purpose of asking harder and harder questions to defeat the best math programmer, but a site where most can enjoy.

But the core idea has not changed: it's most likely about reducing complexity using maths plus some searching optimization. The math behind has been the same: everything about number theory plus a bit of geometry and combinatorics. On the searching side nothing changed as well: it's always dynamic programming -- if it isn't then probably the math part alone suffices to solve without the need to search.

Opposite to those purely mathematical problems, there are some purely computational problems too. Well, maybe not that computational like P345 "Matrix sum" where you find maximum trace (sort of) in a large matrix, but there are numerical problems with zero mathematical insight involved.

I wanted to use the example of cycle number aka friends of 142857 but there is still minimal maths behind like its relations to the numbers $10^k-1$ (which is also related to questions concerning repeating periods). But we can go much less mathematical. How about numbers that used all 9 digits? Primes with a particular appearance (not mathematical properties)? Fortunately there is a framework to solve those.

I solved about 20 problems recently and half of them done using the same framework. It's so handy that it's worth a talk, and perhaps it will guide you to solve those questions as well.

*

It is all about dynamic programming. When we first encounter DP we usually learn to solve backwards like all those shortest path problems. But it is also possible to recursively solve from the front. Mathematically there is a fancier name: Markov chain.

The idea is the same: we recursively calculate the state at each iteration till we need reach the end. We first define the initial state $A_0$. For each iteration we calculate $A_{k+1}$ from $A_k$ and extract information from the state if necessary. Terminating at $A_n$ would give the answer immediately. 

Example 1. Consider a simple random walk problem where an ant starts from position zero, where he can only walks by +2, +3 or -1 each turn with equal probability. There are traps on each odd (positive) prime where the ant will get stuck and stop moving. Can you give the expected position of stuck ants in 10000 turns?

A typical absorbing Markov chain. What's not typical is the randomly assigned "odd prime traps". Without those traps it's actually easy to find the chance for an ant to reach position $k$ at turn $n$: we have the equations $2a + 3b - c = k$ and $a+b+c = n$ with a dimension 1 solution space. Combining with the non-negativity condition should give a set of easily summable "ways". Adding across $n$ should give the chance of reaching the position on or before turn $n$...that is, without assuming the traps.

Instead, we set up a dictionary $X$ with a single value: $X[0] = 1$. In each iteration we read $X[i] = p_i$. If $i$ is not an odd prime, assign(add) the probability to a temporary dictionary $X'[i-1], X'[i+2], X'[i+3] += p_i/3$. Of course there are technical things to take care of like tracing the elements in $X$ if we cannot alter that inside a loop, but that should be routine to take care of.

Example 2. The same from example 1, except that the ant has a protective mechanism that allows it to land on a trap once and keep proceeding.

In that case, the state shall store another information other than the position: the number of times of traps that the any has stepped on. From $X[(i,j)] = p_{ij}$ where $i$ is not odd prime or $j \leq 1$ we send to $X'[(i',j')]$ where $j' = j+1$ is $i'$ is an odd prime.

Example 3. Consider a random binary array of length $n$. Compute the probability $p(n,k)$ of the array containing a monotone (i.e. just 0 or just 1) subarray of length $k$ up to a certain precision (call that a streak of length $k$).

Again a problem seemingly possible by direct calculation: fixing a subarray of length $k$ should give a probability of $(n-k+1)2^{-k}$, but you will face a wall of inclusion-exclusion consideration, plus the magnitude of numbers that you work with increases exponentially with $n$ and $k$.

Instead taking light from example 2, we only need two pieces of information: the last bit (also equal to bit in the recent streak) and recent streak length.

There will be $2k-2$ states in the form $(i,j)$ where $i \in \left\{ 0, 1\right\}$ and $0\leq j \leq k-1$. For each $X[(i,j)] = p_{ij}$ assign $p_{ij}/2$ chance to $X'[(1-i, 1)]$ and another half to $X'[(i,j+1)]$. If $j+1 = k$ sent that to the absorbing state instead.

In that way we can get arbitrarily accurate answer if we run every iteration manually, but $n$ can easily be much larger -- that's why we were merely asked for the probability up to a certain precision. We need an approximation.

Notice that a streak of length $k$ itself appears with a chance of $2^{-k}$. Even with the freedom of appearing anywhere in the streak, the range of $k$ so that $p(n,k)$ is non-negligible (i.e. not 0 or 1 rounded by error allowance) should be around $c\log _2(n)$. That is, sensible $k$ is very small comparing to $n$ for any reasonably large $n$. Then the chance of a $k$ streak appearing in an array of $2n$ bits is roughly equal to the streak appearing at either the first $n$ or the last $n$ bits. As a result we approximate $p(n, k)$ with $1-(1-p(\alpha,k))^{n/\alpha}$. 

The $\alpha$ is a threshold where we would like to simulate and should run in acceptable time. Take a large enough threshold and we should be done...right? Not yet. It seems like the approximates aren't precise enough. We can do, for example, 5 millions iterations at best within reasonable time. But that does not stop an error of order $10^{-6}$ from creeping around. We need the fix below:

Since this is an absorbing Markov chain the probability is strictly increasing (or decreasing depending on the way you view it) with $n$, and probability is moving at an exponentially decaying rate (you can verify this). We can exploit that to do an ad-hoc improvement: set a few checkpoints along the iteration to $p(\alpha, k)$ to approximate the convergence rate, then apply geometric sum to fix the probability in one go. It is likely to cause error of an order lower, but who cares?

And of course, we can apply the same idea to the dual of probability: success trials vs total trials. The same iteration method can be applied except we add them instead of splitting the chances.

Example 4. How many $20$-digit numbers (no leading zeros) such that no digit occurs no more than 3 times in it?

Well, partitions and multinomials should help better especially if we go way beyond such parameter. But what can we do without assuming those?

The states this time should be tuples $(a_0,...,a_9)$ where $a_i \leq 3$. For each iteration $X[(a_0,...,a_9)]$ is added to the states with one of $a_i$ higher by 1 (and still not exceeding 3). There are 9 initial states at the beginning representing the 9 single digit numbers. 

*

And that's it! I said at the beginning that the technique is widely applicable to many questions on projecteuler or other sites and that's not a bluff. Check the range P151-200 if you want a few easy scores ;).

Markov chains and DP aside, I just came across to the concept of semiconvergents when approximating $\sqrt{n}$ by fractions. Either I forgot everything about it on lessons or that it's new to me. I knew the convergents are the best approximations, but those marginally non-semiconvergents are so nasty! 

Suppose that $p_{k}/q_{k}$ are convergents for $\sqrt{n}$. Let $a_k$ be the corresponding continued fraction coefficients. It turns out that for any $[(a_k+1)/2] < r < a_k$, $(p_{k-1}+rp_k)/(q_{k-1}+rq_k)$ are better convergents than $p_k/q_k$ (but at a bigger denominator) called semiconvergents.

More interestingly, when $r = [(a_k+1)/2]$ the resulting fraction may or may not be a semiconvergent! I was so annoyed that such marginally non-semiconvergents are so close to the previous convergent that usual decimal calculation failed to distinguish them. I finally took the approach as follows:

Consider two fractions $p/q$ and $p'/q'$, assume that $p/q$ is larger. To avoid sign shenanigans I compare $\sqrt{n}$ to their average $(pq'+p'q)/(2qq')$. If $\sqrt{n}$ is larger then it's closer to the larger fraction and vice versa. I don't want any square root as well, so I compare the square of them. That is, to compute $(pq' + p'q)^2 - 4q^2q'^2n$. It turns out that if we are comparing the convergent and the next potentially semiconvergent $(p_{k-1}+rp_k)/(q_{k-1}+rq_k)$ where $r = [(a_k+1)/2]$, that difference is always $\pm 1$!!! If you still remember that $p_kq_{k+1}-q_kp_{k+1}$ is also $\pm 1$ you know these two fractions are really as close as they can get.

After few hours of number theory revision plus few hours of coding I finally got the right answer, only to find that Sage has the full packet to automate all these...

Wordle, Nerdle and other dles

Edit: well I don't recommend people playing the original Wordle, which is now under NYT due to their hideous changes to the game, including banning words from dictionary, making answer words notoriously difficult, and ADDING AD TRACKERS ON THE GAME SITE. 

Although we won't possibly try Wordle anymore...the science behind the game is still fun to look into. There are also other interesting non-commercial variants like those I listed below. I hope you will spend a little time trying and feel fun about those :)

Recently it has became a trend to play Wordle or its variant: Nerdle, Kotobade Asobou, Primel,... and you can extend the list for another 10 or more games.

From a computational perspective, finding the optimal route is easy given the fixed dictionary set and the limited word length (5). Not necessarily the best but the entropy approach is classic (cf. strategies against games like hangman), efficient and near optimal. 3Blue1Brown made two very high quality videos (as usual) which you can find here and there.

The only thing to point out is that the overall efficiency (distribution on number of guesses) relies on how you weight the frequency/likelihood of those answer-words. It is fine not to assume anything (word frequency), but if any I would set the cut-off (the inflexion point for the sigmoid function) much much narrower given that most answer-words seems to be common enough, more common than the impression from the actual pool size (~2300 words). Of course the ideal weighting is to equate the frequency of occurrence for words as answer, but that would be a meta thing to consider after.

I have been using the same starter from day 1 -- POWER. Clearly not the most efficient as O and E are not the most popular vowels and W is fairly uncommon, but I feel like to stick with that and see how do I perform. So far so good: I averaged 3.6 guesses over the past games.

But English is never my specialty...it would be more interesting to talk about Nerdle, the one based on numbers and the four arithmetic operators. Mahjong Handle is also fun given its totally different nature and an essentially harder variant to tackle. 

Nerdle.

10 numbers, 4 operators and the equal sign, with 8 slots and 6 guesses. A much easier game given its highly predictable pattern (math based) and a small letter pool size. In fact there are two starters that covers all 15 letters that you can almost always guess it right on the third guess with some exception. 

The first exception comes from equivalence by operator inverses. For example 12/3 = 4 can be expressed as 4*3 = 12. Such equivalence can usually be eliminated once you know which operator appears and which does not.

The second exception comes from equivalence upon translation for + and -. For example 3+8=11 translates to 5+8=13. Again it can be eliminated by fully exhausting all 10 possible numbers with proper starters. (It is in fact possible for translation to happen using the same set of numbers. Can you find one? -- just keep reading if you can't :P)

The third exception is by commutativity. For example 6+9=15 swaps to 9+6=15, 12/3=4 swaps to 12/4=3 and so on. Unlike the previous two exceptions, the starters do not necessarily eliminate commutativity. In fact, the author of Nerdle said that it won't be fun without allowing commutativity...although he added the choice of playing the game that accepts equivalent commutated answer at the end. 

The strategy is simple from here: you use the two starters (in a very rare case if the first starter is good enough one may also give it a try). Once you know all the symbols appearing in the expression it should be easy to get the right answer in the third guess (upon commutativity). There many ways for one to eliminate most random permutations of letters:

- RHS is presumably a single number without operators. The equal sign should appear on the 5th-7th slot, which is then clear from the starters. That means the expression on the left consists of 4-6 letters with 1 or at most 2 operators. You can then guess the position of those operators before filling the numbers in.

- The possibility for RHS is greatly limited by the operators given. An expression with single digit numbers, + and - only would not exceed 19/29 and you know the 1 must be at the 6th slot (if ='s on the 5th). Checks like mod 10 are also very helpful.

Take Nerdle#20 as an example. The two starters told you that the letters are 1, 3, 5, 6, + and =; also = is at 6th with +, 1, 6, 5 not at 2nd, 3rd, 7th and 8th slot respectively. What's the correct answer?

With 5 slots on LHS and only + allowed the answer is either a sum of 3 single digit numbers or a sum of two double digits. Let's look at the possibility of a sum of three single digit numbers. Clearly RHS must be 1x: 11 and 13 are too small as 6+5+3=14; 15 is not allowed and the only combination that sums to 16 is 6+5+5 where 3 is missing. 

What about a sum of two double digits? By checking mod 10 the possibilities for the ones are 1+5=3+3=6, 5+6=11 and nothing else. Notice that the tens on RHS is not 6 but it's not 11 either, so we need an extra 10 from the ones meaning that the ones must be 5 and 6. We now look for combinations that add to 2, 4 or 5 (so that the corresponding tens would be 3, 5 or 6). The possibilities are 1+1=2 and 1+3=4.

Plugging in we conclude that we have two distinct expressions satisfying the hints from the two starters: 15+16=31 and 15+36=51. One of them would be the third guess and if that fails we know for sure what's the right answer at the fourth guess even without commutativity (why?).

*

The phenomenon of "when your first serious attempt (for the right answer) failed you can easily give the correct answer right away" is important because not only that the chance of getting right is respectable, but it is also informative for you to get the right answer even if it doesn't work. In that way we have largely avoided the long tail cases (guessing 5+ times) and compresses the average number of guesses required  to the minimum. But what about games where long tail cases are well possible?

Welcome to the world of Mahjong Handle, where you guess a given valid hand in 6 guesses. 

*I never play Mahjong in English and I guess that applies to most of you guys...check Wiki if you are not sure about the terminology.

How hard is Mahjong Handle? We start by counting the number of valid winning hands in Japanese mahjong. I am sure there is a calculated number somewhere on the web, but to make it simpler we consider a very restricted yaku type -- all triplet hand (対々和) where you need 4 triplets and a pair. Simple math tells you that there are C(36,4)*32 = 1884960 ways to score an all triplet hand and that is already 1000 times as massive as Wordle's answer pool! There is no doubt that the actual number of valid hands is at least 20 times larger...or 50 times, 100 times maybe?

With that in mind, exhaustive information theory approach isn't practical anymore (another differences between Wordle and Mahjong Handle is that frequency analysis doesn't work here -- at least there is no obvious frequency references). Even if one managed to estimate the information provided by each guesses one must face the long tail problem. Unlike Nerdle, it may take up to 2 extra necessary guesses. Given the overall complexity of the game it often decides whether one gets it within 6 guesses or not. 

To give a more solid example one may consider the combination 2223334 and you are waiting for one extra tile. The extra tile can be 2, 3 or 4:

2: 222 234 33

3: 22 234 333

4: 222 333 44

While you may not know anything about whether it's 2, 3 or 4 in previous guesses. Things can be taken to extreme in the case of nine gates(九蓮宝燈) where all nine tiles are possible in the case of 11123456778999.

Gathering information on appearance is cheap, but information on repetition is expensive because it takes up multiple slots. It's even more expensive to ask if a tile appears 3 or 4 times, yet it's always possible given that triplet is a basic block in the hand. 

As a consequence we often fall into a long tail trap where the remaining uncertainty is low, but each guess would only help by a little. The simple greedy approach as in the video (entropy + probability) may not work very well, but I bet that a secondary correction would help greatly (note: 3Blue1Brown also mentioned this in his second video).

The real challenge is to evaluate each pieces of information gathered from the guesses though. Since exhaustive evaluation is now impossible, we can instead assign weightings to different kinds of partial information regarding the building block of 3 or 2. Rating from the least to the most useful information:

- a given tile is not in the hand

- a given tile is in a hand

- a tile is in a hand and is isolated from the sides

- a tile is in a given block

- a tile is in a block of sequences

- a sequence block with 2 known tiles

- a fully known sequence block

- a fully known triplet block

- a fully known block and isolated from the sides

...

Of course there are technical problems where blocks are often ambiguous when they stick together, but the idea should be clear: we assign weightings to each categories of information and play Mahjong handle prioritizing guesses according to the  weightings assigned. We then adjust weightings to improve  efficiency. No optimal performance guaranteed (as for any non-convex optimization), but it should be good enough.

And for humans like us how do we tackle the game?

Well I don't have any concrete suggestions even for starters. Thirteen orphans(国士無双) is certainly something to start with, but some says that these terminal tiles do not actually appear in hands *that* often comparing to the simple 13/36 coverage. Some also suggests the use of seven pairs due to its flexibility and to detect repetition but some also say that to be a waste. Some prefer to use loads of sequences...it's hard to tell which one's the best but I ended up using thirteen orphans as my starter. There are two reasons for that:

1) Coverage is still important. It is still very probable for at least one of the 13 tiles to appear in the hand and this is the cheapest way to ask for all 13 of them in one go.

2) Detecting honor tiles are very costly. In normal hands you need 2 or 3 copies of an honor tile for the hand to be valid, but for thirteen orphans you only need a single copy of it. This is another long tail problem -- any of the seven honor tiles may appear in your hand. Any algorithm that neglects them will face the chance of wasting 2 or 3 extra guesses at the end just to detect them. 

After that it's also about detecting sequences and repetitions. When both terminals (1,9) are void from the hand you can detect any sequence with 3 tiles (456), although repetition of 2, 3, 6 and 7 will be harder to detect. Some would prefer the use of two sequences (e.g. 234+678) to avoid that. Which is the better approach? I can't really tell.

For Wordle and Nerdle, one starts making reasonable attempt at guess number 3, but for Mahjong handle the guess should start no earlier than the fourth guess. From here you can really pile up something close to the answer and complete the final pieces using the ordering hints. There are too many 'rules' to apply and I can't even count them all, but here is one for example: if you have two consecutive tiles (e.g 56s) one labelled orange and one labelled blue then these two tiles must be a repetition of the tile labelled blue (why?).

Still getting it right on the fifth guess is not that easy and here is my stats:

There are definitely better strats as observed from the daily performance of my friends, but I enjoyed more the later guesses for this game and haven't bothered to optimize the overall approach (yet). If you have any ideas please comment and tell me that :D

Faster algorithm solving minesweeper puzzles (1)

Minesweeper is something that I'm always addicted to. This is obvious when this blog contains multiple entries talking about different aspects of this absolute classic. Last time, I talked about solving minesweeper using logical deduction generalised as a satisfiability problem. That was quite a long time ago -- when I was playing mienfield. 3 years after that I am now addicted to another minesweeper game called Minesweeper: Collector, that you can find on the Google play store.

Yes of course. Using ILP (integer linear programming) or even SAT (satisfiability) to solve minesweeper is not a very smart idea. Since we are working with equations and we know integral solution exists, we can simply employ linear algebra to make our life easier.

It is a bit hard to define how useful a deduction is by solving all the equations. For instance if we can conclude from 100 equations that now the space of possible solutions has dimension 68, then probably a faster way to solve the puzzle could be done by performing an educated guess in terms of probability. However probability is not something that linear algebra can handle easily so we would simply look for any definite deduction here. The most desirable result from the algorithm is that we can deduce the solution of some particular grids.

For the classic rectangular minesweeper we can think the whole puzzle as a matrix $M\in \mathbb{R} ^{m\times n}$, then we can setup variables $v_{11},...,v_{mn}$. Of course the same idea applies to different kinds of minesweeper shape [hexagonal etc] it is just the naming/coordinate setup that differs. They are supposed to be binary, but this is some technicality that we must handle later.

If a certain grid [for example row $s$ column $t$] is known but its neighborhoods are not all revealed then the grid yields an equation denoted by $E_{st}$. It has the form

$E_{st} ~:~ \sum _{p=s\pm 1, q = t\pm 1}^{1\leq p \leq m, 1\leq q \leq n} \delta _{pq}v_{pq} = c_{st}$

Where $c_{st}$ is the number of mines surrounded, and $\delta _{st} = 1$ if the grid $(s,t)$ is concealed, 0 otherwise. The aim of course, is to identify the mines [i.e. solving $v$] and receive more hints, eventually solving the whole puzzle.

Here is our first algorithm:

Algorithm 1.
-----
Input: A partially solved minesweeper matrix $M\in \mathbb{R}^{m\times n}$ provided that solution exists
Output: Any definite deduction

- Convert puzzle into linear eqautions
- RREF and solve $M$
- Interpret the solution
- Return any conclusion

For example we look at a classic 1-2 combination

$\begin{pmatrix}
\square & \square & \square & \square & \square & \square & \square & \square \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & \square
\end{pmatrix}$

that should give you deduction like

$\begin{pmatrix}
\square & X & O & O & X & X &O & O \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & O
\end{pmatrix}$

[where X represents mine and O is safe.] Let $v_1,...,v_{10}$ be the variables naming from left to right, top to bottom. Loot at the matrix reduction:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \end{pmatrix}$

What a mess! But we can still interpret the solution.

From row 3 we have $v_3+v_7+v_8+v_{10} = 0$, then by non-negativity they are all zero. By removing column 3,7,8,10 and row 3 we instantly get $v_2 = v_5 = v_6 = 1, v_4 = 0$. Now the solution space is given by:

$v = (0,1,0,0,1,1,0,0,1,0)^t + t(1,0,0,0,0,0,0,0,-1,0)^t$ where $t \in \mathbb{R}$, or simply $t \in \left\{ 0,1\right\}$.

as expected. However the deduction is very messy that it cannot be automated in an obvious way. Things get worse if the solution space is more complicated. Look at this simple example:

$\begin{pmatrix}
\square & \square &  \square & \square & \square & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

that yields immediately the following [this should be really obvious for any experienced player!]

$\begin{pmatrix}
\square & O &  \square & \square & X & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

assign the names $v_1,...,v_8$ as before, reduce the matrix:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix}1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2\\
0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & -1\\
0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2 \end{pmatrix}$

The only thing we can deduce is the second equation. Since we know $v_2,v_5\in \left\{ 0,1\right\}$ we must have $v_2 = 0, v_5 = 1$ as predicted, and this is basically all we know.

The trouble here is the deduction heavily relies on facts that we have omitted by modelling the problem into a system of linear equations. Of course rearranging the columns [hence changing the RREF] could solve this problem, but recognising the rearrangement of columns is basically equivalent to knowing the grids that can be definitely [or at least almost definitely - when the solution of that grid has a very low dimension] which is the fundamental aim.

To improve our efficiency instead of adding conditionals that check whether an equation is useful for deduction, we can change the fields that we are working on. Rings wouldn't work [and that is why ILP is bad], but we can look at fields, like $F_2$ or $F_7$!. This will be addressed in the next entry.

An algorithm to weight influences

This is my first few times using MathJax! If you have any troubles in viewing these TeX formula don't hesitate to tell me.

Introduction

There are many types of contests that require subjective judging like diving as well as osu! mapping contests. We are human that it is unavoidable that bias may occur even though there are well-written guidelines to follow. The aim of this entry is to make an attempt on correcting such bias by an algorithm, and to determine the degree of bias occurred in the judgement.

Friendwheel

Errrrrr three months from my last entry...

Anyway if you haven't heard of friendwheel, a facebook apps that generates the graph of friendship links of all your friends:

(I blurred the names of my friends for privacy. These blurred pixel looks awesome right?)

In general, they put similar friends closer (this is how the wheel works --- grouping in similar colour)

However as you can see some of the points are emitting a lot of linkage far from the neighbouring group. It turns out that their alogarithm is not very effective.

Definition. Distance between two points are defined by (number of points between them)+1

Definition. Circular n-tuple (a_1,...,a_n) is n numbers in order, and a_1 is supposed to be the next term of a_n. Due to the cyclic structure, it is equivalent to (a_2,a_3,...a_n, a_1) and so on.

Definition. Given a graph G = (V,E), the optimal permutation is a circular |V|-tuple where the tuple is the permutation of vertices so that sum of distance between any two linked vertices is the minimal.

Definition Given a graph G = (V,E). Optimal distance is the sum of distance between any two linked vertices.

The optimal permutation is not necessarily unique. For example consider:

G = (V,E); V = {1,2,3,4}, E = {(1,2),(3,4)}, then both (1,2,3,4) and (1,2,4,3) are optimal permutations with optimal distacnce 2.

Now the problem is, how should we reduce the sum of distance given G and an arbitrary permutation of V? I'll propose a heuristic here:

begin;
local_min_reached = FALSE
while not local_min_reached:
---swapping = FALSE
---for i in 1 to n:
------check if swapping a_i and a_{i+1} reduces sum of distance
------if yes then swap the two vertices
------swapping = TRUE
---if swapping = FALSE:
------local_min_reached = TRUE
return permutation of edges.

I'm so lazy to calculate its preformance ratio as well as other stuffs since it would take me quite a lot of time to do the simulation (like my research topic), but I'm sure that this one is qutie near to the optimal solution. I have no idea to construct G so that the procedure stuck at local optimum and fail to reach the global optimum with the above alogarithm.

Any idea?