Call for Participation: The 2nd Oktave Micro-workshop

(Cross-posted at the Oktave Forum)

OKTAVE MICRO-WORKSHOP SERIES 2009

CALL FOR PARTICIPATION

http://omw.oktave.in/index.php/omw-events/details/2-omw-2-general-topics

The Oktave Micro-Workshop on General Topics in Information Management will be held at 5:00 PM on Friday, April 3, 2009 at IIIT-Bangalore.

After rigorous peer-review, the following papers have been accepted for presentation at this micro-workshop:

1. A Tutorial Introduction to Information Networks: Part-I

Srinath Srinivasa

Abstract: This paper, as part of a multi-part series aims to provide a tutorial introduction to the growing field of the theory of information networks. Information networks are networks of information processing elements set up to meet information needs in any population. This part of the tutorial takes a philosophical perspective on information networks and motivates its significance. This is done by contrasting information exchange with material exchange and providing examples of information networks from nature. The paper then sets a roadmap for the rest of the tutorials to follow.

2. User Authentication in a Pervasive Environment

Karthick Lakshmanan

Abstract: Pervasive computing is a storehouse of opportunities to do research in multitudes of challenging issues with the objective of providing a minimally obtrusive and seamless computing environment to the users. To achieve this aim, the user should be able to access information through different computing environments on the go. The user access should be authenticated to have a secure access to the computing environment. Thus, user authentication systems form an integral part of the overall pervasive environment. This paper aims to provide a comprehensive analysis of the challenges associated with the design of a secure and seamless user authentication system for a pervasive environment and discusses the proposed solutions in related researches.

Please register for the micro-workshop here.

Call for Participation: Oktave Micro-Workshop

(Cross-posted at the Oktave Forum)

OKTAVE MICRO-WORKSHOP SERIES 2009

CALL FOR PARTICIPATION

http://omw.oktave.in/index.php/omw-events/details/1-omw-1-multi-agent-systems

The Oktave Micro-Workshop on Multi-Agent Systems will be held at 4:00 PM on Friday, March 6, 2009 at IIIT-Bangalore.

After rigorous peer-review, the following papers have been accepted for presentation at this micro-workshop:

1. iLearn – Collaborative Learning System

Abhilash L L, Bharath Palavalli, Harsha K, Ricardo Lage

Abstract: iLearn is a multi-agent learning management system that provides a platform focused on promoting student interactions. The agent environment will allow students seeking help to find the students providing help. The incentive system also ’persuades’ students to improve themselves and offer more help to a lot of different students thus improving the overall quality of content in the system. The system also provides incentives to faculty for generating high quality content and for spending extra time helping students.

2. Energy Control Game Model for Dynamic Spectrum Scanning

Jyotsna Bapat, et al.

Please register for the micro-workshop here.

Loving Twitter

I’m into micro-blogging these days. That means this blog is going to be updated all the more infrequently. I’m totally loving Twitter. As with most other things, I got hooked on to it rather late. But the natural way of communication that it facilitates has me totally captivated. Then again, I had felt similarly about blogs, and then this thing known as “blogger burnout” happened. Ah, well… I hope I don’t experience “Twitter burnout” too soon.

Stock Market Humor

Seen as the Google Chat status message of Deepak Joshi, my dear friend and cousin:

Love the stock markets. They make you feel good about everything else.

Topical Anchors

My friend Aditya is conducting an experiment about “topical anchors”. Given a set of related words, a topical anchor is a word or phrase that best represents the given set of words. Quoting Aditya:

For example, if given the words ‘Sachin Tendulkar’, ‘Sourav Ganguly’ and ‘Rahul Dravid’, you have to answer with words about the subject they represent like ‘Cricket’, ‘India’ and you can also add ‘Batsmen’.

and

For the words ‘Mickey Mouse’, ‘Donald Duck’ and ‘Goofy’, you can think of the representative words to be ‘Disney’ and ‘cartoon’. There is no one right answer to the questions but do not be too generic by answering ‘humans’, ‘earthlings’ for the above mentioned cricketers and similarly do not be opinionated by answering ‘gods of cricket’, ‘old losers’. We need an answer which will represent the words best.

Aditya has developed some algorithms for automatically determining the topical anchors for a given set of words. He wants to calibrate his algorithms against human feedback. So, if you’re free, please do participate in this experiment and provide feedback.

Thanks.

Harry Vs Draco

Harry Potter and Draco Malfoy are the frontrunners for the “Best Student of the Year” award at Hogwarts. Professor Dumbledore suggests that they play a certain game (invented by a great wizard) to determine the winner. Dumbledore describes the game to Harry and Draco as follows.

Consider a board as below, with two distinct non-zero integers m and n “thrown” onto it. At the beginning of the game, Dumbledore, as the impartial referee, will provide m and n. Then, there will be a toss to decide who gets to make the first move. The winner of the toss can either make the first move himself or invite his opponent to make the first move.

When his turn comes, each player has to introduce a new positive integer onto the board such that it is the difference between any two existing integers on the board.

For example:

First move: Player 1 would introduce k = |m – n|

