title: Expected value of visits to a node in a randomly constructed graph
body: <p>A boy has n coins with <strong>unique</strong> weights. He chooses a coin <strong>randomly</strong> and places it at the first <strong>empty</strong> node. To reach the empty node he compares the coin he currently has with the coin at the node and proceeds left if the coin he has is lighter otherwise he proceeds right (he can just go left or right at every node). He keeps doing this until all coins are exhausted.</p>
  
  <p>He gets to keep all the coins which are at the nodes he visited just once. What would be the expected value of his prize.</p>
  
  <p>I can solve it using brute force for smaller values of n but that will not be efficient enough.</p>
  
  <p>Other direction in which I can think is that if somehow we can manage the expectation of getting a coin with a weight w given the weights of other coins then we can sum up all such expectations. But I am unable to work this out.</p>
  
  <p><em>Note, even when a coin is placed at a node, visit count increases</em></p>
  
  <p><strong>Example</strong>:</p>
  
  <p>n=3 ; weights ε {1, 2, 3}</p>
  
  <p>if he chooses 1,2,3 he will get 3 unit<br></p>
  
  <pre><code>1
   \
    2
     \
      3
  </code></pre>
  
  <p>if he chooses 1,3,2 he will get 2 unit</p>
  
  <pre><code>1
   \
    3
   /
  2
  </code></pre>
  
  <p>if he chooses 2,1,3 he will get (1 + 3) = 4 unit</p>
  
  <pre><code>  2
   / \
  1   3
  </code></pre>
  
  <p>if he chooses 2,3,1 he will get (1 + 3) = 4 unit</p>
  
  <p>if he chooses 3,1,2 he will get 2 unit</p>
  
  <p>if he chooses 3,2,1 he will get 1 unit</p>
  
  <p>So, expected amount of weight is (3 + 2 + 4 + 4 + 2 + 1) / 6 = 8 / 3</p>
  
  <p>Thanks.</p>