What are the expected values E(X_{i}) for various n and i? What are the medians and modes?

Given some subset S of {1,2,3,...,n}, let X_{S} = Σ X_{i}, i∈S. What is the probability that P(X_{S} > 1/2) for various n and S? That is, what is the chance that the sum of the X_{i} for i in S is larger than the sum of the X_{i} for i not in S?

More generally, if S and T are non-overlapping subsets of {1,2,3,...,n}, what is P(X_{S} > X_{T})?

n \ i | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 1 | ||||

2 | 1 / 4 | 3 / 4 | |||

3 | 2 / 18 | 5 / 18 | 11 / 18 | ||

4 | 3 / 48 | 7 / 48 | 13 / 48 | 25 / 48 | |

5 | 12 / 300 | 27 / 300 | 47 / 300 | 77 / 300 | 137 / 300 |

George Sicherman noticed that column 1 of the table was 1/n^{2} and the main diagonal was S(n)/(n n!), where S(n) is the n^{th} Stirling number of the first kind.

Dan Dima said this problem was the January 2006 IBM Ponder This problem of the month. You can find the question and answer here. Thus with n pieces, E(X_{i}) = 1 / (n Σ 1/(n-k)) where the sum ranges over 0≤k<i.

n \ i | 1 | 2 | 3 | 4 |
---|---|---|---|---|

1 | 1 | |||

2 | 1 / 4 | 3 / 4 | ||

3 | (2–√2)/6 | √3/6 | (6–√6)/6 | |

4 | (2–^{3}√4)/8 | .144+ | .275+ | 1 / 2 |

n \ i | 1 | 2 | 3 | 4 |
---|---|---|---|---|

1 | 1 | |||

2 | (0, 1/2) | (1/2, 1) | ||

3 | 0 | 1 / 3 | 1 / 2 | |

4 | 0 | 1 / 7 | 2 / 7 | 5 / 11 |

n | S | P(S) |
---|---|---|

3 | {3} | 3 / 4 |

4 | {4} | 1 / 2 |

{4,1} | 3 / 4 | |

5 | {5} | 5 / 16 |

{5,4} | 95 / 96 | |

{5,3} | 15 / 16 | |

{5,2} | 5 / 8 | |

{5,1} | 5 / 12 | |

{4,3} | 5 / 32 |

n | S | T | P(S,T) |
---|---|---|---|

3 | {3} | {2,1} | 3 / 4 |

4 | {4,1} | {3,2} | 3 / 4 |

{4} | {3,2,1} | 1 / 2 | |

{4} | {3,2} | 3 / 5 | |

{4} | {3,1} | 4 / 5 | |

{4} | {2,1} | 14 / 15 | |

{3} | {2,1} | 2 / 3 |

If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 1/1/18.