A bound on $((n),(k))$

[_luca.barletta]

Show that
$((n),(k))=(n!)/(k!(n-k)!)<=2^(n*H(k/n))$
where $H$ is the entropy function:
$H(x)=-xlog_2x-(1-x)log_2(1-x)$.

[adaBTTLS1]

"Gugo82":[OT]
[quote="adaBTTLS"]I writed the sum [...]

Wrote.
[/OT][/quote]



I studied not English. For your signalling, I have just found in the dictionary a table of irregular verbs. Thanks and goodbye.

[gugo82]

[OT]

"adaBTTLS":I writed the sum [...]

Wrote.
[/OT]

[_luca.barletta]

Part 2:
show that
$1/(n+1)2^(n*H(k/n))<=((n),(k))$.

[adaBTTLS1]

I writed the sum in function of $i$ because $p=k/n$ must be constant, else the sum is not equal to $1$. But the inequality having to prove contains uniquely 1 term, then $p=k/n$ can be solely a numerical equality. good bye.

[_luca.barletta]

Now your idea is clear to me, you choose a priori an experiment such that $Pr(E)=k/n$. It works.

"adaBTTLS":if p can not to be equal to k/n (i.e. it must to be different from k/n), p is not independent by n and k.

I have never stated that $p$ cannot be numerically equal to $k/n$, I have said that generally $p$ is not a function of $k$ and $n$.

[adaBTTLS1]

if p can not to be equal to k/n (i.e. it must to be different from k/n), p is not independent by n and k.

we have a fair die with 6 faces. is it allowed to ask oneself the following thing: "which is the probability that, in 6 throwing, we obtain exactly 2 times a number greather than 4 ?" ?
if it is allowed, what is the answer?

$Sigma_(i=0)^n\((n), (i))*(p)^i*(1-p)^(n-i)\=1$
$0 $p=k/n$, $p, 1-p in (0,1)$
the expression that I say least or equal to 1 is one of the terms of the sum...

I wait for the solution. by.

[_luca.barletta]

"adaBTTLS":even if the expression represents not the probability that I have said, the inequality is valid. or not?

I guarantee that the inequality holds , but you should prove it. You have only restated the problem.

[adaBTTLS1]

if k and n are fixed, and $n if $n=k$ is not defined $H(k/n)$;
if k and n are fixed, and $n>k$, the number $k/n$ is in the range $(0,1)$ and we can claim it $p$.
even if the expression represents not the probability that I have said, the inequality is valid. or not?
excuse me for the hard English. by.

[_luca.barletta]

"adaBTTLS":$((n), (k)) * (k/n)^k * (1-k/n)^(n-k) <= 1$
if $(k/n)$ represents the probability of an event $E$, these expression represents the probability that $E$ happens $k$ times in $n$ occasions.

no, if $p$ is the probability of an event $E$ then the probability that $E$ happens $k$ times in $n$ independent trials is
$((n),(k))p^k(1-p)^(n-k)$
the probability $p$ does not depend on $k$ and $n$.

[adaBTTLS1]

we express he entropy function for the value k/n:
$H(k/n)=-k/n*log_2\(k/n)-(1-k/n)*log_2\(1-k/n)=-log_2\[(k/n)^(k/n)*((n-k)/n)^((n-k)/n)]=log_2\n\-log_2\[k^(k/n)*(n-k)^((n-k)/n)]$
then $2^(n*H(k/n))=2^(n*{log_2\n\-log_2\[k^(k/n)*(n-k)^((n-k)/n)]})=(n^n)/(k^k*(n-k)^(n-k))$
the thesis becomes $((n), (k)) <= (n^n)/(k^k*(n-k)^(n-k))=(n/k)^k*(n/(n-k))^(n-k)$
we multiply for the inverse of the expression $(n/k)^k*(n/(n-k))^(n-k)$ and we obtain:
$((n), (k)) * (k/n)^k * (1-k/n)^(n-k) <= 1$
if $(k/n)$ represents the probability of an event $E$, these expression represents the probability that $E$ happens $k$ times in $n$ occasions.
that's OK? by.