Second move: Player 2 would introduce either x = |m – k| or y = |n – k|

Third move: (Assuming that Player 2 introduced x = |m – k| in the second move) Player 1 introduces either u = |m – x| or v = |n – x| or w = |k – x| or y = |n – k|

Fourth move: Player 2 introduces…

and so on…

The game goes on like this and concludes only when one of the players finds it impossible to introduce any more new numbers to the board; the other player thus wins.

Well, now, the stage is set. Dumbledore has provided m and n. Harry has won the toss!

Can you help Harry ensure that he wins the game? Who should make the first move and why?

Connect these

(1)

***

(2)

***

(3)

***

Bonus question: Can you connect image (1) to image (4) below?

(4)

Analysis of Strategies for the n-Door Monty Hall Problem

In an earlier post (see comments also), I had put forth a question about the winning strategy for the famous n-Door Monty Hall problem. Let me pose it again here, this time in a general way.

Of the following strategies, which has the highest chance of winning in the n-door problem (n > 3)?

1. Stick with your initial choice till the very end without switching
2. Stick with your initial choice till the end and switch only at the last stage
3. Switch your choice at the very beginning and stick with this new door till the very end without switching again
4. Switch at every possible stage

For those who are already familiar with the 3-door problem, strategy 4 might intuitively seem to be the best strategy. However, that is not the case!

Consider n doors as follows: C, G₁, G₂, …, G_n-1

Assertion 1: The door we choose at the first stage is C (the “car door”) with probability 1/n, while it is a G_x (one of the “goat doors”) with probability (n – 1)/n.

Strategy 1: Stick with your initial choice till the very end without switching

This strategy is equivalent to simply picking a door uniformly at random. Hence, it is trivially true that the probability of picking C (i.e. probability of winning the car) is 1/n.

Strategy 2: Stick with your initial choice till the end and switch only at the last stage

This strategy is interesting. At every stage except the last one, Monty Hall will go ahead and show us one of the goat doors. That is, out of a total of (n – 1) goat doors, we are shown (n – 2). Hence, the unopened door at the last stage and the door we chose at the first stage are the only two mystery doors to us! One of these contains the car, while the other contains a goat. As we can see, by waiting till the last stage, we maximized our own information content.

If the door we chose at the first stage is C, then according to this strategy, we definitely lose — because the other mystery door (to which we have to switch) then contains a goat.

However, if we chose a G_x at the first stage, then we always win! Because the other mystery door (to which we have to switch) then contains the car.

Therefore, the probability of winning with this strategy is (probability of choosing a G_x at the first stage) * 1. From Assertion 1, this equals (n – 1)/n.

Strategy 3: Switch your choice at the very beginning and stick with this new door till the very end without switching again

According to this strategy, we choose a door at the first stage and switch our choice at the second stage. Thereafter, we stick to the door that we chose at the second stage, till the end of the game.

If the door we chose at the first stage is C, then we definitely lose — because we would switch to a goat door at the second stage and stick with it thereafter.

So, we could win only if we chose a G_x at the first stage. However, merely choosing a G_x at the first stage does not mean we always win. After the first stage, Monty shows us one of the goat doors. This still leaves (n – 2) other doors (excluding our initial choice) as a mystery to us. So, we will switch to one of the remaining (n – 2) doors uniformly at random. So, the probability of switching to C is 1/(n – 2).

Therefore, the probability of winning with this strategy is (probability of choosing a G_x at the first stage) * 1/(n – 2). Hence, It follows (from Assertion 1) that the probability of winning with this strategy is (n – 1)/(n (n – 2)) or (n – 1)/(n² – 2n).

Strategy 4: Switch at every possible stage

In this strategy, we keep hopping from one door to another door at every stage. In this approach, the only way to win is by switching to C at the (n – 1)th stage, no matter which doors we have switched to up until then. The only thing that matters is whether we are able to switch to C at the last stage. This can happen if and only if we are at a G_x at the (n – 2)th stage.

It is obvious that by the time we reach the last stage, Monty would have revealed all but one goat door. So, we’ll be left with two doors — one goat door (i.e. some G_x) and C. Hence, it is clear that we will win if we are at the solitary goat door at the end of the (n – 2)th stage.

Let us first see what is the probability (P) of making it to some G_x at the last-but-one stage, given that we start with C at the first stage. In other words, having started with C at the first stage, what is the probability that we will have reached some G_x after exactly (n – 3) transitions (or switches)?

From C, we will always make a transition to some goat door other than the one that Monty reveals at the end of the first stage. So, we can make a transition to one of the remaining (n – 2) goat doors with probability 1. That leaves us with exactly (n – 4) transitions after which to reach some goat door. From here on, Monty is going to unveil one goat door at each stage except the last. So, the number of possible transitions at each stage, no matter what door we are at, keeps decreasing by 1. Also, note that there is a transition from every goat door to C.

Therefore, the probability of transition to a goat door for the third stage is ((n – 3) – 1)/(n – 3); the probability of transition to a goat door for the fourth stage is (n – 5)/(n – 4); … ; the probability of transition to a goat door for the (n – 3)th stage is 2/3; the probability of transition to a goat door for the (n – 2)th stage is 1/2.

