On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F19%3A00507737" target="_blank" >RIV/67985840:_____/19:00507737 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.4418/2019.74.1.8" target="_blank" >http://dx.doi.org/10.4418/2019.74.1.8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4418/2019.74.1.8" target="_blank" >10.4418/2019.74.1.8</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs

Popis výsledku v původním jazyce

Suppose that you have n colours and m mutually independent dice, each of which has r sides. Each dice lands on any of its sides with equal probability. You may colour the sides of each die in any way you wish, but there is one restriction: you are not allowed to use the same colour more than once on the sides of a die. Any other colouring is allowed. Let X be the number of different colours that you see after rolling the dice. How should you colour the sides of the dice in order to maximize the Shannon entropy of X? In this article we investigate this question. It is shown that the entropy of X is at most 1/2 log(n/2 + 16 + 1/2) log(πe) and that the bound is tight, up to a constant additive factor, in the case of there being equally many coins and colours. Our proof employs the differential entropy bound on discrete entropy, along with a lower bound on the entropy of binomial random variables whose outcome is conditioned to be an even integer. We conjecture that the entropy is maximized when the colours are distributed over the sides of the dice as evenly as possible.

Název v anglickém jazyce

On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs

Popis výsledku anglicky

Suppose that you have n colours and m mutually independent dice, each of which has r sides. Each dice lands on any of its sides with equal probability. You may colour the sides of each die in any way you wish, but there is one restriction: you are not allowed to use the same colour more than once on the sides of a die. Any other colouring is allowed. Let X be the number of different colours that you see after rolling the dice. How should you colour the sides of the dice in order to maximize the Shannon entropy of X? In this article we investigate this question. It is shown that the entropy of X is at most 1/2 log(n/2 + 16 + 1/2) log(πe) and that the bound is tight, up to a constant additive factor, in the case of there being equally many coins and colours. Our proof employs the differential entropy bound on discrete entropy, along with a lower bound on the entropy of binomial random variables whose outcome is conditioned to be an even integer. We conjecture that the entropy is maximized when the colours are distributed over the sides of the dice as evenly as possible.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GJ18-01472Y" target="_blank" >GJ18-01472Y: Limity grafů a nehomogenní náhodné grafy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Le Matematiche

ISSN

0373-3505

e-ISSN

—

Svazek periodika

74

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

IT - Italská republika

Počet stran výsledku

12

Strana od-do

119-130

Kód UT WoS článku

000470736200008

EID výsledku v databázi Scopus

2-s2.0-85069525062