Skip to main content
Bounty Ended with 100 reputation awarded by Mikhail Gaichenkov
Post Undeleted by David E Speyer
added 122 characters in body
Source Link
David E Speyer
  • 156.2k
  • 14
  • 420
  • 763

Here is a quick and dirty probabilistic analysis which gets the right answer. For a permutation $w \in S_n$, define $$I(w) = \sum_{1 \leq i < j \leq n} \begin{cases} -1 & w(i) < w(j) \\ 1 & w(i) >w(j) \\ \end{cases}.$$ So $I(w) = 2 \# (\mbox{number of inversions of $w$}) - \binom{n}{2}$. If $w$ is chosen uniformly at random, then the expected value of $I(w)$ is $0$.

Now, let's think about the expected value of $I(w)^2$. Squaring the sum, we get terms indexed by $(i_1, j_1, i_2, j_2)$ with $i_1<j_1$ and $i_2< j_2$. If $i_1$, $i_2$, $j_1$ and $j_2$ are all distinct, then the expected value is $0$. If $j_1 = i_2$$\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ is a singleton, then there are $2$ ways towe get anonzero contributions. For example, if $1$$i_1 = i_2$, then (either$2/3$ of the terms are positive one, coming from the cases where $w(i_1) < w(j_1) = w(i_2) < w(j_2)$$w(i_1)=w(i_2)$ is either the minimium or $w(i_1) > w(j_1) = w(i_2) > w(j_2)$) and $4$ ways to get a $-1$maximum of (the$\{ w(i_1), w(i_2), w(j_1), w(j_2))\}$; the other four permutations), so each$1/3$ of thosethe terms has expectation $-1/3$are negative one. The same happens when we haveThere are $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ singleton in other ways$2 \binom{n}{3}$ pairs $((i_1, j_1), (i_2, j_2))$ with $i_1=i_2 < j_1, j_2$. SoGoing through all such collisions contribute a term on the order ofcases, I get $-cn^3$ to the$4 \binom{n}{3}$ cases with expectation. (More precisely$1/3$ and $2 \binom{n}{3}$ with expectation $-1/3$, I getso expectation $-n(n-1)(n-2)/3$$\sim n^3/9$ as a whole.) The possibility of a double collisioncase where $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ has two elements only contributes $O(n^2)$ (more precisely I get $n(n-1)/2$).

So $I(w)$ has expected value $0$ and standard deviation $n^{3/2}$$n^{3/2}/3$. Without further data, I would expect the probability of it assuming its modal value to be $c/n^{3/2}$. So I expect $M(n) \approx c n!/n^{3/2}$ and $$\frac{M(n+1)}{M(n)} \approx \frac{(n+1)(n+1)^{-3/2}}{n^{-3/2}} = n (1+1/n)^{-1/2} \approx n-1/2.$$

Here is a quick and dirty probabilistic analysis which gets the right answer. For a permutation $w \in S_n$, define $$I(w) = \sum_{1 \leq i < j \leq n} \begin{cases} -1 & w(i) < w(j) \\ 1 & w(i) >w(j) \\ \end{cases}.$$ So $I(w) = 2 \# (\mbox{number of inversions of $w$}) - \binom{n}{2}$. If $w$ is chosen uniformly at random, then the expected value of $I(w)$ is $0$.

Now, let's think about the expected value of $I(w)^2$. Squaring the sum, we get terms indexed by $(i_1, j_1, i_2, j_2)$ with $i_1<j_1$ and $i_2< j_2$. If $i_1$, $i_2$, $j_1$ and $j_2$ are all distinct, then the expected value is $0$. If $j_1 = i_2$, then there are $2$ ways to get a $1$ (either $w(i_1) < w(j_1) = w(i_2) < w(j_2)$ or $w(i_1) > w(j_1) = w(i_2) > w(j_2)$) and $4$ ways to get a $-1$ (the other four permutations), so each of those terms has expectation $-1/3$. The same happens when we have $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ singleton in other ways. So all such collisions contribute a term on the order of $-cn^3$ to the expectation. (More precisely, I get $-n(n-1)(n-2)/3$.) The possibility of a double collision contributes $O(n^2)$ (more precisely I get $n(n-1)/2$).

