Questions en théorie des probabilités
Alors que j'ai réussi quelques cours sur la théorie des probabilités, tant au lycée qu'à l'université, j'ai du mal à lire les articles TCS en matière de probabilité. Il semble que les auteurs des articles du TCS connaissent très bien la probabilité. Ils fonctionnent comme par magie avec des...
Y a-t-il une borne inverse de Chernoff qui limite la probabilité de queue au moins autant. c'est-à-dire si X1,X2,…,XnX1,X2,…,XnX_1,X_2,\ldots,X_n sont des variables aléatoires binomiales indépendantes et μ=E[∑ni=1Xi]μ=E[∑i=1nXi]\mu=\mathbb{E}[\sum_{i=1}^n X_i] . Alors peut-on prouver...
Il est bien connu qu'une marche aléatoire dans la grille bidimensionnelle retournera à l'origine avec la probabilité 1. Il est également connu que la même marche aléatoire en TROIS dimensions a une probabilité strictement inférieure à 1 de revenir à l'origine . Ma question est: Y a-t-il quelque...
Citant Wikipedia , "[Le jeu de la vie de Conway] a le pouvoir d'une machine de Turing universelle: c'est-à-dire que tout ce qui peut être calculé de manière algorithmique peut être calculé dans le jeu de la vie de Conway." Ces résultats s'étendent-ils aux versions bruyantes de Game of Life de...
Le problème suivant est survenu lors de la recherche et il est étonnamment propre: Vous avez une source de pièces. Chaque pièce a un biais, à savoir une probabilité qu'elle tombe sur la "tête". Pour chaque pièce indépendamment, il y a une probabilité 2/3 qu'elle ait un biais d'au moins 0,9, et avec...
J'ai entendu dire qu'il existe des arguments heuristiques en physique statistique qui donnent des résultats dans la théorie des probabilités pour lesquels des preuves rigoureuses sont inconnues ou très difficiles à obtenir. Quel est un simple exemple de jouet d'un tel phénomène? Ce serait bien si...
Je m'intéresse à la densité critique de 3-satisfiabilité (3-SAT) . On suppose qu'un tel α existe: si le nombre de clauses 3-SAT générées aléatoirement est ( α + ϵ ) n ou plus, elles sont presque sûrement insatisfaisantes. (Ici, ϵ est une petite constante et n est le nombre de variables.) Si le...
Il est bien connu que de nombreux paramètres de graphique importants montrent une concentration (forte) sur des graphiques aléatoires, au moins dans une certaine plage de probabilité de bord. Quelques exemples typiques sont le nombre chromatique, la clique maximale, l'ensemble indépendant maximal,...
Le temps de trajet dans un graphique connecté est défini comme le nombre attendu d'étapes dans une marche aléatoire commençant à , avant que le nœud soit visité et que le nœud soit à nouveau atteint. Il s'agit essentiellement de la somme des deux temps de frappe et
Lorsque j'enseigne les limites de la queue, j'utilise la progression habituelle: Si votre RV est positif, vous pouvez appliquer l'inégalité de Markov Si vous avez l' indépendance et aussi la variance limitée, vous pouvez appliquer l'inégalité de Tchebychev Si chaque VR indépendant a également tous...
(Von Neumann a donné un algorithme qui simule une pièce équitable donnant accès à des pièces biaisées identiques. L'algorithme nécessite potentiellement un nombre infini de pièces (bien qu'en attente, un nombre fini suffira). Cette question concerne le cas où le nombre de lancers autorisés est...
J'ai rencontré le résultat suivant lors de mes recherches. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 oùetsont choisis au hasard parmi.a1,⋯,am[n]m=ω(n−−√)m=ω(n)m=\omega(\sqrt...
Si est une fonction convexe, l'inégalité de Jensen indique que , et mutatis mutandis lorsque est concave. De toute évidence, dans le pire des cas, vous ne pouvez pas dépasser la limite en termes de pour un convexe , mais existe-t-il une limite qui va dans ce sens si est convexe mais "pas trop...
Un problème classique dans la théorie des probabilités est d'exprimer la probabilité d'un événement en termes d'événements plus spécifiques. Dans le cas le plus simple, on peut dire . Write Let pour l'événement .A B A ∩ BP[ A ∪ B ] = P[ A ] + P[ B ] - P[ A ∩ B ]P[UNE∪B]=P[UNE]+P[B]-P[UNE∩B]P[A \cup...
J'ai pensé à ce problème il y a longtemps, mais je n'ai aucune idée à ce sujet. L'algorithme de génération est le suivant. Nous supposons qu'il y a nnn nœuds discrets numérotés de 000 à n−1n−1n - 1 . Ensuite, pour chaque iii dans {1,…,n−1}{1,…,n−1}\{1, \dotsc, n - 1\} , nous faisons du parent du...
Il est bien connu que si vous lancez n balles dans n cases, le bin le plus chargé est très susceptible d'avoir balles dedans. En général, on peut poser des questions sur balles dans cases. Un article de RANDOM 1998 de Raab et Steger explore cela en détail, montrant qu'à mesure que augmente, la...
Une chose que les ordinateurs quantiques peuvent faire (peut-être même avec seulement des circuits quantiques BPP + log-depth) est d'échantillonner approximativement la transformée de Fourier d'une fonction booléenne évaluée en P.±1±1\pm 1 Ici et ci-dessous quand je parle d'échantillonner la...
Considérez le processus suivant: Il y a nnn bacs disposés de haut en bas. Initialement, chaque bac contient une balle. À chaque étape, nous choisir une balle bbb uniformément au hasard et déplacez toutes les boules du bac contenant bbb vers le bac en dessous. S'il s'agissait déjà du bac le plus...
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Lemme: En supposant une équivalence éta, nous avons cela (\x -> ⊥) = ⊥ :: A -> B. Preuve: ⊥ = (\x -> ⊥ x)par eta-équivalence, et (\x -> ⊥ x) = (\x -> ⊥)par réduction sous lambda. Le rapport Haskell 2010, section 6.2 spécifie la seqfonction par deux équations: seq :: a -> b -> b...