Chasing Dhoni

Former India captain Mahendra Singh Dhoni has a mixed record when it comes to chasing in limited overs games (ODIs and T20s). He initially built up his reputation as an expert chaser, who knew exactly how to pace an innings and accelerate at the right moment to deliver victory.

Of late, though, his chasing has been going wrong, the latest example being Chennai Super Kings’ loss at Kings XI Punjab over the weekend. Dhoni no doubt played excellently – 79 off 44 is a brilliant innings in most contexts. Where he possibly fell short was in the way he paced the innings.

And the algorithm I’ve built to represent (and potentially evaluate) a cricket match seems to have done a remarkable job in identifying this problem in the KXIP-CSK game. Now, apart from displaying how the game “flowed” from start to finish, the algorithm is also designed to pick out key moments or periods in the game.

One kind of “key period” that the algorithm tries to pick is a batsman’s innings – periods of play where a batsman made a significant contribution (either positive or negative) to his team’s chances of winning. And notice how nicely it has identified two distinct periods in Dhoni’s batting:

The first period is one where Dhoni settled down, and batted rather slowly – he hit only 21 runs in 22 balls in that period, which is incredibly slow for a 10 runs per over game. Notice how this period of Dhoni’s batting coincides with a period when the game decisively swung KXIP’s way.

And then Dhoni went for it, hitting 36 runs in 11 balls (which is great going even for a 10-runs-per-over game), including 19 off the penultimate over bowled by Andrew Tye. While this brought CSK back into the game (to right where the game stood prior to Dhoni’s slow period of batting), it was a little too late as KXIP managed to hold on.

Now I understand I’m making an argument using one data point here, but this problem with Dhoni, where he first slows down and then goes for it with only a few overs to go, has been discussed widely. What’s interesting is how neatly my algorithm has picked out these periods!

Why Twitter is like Times Now

One reason I stopped watching news television about a decade back is because of its evolution into a “one issue channel”. On each day, a channel basically picks a “topic of the day”, and most discussion on that day is regarding that particular topic.

In that sense, these “news channels” hardly provide news (unless you bother to follow the tickers at the bottom) – they only provide more and more discussion about the topic du jour (ok I’m feeling all pseud about using French on my blog!). If you’re interested in that topic, and willing to consume endless content about it, great for you. If not, you better look for your news elsewhere (like the <whatever> o’clock news on the government-owned channel which at least makes a pretence of covering all relevant stuff).

One thing that made Twitter attractive soon after I joined it in 2008 was the diversity of discussions. Maybe it was the nature of the early users, but the people I followed provoked thought and provided content on a wide array of topics, at least some of which I would find interesting. And that made spending time on twitter worthwhile.

It’s still true on a lot of days nowadays, but I find that Twitter is increasingly becoming like a modern news channel such as Times Now. When there are certain events, especially of a political nature, it effectively becomes a one-topic channel, with most of the timeline getting filled with news and opinion about the event. And if it is either an event you don’t care about, or if you’ve moved on from the event, Twitter effectively becomes unusable on such days.

In fact, a few of my twitter breaks in the last 2-3 years have followed such periods when Twitter has turned into a “one issue channel”. And on each of these occasions, when I’ve joined back, I’ve responded by unfollowing many of these “one-issue tweeters” (like this guy who I don’t follow any more because he has a compulsive need to livetweet any game that Arsenal is playing).

That Twitter becomes a one-topic channel occasionally is not surprising. Basically it goes like this – there are people who are deeply passionate or involved in the topic, and they show their passion by putting out lots of tweets on the topic. And when the topic is a current event, it means that several people on your timeline might feel passionately about it.

People not interested in the topic will continue to tweet at their “usual rate”, but that gets effectively drowned out in the din of the passionate tweeters. And when you look at your linear timeline, you only see the passion, and not the diverse content that you use Twitter for.

Some people might suggest a curated algorithmic feed (rather than a linear feed) as a solution for this – where a smart algorithm learns that you’re not interested in the topic people are so passionate about and shows you less of that stuff. I have a simpler solution.

Basically the reason I’m loathe to unfollow these passionate tweeters is that outside of their temporary passions, they are terrific people and tweet about interesting stuff (else I wouldn’t follow them in the first place). The cost of this, however, is that I have to endure their passions, which I frequently have no interest in.