So $I(w)$ has expected value $0$ and standard deviation $n^{3/2}$. Without further data, I would expect the probability of it assuming its modal value to be $c/n^{3/2}$. So I expect $M(n) \approx c n!/n^{3/2}$ and $$\frac{M(n+1)}{M(n)} \approx \frac{(n+1)(n+1)^{-3/2}}{n^{-3/2}} = n (1+1/n)^{-1/2} \approx n-1/2.$$

Here is a quick and dirty probabilistic analysis which gets the right answer. For a permutation $w \in S_n$, define $$I(w) = \sum_{1 \leq i < j \leq n} \begin{cases} -1 & w(i) < w(j) \\ 1 & w(i) >w(j) \\ \end{cases}.$$ So $I(w) = 2 \# (\mbox{number of inversions of $w$}) - \binom{n}{2}$. If $w$ is chosen uniformly at random, then the expected value of $I(w)$ is $0$.

Now, let's think about the expected value of $I(w)^2$. Squaring the sum, we get terms indexed by $(i_1, j_1, i_2, j_2)$ with $i_1<j_1$ and $i_2< j_2$. If $i_1$, $i_2$, $j_1$ and $j_2$ are all distinct, then the expected value is $0$. If $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ is a singleton, we get nonzero contributions. For example, if $i_1 = i_2$, then $2/3$ of the terms are positive one, coming from the cases where $w(i_1)=w(i_2)$ is either the minimium or maximum of $\{ w(i_1), w(i_2), w(j_1), w(j_2))\}$; the other $1/3$ of the terms are negative one. There are $2 \binom{n}{3}$ pairs $((i_1, j_1), (i_2, j_2))$ with $i_1=i_2 < j_1, j_2$. Going through all cases, I get $4 \binom{n}{3}$ cases with expectation $1/3$ and $2 \binom{n}{3}$ with expectation $-1/3$, so expectation $\sim n^3/9$ as a whole. The case where $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ has two elements only contributes $O(n^2)$.

So $I(w)$ has expected value $0$ and standard deviation $n^{3/2}/3$. Without further data, I would expect the probability of it assuming its modal value to be $c/n^{3/2}$. So I expect $M(n) \approx c n!/n^{3/2}$ and $$\frac{M(n+1)}{M(n)} \approx \frac{(n+1)(n+1)^{-3/2}}{n^{-3/2}} = n (1+1/n)^{-1/2} \approx n-1/2.$$

Post Deleted by David E Speyer
Source Link
David E Speyer
  • 156.2k
  • 14
  • 420
  • 763

Here is a quick and dirty probabilistic analysis which gets the right answer. For a permutation $w \in S_n$, define $$I(w) = \sum_{1 \leq i < j \leq n} \begin{cases} -1 & w(i) < w(j) \\ 1 & w(i) >w(j) \\ \end{cases}.$$ So $I(w) = 2 \# (\mbox{number of inversions of $w$}) - \binom{n}{2}$. If $w$ is chosen uniformly at random, then the expected value of $I(w)$ is $0$.

Now, let's think about the expected value of $I(w)^2$. Squaring the sum, we get terms indexed by $(i_1, j_1, i_2, j_2)$ with $i_1<j_1$ and $i_2< j_2$. If $i_1$, $i_2$, $j_1$ and $j_2$ are all distinct, then the expected value is $0$. If $j_1 = i_2$, then there are $2$ ways to get a $1$ (either $w(i_1) < w(j_1) = w(i_2) < w(j_2)$ or $w(i_1) > w(j_1) = w(i_2) > w(j_2)$) and $4$ ways to get a $-1$ (the other four permutations), so each of those terms has expectation $-1/3$. The same happens when we have $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ singleton in other ways. So all such collisions contribute a term on the order of $-cn^3$ to the expectation. (More precisely, I get $-n(n-1)(n-2)/3$.) The possibility of a double collision contributes $O(n^2)$ (more precisely I get $n(n-1)/2$).

So $I(w)$ has expected value $0$ and standard deviation $n^{3/2}$. Without further data, I would expect the probability of it assuming its modal value to be $c/n^{3/2}$. So I expect $M(n) \approx c n!/n^{3/2}$ and $$\frac{M(n+1)}{M(n)} \approx \frac{(n+1)(n+1)^{-3/2}}{n^{-3/2}} = n (1+1/n)^{-1/2} \approx n-1/2.$$