Timeline for Expectation of edge weights on the complete graph
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2022 at 10:51 | answer | added | Brendan McKay | timeline score: 1 | |
| May 2, 2022 at 10:29 | comment | added | Brendan McKay | @JamesMartin You are correct. I'll adjust my claim: the maximum is $k$ almost surely if $k=c\log_2 n$ with $c<2$. I'll add a proof in a while. | |
| May 2, 2022 at 9:40 | comment | added | James Martin | For $k\sim c\log n$, $c$ large enough, I think we're in a "large deviations" regime. We have $\approx e^{ak}$ copies of Binomial($k,1/2$). Look for $\beta$ such that $\frac{1}{k}\log P(\text{Bin}(k,1/2)\geq \beta k) \sim -a$. Then the max of the copies would typically have value around $\beta k$. This would be sound if the copies were independent. For the non-independent case, you already get an upper bound. Maybe the lower bound could come from a second moment argument? Anyway, in summary I think you will get $E(X_{n,k})\sim \beta k$ for some $\beta=\beta(c)\in(1/2, 1]$, as $k\to\infty$. | |
| May 2, 2022 at 9:31 | comment | added | James Martin | @BrendanMcKay are you sure? I agree for $c$ sufficiently small; but say $n=2^{k/4}$. You have order $2^{k/2}$ edges $(u,v)$, and each one gives you a value $w(u,v)=k$ with probability $2^{-(k-1)}$ (if I understand the model). That seems to give you a vanishingly small chance of the maximum being $k$. | |
| May 2, 2022 at 5:55 | comment | added | Brendan McKay | To flesh that out a bit: If $k=c\log n$ for constant $c$, then the maximum is $k$ with probability bounded above 0. (I think it is $k$ almost surely, but I don't have a proof.) If $k=o(\log n)$, the maximum is $k$ almost surely. | |
| May 2, 2022 at 5:42 | comment | added | Brendan McKay | If $k=c\log n$ for constant $c$, then the maximum is $k$ with probability bounded above 0. If $k$ is a constant, the maximum is $k$ almost surely. | |
| May 1, 2022 at 16:13 | comment | added | Stanley Yao Xiao | @JamesMartin I believe in the relevant case $k = O(\log n)$, or even a fixed large constant independent of $n$. | |
| May 1, 2022 at 16:13 | comment | added | Stanley Yao Xiao | @BrendanMcKay I have clarified what I mean by summing two binary strings. | |
| May 1, 2022 at 16:12 | history | edited | Stanley Yao Xiao | CC BY-SA 4.0 |
added 125 characters in body
|
| May 1, 2022 at 14:04 | comment | added | James Martin | Since you say "$n$ much larger than $k$" it sounds like you're looking for some sort of asymptotics. Can you say more about which regime you're interested in? The case $n\approx 2^k$ will be very different from the case $n\approx k^2$.... | |
| May 1, 2022 at 5:25 | comment | added | Brendan McKay | What operation is $b(u)+b(v)$? Addition as binary numbers? Element-wise mod 2 addition? | |
| May 1, 2022 at 0:23 | history | asked | Stanley Yao Xiao | CC BY-SA 4.0 |