The simple solution is that you should be able to “temporarily unfollow” people (Twitter itself doesn’t need to allow this option – a third party client that you use can offer this at a higher layer). This is like WhatsApp where you can mute groups for just a day, or a week. So you can unfollow these passionate people for a day, by which time their passion will subside, and you can see their interesting selves tomorrow!

Of course it’s possible to manually implement this, but I know that if I unfollow them today I might forget to follow them back tomorrow. And there are countless examples of people in that category – who I unfollowed when they were passionate and have thus missed out on their awesomeness.


Coin change problem with change – Dijkstra’s Algorithm

The coin change problem is a well studied problem in Computer Science, and is a popular example given for teaching students Dynamic Programming. The problem is simple – given an amount and a set of coins, what is the minimum number of coins that can be used to pay that amount?

So, for example, if we have coins for 1,2,5,10,20,50,100 (like we do now in India), the easiest way to pay Rs. 11 is by using two coins – 10 and 1. If you have to pay Rs. 16, you can break it up as 10+5+1 and pay it using three coins.

The problem with the traditional formulation of the coin change problem is that it doesn’t involve “change” – the payer is not allowed to take back coins from the payee. So, for example, if you’ve to pay Rs. 99, you need to use 6 coins (50+20+20+5+2+2). On the other hand, if change is allowed, Rs. 99 can be paid using just 2 coins – pay Rs. 100 and get back Re. 1.

So how do you determine the way to pay using fewest coins when change is allowed? In other words, what happens to the coin change problems when negative coins can be used? (Paying 100 and getting back 1 is the same as paying 100 and (-1) ) .

Unfortunately, dynamic programming doesn’t work in this case, since we cannot process in a linear order. For example, the optimal way to pay 9 rupees when negatives are allowed is to break it up as (+10,-1), and calculating from 0 onwards (as we do in the DP) is not efficient.

For this reason, I’ve used an implementation of Dijkstra’s algorithm to determine the minimum number of coins to be used to pay any amount when cash back is allowed. Each amount is a node in the graph, with an edge between two amounts if the difference in amounts can be paid using a single coin. So there is an edge between 1 and 11 because the difference (10) can be paid using a single coin. Since cash back is allowed, the graph need not be directed.

So all we need to do to determine the way to pay each amount most optimally is to run Dijkstra’s algorithm starting from 0. The breadth first search has complexity $latex O(M^2 n)$ where M is the maximum amount we want to pay, while n is the number of coins.

I’ve implemented this algorithm using R, and the code can be found here. I’ve also used the algorithm to compute the number of coins to be used to pay all numbers between 1 and 10000 under different scenarios, and the results of that can be found here.

You can feel free to use this algorithm or code or results in any of your work, but make sure you provide appropriate credit!

PS: I’ve used “coin” here in a generic sense, in that it can mean “note” as well.

On apps tracking you and turning you into “lab rats”

Tech2, a division of FirstPost, reports that “Facebook could be tracking all rainbow profile pictures“. In what I think is a nonsensical first paragraph, the report says:

Facebook’s News Feed experiment received a huge blow from its social media networkers. With the new rainbow coloured profile picture that celebrates equality of marriage turned us into ‘lab rats’ again? Facebook is probably tracking all those who are using its new tool to change the profile picture, believes The Atlantic.

I’m surprised things like this still makes news. It is a feature (not a bug) of any good organisation that it learns from its user interactions and user behaviour, and hence tracking how users respond to certain kinds of news or updates is a fundamental part of how Facebook should behave.

And Facebook is a company that constantly improves and updates the algorithm it uses in order to decide what updates to show whom. And to do that, it needs to maintain data on who liked what, commented on what, and turned off what kind of updates. Collecting and maintaining and analysing such data is a fundamental, and critical, part of Facebook’s operations, and expecting them not to do so is downright silly (and it would be a downright silly act on part of the management if they stop experimenting or collecting data).

Whenever you sign on to an app or a service, you need to take it as a given that the app is collecting data and information from you. And that if you are not comfortable with this kind of data capture, you are better off not using the app. Of course, network effects mean that it is not that easy to live like you did in “the world until yesterday”.

This seems like yet another case of Radically Networked Outrage by outragers not having enough things to outrage about.

