Questions sur la branche des mathématiques concernée par la modélisation et l'analyse de phénomènes aléatoires.
Il est bien connu que cet algorithme «naïf» pour mélanger un tableau en échangeant chaque élément avec un autre choisi au hasard ne fonctionne pas correctement: for (i=0..n-1) swap(A[i], A[random(n)]); Plus précisément, puisque à chacune des nnn itérations, l’une desnnn choix est fait (avec une...
Vous avez une pièce. Vous pouvez le retourner autant de fois que vous le souhaitez. Vous voulez générer un nombre aléatoire rrr tel que a ≤ r < bune≤r<ba \leq r < b où r , a , b ∈ Z+r,une,b∈Z+r,a,b\in \mathbb{Z}^+ . La distribution des nombres doit être uniforme. C'est facile si b−a=2nb−a=2nb...
Cette question a été migrée à partir de la bourse théorique de l'informatique, car elle peut être répondue sur la bourse de la science informatique. Migré il y a 7 ans . Ce problème est tiré de interviewstreet.com On nous donne un tableau d'entiers qui représente segments de ligne tels que les...
Pour formuler la question, en informatique, nous voulons souvent calculer le produit de plusieurs probabilités: P(A,B,C) = P(A) * P(B) * P(C) L'approche la plus simple consiste simplement à multiplier ces nombres, et c'est ce que j'allais faire. Cependant, mon patron a dit qu'il valait mieux...
Supposons que l'on vous donne une pièce équitable et que vous souhaitez simuler la distribution de probabilité de lancer à plusieurs reprises un dé équitable (à six faces). Mon idée initiale est que nous devons choisir des entiers appropriés , tels que 2 k = 6 m . Ainsi, après avoir retourné la...
Supposons que nous avons un générateur aléatoire qui délivre les numéros dans la gamme avec une distribution uniforme et nous devons générer des nombres aléatoires dans la gamme avec une distribution uniforme.[ 0 .. N - 1 ][0..R−1][0..R−1][0..R-1][0..N−1][0..N−1][0..N-1] Supposons que et ne divise...
Supposons que nous ayons une boîte noire que nous pouvons interroger et réinitialiser. Lorsque nous réinitialisons , l'état de est défini sur un élément choisi uniformément au hasard dans l'ensemble où est fixe et connu pour donné . Pour interroger , un élément (la supposition) de est fourni, et la...
J'ai auto-étudié la maximisation des attentes récemment et je me suis emparé de quelques exemples simples dans le processus: De là : Il y a trois pièces , et avec , et la probabilité respective d'atterrir sur la tête lorsqu'elle est lancée. Toss . Si le résultat est Tête, lancez trois fois, sinon...
Étant donné un dé biaisé de côté , comment générer uniformément un nombre aléatoire dans la plage ? La distribution de probabilité des faces du dé n'est pas connue, tout ce que l'on sait, c'est que chaque face a une probabilité non nulle et que la distribution de probabilité est la même sur tous...
Disons que nous avons une grande collection de tâches et une collection de processeurs identiques (en termes de performances) qui fonctionnent complètement dans parallèle. Pour les scénarios d'intérêt, nous pouvons supposer . Chaque prend un certain temps / cycles à terminer une fois qu'il est...
L'algorithme de sélection aléatoire est le suivant: Entrée: un tableau de nombres (distincts, pour simplifier) et un nombren k ∈ [ n ]AAAnnnk∈[n]k∈[n]k\in [n] Sortie: le " élément de rang " de A (c'est-à-dire celui en position k si A a été trié)A k AkkkAAAkkkAAA Méthode: S'il y a un élément dans...
Un prédicteur Naive Bayes fait ses prédictions en utilisant cette formule: P( O= y| X= x ) = α P( O= y) ∏jeP( Xje= xje| Oui= y)P(Oui=y|X=X)=αP(Oui=y)∏jeP(Xje=Xje|Oui=y)P(Y=y|X=x) = \alpha P(Y=y)\prod_i P(X_i=x_i|Y=y) où est un facteur de normalisation. Cela nécessite d'estimer les paramètres partir...
Contexte \newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr...
Considérons une séquence de nnn flips d'une pièce non biaisée. Soit HiHiH_i la valeur absolue de l'excédent du nombre de têtes sur les queues vu dans les premiers iii flips. Définissez H=maxiHiH=maxiHiH=\text{max}_i H_i . Montrer que E[Hi]=Θ(i√)E[Hi]=Θ(i)E[H_i]=\Theta ( \sqrt{i}...
Au travail, j'ai été chargé de déduire des informations de type sur un langage dynamique. Je réécris des séquences d'instructions en imbriquéeslet expressions , comme ceci: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then...
Il existe une famille de graphes aléatoires à nœuds ( due à Gilbert ). Chaque bord possible est inséré indépendamment dans avec une probabilité . Soit le nombre de cliques de taille dans .nG(n,p)G(n,p)G(n, p)nnnp X k k G ( n , p )G(n,p)G(n,p)G(n, p)pppXkXkX_kkkkG(n,p)G(n,p)G(n, p) Je sais que...
J'ai écrit ce code Python et je me suis demandé s'il ne se terminait pas simplement parfois (en supposant que nous avions une mémoire / temps infinie et aucune limite de profondeur de récursivité). Intuitivement, vous penseriez qu'il se termine, car à un moment donné, vous devez avoir de la chance...
Cette question concerne l'intersection de la théorie des probabilités et de la complexité de calcul. Une observation clé est que certaines distributions sont plus faciles à générer que d'autres. Par exemple, le problème Étant donné un nombre nnn , renvoyer un nombre uniformément distribué iiiavec...
Je lis actuellement des articles sur le regroupement de chaînes de Markov et je ne vois pas la différence entre une chaîne de Markov et un graphique pondéré simple. Par exemple, dans l'article Optimisation de l'espace d'état dans les chaînes de Markov, ils fournissent la définition suivante d'une...
Avertissement: je suis un biologiste, donc désolé pour (peut-être) une question de base formulée en termes aussi grossiers. Je ne sais pas si je devrais poser cette question ici ou sur DS / SC, mais CS est le plus grand des trois, alors voilà. (Après avoir posté, il m'est venu à l'esprit que la...