Suite récurrente à double indice

gasasaaa · November 2019

J'essaie actuellement de résoudre un petit problème de proba, qui m'a amené à trouver une suite récurrente de la forme :

$p_{k,i} = p_{k-1,i-1}*\frac{n-(i-1)}{n} + p_{k-1,i} * \frac{i}{n}$, sachant que $p_{1,1} = 1$ et $p_{1,i} = 0 pt i > 1$
(n est ici un entier quelconque).

Je vous avoue que comme ça, je ne vois pas trouver une forme générique de $p_{k,i}$. Est-ce que quelqu'un aurait une idée, ou au moins le nom de ce type de suite, car je vous avoue que je n'ai réussi à trouver aucune documentation relative à ces suites, qui doivent pourtant être quelque chose d'assez classique en mathématique.

Merci et bonne soirée

aléa · November 2019

Ce serait mieux de donner le problème...

gasasaaa · November 2019

Ce serait mieux de donner le problème si je veux la solution au problème en effet

Mais ce n'est pas vraiment mon objectif ici. J'aimerais surtout en apprendre plus sur ces suites.

side · November 2019

supp

YvesM · November 2019

Bonjour,

Essaie une séparation des variables $p_{k,i}=A_k B_i$.

LOU16 · November 2019

Bonjour,
J'ai trouvé que:

$\forall \:k,i \in \N^*,\quad \quad p_{k,i} = \displaystyle \dfrac {\displaystyle \binom ni \:i!\: \mathcal S_{k,i}}{n^k} \quad$ où: $\mathcal S_{k,i} \:\text{ est le "nombre de Stirling de deuxième espèce" défini par}:\:\: \mathcal S_{k,i} = \dfrac 1{i!}\displaystyle \sum _{s=0}^{i} (-1)^{i-s} \binom is s^k.$
Ainsi $\:i! \mathcal S_{k,i} $ est le nombre de surjections de $\:[\![1;k]\!]\:$ dans $\:[\![1;i]\!]$, mais il existe d'autres caractérisations des $\mathcal S_{k,i}$ , par exemple celle-ci: $ \displaystyle \forall n \in \N,\quad X^n = \sum_{k=0}^n \mathcal S_{n,k} \prod_{s=0}^{k-1}(X-s), \:\:$ ce qui permet de retrouver le fait que $ \displaystyle \sum_{i=1}^k p_{k,i}=1,\:$ ou bien celle-là:
$$\mathcal S_{n,k}\: \text{est le nombre de partitions de}\:[\![1;n]\!]\:\text{en} \: k\: \text{parties}.$$
Il semble qu'ici $p_{k,i}$ désigne la probabilité d'obtenir exactement $i$ numéros distincts à l'issue de $k$ tirages successifs "avec remise" d'une boule, effectués dans une urne contenant $n$ boules distinguées par des numéros.

aléa · November 2019

J'aimerais surtout en apprendre plus sur ces suites.

Maintenant que Lou a donné le résultat, peut-être que tu pourrais en retour donner le problème ?

gasasaaa · November 2019

Re !
Merci à tous pour vos réponses. Désolé de ne pas avoir donné de retour plus tôt, mais j'essayais de m'en sortir avec les idées [de] side et de YvesM, qui me paraissent bonnes, mais je n'ai pas réussi à aboutir avec ces indications (mais peut-être était-ce faisable).
Concernant ton résultat Lou, j'ai été plutôt bluffé... d'où est-ce que ça sort ? ::o Tu as vraiment déduit ce résultat de la formule de récurrence ?

Et pour répondre à Alea, le problème était le suivant.
(Bien que le problème d'urne et de boule donnée par Lou16 soit strictement équivalent, ma formulation était un peu différente. Mais on est bien d'accord qu'il s'agit de la même chose).
J'ai 500 amis sur Facebook. Combien y aura-t-il de jours cette année où je devrais souhaiter au moins un anniversaire ?

J'appelle $N_k$ la variable aléatoire représentant le nombre de jours où j'ai un un anniversaire à souhaiter cette année, en ne prenant en compte que les k premiers amis de ma liste d'amis.
$n$ le nombre de jour qu'il y a dans l'année
$p_{k,i} = P(N_{k} = i)$
La relation de récurrence que j'ai alors trouvé correspond juste à un partitionnement selon les valeurs de $N_{k-1}$

Enfin, pour la formule trouvée par Lou16, elle me semble juste et représente finalement un problème de dénombrement que j'aurais pu trouver seul (mais qui est plus simple a posteriori quand on connaît le résultat).

Je choisis d'abord mes $i$ dates parmi $N$. d'où $\binom ni$
Parmi ces $i$ dates, il faut que je dénombre le nombre de manière de remplir chaque date au moins une fois avec les dates de mes amis. Cela revient à trouver le nombre de surjection de $[1,k]$ dans $[1,i]$, d'où le fameux nombre de Stirling. On a alors $p_{k,i} = \frac{\text{nb de cas favorables}}{\text{nb de cas total}}$, et on retrouve bien la formule de Lou. Personnellement, je réfléchirai un petit peu sur la définition explicite que tu donnes du nombre de Stirling, mais ça doit se retrouver assez simplement.
En tout cas, un grand merci pour votre aide, et bonne soirée à tous.

[James Stirling (1692-1770) prend toujours une majuscule. AD]

LOU16 · November 2019

Bonjour,
@gasasaaa

Ma réponse ne pouvait bien entendu ne se fonder que sur ta relation de récurrence car c'était le seul élément dont je disposais.
J'ai fait quelque chose d'extrêmement simple, à savoir calculer les $p_{ki}$ pour les petites valeurs de $k$ et de $i$, jusqu'à ce que les résultats obtenus fassent apparaitre des coefficients $\mathcal S_{k,i}$ liés par la relation $\:\:\boxed{\mathcal S_{n,k} = k\mathcal S_{n-1,k}+ \mathcal S_{n-1,k-1}}$, connue pour engendrer les nombres de Stirling de deuxième espèce, agencés dans le tableau ci-dessous où $n$ est la ligne et $k$ la colonne. ($0\leqslant k\leqslant n \leqslant 6$)
$$ \begin {array} {ccccccc} 1\\ 0&1\\0&1&1\\0&1&3&1\\0&1&7&6&1\\0&1&15&25&10&1\\0&1&31&90&65&15&1 \end{array}$$

aléa · November 2019

@gasasaaa : Merci pour ta réponse.

Suite récurrente à double indice

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 43