Jobs and courtship

Jobs, unlike romantic relationships, don’t come with a courtship period. You basically go for a bunch of interviews and at the end of it both parties (you and the employer) have to decide whether it is going to be a good fit. Neither party has complete information – you don’t know what a typical day at the job is like, and your employer doesn’t know much about your working style. And so both of you are taking a risk. And there is a significant probability that you are actually a misfit and the “relationship” can go bad.

For the company it doesn’t matter so much if the odd job goes bad. They’ll usually have their recruitment algorithm such that the probability of a misfit employee is so low it won’t affect their attrition numbers. From the point of view of the employees, though, it can get tough. Every misfit you go through has to be explained at the next interview. You have a lot of misfits, and you’re deemed to be an unfaithful guy (like being called a “much-married man”). And makes it so tough for you to get another job that you are more likely to stumble into one where you’re a misfit once again!

Unfortunately, it is not practical for companies to hire interns. I mean, it is a successful recruitment strategy at the college-students level but not too many people are willing to get into the uncertainty of a non-going-concern job in the middle of their careers. This risk-aversion means that a lot of people have no option but to soldier on despite being gross misfits.

And then there are those that keep “divorcing” in an attempt to fit in, until they are deemed unemployable.

PS: In this regard, recruitments are like arranged marriage. You make a decision based on a handful of interviews in simulated conditions without actually getting to know each other. And speaking of arranged marriage, I reprise this post of mine from six years ago.

Bol Bol Why did you ditch me …

of late i’m having frequent bouts of extreme depression…

After careful analysis you see that the only chance for you to win is if the Queen of Hearts is with West.

I’m trying to figure out whether i have a crush on her or not.

…I’ve started enjoying it – talking to her frequently, guessing what goes behind each thread of conversation, trying to understand her while she tries to understand me…

You think of a wonderful scenario. You start day-dreaming about it. You day-dream about it so much that you start believing it’s true.

Of course, this screw-up has been hitting me for the last 12 hours. And that reminds me of the fact that she hasn’t responded to my mails or messages for a long time. Pushes me further down. Feel like totally giving up in life.

Suddenly “inspired” by an arbit conversation with a friend, I happened to rummage my almost defunct yahoo mailbox and look through some old mails. a series of exchanges with her, circa early 2004.

I input a girl into my algorithm and ask it if there is a possibility of a relationship with her. If it says no, I can completely believe it and get on with life. A ‘yes’, however, means trouble. It means there is a possibility of a relationship, but there is no guarantee.

That little bit of indiscretion. The little bit of getting carried away. And then, that little bit of my foot in my mouth – I could’ve probably wriggled out of the situation, but i chose not to. Yet another relationship in limbo.

Think I have hit a local optimum. And jumping the gun being my habit, I tell my mom about it before I confirm it with the woman in question.

I’m still trying to figure out the nature of this relationship. It’s much stronger than simple good platonic friendship, but doesn’t seem to be anywhere near a romantic relationship

I made the measurement today. don’t ask me how. we are good friends.

Ranga sends this: Any kind of symbiotic relationship ends up being remunerative.

i believe people enter your life exactly at a point when u need them to grow together and exit/fade away from your life at the right time, enabling you to move ahead. its sad but true”

at several points of time in life, you end up in the unpleasant situation where your relationship with someone has hit the pits. there is a cold war on, and you haven’t spoken to him/her for a while. and you want to try and re-build the relationships.

She took my hand in hers and started gently stroking my fingers. One by one.

For most of the first half of last year, I used to turn to her whenever I was depressed.

When we met for the first time, my order of a mousse was met with a “oh, I didn’t know you are such a high calorie person. I?m very calorie conscious you know. I’ll have tea -without milk or sugar”. I had quickly changed my order to a cup of cold coffee.

And that relationship. Something had snapped right at the end. She had suddenly wanted to puke and wanted to hang up.

Having been in a budding long distance relationship (which ultimately didn’t wrok out; in fact, it failed before it became “official”), I couldn’t agree more with this article.

She is still an out-of-money option – quite ordinary for most of the time, offering nothing, or mildly negative returns; but once in a very long time you get great value, making the long periods of mediocrity worth their while.

Tauba Tera Jalwa, Tauba tera pyar,
Tera Emosanal Attyachaar!