Charcoal, 46 bytes (noncompeting)

ＵＯＮＮO_¶_OＡＫＡαＡ№αOβＨＷψβ«Ａ§α§⌕ＡαO‽βXＡ№αOβ

Note: ψ/k is 1000.

Verbose

Oblong(InputNumber(), InputNumber(), "O_\n_O")
Assign(PeekAll(), a)
Assign(Count(a, "O"), b)
RefreshWhile (k, b) {
    AssignAtIndex(a, AtIndex(FindAll(a, "O"), Random(b)), "X")
    Assign(Count(a, "O"), b)
}

Charcoal, 49 46 39 bytes (noncompeting)

ＵＯＮＮO_¶_OＡＫＡαＡ№αOβＨＷψβ«Ａ§α§⌕ＡαO‽βXＡ№αOβ

Verbose

Oblong(InputNumber(), InputNumber(), "O_\n_O")
Assign(PeekAll(), a)
Assign(Count(a, "O"), b)
RefreshWhile (k, b) {
    AssignAtIndex(a, AtIndex(FindAll(a, "O"), Random(b)), "X")
    Assign(Count(a, "O"), b)
}

Charcoal, 49 bytes (noncompeting)

Ｎα⪫…⟦…O_α…_Oα⟧Ｎ¶ＡＫＡβＡ№βOθＨＷ¹⁰⁰⁰θ«Ａ§β§⌕ＡβO‽θXＡ№βOθ

Verbose

InputNumber(a)
Print(Join(CycleChop([CycleChop("O_", a),CycleChop("_O", a)],InputNumber()), "\n"))
Assign(PeekAll(), b)
Assign(Count(b, "O"), c)
RefreshWhile (1000, c) {
    AssignAtIndex(b, AtIndex(FindAll(b, "O"), Random(c)), "X")
    Assign(Count(b, "O"), c)
}

Charcoal, 46 bytes (noncompeting)

ＵＯＮＮO_¶_OＡＫＡαＡ№αOβＨＷψβ«Ａ§α§⌕ＡαO‽βXＡ№αOβ

Note: ψ/k is 1000.

Verbose

Oblong(InputNumber(), InputNumber(), "O_\n_O")
Assign(PeekAll(), a)
Assign(Count(a, "O"), b)
RefreshWhile (k, b) {
    AssignAtIndex(a, AtIndex(FindAll(a, "O"), Random(b)), "X")
    Assign(Count(a, "O"), b)
}