Therefore, with C as the initial choice, the probability that we reach some G_x after exactly (n – 2) stages is given by

P = 1 * (n – 4)/(n – 3) * (n – 5)/(n – 4) * … * 2/3 * 1/2.

This implies P = 1/(n – 3).

However, this seems to hold only if we do not make any transitions to C up to the end of (n – 2) stages. But what if we do switch to C at some stage? Then, we switch back to one of the remaining (n – m – 1) instances of G_x with probability 1, where m is the stage number that took us to C. Therefore, switching to C at some intermediate stage does not affect our calculation of P.

Now, let us see what is the probability (Q) of making it to some G_x at the last-but-one stage, given that we start with a G_x at the first stage. In other words, having started with some G_x at the first stage, what is the probability that we will have reached another G_x after exactly (n – 3) transitions?

From a G_x, we will make a transition to either some G_x other than the one that Monty reveals at the end of the first stage or C. So, for the second stage, the probability that we make a transition to one of the remaining (n – 3) goat doors is (n – 3)/(n – 2); for the third stage, the probability that we make a transition to one of the remaining (n – 4) goat doors is (n – 4)/(n – 3); … ; for the (n – 3)th stage, the probability that we make a transition to one of the remaining 2 goat doors is 2/3; for the (n – 2)th stage, the probability that we make a transition to the remaining 1 goat door is 1/2.

Therefore, with some G_x as the initial choice, the probability that we reach another G_x after (n – 2) stages is given by

Q = (n – 3)/(n – 2) * (n – 4)/(n – 3) * … * 2/3 * 1/2

This implies Q = 1/(n – 2).

Again, at any stage, if we make a transition to C, then we make a transition to a G_x at the next stage with probability 1. Therefore, switching to C at some intermediate stage does not affect our calculation of Q.

Thus, the probability of winning with the strategy of always switching is (probability of choosing C at the first stage) * P + (probability of choosing a G_x at the first stage) * Q. From Assertion 1, it follows that the probability of winning with this strategy is given by 1/(n * (n – 3)) + (n – 1)/(n * (n – 2)). This equals (n² – 3n + 1)/(n³ – 5n² + 6n).

In the order of probability of winning, the above four strategies compare as follows:

Strategy 2 > Strategy 4 > Strategy 3 > Strategy 1.

There are many other strategies for playing this game, of course. For ex., you could switch and stick alternately (or with any other pattern, for that matter). However, intuitively, it seems that it would pretty much be impossible to beat Strategy 2 — as n increases, the probability of winning approaches 1. Perhaps, there exists a formal proof of the supremacy of Strategy 2. But I’ve not been able to find it on the Web. If you come across such a proof, please leave a comment.

PS: If you find any discrepancies in this article, please let me know. I am not too sure about the correctness of the proof for strategy 4.

The Birthday Problem

The well-known birthday problem:

How many people do you need to assemble before the probability that some two of them have the same birthday is greater than 0.5?

Assumptions: (1) A year has 365 days (no leap year), and (2) By “same birthday”, we only mean the same day and month (not necessarily the same year).

My first intuition was 183 — the smallest number that is more than half the number of days in a year. But as it turns out, 183 is the number of people you need to assemble before the probability that someone has the same birthday as you — a specific person — is greater than 0.5!

Look closely. The question is not about someone matching a particular person’s birthday. It is about the birthdays of some two people matching. Enough said. What is the right answer then, and why? How do we generalize this to matching the birthdays of some N people?

If you are guessing or have worked out a solution now, please leave comments.

The point of asking such questions (even though they might seem trivial to some) is to further our own understanding, and more importantly, to enjoy the process of understanding! So, if you already know the answer, please defer commenting.

The Multi-Stage Monty Hall Problem

Some time back, Sids had a post on the Monty Hall problem/game, which is as follows (Source: Wikipedia).

Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?

In this case, there are three doors. So, the game is played in two stages — Stage 1: Choose a door; Stage 2: Switch or stick with your choice. Here, the probability that you win the car is 2/3 if you switch your choice. So, yes. It is to your advantage to switch. See this page for details.

Let us now generalize this game to N doors. That means, the game is played in (N - 1) stages.

Stage 1: Choose a door

For stages X = 2 through (N – 1):

Monty Hall shows you one of the “goat doors”. Then, you either switch to one of the remaining (N - X) doors or stick with your choice

Questions:

1. What strategy has the highest probability of winning in this scenario?
2. Why is this the best strategy?
3. What is the probability of winning with this strategy?

For simplicity, let us consider N = 4. You get to choose a door at the first stage, and for the next two stages, you can either switch or stick. So the various permutations are:

1. Choose, Stick, Stick
2. Choose, Stick, Switch
3. Choose, Switch, Stick
4. Choose, Switch, Switch

Which of these four strategies wins most probably? And why? Once this is figured out, try looking at the generalized problem with N doors.

PS: If you already know the answer (or have found a link to it), kindly procrastinate on writing a comment about it.