title: Information Gain and Entropy
body: <p>I recently read <a href="https://stackoverflow.com/questions/1859554/what-is-entropy-and-information-gain">this question</a> regarding information gain and entropy. I think I have a semi-decent grasp on the main idea, but I'm curious as what to do with situations such as follows:</p>
  
  <p>If we have a bag of 7 coins, 1 of which is heavier than the others, and 1 of which is lighter than the others, and we know the heavier coin + the lighter coin is the same as 2 normal coins, what is the information gain associated with picking two random coins and weighing them against each other?</p>
  
  <p>Our goal here is to identify the two odd coins. I've been thinking this problem over for a while, and can't frame it correctly in a decision tree, or any other way for that matter. Any help?</p>
  
  <p>EDIT: I understand the formula for entropy and the formula for information gain. What I don't understand is how to frame this problem in a decision tree format.</p>
  
  <p>EDIT 2: Here is where I'm at so far:</p>
  
  <p>Assuming we pick two coins and they both end up weighing the same, we can assume our new chances of picking H+L come out to 1/5 * 1/4 = 1/20 , easy enough.</p>
  
  <p>Assuming we pick two coins and the left side is heavier. There are three different cases where this can occur:</p>
  
  <p>HM: Which gives us 1/2 chance of picking H and a 1/4 chance of picking L: 1/8
  HL: 1/2 chance of picking high, 1/1 chance of picking low: 1/1
  ML: 1/2 chance of picking low, 1/4 chance of picking high: 1/8</p>
  
  <p>However, the odds of us picking HM are 1/7 * 5/6 which is 5/42<br>
  The odds of us picking HL are          1/7 * 1/6 which is 1/42<br>
  And the odds of us picking ML are      1/7 * 5/6 which is 5/42</p>
  
  <p>If we weight the overall probabilities with these odds, we are given:</p>
  
  <p>(1/8) * (5/42) + (1/1) * (1/42) + (1/8) * (5/42) = 3/56.</p>
  
  <p>The same holds true for option B.</p>
  
  <p>option A = 3/56<br>
  option B = 3/56<br>
  option C = 1/20</p>
  
  <p>However, option C should be weighted heavier because there is a 5/7 * 4/6 chance to pick two mediums. So I'm assuming from here I weight THOSE odds. </p>
  
  <p>I am pretty sure I've messed up somewhere along the way, but I think I'm on the right path!</p>
  
  <p>EDIT 3: More stuff.</p>
  
  <p>Assuming the scale is unbalanced, the odds are (10/11) that only one of the coins is the H or L coin, and (1/11) that both coins are H/L</p>
  
  <p>Therefore we can conclude:<br>
  (10 / 11) * (1/2 * 1/5)  and<br>
  (1 / 11) * (1/2)</p>
  
  <p>EDIT 4: Going to go ahead and say that it is a total 4/42 increase.</p>