Return to Answer

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\sum_{j=1}^n \prob(\xi=\max(A)\mathrel||A|=j)\cdot \prob(|A|=j)=\sum_{j=1}^n\frac1j \cdot\frac{{n\choose j}}{2^n-1} $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=k \, \&\,A\subset [k])= \sum_{k=1}^n \prob(\xi=k|A\subset [k])\cdot \prob(A\subset [k])\\= \sum_{k=1}^n \frac1k\cdot \frac{2^k-1}{2^n-1}. $$

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\sum_{j=1}^n \prob(\xi=\max(A)\mathrel||A|=j)\cdot \prob(|A|=j)=\sum_{j=1}^n\frac1j \cdot\frac{{n\choose j}}{2^n-1} $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=k \, \&\,A\subset [k])= \sum_{k=1}^n \prob(\xi=k\mathrel|A\subset [k])\cdot \prob(A\subset [k])\\= \sum_{k=1}^n \frac1k\cdot \frac{2^k-1}{2^n-1}. $$

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\frac1{2^n-1}\sum_{j=1}^n\frac1j {n\choose j}. $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=\max(A)\mathrel|\max(A)=k)\cdot \prob(\max A=k)\\= \sum_{k=1}^n \left(\frac{2^k-1}{2^{k-1}}\cdot\prob_{A\subset [k],A\ne \emptyset}(\xi=k)\right)\cdot \frac{2^{k-1}}{2^n-1}=\frac1{2^n-1} \sum_{k=1}^n \frac{2^k-1}k. $$ I have used that \begin{align*} \prob(\xi=\max(A)\mathrel|\max(A)=k)&=\frac1{2^{k-1}}\sum_{C\subset [k],C\ne \emptyset}\prob(\xi=k\mathrel|A=C),\\ \prob_{A\subset [k],A\ne \emptyset}(\xi=k)&=\frac1{2^{k}-1}\sum_{C\subset [k],C\ne \emptyset}\prob(\xi=k\mathrel|A=C). \end{align*}

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\sum_{j=1}^n \prob(\xi=\max(A)\mathrel||A|=j)\cdot \prob(|A|=j)=\sum_{j=1}^n\frac1j \cdot\frac{{n\choose j}}{2^n-1} $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=k \, \&\,A\subset [k])= \sum_{k=1}^n \prob(\xi=k|A\subset [k])\cdot \prob(A\subset [k])\\= \sum_{k=1}^n \frac1k\cdot \frac{2^k-1}{2^n-1}. $$

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\frac1{2^n-1}\sum_{j=1}^n\frac1j {n\choose j}. $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=\max(A)\mathrel|\max(A)=k)\cdot \prob(\max A=k)\\= \sum_{k=1}^n \left(\frac{2^k-1}{2^{k-1}}\cdot\prob_{A\subset [k],A\ne \emptyset}(\xi=k)\right)\cdot \frac{2^{k-1}}{2^n-1}=\frac1{2^n-1} \sum_{k=1}^n \frac{2^k-1}k. $$ I have used that \begin{align*} \prob(\xi=\max(A)\mathrel|\max(A)=k)&=\frac1{2^{k-1}}\sum_{C\subset [k]}\prob(\xi=k\mathrel|A=C),\\ \prob_{A\subset [k],A\ne \emptyset}(\xi=k)&=\frac1{2^{k}-1}\sum_{C\subset [k]}\prob(\xi=k\mathrel|A=C). \end{align*}

$\DeclareMathOperator\prob{prob}$Alapan Das' clever argument may be rephrased on the probabilistic language. Write $[m]=\{1,2,\dotsc,m\}$. Choose a random non-empty subset $A\subset [n]$ (all $2^n-1$ possible outcomes having equal probabilities). Then choose a random element $\xi\in A$ uniformly. Denote $p=\prob (\xi=\max(A))$. On one hand, denoting $j=\lvert A\rvert$ we get $$ p=\frac1{2^n-1}\sum_{j=1}^n\frac1j {n\choose j}. $$

On the other hand, $$ p=\sum_{k=1}^n \prob(\xi=\max(A)\mathrel|\max(A)=k)\cdot \prob(\max A=k)\\= \sum_{k=1}^n \left(\frac{2^k-1}{2^{k-1}}\cdot\prob_{A\subset [k],A\ne \emptyset}(\xi=k)\right)\cdot \frac{2^{k-1}}{2^n-1}=\frac1{2^n-1} \sum_{k=1}^n \frac{2^k-1}k. $$ I have used that \begin{align*} \prob(\xi=\max(A)\mathrel|\max(A)=k)&=\frac1{2^{k-1}}\sum_{C\subset [k],C\ne \emptyset}\prob(\xi=k\mathrel|A=C),\\ \prob_{A\subset [k],A\ne \emptyset}(\xi=k)&=\frac1{2^{k}-1}\sum_{C\subset [k],C\ne \emptyset}\prob(\xi=k\mathrel|A=C). \end{align*}